ARTICLE · 1064679
2026网安习题大全(3)
题目21：螺旋矩阵
问题描述：给定一个 m x n 的矩阵 matrix，按照顺时针螺旋顺序，返回矩阵中的所有元素。
解题思路：定义四个边界 top、bottom、left、right，按照右、下、左、上的顺序遍历矩阵，每遍历完一条边就收缩对应边界，直到边界交叉为止。
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 def spiralOrder(matrix): if not matrix: return [] result = [] top, bottom = 0, len(matrix) - 1 left, right = 0, len(matrix[0]) - 1 while top <= bottom and left <= right: for c in range(left, right + 1): result.append(matrix[top][c]) top += 1 for r in range(top, bottom + 1): result.append(matrix[r][right]) right -= 1 if top <= bottom: for c in range(right, left - 1, -1): result.append(matrix[bottom][c]) bottom -= 1 if left <= right: for r in range(bottom, top - 1, -1): result.append(matrix[r][left]) left += 1 return result
题目22：K 个一组翻转链表
问题描述：给定一个链表，每 k 个节点一组进行翻转，返回翻转后的链表。如果节点总数不是 k 的整数倍，则将最后剩余的节点保持原有顺序。
解题思路：使用哑节点。先检查剩余节点是否有 k 个，若不足则直接返回。否则翻转这 k 个节点，将翻转后的子链表接回原链表，然后移动指针继续处理下一组。
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 def reverseKGroup(head, k): dummy = ListNode(0) dummy.next = head prev_group = dummy while True: # 检查剩余节点是否有 k 个 node = prev_group for _ in range(k): node = node.next if not node: return dummy.next # 翻转 k 个节点 prev = None curr = prev_group.next for _ in range(k): nxt = curr.next curr.next = prev prev = curr curr = nxt # 接回链表 tail = prev_group.next prev_group.next = prev tail.next = curr prev_group = tail
题目23：单词搜索
问题描述：给定一个 m x n 的二维字符网格 board 和一个字符串 word，判断 word 是否存在于网格中。单词必须由水平或垂直相邻的单元格内的字母构成，且同一单元格内的字母不允许被重复使用。
解题思路：使用 DFS + 回溯。遍历网格每个位置，以该位置为起点进行 DFS，匹配 word 的每个字符。匹配过程中将当前单元格临时标记为已访问，回溯时恢复。
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 def exist(board, word): if not board or not word: return False rows, cols = len(board), len(board[0]) def dfs(r, c, index): if index == len(word): return True if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[index]: return False temp = board[r][c] board[r][c] = '#' found = (dfs(r + 1, c, index + 1) or dfs(r - 1, c, index + 1) or dfs(r, c + 1, index + 1) or dfs(r, c - 1, index + 1)) board[r][c] = temp return found for r in range(rows): for c in range(cols): if dfs(r, c, 0): return True return False
题目24：组合总和 II
问题描述：给定一个可能包含重复数字的数组 candidates 和一个目标整数 target，找出所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。
解题思路：先对数组排序，使用回溯法。递归时跳过同一层中重复的元素，避免产生重复组合。每次选择当前元素后，从下一个位置继续递归。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def combinationSum2(candidates, target): candidates.sort() result = [] def backtrack(start, path, remain): if remain == 0: result.append(path[:]) return if remain < 0: return for i in range(start, len(candidates)): if i > start and candidates[i] == candidates[i - 1]: continue path.append(candidates[i]) backtrack(i + 1, path, remain - candidates[i]) path.pop() backtrack(0, [], target) return result
题目25：LRU 缓存
问题描述：设计并实现一个满足 LRU（最近最少使用）缓存约束的数据结构。支持 get 和 put 操作，且都要求以 O(1) 的平均时间复杂度运行。
解题思路：使用哈希表 + 双向链表。哈希表存储 key 到链表节点的映射，双向链表维护访问顺序：头部为最近使用，尾部为最久未使用。get 时将节点移到头部，put 时若容量满则删除尾部节点。
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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Node: def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = Noneclass LRUCache: def __init__(self, capacity): self.capacity = capacity self.cache = {} self.head = Node() self.tail = Node() self.head.next = self.tail self.tail.prev = self.head def _remove(self, node): node.prev.next = node.next node.next.prev = node.prev def _add_to_head(self, node): node.next = self.head.next node.prev = self.head self.head.next.prev = node self.head.next = node def get(self, key): if key not in self.cache: return -1 node = self.cache[key] self._remove(node) self._add_to_head(node) return node.val def put(self, key, value): if key in self.cache: node = self.cache[key] node.val = value self._remove(node) self._add_to_head(node) else: if len(self.cache) == self.capacity: lru = self.tail.prev self._remove(lru) del self.cache[lru.key] node = Node(key, value) self.cache[key] = node self._add_to_head(node)
题目26：二叉树的最大深度
问题描述：给定一个二叉树的根节点 root，返回其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
解题思路：使用递归。当前节点的最大深度等于其左子树和右子树最大深度的较大值加一。若节点为空则返回 0。
Python 代码示例：
1 2 3 4 5 def maxDepth(root): if not root: return 0 return 1 + max(maxDepth(root.left), maxDepth(root.right))
题目27：二叉树的层序遍历
问题描述：给定一个二叉树的根节点 root，返回其节点值的层序遍历结果，即逐层地从左到右访问所有节点。
解题思路：使用队列进行 BFS。每轮记录当前队列长度（即当前层的节点数），依次弹出节点并将其子节点入队，将当前层的值收集为一个列表加入结果。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 from collections import dequedef levelOrder(root): if not root: return [] result = [] queue = deque([root]) while queue: level = [] for _ in range(len(queue)): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result
题目28：验证二叉搜索树
问题描述：给定一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。有效 BST 满足：左子树所有节点值小于根节点值，右子树所有节点值大于根节点值。
解题思路：使用递归并维护上下界。每个节点必须满足 lower < node.val < upper。递归左子树时将上界更新为当前节点值，递归右子树时将下界更新为当前节点值。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 def isValidBST(root): def validate(node, lower, upper): if not node: return True if node.val <= lower or node.val >= upper: return False return (validate(node.left, lower, node.val) and validate(node.right, node.val, upper)) return validate(root, float('-inf'), float('inf'))
题目29：二叉树的中序遍历
问题描述：给定一个二叉树的根节点 root，返回它的中序遍历结果。
解题思路：使用迭代 + 栈。从根节点开始，不断将左子节点压入栈，直到为空；然后弹出栈顶节点访问其值，再转向其右子节点。重复此过程直到栈空且当前节点为空。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def inorderTraversal(root): result = [] stack = [] curr = root while curr or stack: while curr: stack.append(curr) curr = curr.left curr = stack.pop() result.append(curr.val) curr = curr.right return result
题目30：从前序与中序遍历序列构造二叉树
问题描述：给定一棵二叉树的前序遍历序列 preorder 和中序遍历序列 inorder，构造并返回这棵二叉树。
解题思路：前序遍历的第一个元素是根节点。在中序遍历中找到根节点的位置，即可将中序序列分为左子树和右子树两部分。利用哈希表记录中序序列中每个值的位置，递归构造左右子树。
Python 代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def buildTree(preorder, inorder): if not preorder or not inorder: return None index_map = {val: i for i, val in enumerate(inorder)} pre_idx = [0] def build(left, right): if left > right: return None root_val = preorder[pre_idx[0]] pre_idx[0] += 1 root = TreeNode(root_val) mid = index_map[root_val] root.left = build(left, mid - 1) root.right = build(mid + 1, right) return root return build(0, len(inorder) - 1)