网络安全技术练习题大全(24)

题目31：Fizz Buzz

问题描述：给你一个整数 n，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：

• • answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数；
• • answer[i] == "Fizz" 如果 i 是 3 的倍数；
• • answer[i] == "Buzz" 如果 i 是 5 的倍数；
• • answer[i] == i（以字符串形式）如果上述条件全不满足。

示例：

• • 输入：n = 3，输出：["1","2","Fizz"]
• • 输入：n = 5，输出：["1","2","Fizz","4","Buzz"]
• • 输入：n = 15，输出：["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

解题思路：从 1 遍历到 n，对每个数字依次判断是否能被 3 和 5 整除。根据判断结果将对应的字符串加入结果列表。时间复杂度 O(n)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def fizzBuzz(n):    result = []    for i in range(1, n + 1):        if i % 3 == 0 and i % 5 == 0:            result.append("FizzBuzz")        elif i % 3 == 0:            result.append("Fizz")        elif i % 5 == 0:            result.append("Buzz")        else:            result.append(str(i))    return result

题目32：计数二进制子串

问题描述：给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。重复出现（不同位置）的子串也要统计它们出现的次数。

示例：

• • 输入：s = "00110011"，输出：6
• • 解释：6 个子串满足具有相同数量的连续 1 和 0："0011"、"01"、"1100"、"10"、"0011"、"01"。
• • 输入：s = "10101"，输出：4
• • 解释：有 4 个子串："10"、"01"、"10"、"01"。

解题思路：将字符串按连续相同字符分组，记录每组的长度。例如 "00110011" 分组为 [2, 2, 2, 2]。相邻两组可以组成满足条件的子串，数量为 min(前一组长度, 后一组长度)。遍历分组长度数组，累加相邻两组的 min 值。时间复杂度 O(n)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def countBinarySubstrings(s):    groups = []    count = 1    for i in range(1, len(s)):        if s[i] == s[i - 1]:            count += 1        else:            groups.append(count)            count = 1    groups.append(count)    result = 0    for i in range(1, len(groups)):        result += min(groups[i - 1], groups[i])    return result

题目33：检测大写字母

问题描述：我们定义，在以下情况时，单词的大写用法是正确的：

• • 全部字母都是大写，比如 "USA"；
• • 单词中所有字母都不是大写，比如 "leetcode"；
• • 如果单词不只含有一个字母，只有首字母大写，比如 "Google"。

给你一个字符串 word。如果大写用法正确，返回 true；否则，返回 false。

示例：

• • 输入：word = "USA"，输出：true
• • 输入：word = "FlaG"，输出：false

解题思路：统计字符串中大写字母的个数。如果大写字母个数为 0 或者等于字符串长度，则合法；如果大写字母个数为 1 且首字母为大写，则合法；其他情况均不合法。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
def detectCapitalUse(word):    upper_count = sum(1 for ch in word if ch.isupper())    if upper_count == 0 or upper_count == len(word):        return True    if upper_count == 1 and word[0].isupper():        return True    return False

题目34：转置矩阵

问题描述：给你一个二维整数数组 matrix，返回 matrix 的转置矩阵。矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

示例：

• • 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
• • 输出：[[1,4,7],[2,5,8],[3,6,9]]
• • 输入：matrix = [[1,2,3],[4,5,6]]
• • 输出：[[1,4],[2,5],[3,6]]

解题思路：创建一个新的矩阵，行数为原矩阵的列数，列数为原矩阵的行数。遍历原矩阵的每个元素 matrix[i][j]，将其放到新矩阵的 result[j][i] 位置。时间复杂度 O(m * n)，空间复杂度 O(m * n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
def transpose(matrix):    rows, cols = len(matrix), len(matrix[0])    result = [[0] * rows for _ in range(cols)]    for i in range(rows):        for j in range(cols):            result[j][i] = matrix[i][j]    return result

题目35：三个数的最大乘积

问题描述：给你一个整型数组 nums，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例：

• • 输入：nums = [1,2,3]，输出：6
• • 输入：nums = [1,2,3,4]，输出：24
• • 输入：nums = [-1,-2,-3]，输出：-6

解题思路：最大乘积可能来自两种情况：

• • 最大的三个正数相乘；
• • 最小的两个负数（乘积为正）与最大的正数相乘。

因此，只需要找出数组中最大的三个数和最小的两个数。分别计算这两种情况的乘积，取较大值。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
def maximumProduct(nums):    nums.sort()    n = len(nums)    return max(nums[-1] * nums[-2] * nums[-3],               nums[0] * nums[1] * nums[-1])

题目36：数组的度

问题描述：给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例：

• • 输入：nums = [1,2,2,3,1]，输出：2
• • 解释：nums 的度是 2，因为元素 1 和 2 都出现了 2 次。拥有相同度的最短连续子数组是 [2,2]，长度为 2。
• • 输入：nums = [1,2,2,3,1,4,2]，输出：6
• • 解释：nums 的度是 3，元素 2 出现了 3 次。所以 [2,2,3,1,4,2] 是最短的，长度为 6。

解题思路：使用三个哈希表分别记录每个元素第一次出现的位置、最后一次出现的位置以及出现的次数。遍历数组填充这三个哈希表。然后遍历哈希表，找到出现次数等于数组度的所有元素，计算它们的 last_index - first_index + 1，取最小值即为答案。时间复杂度 O(n)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def findShortestSubArray(nums):    first = {}    last = {}    count = {}    for i, num in enumerate(nums):        if num not in first:            first[num] = i        last[num] = i        count[num] = count.get(num, 0) + 1    degree = max(count.values())    min_len = len(nums)    for num in count:        if count[num] == degree:            min_len = min(min_len, last[num] - first[num] + 1)    return min_len

题目37：图片平滑器

问题描述：图像平滑器是大小为 3 x 3 的过滤器，将每个单元格的值替换为其周围所有单元格（包括自身）的平均值，周围不足 9 个单元格的取实际存在的单元格平均值。给你一个表示图像灰度的 m x n 整数矩阵 img，返回平滑后的图像。注意：平均值需要向下取整。

示例：

• • 输入：img = [[1,1,1],[1,0,1],[1,1,1]]
• • 输出：[[0,0,0],[0,0,0],[0,0,0]]
• • 解释：对于每个单元格，周围所有单元格的平均值都是 (1+1+1+1+0+1+1+1+1)/9 = 0.888...，向下取整为 0。

解题思路：遍历矩阵中的每个单元格 (i, j)，再遍历其周围 3x3 范围内的所有单元格，累加有效单元格的值和个数。计算平均值并向下取整，存入结果矩阵。时间复杂度 O(m * n * 9) = O(m * n)，空间复杂度 O(m * n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def imageSmoother(img):    m, n = len(img), len(img[0])    result = [[0] * n for _ in range(m)]    for i in range(m):        for j in range(n):            total = 0            count = 0            for x in range(max(0, i - 1), min(m, i + 2)):                for y in range(max(0, j - 1), min(n, j + 2)):                    total += img[x][y]                    count += 1            result[i][j] = total // count    return result

题目38：密钥格式化

问题描述：给定一个许可密钥字符串 s，仅由字母、数字字符和破折号组成。字符串被 n 个破折号分成 n + 1 组。你还需要给定一个整数 k。我们想要重新格式化字符串 s，使每个分组恰好包含 k 个字符。特别地，第一个分组包含的字符数必须小于等于 k，但至少要包含 1 个字符。另外，两个分组之间需要用破折号 - 隔开，并且将所有小写字母转换为大写字母。返回重新格式化后的字符串。

示例：

• • 输入：s = "5F3Z-2e-9-w", k = 4，输出："5F3Z-2E9W"
• • 解释：字符串 s 被分成了两个部分，每部分 4 个字符。注意，两个额外的破折号需要删除，而所有小写字母需要转换为大写。
• • 输入：s = "2-5g-3-J", k = 2，输出："2-5G-3J"
• • 解释：字符串 s 被分成了三个部分，前两个部分长度为 2，第三个部分仅为 1 个字符。

解题思路：先移除字符串中的所有破折号，并转换为大写。然后从字符串末尾开始，每 k 个字符分成一组，组间用破折号连接。最后将结果反转（或直接用列表收集后反转）。时间复杂度 O(n)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
def licenseKeyFormatting(s, k):    s = s.replace('-', '').upper()    result = []    n = len(s)    for i in range(n, 0, -k):        result.append(s[max(0, i - k):i])    return '-'.join(reversed(result))

题目39：供暖器

问题描述：冬季已经来临。你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。在加热器的加热半径范围内的每个房屋都可以获得供暖。现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

示例：

• • 输入：houses = [1,2,3], heaters = [2]，输出：1
• • 解释：仅在位置 2 上有一个供暖器。如果我们将加热半径设为 1，那么所有房屋就都能得到供暖。
• • 输入：houses = [1,2,3,4], heaters = [1,4]，输出：1
• • 解释：在位置 1 和 4 上各有一个供暖器。如果加热半径设为 1，所有房屋就都能得到供暖。

解题思路：将房屋和供暖器都排序。对于每个房屋，找到离它最近的供暖器，计算距离。所有房屋中距离的最大值就是所需的最小加热半径。为了高效查找最近的供暖器，可以使用二分查找，或者双指针遍历。时间复杂度 O(m log m + n log n)（排序），空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import bisectdef findRadius(houses, heaters):    houses.sort()    heaters.sort()    radius = 0    for house in houses:        idx = bisect.bisect_left(heaters, house)        left_dist = house - heaters[idx - 1] if idx > 0 else float('inf')        right_dist = heaters[idx] - house if idx < len(heaters) else float('inf')        radius = max(radius, min(left_dist, right_dist))    return radius

题目40：学生出勤记录 I

问题描述：给你一个字符串 s 表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

• • 'A'：Absent，缺勤
• • 'L'：Late，迟到
• • 'P'：Present，到场

如果学生能够同时满足下面两个条件，则可以获得出勤奖励：

• • 按总出勤计，学生缺勤（'A'）严格少于两天。
• • 学生不会存在连续 3 天或连续 3 天以上的迟到（'L'）记录。

如果学生可以获得出勤奖励，返回 true；否则，返回 false。

示例：

• • 输入：s = "PPALLP"，输出：true
• • 解释：学生缺勤次数少于 2 次，且不存在连续 3 天的迟到。
• • 输入：s = "PPALLL"，输出：false
• • 解释：学生最后三天连续迟到，所以不满足出勤奖励条件。

解题思路：遍历字符串，统计缺勤 'A' 的总数，如果超过 1 则直接返回 False。同时检查是否存在连续三个 'L'，可以通过滑动窗口或计数连续 'L' 的长度，如果达到 3 则返回 False。遍历结束后返回 True。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def checkRecord(s):    absent_count = 0    late_count = 0    for ch in s:        if ch == 'A':            absent_count += 1            if absent_count >= 2:                return False            late_count = 0        elif ch == 'L':            late_count += 1            if late_count >= 3:                return False        else:            late_count = 0    return True