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

题目91：最长连续序列

问题描述：给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

解题思路：使用哈希集合。将所有数字放入集合中，然后遍历集合中的每个数字。对于每个数字 num，先判断 num - 1 是否在集合中，若在则说明 num 不是连续序列的起点，跳过。若 num - 1 不在集合中，则从 num 开始不断检查 num + 1、num + 2……是否在集合中，统计当前连续序列长度并更新最大值。每个数字最多被访问两次，时间复杂度 O(n)。

Python代码示例：

def longestConsecutive(nums):    num_set = set(nums)    max_len = 0    for num in num_set:        if num - 1 not in num_set:            current = num            length = 1            while current + 1 in num_set:                current += 1                length += 1            max_len = max(max_len, length)    return max_len

题目92：用最少数量的箭引爆气球

问题描述：有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points，其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。你不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart、xend，且满足 xstart <= x <= xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。给你一个数组 points，返回引爆所有气球所必须射出的最小弓箭数。

解题思路：使用贪心算法。将所有气球按右端点升序排序。维护当前箭的射出位置为第一个气球的右端点，遍历后续气球：若当前气球的左端点大于箭的位置，说明该气球无法被当前箭引爆，需要再射一支箭，更新箭的位置为当前气球的右端点；否则该气球可被当前箭引爆，跳过。最终箭的数量即为答案。

Python代码示例：

def findMinArrowShots(points):    if not points:        return 0    points.sort(key=lambda x: x[1])    arrows = 1    position = points[0][1]    for start, end in points[1:]:        if start > position:            arrows += 1            position = end    return arrows

题目93：爱吃香蕉的珂珂

问题描述：珂珂喜欢吃香蕉。这里有n堆香蕉，第i堆中有piles[i]根香蕉。警卫已经离开了，将在h小时后回来。珂珂可以决定她吃香蕉的速度k（单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉k根。如果这堆香蕉少于k根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在h小时内吃掉所有香蕉的最小速度k（k 为整数）。

解题思路：使用二分查找答案。速度 k 的范围为 [1, max(piles)]。对于每个候选速度 mid，计算吃完所有香蕉所需的总小时数：每堆需要 ceil(pile / mid) 小时，累加后判断是否不超过 h。若不超过 h，说明速度可以更小，收缩右边界；否则增大左边界。最终 left 即为最小速度。

Python代码示例：

def minEatingSpeed(piles, h):    def can_finish(speed):        hours = 0        for pile in piles:            hours += (pile + speed - 1) // speed            if hours > h:                return False        return True    left, right = 1, max(piles)    while left < right:        mid = (left + right) // 2        if can_finish(mid):            right = mid        else:            left = mid + 1    return left

题目94：火星词典

问题描述：现有一种使用英语字母的外星语言，这门语言的字母顺序与英语顺序不同。给定一个字符串列表 words，作为这门语言的词典，words 中的字符串已经按这门新语言的字母顺序进行了排序。请你根据该词典还原出此语言中已知的字母顺序，并返回该顺序的字符串。若不存在合法字母顺序，返回 ""。若存在多种可能的合法字母顺序，返回其中任意一种即可。

解题思路：使用拓扑排序。遍历相邻的两个单词，找到第一个不同的字符c1和c2，说明c1在c2之前，建立一条从c1到c2的有向边，同时更新入度。注意特殊情况：若前面的单词是后面单词的前缀且更长，则说明顺序不合法，返回""。然后对所有出现过的字符进行拓扑排序（BFS + 入度表），若结果包含所有字符则返回排序结果，否则说明存在环，返回""。

Python代码示例：

from collections import defaultdict, dequedef alienOrder(words):    graph = defaultdict(set)    indegree = {}    for word in words:        for char in word:            indegree[char] = 0    for i in range(len(words) - 1):        w1, w2 = words[i], words[i + 1]        min_len = min(len(w1), len(w2))        if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:            return ""        for j in range(min_len):            if w1[j] != w2[j]:                if w2[j] not in graph[w1[j]]:                    graph[w1[j]].add(w2[j])                    indegree[w2[j]] += 1                break    queue = deque([c for c in indegree if indegree[c] == 0])    result = []    while queue:        char = queue.popleft()        result.append(char)        for neighbor in graph[char]:            indegree[neighbor] -= 1            if indegree[neighbor] == 0:                queue.append(neighbor)    return ''.join(result) if len(result) == len(indegree) else ""

题目95：火柴拼正方形

问题描述：你将得到一个整数数组 matchsticks，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用所有的火柴棍拼成一个正方形。你不能折断任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须使用一次。如果你能使这个正方形，则返回 true，否则返回 false。

解题思路：使用回溯法 + 剪枝。先计算所有火柴棒的总长度 total，若 total % 4 != 0 则直接返回 False，目标边长为 side = total // 4。将火柴棒按长度降序排序，便于剪枝。用长度为 4 的数组 sides 记录四条边当前的长度，依次尝试将每根火柴放入某条边，若放入后不超过 side 则递归处理下一根火柴。剪枝策略：若某条边放入火柴后与之前某条边长度相同，则跳过（避免重复尝试）；若某条边长度为 0 且放入失败，则直接返回（后续空边情况相同）。

Python代码示例：

def makesquare(matchsticks):    total = sum(matchsticks)    if total % 4 != 0:        return False    side = total // 4    if max(matchsticks) > side:        return False    matchsticks.sort(reverse=True)    sides = [0] * 4    def backtrack(index):        if index == len(matchsticks):            return all(s == side for s in sides)        for i in range(4):            if sides[i] + matchsticks[index] <= side:                sides[i] += matchsticks[index]                if backtrack(index + 1):                    return True                sides[i] -= matchsticks[index]            if sides[i] == 0:                break        return False    return backtrack(0)

题目96：天际线问题

问题描述：城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。给你所有建筑物的位置和高度，请返回由这些建筑物形成的天际线。每个建筑物的几何信息由数组 buildings 表示，其中三元组 buildings[i] = [lefti, righti, heighti] 表示：

• • lefti 是第 i 座建筑物左边缘的 x 坐标
• • righti 是第 i 座建筑物右边缘的 x 坐标
• • heighti 是第 i 座建筑物的高度

天际线应该表示为由“关键点”组成的列表，格式 [[x1,y1],[x2,y2],...]，并按 x 坐标进行排序。关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y 坐标均为 0，仅用于标记天际线的终点。此外，任何两个相邻建筑物之间的地面都应被视为天际线轮廓的一部分。注意：输出天际线中不得有连续的相同高度的水平线。

解题思路：使用扫描线 + 最大堆。将每个建筑物拆成两个事件：左端点 (left, -height) 表示加入建筑，右端点 (right, height) 表示移除建筑。将所有事件按 x 坐标排序，x 相同时左端点优先处理（因为高度为负，且新建筑在旧建筑结束时开始）。维护一个最大堆记录当前活跃的建筑高度（用负数模拟最大堆），并用一个哈希表记录每个高度被移除的次数以支持延迟删除。每次处理完同一 x 坐标的所有事件后，清理堆顶已失效的高度，若当前最大高度与上一关键点高度不同，则记录关键点。

Python代码示例：

import heapqfrom collections import defaultdictdef getSkyline(buildings):    events = []    for left, right, height in buildings:        events.append((left, -height, right))        events.append((right, height, 0))    events.sort(key=lambda x: (x[0], x[1]))    result = []    heap = [0]    delayed = defaultdict(int)    prev_height = 0    i = 0    while i < len(events):        x = events[i][0]        while i < len(events) and events[i][0] == x:            _, h, r = events[i]            if h < 0:                heapq.heappush(heap, h)            else:                delayed[h] += 1            i += 1        while heap and delayed[-heap[0]] > 0:            delayed[-heap[0]] -= 1            heapq.heappop(heap)        current_height = -heap[0]        if current_height != prev_height:            result.append([x, current_height])            prev_height = current_height    return result

题目97：拼接最大数

问题描述：给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

解题思路：将问题拆分为三个子问题：

1. 1. 从单个数组中选出 t 个数字使其最大（单调栈）
2. 2. 合并两个数组为最大的数（贪心比较）
3. 3. 枚举所有可能的 t（从第一个数组选 t 个，从第二个数组选 k - t 个），取最大值

从单个数组选出 t 个数字使其最大：使用单调递减栈，遍历数组，当栈非空且栈顶小于当前元素且剩余元素足够时弹出栈顶，最终取栈的前 t 个元素。合并两个数组：每次比较两个数组从当前位置到末尾的字典序，取较大者对应的元素。枚举：t 的范围为 max(0, k - n) <= t <= min(k, m)，对每种情况计算结果并取最大。

Python代码示例：

def maxNumber(nums1, nums2, k):    def pick_max(nums, k):        drop = len(nums) - k        stack = []        for num in nums:            while drop and stack and stack[-1] < num:                stack.pop()                drop -= 1            stack.append(num)        return stack[:k]    def merge(a, b):        result = []        while a or b:            if a > b:                result.append(a.pop(0))            else:                result.append(b.pop(0))        return result    max_result = []    m, n = len(nums1), len(nums2)    for t in range(max(0, k - n), min(k, m) + 1):        part1 = pick_max(nums1, t)        part2 = pick_max(nums2, k - t)        candidate = merge(part1, part2)        if candidate > max_result:            max_result = candidate    return max_result

题目98：移除K位数字

问题描述：给你一个以字符串表示的非负整数 num 和一个整数 k，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

解题思路：使用单调递增栈。从左到右遍历数字字符串，当栈非空、栈顶数字大于当前数字、且还有移除次数时，弹出栈顶并减少 k。然后将当前数字入栈。遍历结束后，若 k 仍有剩余，则从末尾删除对应数量的数字。最后去除结果的前导零，若结果为空则返回 "0"。

Python代码示例：

def removeKdigits(num, k):    stack = []    for digit in num:        while k > 0 and stack and stack[-1] > digit:            stack.pop()            k -= 1        stack.append(digit)    if k > 0:        stack = stack[:-k]    result = ''.join(stack).lstrip('0')    return result if result else "0"

题目99：二叉树的序列化与反序列化

问题描述：序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列化/反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

解题思路：使用前序遍历（DFS）进行序列化。序列化时，遇到空节点用 "None" 标记，节点之间用逗号分隔。反序列化时，将字符串按逗号分割成列表，用迭代器依次读取：若当前值为 "None" 则返回 None，否则创建当前节点，并递归构建左子树和右子树。

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

class Codec:    def serialize(self, root):        def dfs(node):            if not node:                return ["None"]            return ([str(node.val)] +                    dfs(node.left) +                    dfs(node.right))        return ','.join(dfs(root))    def deserialize(self, data):        def dfs():            val = next(values)            if val == "None":                return None            node = TreeNode(int(val))            node.left = dfs()            node.right = dfs()            return node        values = iter(data.split(','))        return dfs()

题目100：数组中两个数的最大异或值

问题描述：给你一个整数数组 nums，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n。要求时间复杂度为 O(n)。

解题思路：使用前缀树（Trie）+ 贪心。将每个数字的二进制位（从高位到低位，共 31 位）插入前缀树中，每个节点有两个子节点分别表示 0 和 1。对于每个数字，在 Trie 中尽可能选择与当前位相反的位，这样异或结果在该位上为 1。从高位到低位贪心选择，最终得到的结果即为最大异或值。

Python代码示例：

class TrieNode:    def __init__(self):        self.children = {}def findMaximumXOR(nums):    root = TrieNode()    for num in nums:        node = root        for i in range(31, -1, -1):            bit = (num >> i) & 1            if bit not in node.children:                node.children[bit] = TrieNode()            node = node.children[bit]    max_xor = 0    for num in nums:        node = root        current_xor = 0        for i in range(31, -1, -1):            bit = (num >> i) & 1            opposite = 1 - bit            if opposite in node.children:                current_xor |= (1 << i)                node = node.children[opposite]            else:                node = node.children[bit]        max_xor = max(max_xor, current_xor)    return max_xor