网络安全黑客技术练习题大全(44)

题目31：树的子结构

问题描述：输入两棵二叉树A和B，判断B是不是A的子结构。（约定空树不是任意一个树的子结构）子结构定义为：B是A的子结构，当且仅当存在A中的一个节点，以该节点为根的子树包含B 的所有节点，且结构相同、节点值相同。

解题思路：递归。

• • 若 B 为空，返回 False（空树不是子结构）。
• • 定义辅助函数 isSub(A, B)：判断以 A 为根的树是否包含以 B 为根的树（允许 A 有额外子节点，但 B 的节点必须完全匹配）。
• • 主函数遍历 A 的每个节点，若 A 的当前节点值与 B 的根节点值相同，则调用 isSub 检查；否则递归检查 A 的左子树和右子树。

Python代码示例（假设 TreeNode 类已定义）：

def isSubStructure(A, B):    if not A or not B:        return False    return isSub(A, B) or isSubStructure(A.left, B) or isSubStructure(A.right, B)def isSub(A, B):    if not B:        return True    if not A or A.val != B.val:        return False    return isSub(A.left, B.left) and isSub(A.right, B.right)

题目32：栈的压入、弹出序列

问题描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 [1,2,3,4,5] 是某栈的压栈序列，序列 [4,5,3,2,1] 是该栈对应的一个弹出序列，但 [4,3,5,1,2] 就不可能是该压栈序列的弹出序列。

解题思路：使用一个辅助栈模拟压入和弹出过程。遍历压入序列，将元素依次压入辅助栈。每次压入后，检查栈顶是否等于弹出序列的当前元素，若相等则弹出栈顶并移动弹出序列的指针。最终若辅助栈为空，则说明弹出序列合法。

Python代码示例：

def validateStackSequences(pushed, popped):    stack = []    j = 0    for num in pushed:        stack.append(num)        while stack and stack[-1] == popped[j]:            stack.pop()            j += 1    return not stack

题目33：把数组排成最小的数

问题描述：输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如，输入数组 [3, 30, 34, 5, 9]，则拼接出的最小数字为 "3033459"。

解题思路：自定义排序。对于两个数字a和b，比较拼接字符串a+b和b+a的字典序，若a+b < b+a，则a应排在b前面。将数组按此规则升序排序后拼接。注意处理全为 0 的情况，返回"0"。

Python代码示例：

from functools import cmp_to_keydef minNumber(nums):    def compare(a, b):        if a + b < b + a:            return -1        elif a + b > b + a:            return 1        return 0    strs = [str(num) for num in nums]    strs.sort(key=cmp_to_key(compare))    result = ''.join(strs)    return '0' if result[0] == '0' else result

题目34：丑数 II

问题描述：给你一个整数 n，请你找出并返回第 n 个丑数。丑数是指只包含质因数 2、3 和 5 的正整数。例如，前几个丑数是 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...。

解题思路：动态规划 + 三指针。维护一个数组 dp，dp[i] 表示第 i+1 个丑数，dp[0] = 1。用三个指针 p2、p3、p5 分别表示下一个丑数应由 2 * dp[p2]、3 * dp[p3]、5 * dp[p5] 中的最小值产生。每次取三者最小值作为下一个丑数，并将对应指针后移。注意去重（若某个乘积等于当前最小值，对应指针也要后移）。

Python代码示例：

def nthUglyNumber(n):    dp = [1] * n    p2 = p3 = p5 = 0    for i in range(1, n):        next_ugly = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)        dp[i] = next_ugly        if dp[p2] * 2 == next_ugly:            p2 += 1        if dp[p3] * 3 == next_ugly:            p3 += 1        if dp[p5] * 5 == next_ugly:            p5 += 1    return dp[n - 1]

题目35：和为 S 的连续正数序列

问题描述：输入一个正整数 target，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

解题思路：滑动窗口（双指针）。用left和right表示当前窗口的左右边界，初始left = 1, right = 2，窗口和cur_sum = 3。当cur_sum < target时，右指针右移并累加；当cur_sum > target时，左指针右移并减去；当cur_sum == target时，记录当前序列，然后左指针右移继续寻找。循环条件left < right且left <= target // 2。

Python代码示例：

def findContinuousSequence(target):    result = []    left, right = 1, 2    cur_sum = 3    while left < right:        if cur_sum == target:            result.append(list(range(left, right + 1)))            cur_sum -= left            left += 1        elif cur_sum < target:            right += 1            cur_sum += right        else:            cur_sum -= left            left += 1    return result

题目36：数组中数字出现的次数 II

问题描述：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。要求时间复杂度 O(n)，空间复杂度 O(1)。

解题思路：位运算。对每个二进制位统计 1 的出现次数，对 3 取模。若某一位的余数为 1，则说明只出现一次的数字在该位上是 1。将所有位的结果组合起来即可。

Python代码示例：

def singleNumber(nums):    result = 0    for i in range(32):        bit_count = sum((num >> i) & 1 for num in nums)        if bit_count % 3 != 0:            result |= (1 << i)    if result >= 2**31:        result -= 2**32    return result

题目37：二进制中 1 的个数

问题描述：编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数。

解题思路：利用位运算技巧 n & (n - 1)，该操作会将 n 的二进制表示中最右边的 1 变为 0。不断执行该操作并计数，直到 n 变为 0。循环次数等于二进制中 1 的个数。

Python代码示例：

def hammingWeight(n):    count = 0    while n:        n &= n - 1        count += 1    return count

题目38：礼物的最大价值

问题描述：在一个 m x n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物价值，请计算你最多能拿到多少价值的礼物。

解题思路：动态规划。设 dp[i][j] 为到达位置 (i, j) 能拿到的最大价值。状态转移：dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])。可用一维数组滚动优化空间。

Python代码示例：

def maxValue(grid):    m, n = len(grid), len(grid[0])    dp = [0] * n    for i in range(m):        for j in range(n):            if j == 0:                dp[j] += grid[i][j]            else:                dp[j] = max(dp[j], dp[j - 1]) + grid[i][j]    return dp[-1]

题目39：剪绳子

问题描述：给你一根长度为n的绳子，请把绳子剪成整数长度的m段（m、n都是整数，n > 1且m > 1），每段绳子的长度记为k[0], k[1], ..., k[m-1]。请问k[0] * k[1] * ... * k[m-1]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

解题思路：数学贪心或动态规划。贪心策略：尽量多剪长度为 3 的段。当 n <= 3 时特殊处理；当余数为 1 时，将 3 + 1 替换为 2 + 2（因为 2 * 2 > 3 * 1）。动态规划：设 dp[i] 为长度为 i 的绳子剪后的最大乘积，dp[i] = max(dp[i], dp[j] * dp[i-j])。

Python代码示例（贪心）：

def cuttingRope(n):    if n <= 3:        return n - 1    quotient, remainder = divmod(n, 3)    if remainder == 0:        return 3 ** quotient    elif remainder == 1:        return 3 ** (quotient - 1) * 4    else:        return 3 ** quotient * 2

题目40：把字符串转换成整数

问题描述：写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 int() 或其他类似的库函数。要求：

• • 忽略前导空格。
• • 检查可选的正负号。
• • 读取数字直到遇到非数字字符。
• • 若结果超出 32 位有符号整数范围 [-2^31, 2^31 - 1]，则截断到边界值。

解题思路：按顺序处理：跳过空格 → 处理符号 → 逐字符读取数字并累加结果。每次累加前判断是否溢出，若溢出则直接返回边界值。

Python代码示例：

def strToInt(s):    i, n = 0, len(s)    while i < n and s[i] == ' ':        i += 1    if i == n:        return 0    sign = 1    if s[i] in '+-':        sign = -1 if s[i] == '-' else 1        i += 1    result = 0    INT_MIN, INT_MAX = -2**31, 2**31 - 1    while i < n and s[i].isdigit():        digit = int(s[i])        if result > (INT_MAX - digit) // 10:            return INT_MAX if sign == 1 else INT_MIN        result = result * 10 + digit        i += 1    return sign * result