超全网络安全技术练习题(21)
- 2026-11-16 20:23:34
题目1:最小基因变化
问题描述:基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化意味着这个基因序列中的一个字符发生了变化。例如,"AACCGGTT" 变为 "AACCGGTA" 就是一次基因变化。另有一个基因库 bank 记录了所有有效的基因变化,只有基因库中的基因序列才是合法的基因序列。给你两个基因序列 start 和 end,以及一个基因库 bank,请你找出能够使上述基因从 start 变为 end 的最少变化次数。如果无法完成此基因变化,返回 -1。
解题思路:使用广度优先搜索(BFS)。从 start 开始,每次尝试将 8 个位置中的某一个字符替换为其他 3 种字符,若新字符串在基因库中且未被访问过,则加入队列。BFS 按层遍历,第一次遇到 end 时的层数即为最少变化次数。若队列为空仍未找到,返回 -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 from collections import dequedef minMutation(start, end, bank): bank_set = set(bank) if end not in bank_set: return -1 queue = deque([(start, 0)]) visited = {start} chars = "ACGT" while queue: gene, steps = queue.popleft() if gene == end: return steps for i in range(len(gene)): for c in chars: if c == gene[i]: continue new_gene = gene[:i] + c + gene[i + 1:] if new_gene in bank_set and new_gene not in visited: visited.add(new_gene) queue.append((new_gene, steps + 1)) return -1
题目2:整数转罗马数字
问题描述:罗马数字包含以下七种字符:I、V、X、L、C、D 和 M。例如,罗马数字 2 写做 II,12 写做 XII,27 写做 XXVII。通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV;9 表示为 IX;40 表示为 XL;90 表示为 XC;400 表示为 CD;900 表示为 CM。给你一个整数,将它转为罗马数字。
解题思路:使用贪心算法。将所有可能的罗马数字符号(包括特例)按数值从大到小排列。从大到小遍历,若当前数值小于等于 num,则将其对应符号加入结果,并从 num 中减去该数值,重复直到 num 为 0。
Python代码示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def intToRoman(num): value_symbols = [ (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I") ] result = [] for value, symbol in value_symbols: while num >= value: result.append(symbol) num -= value return ''.join(result)
题目3:罗马数字转整数
问题描述:罗马数字包含七种字符:I、V、X、L、C、D 和 M。给定一个罗马数字,将其转换成整数。
解题思路:从左到右遍历罗马数字。若当前字符对应的数值小于右边字符对应的数值,则说明这是一个特例(如 IV、IX),应减去当前数值;否则加上当前数值。遍历结束后累加结果即为整数。
Python代码示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def romanToInt(s): values = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000 } result = 0 n = len(s) for i in range(n): if i + 1 < n and values[s[i]] < values[s[i + 1]]: result -= values[s[i]] else: result += values[s[i]] return result
题目4:判定字符是否唯一
问题描述:实现一个算法,确定一个字符串 s 的所有字符是否全都不同。假设字符串只包含小写字母。
解题思路:使用位运算。用一个 26 位整数作为位掩码,记录每个字符是否出现过。遍历字符串,对于每个字符,计算其对应的位;若该位已经为 1,说明字符重复,返回 False;否则将该位置为 1。遍历结束返回 True。
Python代码示例:
1 2 3 4 5 6 7 8 9 10 def isUnique(s): mask = 0 for char in s: bit = 1 << (ord(char) - ord('a')) if mask & bit: return False mask |= bit return True
题目5:数组中重复的数据
问题描述:给你一个长度为 n 的整数数组 nums,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现一次或两次。请你找出所有出现两次的整数,并以数组形式返回。你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。
解题思路:使用原地哈希。遍历数组,对于每个元素 num,将其对应的下标 abs(num) - 1 处的值取反。若该位置已经是负数,说明 abs(num) 之前已经出现过一次,因此它是重复元素,加入结果。遍历结束后返回结果。
Python代码示例:
1 2 3 4 5 6 7 8 9 10 11 def findDuplicates(nums): result = [] for num in nums: index = abs(num) - 1 if nums[index] < 0: result.append(abs(num)) else: nums[index] = -nums[index] return result
题目6:螺旋矩阵II
问题描述:给你一个正整数 n,生成一个包含 1 到 n² 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix。
解题思路:模拟螺旋填充过程。维护四个边界 top、bottom、left、right,按照从左到右、从上到下、从右到左、从下到上的顺序依次填入数字。每完成一个方向就收缩对应边界,直到填满 n² 个数字。
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 def generateMatrix(n): matrix = [[0] * n for _ in range(n)] top, bottom = 0, n - 1 left, right = 0, n - 1 num = 1 while left <= right and top <= bottom: for j in range(left, right + 1): matrix[top][j] = num num += 1 top += 1 for i in range(top, bottom + 1): matrix[i][right] = num num += 1 right -= 1 if top <= bottom: for j in range(right, left - 1, -1): matrix[bottom][j] = num num += 1 bottom -= 1 if left <= right: for i in range(bottom, top - 1, -1): matrix[i][left] = num num += 1 left += 1 return matrix
题目7:字符串相加
问题描述:给定两个字符串形式的非负整数 num1 和 num2,计算它们的和并同样以字符串形式返回。你不能使用任何內建的用于处理大整数的库(比如 BigInteger),也不能直接将输入的字符串转换为整数形式。
解题思路:模拟竖式加法。用两个指针分别从两个字符串的末尾向前遍历,同时维护一个进位变量。每次将两个指针所指数字(若越界则视为 0)与进位相加,当前位结果为 total % 10,新进位为 total // 10。遍历结束后若进位仍为 1,则再补一位。最后反转结果字符串。
Python代码示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def addStrings(num1, num2): i, j = len(num1) - 1, len(num2) - 1 carry = 0 result = [] while i >= 0 or j >= 0 or carry: x = int(num1[i]) if i >= 0 else 0 y = int(num2[j]) if j >= 0 else 0 total = x + y + carry result.append(str(total % 10)) carry = total // 10 i -= 1 j -= 1 return ''.join(reversed(result))
题目8:下一个更大元素II
问题描述:给定一个循环数组 nums(nums[nums.length - 1] 的下一个元素是 nums[0]),返回 nums 中每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。
解题思路:使用单调递减栈 + 循环遍历两倍数组长度。栈中存储下标,遍历 2n 个位置(用 i % n 取实际下标),当当前元素大于栈顶下标对应元素时,说明找到了栈顶元素的下一个更大元素,弹出并记录答案。每个元素最多入栈出栈一次,时间复杂度 O(n)。
Python代码示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 def nextGreaterElements(nums): n = len(nums) result = [-1] * n stack = [] for i in range(2 * n): index = i % n while stack and nums[stack[-1]] < nums[index]: result[stack.pop()] = nums[index] if i < n: stack.append(index) return result
题目9:二叉树的直径
问题描述:给你一棵二叉树的根节点,返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点。两节点之间路径的长度由它们之间边数表示。
解题思路:使用递归计算每个节点的深度。对于每个节点,以它为“拐点”的路径长度为左子树深度加右子树深度,用全局变量记录这个最大值。递归返回当前节点的深度(左右子树深度的较大值加一)。注意直径是边数,所以最终答案是左右深度之和。
Python代码示例(假设 TreeNode 类已定义):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def diameterOfBinaryTree(root): diameter = 0 def depth(node): nonlocal diameter if not node: return 0 left_depth = depth(node.left) right_depth = depth(node.right) diameter = max(diameter, left_depth + right_depth) return max(left_depth, right_depth) + 1 depth(root) return diameter
题目10:根据身高重建队列
问题描述:假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi,前面正好有 ki 个身高大于或等于 hi 的人。请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue,其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人)。
解题思路:使用排序 + 插入。先按身高降序排序,身高相同的按 ki 升序排序。然后依次将每个人插入到结果列表中下标为 ki 的位置。由于先处理身高高的人,后插入身高较矮的人不会影响已插入人的 ki 值,因此插入位置直接为 ki 即可。
Python代码示例:
1 2 3 4 5 6 7 8 def reconstructQueue(people): people.sort(key=lambda x: (-x[0], x[1])) result = [] for person in people: result.insert(person[1], person) return result