2026网安习题大全(9)

题目81：多数元素 II

问题描述：给定一个大小为 n 的整数数组 nums，找出其中所有出现次数超过 ⌊n / 3⌋ 的元素。

解题思路：使用摩尔投票法的扩展版本。最多只有两个元素的出现次数超过 n/3。维护两个候选元素 cand1、cand2 和对应的计数器 count1、count2，第一遍遍历选出候选，第二遍遍历验证候选是否满足条件。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def majorityElement(nums):    cand1 = cand2 = None    count1 = count2 = 0    for num in nums:        if num == cand1:            count1 += 1        elif num == cand2:            count2 += 1        elif count1 == 0:            cand1, count1 = num, 1        elif count2 == 0:            cand2, count2 = num, 1        else:            count1 -= 1            count2 -= 1    result = []    for cand in (cand1, cand2):        if cand is not None and nums.count(cand) > len(nums) // 3:            if cand not in result:                result.append(cand)    return result

题目82：除自身以外数组的乘积

问题描述：给定一个整数数组 nums，返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。要求不使用除法，且时间复杂度为 O(n)。

解题思路：使用前缀积和后缀积。先从左到右遍历，计算每个位置左侧所有元素的乘积存入结果数组；再从右到左遍历，用一个变量维护右侧所有元素的乘积，与结果数组中对应位置相乘得到最终结果。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def productExceptSelf(nums):    n = len(nums)    answer = [1] * n    left = 1    for i in range(n):        answer[i] = left        left *= nums[i]    right = 1    for i in range(n - 1, -1, -1):        answer[i] *= right        right *= nums[i]    return answer

题目83：递增的三元子序列

问题描述：给定一个整数数组 nums，判断这个数组中是否存在长度为 3 的递增子序列。

解题思路：使用贪心算法。维护两个变量 first 和 second，分别表示当前找到的最小元素和第二小元素。遍历数组，若当前元素大于 second，则找到了递增三元组；若大于 first 则更新 second；否则更新 first。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def increasingTriplet(nums):    first = second = float('inf')    for num in nums:        if num <= first:            first = num        elif num <= second:            second = num        else:            return True    return False

题目84：螺旋矩阵 II

问题描述：给定一个正整数 n，生成一个包含 1 到 n² 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵。

解题思路：模拟螺旋填充过程。定义四个边界 top、bottom、left、right，按照右、下、左、上的顺序依次填入数字，每填完一条边就收缩对应边界，直到填满所有位置。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def generateMatrix(n):    matrix = [[0] * n for _ in range(n)]    top, bottom = 0, n - 1    left, right = 0, n - 1    num = 1    while top <= bottom and left <= right:        for c in range(left, right + 1):            matrix[top][c] = num            num += 1        top += 1        for r in range(top, bottom + 1):            matrix[r][right] = num            num += 1        right -= 1        if top <= bottom:            for c in range(right, left - 1, -1):                matrix[bottom][c] = num                num += 1            bottom -= 1        if left <= right:            for r in range(bottom, top - 1, -1):                matrix[r][left] = num                num += 1            left += 1    return matrix

题目85：旋转图像

问题描述：给定一个 n x n 的二维矩阵 matrix 表示一个图像，将图像顺时针旋转 90 度。要求原地旋转，不能使用另一个矩阵。

解题思路：分两步完成：先沿主对角线（从左上到右下）翻转矩阵，即交换 matrix[i][j] 和 matrix[j][i]；然后翻转每一行，即交换 matrix[i][j] 和 matrix[i][n-1-j]。两步完成后即为顺时针旋转 90 度的结果。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def rotate(matrix):    n = len(matrix)    # 沿主对角线翻转    for i in range(n):        for j in range(i + 1, n):            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]    # 翻转每一行    for i in range(n):        for j in range(n // 2):            matrix[i][j], matrix[i][n - 1 - j] = matrix[i][n - 1 - j], matrix[i][j]

题目86：生命游戏

问题描述：给定一个 m x n 的二维网格 board，每个格子中的细胞可以是活细胞（1）或死细胞（0）。根据康威生命游戏的规则，同时更新所有细胞的状态：

• • 活细胞周围活细胞少于 2 个或超过 3 个则死亡；
• • 死细胞周围恰好有 3 个活细胞则复活。

要求原地更新。

解题思路：用额外的状态值表示中间状态：-1 表示原本活但变为死，2 表示原本死但变为活。遍历每个细胞统计周围 8 个邻居中活细胞数量（绝对值等于 1），根据规则标记中间状态。最后再遍历一次将中间状态转换为最终状态。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def gameOfLife(board):    if not board:        return    rows, cols = len(board), len(board[0])    def count_live(r, c):        count = 0        for dr in (-1, 0, 1):            for dc in (-1, 0, 1):                if dr == 0 and dc == 0:                    continue                nr, nc = r + dr, c + dc                if 0 <= nr < rows and 0 <= nc < cols and abs(board[nr][nc]) == 1:                    count += 1        return count    for r in range(rows):        for c in range(cols):            live = count_live(r, c)            if board[r][c] == 1 and (live < 2 or live > 3):                board[r][c] = -1            elif board[r][c] == 0 and live == 3:                board[r][c] = 2    for r in range(rows):        for c in range(cols):            if board[r][c] == -1:                board[r][c] = 0            elif board[r][c] == 2:                board[r][c] = 1

题目87：加一

问题描述：给定一个由整数组成的非空数组 digits，表示一个非负整数。在该数的基础上加一，返回结果数组。最高位数字存放在数组的首位。

解题思路：从数组末尾开始遍历，若当前位小于 9 则直接加一并返回；若当前位为 9 则置为 0 并继续向前处理。若所有位都是 9，则需要在数组开头插入一个 1。

Python 代码示例：

1
2
3
4
5
6
7
8
def plusOne(digits):    for i in range(len(digits) - 1, -1, -1):        if digits[i] < 9:            digits[i] += 1            return digits        digits[i] = 0    return [1] + digits

题目88：二进制求和

问题描述：给定两个二进制字符串 a 和 b，以二进制字符串的形式返回它们的和。

解题思路：从两个字符串的末尾开始逐位相加，使用进位变量 carry。每一位的和为 carry + a 的当前位 + b 的当前位，结果的当前位为和对 2 取余，进位为和对 2 整除。最后若仍有进位则补上。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def addBinary(a, b):    i, j = len(a) - 1, len(b) - 1    carry = 0    result = []    while i >= 0 or j >= 0 or carry:        total = carry        if i >= 0:            total += int(a[i])            i -= 1        if j >= 0:            total += int(b[j])            j -= 1        result.append(str(total % 2))        carry = total // 2    return ''.join(reversed(result))

题目89：最后一个单词的长度

问题描述：给定一个字符串 s，由若干单词组成，单词之间用空格分隔。返回字符串中最后一个单词的长度。如果不存在最后一个单词，返回 0。

解题思路：先从字符串末尾跳过所有空格，然后从最后一个非空格字符开始向前统计字符数量，直到遇到空格或到达字符串开头。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def lengthOfLastWord(s):    i = len(s) - 1    while i >= 0 and s[i] == ' ':        i -= 1    length = 0    while i >= 0 and s[i] != ' ':        length += 1        i -= 1    return length

题目90：有效的字母异位词

问题描述：给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。字母异位词指由相同字母重新排列形成的字符串。

解题思路：若两个字符串长度不同则直接返回 False。使用长度为 26 的计数数组，遍历 s 时对对应位置加一，遍历 t 时对对应位置减一。最终若计数数组中所有元素都为 0，则互为字母异位词。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def isAnagram(s, t):    if len(s) != len(t):        return False    count = [0] * 26    for ch in s:        count[ord(ch) - ord('a')] += 1    for ch in t:        count[ord(ch) - ord('a')] -= 1    return all(c == 0 for c in count)