网络安全技术练习题大全(27)
- 2026-11-07 05:16:28
题目61：第三大的数
问题描述：给你一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。
示例：
• 输入： nums = [3, 2, 1]，输出：1• 解释：第三大的数是 1。• 输入： nums = [1, 2]，输出：2• 解释：第三大的数不存在，所以返回最大的数 2。• 输入： nums = [2, 2, 3, 1]，输出：1• 解释：注意，要求返回第三大的数，是指第三大且唯一的数。存在两个值为 2的数，它们都排第二。
解题思路：使用三个变量 first、second、third 分别记录第一大、第二大、第三大的唯一值，初始化为负无穷。遍历数组，对于每个元素 num：
• 如果 num > first，则依次更新third = second，second = first，first = num；• 否则如果 num > second且num != first，则third = second，second = num；• 否则如果 num > third且num != second且num != first，则third = num。遍历结束后，如果third仍为负无穷，则返回first；否则返回third。时间复杂度 O(n)，空间复杂度 O(1)。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def thirdMax(nums): first = second = third = float('-inf') for num in nums: if num > first: third = second second = first first = num elif num > second and num != first: third = second second = num elif num > third and num != second and num != first: third = num return third if third != float('-inf') else first
题目62：数字转换为十六进制数
问题描述：给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用补码运算方法。注意：
• 十六进制中所有字母（ a-f）都必须是小写。• 十六进制字符串中不能包含多余的前导零。如果要转化的数为 0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0。• 给定的数确保在 32 位有符号整数范围内。 • 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。
示例：
• 输入： 26，输出："1a"• 输入： -1，输出："ffffffff"
解题思路：使用位运算。对于 32 位整数，可以直接将其视为无符号整数处理。每次取 num 的最低 4 位（num & 0xF），转换为对应的十六进制字符，然后将 num 右移 4 位（num >>= 4）。重复直到 num == 0。最后反转结果字符串。注意处理 num == 0 的情况。时间复杂度 O(log n)，空间复杂度 O(1)。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def toHex(num): if num == 0: return "0" hex_chars = "0123456789abcdef" result = [] # 处理负数：转换为 32 位无符号整数 num &= 0xFFFFFFFF while num: result.append(hex_chars[num & 0xF]) num >>= 4 return ''.join(reversed(result))
题目63：汉明距离
问题描述：两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例：
• 输入： x = 1, y = 4，输出：2• 解释： 1 2 3 1 (0 0 0 1)4 (0 1 0 0) ↑ ↑
上面的箭头指出了对应二进制位不同的位置。
• 输入： x = 3, y = 1，输出：1
解题思路：先计算 x ^ y，得到的结果中 1 的个数即为汉明距离。然后使用 n & (n - 1) 可以消除最低位的 1，统计消除次数即可。时间复杂度 O(1)（最多 32 位），空间复杂度 O(1)。
Python代码示例：
1 2 3 4 5 6 7 8 9 def hammingDistance(x, y): xor = x ^ y distance = 0 while xor: xor &= xor - 1 distance += 1 return distance
题目64：判断子序列
问题描述：给定字符串 s 和 t，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。例如，"ace" 是 "abcde" 的一个子序列，而 "aec" 不是。
示例：
• 输入： s = "abc", t = "ahbgdc"，输出：true• 输入： s = "axc", t = "ahbgdc"，输出：false
解题思路：使用双指针。指针 i 遍历 s，指针 j 遍历 t。当 s[i] == t[j] 时，i 后移；j 每次循环都后移。如果 i 能够到达 s 的末尾，说明 s 是 t 的子序列。时间复杂度 O(n + m)，空间复杂度 O(1)。
Python代码示例：
1 2 3 4 5 6 7 8 def isSubsequence(s, t): i = j = 0 while i < len(s) and j < len(t): if s[i] == t[j]: i += 1 j += 1 return i == len(s)
题目65：将有序数组转换为二叉搜索树
问题描述：给你一个整数数组 nums，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1」的二叉树。
示例：
• 输入： nums = [-10,-3,0,5,9]• 输出： [0,-3,9,-10,null,5]（或[0,-10,5,null,-3,null,9]等，答案不唯一）
解题思路：由于数组已升序排列，可以选择中间元素作为根节点，这样左右子树的元素数量尽量相等，保证平衡。递归地，对左半部分构建左子树，对右半部分构建右子树。时间复杂度 O(n)，空间复杂度 O(log n)（递归栈）。
Python代码示例（假设 TreeNode 类已定义）：
1 2 3 4 5 6 7 8 9 10 11 def sortedArrayToBST(nums): if not nums: return None mid = len(nums) // 2 root = TreeNode(nums[mid]) root.left = sortedArrayToBST(nums[:mid]) root.right = sortedArrayToBST(nums[mid + 1:]) return root
题目66：杨辉三角
问题描述：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例：
• 输入： numRows = 5• 输出： [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
解题思路：逐行构建。第一行固定为 [1]。对于每一行，首尾元素均为 1，中间元素 res[i][j] = res[i-1][j-1] + res[i-1][j]。时间复杂度 O(numRows²)，空间复杂度 O(numRows²)。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 def generate(numRows): result = [] for i in range(numRows): row = [1] * (i + 1) for j in range(1, i): row[j] = result[i - 1][j - 1] + result[i - 1][j] result.append(row) return result
题目67：杨辉三角 II
问题描述：给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。注意：rowIndex 从 0 开始。
示例：
• 输入： rowIndex = 3，输出：[1,3,3,1]
解题思路：使用一维数组滚动更新。初始数组为 [1]。对于每一行，从后往前更新：row[j] = row[j] + row[j-1]。这样可以在 O(rowIndex) 空间内完成。时间复杂度 O(rowIndex²)，空间复杂度 O(rowIndex)。
Python代码示例：
1 2 3 4 5 6 7 8 def getRow(rowIndex): row = [1] * (rowIndex + 1) for i in range(1, rowIndex + 1): for j in range(i - 1, 0, -1): row[j] += row[j - 1] return row
题目68：排列硬币
问题描述：你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行可能是不完整的。给你一个数字 n，计算并返回可形成完整阶梯行的总行数。
示例：
• 输入： n = 5，输出：2• 解释：因为第三行不完整，所以返回 2。 • 输入： n = 8，输出：3
解题思路：方法一：数学公式。完整 k 行需要的硬币数为 k*(k+1)/2。解方程 k*(k+1)/2 <= n，得到 k = floor((sqrt(8n+1)-1)/2)。方法二：二分查找。在 [1, n] 范围内查找最大的 k 使得 k*(k+1)/2 <= n。时间复杂度 O(log n)，空间复杂度 O(1)。
Python代码示例（数学公式）：
1 2 3 4 import mathdef arrangeCoins(n): return int((math.sqrt(8 * n + 1) - 1) // 2)
题目69：二叉树的层平均值
问题描述：给定一个非空二叉树的根节点 root，以数组的形式返回每一层节点的平均值。与实际答案相差 10^-5 以内的答案可以被接受。
示例：
• 输入： root = [3,9,20,null,null,15,7]• 输出： [3.00000,14.50000,11.00000]• 解释：第 0 层的平均值为 3，第 1 层的平均值为 14.5，第 2 层的平均值为 11。
解题思路：使用广度优先搜索（BFS）进行层序遍历。对于每一层，累加所有节点的值，并记录节点个数，计算平均值后加入结果列表。时间复杂度 O(n)，空间复杂度 O(n)。
Python代码示例（假设 TreeNode 类已定义）：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 from collections import dequedef averageOfLevels(root): if not root: return [] result = [] queue = deque([root]) while queue: level_sum = 0 level_size = len(queue) for _ in range(level_size): node = queue.popleft() level_sum += node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level_sum / level_size) return result
题目70：另一棵树的子树
问题描述：给你两棵二叉树 root 和 subRoot。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果 root 存在一棵子树，其结构和节点值与 subRoot 完全相同，则返回 true；否则返回 false。root 的一棵子树包括 root 的某个节点和这个节点的所有后代节点。root 也可以看做它自身的一棵子树。
示例：
• 输入： root = [3,4,5,1,2], subRoot = [4,1,2]• 输出： true• 输入： root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]• 输出： false
解题思路：遍历 root 中的每个节点，对于每个节点，判断以该节点为根的子树是否与 subRoot 完全相同。判断两棵树是否相同可以用递归：根节点值相同，且左右子树分别相同。时间复杂度 O(m * n)，其中 m 是 root 的节点数，n 是 subRoot 的节点数。空间复杂度 O(max(m, n))。
Python代码示例（假设 TreeNode 类已定义）：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def isSubtree(root, subRoot): if not root: return False def is_same(t1, t2): if not t1 and not t2: return True if not t1 or not t2: return False return (t1.val == t2.val and is_same(t1.left, t2.left) and is_same(t1.right, t2.right)) return (is_same(root, subRoot) or isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot))
