超全网络安全技术练习题(19)

题目81：冗余连接

问题描述：树可以看成是一个连通且无环的无向图。给定往一棵树中添加一条边后的图，该图由一个包含 n 个节点（节点值 1 到 n）的树和一个附加的边组成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges 中，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。请找出那条可以删去的边，使得剩下的图是一棵有 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

解题思路：使用并查集（Union-Find）。依次遍历每条边，尝试将两个端点合并到同一个集合中。若两个端点已经属于同一个集合，说明这条边会使图形成环，即为冗余的边，返回该边。否则将两个端点合并。由于题目保证图是由一棵树加一条附加边构成，因此一定能找到答案。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def findRedundantConnection(edges):    n = len(edges)    parent = list(range(n + 1))    def find(x):        while parent[x] != x:            parent[x] = parent[parent[x]]            x = parent[x]        return x    for u, v in edges:        ru, rv = find(u), find(v)        if ru == rv:            return [u, v]        parent[ru] = rv    return []

题目82：统计封闭岛屿的数目

问题描述：二维矩阵 grid 由 0（土地）和 1（水）组成。岛是由最大的 4 个方向连通的 0 组成的群，封闭岛是一个完全由 1 包围（左、上、右、下）的岛。请你返回封闭岛屿的数目。

解题思路：使用深度优先搜索（DFS）。先遍历矩阵的边界，将所有与边界相连的 0 用 DFS 标记为 1（水），这些陆地不属于封闭岛屿。然后遍历矩阵内部，每遇到一个 0，说明发现了一座封闭岛屿，计数加一，并用 DFS 将与之相连的所有 0 标记为 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
def closedIsland(grid):    rows, cols = len(grid), len(grid[0])    def dfs(r, c):        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 0:            return        grid[r][c] = 1        dfs(r + 1, c)        dfs(r - 1, c)        dfs(r, c + 1)        dfs(r, c - 1)    for r in range(rows):        for c in range(cols):            if (r == 0 or r == rows - 1 or c == 0 or c == cols - 1) and grid[r][c] == 0:                dfs(r, c)    count = 0    for r in range(1, rows - 1):        for c in range(1, cols - 1):            if grid[r][c] == 0:                count += 1                dfs(r, c)    return count

题目83：煎饼排序

问题描述：给你一个整数数组 arr，请使用煎饼翻转完成对数组的排序。一次煎饼翻转的执行过程如下：

• • 选择一个整数 k，1 <= k <= arr.length
• • 反转子数组 arr[0...k-1]（下标从 0 开始）

例如，arr = [3,2,1,4]，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1]，得到 arr = [1,2,3,4]。以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。

解题思路：使用贪心策略。从最大的元素开始，依次将未排序部分的最大元素放到正确位置。对于当前需要放置的位置 i（从末尾开始），找到最大值所在下标 max_idx：

• • 若 max_idx == i，说明已经在正确位置，跳过
• • 否则，若 max_idx != 0，先翻转前 max_idx + 1 个元素，将最大值翻到首位，记录 max_idx + 1
• • 再翻转前 i + 1 个元素，将最大值翻到位置 i，记录 i + 1

每轮最多两次翻转，总次数不超过 2n，满足要求。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def pancakeSort(arr):    result = []    n = len(arr)    for i in range(n - 1, 0, -1):        max_idx = 0        for j in range(1, i + 1):            if arr[j] > arr[max_idx]:                max_idx = j        if max_idx == i:            continue        if max_idx != 0:            arr[:max_idx + 1] = reversed(arr[:max_idx + 1])            result.append(max_idx + 1)        arr[:i + 1] = reversed(arr[:i + 1])        result.append(i + 1)    return result

题目84：优势洗牌

问题描述：给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

解题思路：使用贪心 + 排序 + 双指针（田忌赛马思想）。将 nums1 升序排序，将 nums2 的下标按对应值升序排序。用双指针分别指向 nums1 的最小值和最大值，以及 nums2 排序后的最小值和最大值：

• • 若 nums1 的最小值大于 nums2 的最小值，则用 nums1 最小值匹配 nums2 最小值，左指针移动
• • 否则，用 nums1 最小值去匹配 nums2 的最大值（牺牲最小值），右指针移动

最终得到优势最大化的排列。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def advantageCount(nums1, nums2):    n = len(nums1)    nums1.sort()    sorted_idx = sorted(range(n), key=lambda i: nums2[i])    result = [0] * n    left, right = 0, n - 1    for i in sorted_idx:        if nums1[left] > nums2[i]:            result[i] = nums1[left]            left += 1        else:            result[i] = nums1[right]            right -= 1    return result

题目85：重构字符串

问题描述：给定一个字符串 s，检查是否能重新排布其中的字母，使得两相邻的字符不同。返回 s 的任意可能的重新排列。若不可能，返回空字符串 ""。

解题思路：使用贪心 + 最大堆。先统计每个字符的出现次数。若某个字符出现次数超过 (n + 1) // 2，则无法重新排列，返回 ""。将所有字符按出现次数放入最大堆。每次取出出现次数最多的两个不同字符，交替加入结果，然后将其剩余次数减一后重新入堆。若最后堆中只剩一个字符，直接追加到结果末尾。

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
import heapqfrom collections import Counterdef reorganizeString(s):    count = Counter(s)    n = len(s)    if max(count.values()) > (n + 1) // 2:        return ""    heap = [(-freq, char) for char, freq in count.items()]    heapq.heapify(heap)    result = []    while len(heap) >= 2:        freq1, char1 = heapq.heappop(heap)        freq2, char2 = heapq.heappop(heap)        result.append(char1)        result.append(char2)        if freq1 + 1 < 0:            heapq.heappush(heap, (freq1 + 1, char1))        if freq2 + 1 < 0:            heapq.heappush(heap, (freq2 + 1, char2))    if heap:        result.append(heap[0][1])    return ''.join(result)

题目86：汉明距离

问题描述：两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

解题思路：先将两个数进行异或运算，异或结果中为 1 的位表示两个数在该位上不同。然后统计异或结果中 1 的个数即可。可以使用 bin(result).count('1')，也可以用 n & (n - 1) 逐位消除最低位的 1 来计数。

Python代码示例：

1
2
3
4
5
6
7
8
9
def hammingDistance(x, y):    xor = x ^ y    count = 0    while xor:        xor &= xor - 1        count += 1    return count

题目87：比特位计数

问题描述：给你一个整数 n，对于 0 <= i <= n 中的每个 i，计算其二进制表示中 1 的个数，返回一个长度为 n + 1 的数组 ans 作为答案。

解题思路：使用动态规划。对于任意整数 i：

• • 若 i 为偶数，则 i 的二进制中 1 的个数与 i // 2 相同，因为右移一位不改变 1 的个数
• • 若 i 为奇数，则 i 的二进制中 1 的个数比 i - 1 多 1

统一写法：dp[i] = dp[i >> 1] + (i & 1)。时间复杂度 O(n)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
def countBits(n):    dp = [0] * (n + 1)    for i in range(1, n + 1):        dp[i] = dp[i >> 1] + (i & 1)    return dp

题目88：只出现一次的数字III

问题描述：给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素，你可以按任意顺序返回答案。要求时间复杂度 O(n)，空间复杂度 O(1)。

解题思路：先将所有元素异或，得到的结果是两个只出现一次元素的异或值。由于这两个元素不同，异或结果中至少有一位为 1。找到该结果中最右侧的 1 作为分组依据。根据这一位将数组分为两组，每组分别异或，最终得到两个只出现一次的元素。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def singleNumber(nums):    xor = 0    for num in nums:        xor ^= num    diff = xor & (-xor)    a = b = 0    for num in nums:        if num & diff:            a ^= num        else:            b ^= num    return [a, b]

题目89：数字范围按位与

问题描述：给你两个整数 left 和 right，表示区间 [left, right]，返回此区间内所有数字按位与的结果（包含 left、right 端点）。

解题思路：按位与的性质：只要区间内某个二进制位上出现过 0，那么该位的结果就是 0。从 left 和 right 的最高位开始比较，找到它们的公共前缀；公共前缀之后的所有位在区间内都会出现 0，因此结果就是公共前缀后面补 0。实现上可以不断将 left 和 right 右移，直到两者相等，记录右移次数，最后将 left 左移回去。

Python代码示例：

1
2
3
4
5
6
7
8
9
def rangeBitwiseAnd(left, right):    shift = 0    while left < right:        left >>= 1        right >>= 1        shift += 1    return left << shift

题目90：最大单词长度乘积

问题描述：给你一个字符串数组 words，找出并返回 length(words[i]) * length(words[j]) 的最大值，其中两个单词不含有公共字母。如果不存在这样的两个单词，返回 0。

解题思路：使用位掩码。对于每个单词，用一个 26 位整数表示其包含的字母集合（第 k 位为 1 表示包含第 k 个字母）。两两比较单词的掩码，若 mask[i] & mask[j] == 0，说明没有公共字母，计算长度乘积并更新最大值。由于字母集合用整数表示，比较只需 O(1)，整体时间复杂度 O(n²)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def maxProduct(words):    masks = []    for word in words:        mask = 0        for char in word:            mask |= 1 << (ord(char) - ord('a'))        masks.append(mask)    max_prod = 0    n = len(words)    for i in range(n):        for j in range(i + 1, n):            if masks[i] & masks[j] == 0:                max_prod = max(max_prod, len(words[i]) * len(words[j]))    return max_prod