ARTICLE · 1088391
2026网安习题大全(7)
题目61：最长连续序列
问题描述：给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。要求时间复杂度为 O(n)。
解题思路：将所有数字存入哈希集合。遍历集合中的每个数字，只有当该数字是某个连续序列的起点（即 num - 1 不在集合中）时，才向后逐个数统计连续长度，并更新最大值。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def longestConsecutive(nums): num_set = set(nums) longest = 0 for num in num_set: if num - 1 not in num_set: cur = num length = 1 while cur + 1 in num_set: cur += 1 length += 1 longest = max(longest, length) return longest
题目62：移动零
问题描述：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。要求原地操作，不能复制数组。
解题思路：使用双指针。指针 slow 指向当前应放置非零元素的位置，指针 fast 遍历数组。当 nums[fast] 非零时，将其与 nums[slow] 交换，然后 slow 右移。遍历结束后，slow 之后的位置全部置零。
Python 代码示例：
1 2 3 4 5 6 7 def moveZeroes(nums): slow = 0 for fast in range(len(nums)): if nums[fast] != 0: nums[slow], nums[fast] = nums[fast], nums[slow] slow += 1
题目63：找到字符串中所有字母异位词
问题描述：给定两个字符串 s 和 p，找到 s 中所有 p 的字母异位词的子串，返回这些子串的起始索引。字母异位词指由相同字母重排列形成的字符串。
解题思路：使用固定大小的滑动窗口。维护窗口大小为 len(p)，统计窗口内字符频次与 p 的字符频次是否一致。每次窗口右移时更新频次表，若一致则记录起始索引。
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 from collections import Counterdef findAnagrams(s, p): if len(s) < len(p): return [] p_count = Counter(p) window = Counter(s[:len(p)]) result = [] if window == p_count: result.append(0) for i in range(len(p), len(s)): left_char = s[i - len(p)] window[left_char] -= 1 if window[left_char] == 0: del window[left_char] window[s[i]] += 1 if window == p_count: result.append(i - len(p) + 1) return result
题目64：字符串解码
问题描述：给定一个经过编码的字符串，返回它解码后的字符串。编码规则为 k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。可以嵌套。
解题思路：使用两个栈，一个存储重复次数，一个存储之前的字符串。遍历字符串，遇到数字时累积计算 k；遇到 [ 时将当前 k 和当前字符串分别入栈并重置；遇到 ] 时弹出栈顶的字符串和次数，将当前字符串重复拼接；遇到字母时追加到当前字符串。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def decodeString(s): count_stack = [] string_stack = [] cur = '' k = 0 for ch in s: if ch.isdigit(): k = k * 10 + int(ch) elif ch == '[': count_stack.append(k) string_stack.append(cur) cur = '' k = 0 elif ch == ']': cur = string_stack.pop() + cur * count_stack.pop() else: cur += ch return cur
题目65：前 K 个高频元素
问题描述：给定一个非空的整数数组 nums 和一个整数 k，返回其中出现频率前 k 高的元素。可以按任意顺序返回答案。
解题思路：先用哈希表统计每个元素的频率，然后使用桶排序：创建 n + 1 个桶，将频率为 i 的元素放入第 i 个桶。从高频桶到低频桶依次收集元素，直到收集到 k 个为止。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 from collections import Counterdef topKFrequent(nums, k): count = Counter(nums) buckets = [[] for _ in range(len(nums) + 1)] for num, freq in count.items(): buckets[freq].append(num) result = [] for freq in range(len(buckets) - 1, 0, -1): for num in buckets[freq]: result.append(num) if len(result) == k: return result return result
题目66：缺失的第一个正数
问题描述：给定一个未排序的整数数组 nums，找出其中没有出现的最小的正整数。要求时间复杂度为 O(n)，空间复杂度为 O(1)。
解题思路：使用原地哈希。遍历数组，将数值在 [1, n] 范围内的元素放到其正确的位置上（即 nums[i] 应放在索引 nums[i] - 1 处）。再次遍历数组，第一个满足 nums[i] != i + 1 的位置 i + 1 即为缺失的最小正整数。若全部匹配，则返回 n + 1。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 def firstMissingPositive(nums): n = len(nums) for i in range(n): while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] for i in range(n): if nums[i] != i + 1: return i + 1 return n + 1
题目67：接雨水
问题描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解题思路：使用双指针。维护左右两个指针和左右两侧的最大高度 left_max、right_max。每次移动较小一侧的指针，若当前高度小于该侧最大高度，则可接雨水为最大高度减去当前高度；否则更新该侧最大高度。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def trap(height): if not height: return 0 left, right = 0, len(height) - 1 left_max = right_max = 0 water = 0 while left < right: if height[left] < height[right]: if height[left] >= left_max: left_max = height[left] else: water += left_max - height[left] left += 1 else: if height[right] >= right_max: right_max = height[right] else: water += right_max - height[right] right -= 1 return water
题目68：无重复字符的最长子串
问题描述：给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
解题思路：使用滑动窗口 + 哈希表。维护一个窗口 [left, right]，哈希表记录字符最后出现的位置。当遇到重复字符时，将 left 移动到该字符上次出现位置的下一位。遍历过程中记录窗口的最大长度。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 def lengthOfLongestSubstring(s): last_seen = {} left = 0 max_len = 0 for right, ch in enumerate(s): if ch in last_seen and last_seen[ch] >= left: left = last_seen[ch] + 1 last_seen[ch] = right max_len = max(max_len, right - left + 1) return max_len
题目69：最小覆盖子串
问题描述：给定一个字符串 s 和一个字符串 t，返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。
解题思路：使用滑动窗口。先用哈希表统计 t 中每个字符的需求量。右指针扩展窗口，当窗口满足条件时，尝试收缩左指针以找到最小窗口。维护一个变量 formed 记录已满足需求的字符种类数，当 formed == len(need) 时窗口有效。
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 Counterdef minWindow(s, t): if not s or not t: return "" need = Counter(t) window = {} formed = 0 required = len(need) left = 0 min_len = float('inf') min_start = 0 for right, ch in enumerate(s): window[ch] = window.get(ch, 0) + 1 if ch in need and window[ch] == need[ch]: formed += 1 while formed == required: if right - left + 1 < min_len: min_len = right - left + 1 min_start = left left_char = s[left] window[left_char] -= 1 if left_char in need and window[left_char] < need[left_char]: formed -= 1 left += 1 return "" if min_len == float('inf') else s[min_start:min_start + min_len]
题目70：最大矩形
问题描述：给定一个仅包含 '0' 和 '1' 的二维二进制矩阵 matrix，找出只包含 '1' 的最大矩形，并返回其面积。
解题思路：将问题转化为多个“柱状图中最大的矩形”问题。逐行遍历矩阵，维护一个高度数组 heights，其中 heights[j] 表示第 j 列从当前行向上连续 '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 def maximalRectangle(matrix): if not matrix: return 0 cols = len(matrix[0]) heights = [0] * cols max_area = 0 for row in matrix: for j in range(cols): if row[j] == '1': heights[j] += 1 else: heights[j] = 0 # 单调栈求柱状图最大矩形 stack = [] for i in range(cols + 1): h = heights[i] if i < cols else 0 while stack and heights[stack[-1]] > h: height = heights[stack.pop()] width = i if not stack else i - stack[-1] - 1 max_area = max(max_area, height * width) stack.append(i) return max_area