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

题目1：移除元素

问题描述：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例：

• • 输入：nums = [3,2,2,3], val = 3
• • 输出：2, nums = [2,2]
• • 解释：函数应该返回新的长度 2，并且 nums 中的前两个元素均为 2。
• • 输入：nums = [0,1,2,2,3,0,4,2], val = 2
• • 输出：5, nums = [0,1,4,0,3]
• • 解释：函数应该返回新的长度 5，并且 nums 中的前五个元素为 0, 1, 3, 0, 4（顺序可以不同）。

解题思路：使用双指针。指针 slow 指向新数组的末尾位置，指针 fast 用于遍历原数组。遍历时，如果 nums[fast] != val，则将 nums[fast] 复制到 nums[slow]，然后 slow 后移。遍历结束后，slow 即为新数组的长度。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
def removeElement(nums, val):    slow = 0    for fast in range(len(nums)):        if nums[fast] != val:            nums[slow] = nums[fast]            slow += 1    return slow

题目2：字母异位词分组

问题描述：给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例：

• • 输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
• • 输出：[["bat"],["nat","tan"],["ate","eat","tea"]]
• • 输入：strs = [""]
• • 输出：[[""]]

解题思路：字母异位词排序后的字符串一定相同。遍历字符串数组，对每个字符串进行排序，将排序后的字符串作为哈希表的键，原字符串加入对应的列表中。最后返回哈希表中所有列表的值。时间复杂度 O(n * m log m)，其中 n 是字符串数量，m 是字符串最大长度。空间复杂度 O(n * m)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
from collections import defaultdictdef groupAnagrams(strs):    groups = defaultdict(list)    for s in strs:        key = ''.join(sorted(s))        groups[key].append(s)    return list(groups.values())

题目3：反转链表 II

问题描述：给你单链表的头指针 head 和两个整数 left 和 right，其中 left <= right。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。位置从 1 开始计数。

示例：

• • 输入：head = [1,2,3,4,5], left = 2, right = 4
• • 输出：[1,4,3,2,5]
• • 输入：head = [5], left = 1, right = 1
• • 输出：[5]

解题思路：使用哑节点 dummy 指向头节点，避免处理头节点反转的特殊情况。先找到第 left - 1 个节点 prev，然后从第 left 个节点开始，使用头插法反转 right - left + 1 个节点。具体操作：维护 curr 指向待反转的第一个节点，每次将 curr.next 插入到 prev 之后。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例（假设 ListNode 类已定义）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def reverseBetween(head, left, right):    dummy = ListNode(0)    dummy.next = head    prev = dummy    for _ in range(left - 1):        prev = prev.next    curr = prev.next    for _ in range(right - left):        next_temp = curr.next        curr.next = next_temp.next        next_temp.next = prev.next        prev.next = next_temp    return dummy.next

题目4：求根节点到叶节点数字之和

问题描述：给你一个二叉树的根节点 root，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字：

• • 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123。

计算从根节点到叶节点生成的所有数字之和。叶节点是指没有子节点的节点。

示例：

• • 输入：root = [1,2,3]
• • 输出：25
• • 解释：
• • 从根到叶子节点路径 1->2 代表数字 12
• • 从根到叶子节点路径 1->3 代表数字 13
• • 因此，数字总和 = 12 + 13 = 25
• • 输入：root = [4,9,0,5,1]
• • 输出：1026

解题思路：使用深度优先搜索（DFS）。递归时传递当前路径组成的数字 current_sum，每次 current_sum = current_sum * 10 + node.val。当到达叶子节点时，将 current_sum 加入结果。时间复杂度 O(n)，空间复杂度 O(h)（递归栈深度）。

Python代码示例（假设 TreeNode 类已定义）：

1
2
3
4
5
6
7
8
9
10
def sumNumbers(root):    def dfs(node, current_sum):        if not node:            return 0        current_sum = current_sum * 10 + node.val        if not node.left and not node.right:            return current_sum        return dfs(node.left, current_sum) + dfs(node.right, current_sum)    return dfs(root, 0)

题目5：只出现一次的数字 II

问题描述：给你一个整数数组 nums，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且不使用额外空间来解决此问题。

示例：

• • 输入：nums = [2,2,3,2]
• • 输出：3
• • 输入：nums = [0,1,0,1,0,1,99]
• • 输出：99

解题思路：使用位运算。对于每一位，统计数组中所有元素在该位上 1 的个数。如果某个元素出现三次，那么该位上的 1 的总数一定是 3 的倍数，再加上只出现一次的元素在该位上的值。因此，对每一位的计数取模 3，结果就是只出现一次的元素在该位上的值。时间复杂度 O(32n) = O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def singleNumber(nums):    result = 0    for i in range(32):        bit_count = 0        for num in nums:            bit_count += (num >> i) & 1        result |= (bit_count % 3) << i    # 处理负数（32 位有符号整数）    if result >= 2**31:        result -= 2**32    return result

题目6：压缩字符串

问题描述：给你一个字符数组 chars，请使用下述算法压缩：从一个空字符串 s 开始。对于 chars 中的每组连续重复字符：

• • 如果这一组长度为 1，则将字符追加到 s 中；
• • 否则，需要向 s 追加字符，后跟这一组的长度。

压缩后得到的字符串 s 不应该直接返回，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。请在修改完输入数组后，返回该数组的新长度。

示例：

• • 输入：chars = ["a","a","b","b","c","c","c"]
• • 输出：返回 6，输入数组的前 6 个字符应该是 ["a","2","b","2","c","3"]
• • 输入：chars = ["a"]
• • 输出：返回 1，输入数组的前 1 个字符应该是 ["a"]

解题思路：使用双指针。read 指针遍历原数组，write 指针指向写入位置。每次读取一组连续相同字符，记录其长度。将字符写入 chars[write]，write 后移；如果长度大于 1，则将长度的每一位数字依次写入。最后返回 write。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def compress(chars):    write = 0    read = 0    n = len(chars)    while read < n:        char = chars[read]        count = 0        while read < n and chars[read] == char:            read += 1            count += 1        chars[write] = char        write += 1        if count > 1:            for digit in str(count):                chars[write] = digit                write += 1    return write

题目7：分隔链表

问题描述：给你一个链表的头节点 head 和一个特定值 x，请你对链表进行分隔，使得所有小于x 的节点都出现在大于或等于x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。

示例：

• • 输入：head = [1,4,3,2,5,2], x = 3
• • 输出：[1,2,2,4,3,5]
• • 输入：head = [2,1], x = 2
• • 输出：[1,2]

解题思路：创建两个哑节点，分别作为小于 x 和大于等于 x 的两个链表的头。遍历原链表，将节点分别接到对应的链表末尾。遍历结束后，将小于 x 的链表尾部连接到大于等于 x 的链表头部，并将大于等于 x 的链表尾部置空。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例（假设 ListNode 类已定义）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def partition(head, x):    less_dummy = ListNode(0)    greater_dummy = ListNode(0)    less = less_dummy    greater = greater_dummy    while head:        if head.val < x:            less.next = head            less = less.next        else:            greater.next = head            greater = greater.next        head = head.next    greater.next = None    less.next = greater_dummy.next    return less_dummy.next

题目8：二叉搜索树中的搜索

问题描述：给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 None。

示例：

• • 输入：root = [4,2,7,1,3], val = 2
• • 输出：[2,1,3]
• • 输入：root = [4,2,7,1,3], val = 5
• • 输出：None

解题思路：利用二叉搜索树的性质：左子树所有节点值小于根节点，右子树所有节点值大于根节点。从根节点开始：

• • 如果当前节点为空或值等于 val，返回当前节点；
• • 如果 val 小于当前节点值，递归搜索左子树；
• • 如果 val 大于当前节点值，递归搜索右子树。时间复杂度 O(h)，空间复杂度 O(h)（递归栈）。

Python代码示例（假设 TreeNode 类已定义）：

1
2
3
4
5
6
7
8
def searchBST(root, val):    if not root or root.val == val:        return root    if val < root.val:        return searchBST(root.left, val)    else:        return searchBST(root.right, val)

题目9：不同的二叉搜索树

问题描述：给你一个整数 n，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

示例：

• • 输入：n = 3，输出：5
• • 输入：n = 1，输出：1

解题思路：动态规划（卡特兰数）。定义 dp[i] 为 i 个节点能组成的二叉搜索树数量。对于 i 个节点，枚举根节点的位置 j（1 <= j <= i），左子树有 j-1 个节点，右子树有 i-j 个节点。状态转移方程：dp[i] += dp[j-1] * dp[i-j]。初始化 dp[0] = 1，dp[1] = 1。最终返回 dp[n]。时间复杂度 O(n²)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
def numTrees(n):    dp = [0] * (n + 1)    dp[0] = 1    dp[1] = 1    for i in range(2, n + 1):        for j in range(1, i + 1):            dp[i] += dp[j - 1] * dp[i - j]    return dp[n]

题目10：腐烂的橘子

问题描述：在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• • 0 代表空单元格；
• • 1 代表新鲜橘子；
• • 2 代表腐烂的橘子。

每分钟，腐烂的橘子周围 4 个方向上（上、下、左、右）的任何新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

示例：

• • 输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
• • 输出：4
• • 输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
• • 输出：-1
• • 解释：左下角的橘子（第 2 行，第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
• • 输入：grid = [[0,2]]
• • 输出：0

解题思路：使用广度优先搜索（BFS）。先统计新鲜橘子的数量 fresh_count，并将所有腐烂橘子的坐标加入队列。如果 fresh_count == 0，直接返回 0。每一轮 BFS 代表一分钟，遍历当前队列中的所有腐烂橘子，将其周围的新鲜橘子变为腐烂并加入队列，同时减少 fresh_count。如果队列为空时仍有新鲜橘子，返回 -1；否则返回经过的分钟数。时间复杂度 O(m * n)，空间复杂度 O(m * n)。

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
32
from collections import dequedef orangesRotting(grid):    rows, cols = len(grid), len(grid[0])    queue = deque()    fresh_count = 0    for i in range(rows):        for j in range(cols):            if grid[i][j] == 2:                queue.append((i, j))            elif grid[i][j] == 1:                fresh_count += 1    if fresh_count == 0:        return 0    minutes = 0    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]    while queue and fresh_count > 0:        minutes += 1        for _ in range(len(queue)):            r, c = queue.popleft()            for dr, dc in directions:                nr, nc = r + dr, c + dc                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:                    grid[nr][nc] = 2                    fresh_count -= 1                    queue.append((nr, nc))    return minutes if fresh_count == 0 else -1