ARTICLE · 1082196
2026网安习题大全(6)
题目51：最大正方形
问题描述：给定一个由 '0' 和 '1' 组成的二维字符矩阵 matrix，找出只包含 '1' 的最大正方形，并返回其面积。
解题思路：使用动态规划。dp[i][j] 表示以 (i, j) 为右下角的最大正方形的边长。若 matrix[i][j] == '1'，则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。遍历过程中记录最大边长，最终返回其平方。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def maximalSquare(matrix): if not matrix: return 0 rows, cols = len(matrix), len(matrix[0]) dp = [[0] * (cols + 1) for _ in range(rows + 1)] max_side = 0 for r in range(1, rows + 1): for c in range(1, cols + 1): if matrix[r - 1][c - 1] == '1': dp[r][c] = min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]) + 1 max_side = max(max_side, dp[r][c]) return max_side * max_side
题目52：编辑距离
问题描述：给定两个单词 word1 和 word2，返回将 word1 转换成 word2 所使用的最少操作数。可以进行的操作有：插入一个字符、删除一个字符、替换一个字符。
解题思路：使用动态规划。dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作数。若 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]；否则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def minDistance(word1, word2): m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 return dp[m][n]
题目53：颜色分类
问题描述：给定一个包含红色、白色和蓝色（分别用 0、1、2 表示）的数组 nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。要求不使用库排序函数，且只允许一次遍历。
解题思路：使用荷兰国旗问题的三指针法。维护 left、mid、right 三个指针，left 指向 0 的右边界，right 指向 2 的左边界，mid 用于遍历。当 nums[mid] == 0 时与 left 交换并同时右移；当 nums[mid] == 2 时与 right 交换并左移 right；当 nums[mid] == 1 时直接右移 mid。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 def sortColors(nums): left, mid, right = 0, 0, len(nums) - 1 while mid <= right: if nums[mid] == 0: nums[left], nums[mid] = nums[mid], nums[left] left += 1 mid += 1 elif nums[mid] == 2: nums[mid], nums[right] = nums[right], nums[mid] right -= 1 else: mid += 1
题目54：多数元素
问题描述：给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n / 2⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
解题思路：使用摩尔投票法（Boyer-Moore Voting Algorithm）。维护一个候选元素 candidate 和计数器 count。遍历数组，若 count == 0 则将当前元素设为候选，否则若当前元素等于候选则 count += 1，否则 count -= 1。最终 candidate 即为多数元素。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 def majorityElement(nums): candidate = None count = 0 for num in nums: if count == 0: candidate = num count += 1 if num == candidate else -1 return candidate
题目55：找到所有数组中消失的数字
问题描述：给定一个含 n 个整数的数组 nums，其中 nums[i] 在区间 [1, n] 内。找出所有在 [1, n] 范围内但没有出现在 nums 中的数字。要求不使用额外空间且时间复杂度为 O(n)。
解题思路：利用数组本身作为哈希表。遍历数组，将 nums[i] - 1 位置上的元素取负，标记该数字已出现。再次遍历数组，若某个位置上的元素仍为正数，则说明该位置对应的数字 i + 1 未出现。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 def findDisappearedNumbers(nums): for num in nums: index = abs(num) - 1 if nums[index] > 0: nums[index] = -nums[index] result = [] for i, num in enumerate(nums): if num > 0: result.append(i + 1) return result
题目56：只出现一次的数字
问题描述：给定一个非空整数数组 nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。要求时间复杂度为 O(n)，空间复杂度为 O(1)。
解题思路：使用异或运算。异或运算满足交换律和结合律，且 a ^ a = 0，a ^ 0 = a。将数组中所有元素依次异或，最终结果即为只出现一次的元素。
Python 代码示例：
1 2 3 4 5 6 7 def singleNumber(nums): result = 0 for num in nums: result ^= num return result
题目57：相交链表 II
问题描述：给定两个单链表的头节点 headA 和 headB，找出并返回两个链表相交的起始节点。如果两个链表不相交，返回 None。要求空间复杂度为 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 23 24 def getIntersectionNode(headA, headB): lenA = lenB = 0 pA, pB = headA, headB while pA: lenA += 1 pA = pA.next while pB: lenB += 1 pB = pB.next pA, pB = headA, headB if lenA > lenB: for _ in range(lenA - lenB): pA = pA.next else: for _ in range(lenB - lenA): pB = pB.next while pA != pB: pA = pA.next pB = pB.next return pA
题目58：课程表 II
问题描述：给定课程总数 numCourses 和先修课程列表 prerequisites，返回为了完成所有课程所安排的学习顺序。如果不可能完成所有课程，返回空数组。
解题思路：在课程表 I 的拓扑排序基础上，记录出队顺序。使用 BFS + 入度表，将入度为 0 的节点依次入队并出队，将出队顺序记录到结果数组中。若最终结果数组长度等于课程总数，则返回该顺序；否则返回空数组。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 from collections import dequedef findOrder(numCourses, prerequisites): graph = [[] for _ in range(numCourses)] indegree = [0] * numCourses for a, b in prerequisites: graph[b].append(a) indegree[a] += 1 queue = deque([i for i in range(numCourses) if indegree[i] == 0]) order = [] while queue: node = queue.popleft() order.append(node) for nxt in graph[node]: indegree[nxt] -= 1 if indegree[nxt] == 0: queue.append(nxt) return order if len(order) == numCourses else []
题目59：实现 Trie（前缀树）
问题描述：实现一个 Trie（前缀树），包含 insert、search 和 startsWith 三个操作。
解题思路：使用字典嵌套实现。每个节点是一个字典，键为字符，值为子节点。insert 时逐字符创建节点，末尾用特殊标记（如 '#'）表示单词结束。search 需要检查完整路径且末尾有结束标记；startsWith 只需检查路径是否存在。
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 class Trie: def __init__(self): self.root = {} def insert(self, word): node = self.root for ch in word: if ch not in node: node[ch] = {} node = node[ch] node['#'] = True def search(self, word): node = self.root for ch in word: if ch not in node: return False node = node[ch] return '#' in node def startsWith(self, prefix): node = self.root for ch in prefix: if ch not in node: return False node = node[ch] return True
题目60：数组中的第 K 个最大元素
问题描述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。要求时间复杂度为 O(n)。
解题思路：使用快速选择算法（基于快速排序的 partition）。每次选取一个基准元素，将数组分为大于基准和小于基准两部分。若基准位置恰好为 k - 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 import randomdef findKthLargest(nums, k): def partition(left, right, pivot_index): pivot = nums[pivot_index] nums[pivot_index], nums[right] = nums[right], nums[pivot_index] store = left for i in range(left, right): if nums[i] > pivot: nums[store], nums[i] = nums[i], nums[store] store += 1 nums[store], nums[right] = nums[right], nums[store] return store left, right = 0, len(nums) - 1 target = k - 1 while left <= right: pivot_index = random.randint(left, right) pos = partition(left, right, pivot_index) if pos == target: return nums[pos] elif pos < target: left = pos + 1 else: right = pos - 1