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

题目51：最长回文子序列

问题描述：给定一个字符串 s，找到其中最长的回文子序列的长度。子序列是指在不改变剩余字符相对顺序的情况下，删除某些字符后形成的序列。子序列不要求连续。

解题思路：动态规划。设 dp[i][j] 表示 s[i..j] 的最长回文子序列长度。

• • 若 s[i] == s[j]，则 dp[i][j] = dp[i+1][j-1] + 2；
• • 否则 dp[i][j] = max(dp[i+1][j], dp[i][j-1])。初始化 dp[i][i] = 1。从后往前遍历 i，从前往后遍历 j。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
def longestPalindromeSubseq(s):    n = len(s)    dp = [[0] * n for _ in range(n)]    for i in range(n - 1, -1, -1):        dp[i][i] = 1        for j in range(i + 1, n):            if s[i] == s[j]:                dp[i][j] = dp[i + 1][j - 1] + 2            else:                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])    return dp[0][n - 1]

题目52：行星碰撞

问题描述：给定一个整数数组 asteroids，表示在同一行的行星。对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右，负表示向左）。找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞时，较小的行星会爆炸；如果两颗行星大小相同，则两颗都会爆炸。两颗移动方向相同的行星永远不会发生碰撞。

解题思路：使用栈。遍历行星，若栈为空或当前行星为正或栈顶为负（方向相同或远离），则直接入栈。否则发生碰撞：

• • 若栈顶绝对值小于当前行星绝对值，栈顶爆炸，继续比较；
• • 若相等，两者都爆炸，当前行星不入栈；
• • 若栈顶绝对值大于当前行星绝对值，当前行星爆炸，不入栈。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def asteroidCollision(asteroids):    stack = []    for ast in asteroids:        alive = True        while alive and ast < 0 and stack and stack[-1] > 0:            if stack[-1] < -ast:                stack.pop()            elif stack[-1] == -ast:                stack.pop()                alive = False            else:                alive = False        if alive:            stack.append(ast)    return stack

题目53：数组中的逆序对

问题描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

解题思路：归并排序。在合并两个有序子数组时，统计逆序对。当左半部分元素 nums[i] 大于右半部分元素 nums[j] 时，左半部分从 i 到 mid 的所有元素都大于 nums[j]，因此逆序对数量增加 mid - i + 1。递归统计左右子数组的逆序对，再加上合并时的逆序对。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def reversePairs(nums):    def merge_sort(left, right):        if left >= right:            return 0        mid = (left + right) // 2        count = merge_sort(left, mid) + merge_sort(mid + 1, right)        i, j = left, mid + 1        temp = []        while i <= mid and j <= right:            if nums[i] <= nums[j]:                temp.append(nums[i])                i += 1            else:                count += mid - i + 1                temp.append(nums[j])                j += 1        temp.extend(nums[i:mid + 1])        temp.extend(nums[j:right + 1])        nums[left:right + 1] = temp        return count    return merge_sort(0, len(nums) - 1)

题目54：数据流中的第 K 大元素

问题描述：设计一个找到数据流中第 k 大元素的类。注意是排序后的第 k 大元素，不是第 k 个不同的元素。实现 KthLargest 类：

• • KthLargest(int k, int[] nums)：使用整数 k 和整数流 nums 初始化对象。
• • int add(int val)：将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

解题思路：使用最小堆维护前 k 大的元素。堆的大小保持为 k，堆顶即为第 k 大元素。添加新元素时，若堆大小小于 k，直接入堆；否则若新元素大于堆顶，弹出堆顶并压入新元素。最后返回堆顶。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import heapqclass KthLargest:    def __init__(self, k, nums):        self.k = k        self.heap = []        for num in nums:            self.add(num)    def add(self, val):        if len(self.heap) < self.k:            heapq.heappush(self.heap, val)        elif val > self.heap[0]:            heapq.heapreplace(self.heap, val)        return self.heap[0]

题目55：最小高度树

问题描述：树是一个无向图，其中任何两个顶点只通过一条路径连接。给你一棵包含 n 个节点的树，标记为 0 到 n - 1。给定数字 n 和一个有 n - 1 条无向边的 edges 列表，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h。在所有可能的树中，具有最小高度的树被称为最小高度树。请你找到所有的最小高度树并按任意顺序返回它们的根节点标签列表。

解题思路：拓扑排序（剥洋葱法）。从所有度为 1 的节点开始，逐层删除叶子节点，最后剩下的 1 或 2 个节点就是最小高度树的根。因为最小高度树的根一定在树的中心。重复删除所有度为 1 的节点，直到剩余节点数不超过 2。

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
from collections import dequedef findMinHeightTrees(n, edges):    if n == 1:        return [0]    graph = [[] for _ in range(n)]    degree = [0] * n    for u, v in edges:        graph[u].append(v)        graph[v].append(u)        degree[u] += 1        degree[v] += 1    queue = deque([i for i in range(n) if degree[i] == 1])    remaining = n    while remaining > 2:        size = len(queue)        remaining -= size        for _ in range(size):            leaf = queue.popleft()            for neighbor in graph[leaf]:                degree[neighbor] -= 1                if degree[neighbor] == 1:                    queue.append(neighbor)    return list(queue)

题目56：按摩师

问题描述：一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列 nums，表示第 i 个预约的时长，请计算按摩师能够获得的最长总预约时长。

解题思路：动态规划。设 dp[i] 为前 i 个预约能获得的最长总时长。状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。可以用两个变量滚动更新，优化空间。

Python代码示例：

1
2
3
4
5
def massage(nums):    prev, curr = 0, 0    for num in nums:        prev, curr = curr, max(curr, prev + num)    return curr

题目57：判断二分图

问题描述：给定一个无向图 graph，其中 graph[i] 是与节点 i 相邻的所有节点列表。判断这个图是否是一个二分图。二分图定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为二分图。

解题思路：使用 BFS 或 DFS 对图进行染色。将起始节点染成颜色 0，其邻居染成颜色 1，依次交替。若在染色过程中发现相邻节点颜色相同，则不是二分图。需要对所有连通分量进行遍历，因为图可能不连通。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import dequedef isBipartite(graph):    n = len(graph)    color = [-1] * n    for i in range(n):        if color[i] == -1:            color[i] = 0            queue = deque([i])            while queue:                node = queue.popleft()                for neighbor in graph[node]:                    if color[neighbor] == -1:                        color[neighbor] = 1 - color[node]                        queue.append(neighbor)                    elif color[neighbor] == color[node]:                        return False    return True

题目58：字符串的排列

问题描述：给定两个字符串 s1 和 s2，判断 s2 是否包含 s1 的某个排列作为子串。即判断 s1 的任意字母异位词是否是 s2 的子串。

解题思路：使用滑动窗口 + 字符计数。维护一个长度为 len(s1) 的窗口，比较窗口内字符计数与 s1 的字符计数是否一致。可用长度为 26 的数组记录，每次移动窗口时更新计数并比较。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def checkInclusion(s1, s2):    if len(s1) > len(s2):        return False    need = [0] * 26    window = [0] * 26    for ch in s1:        need[ord(ch) - ord('a')] += 1    for i, ch in enumerate(s2):        window[ord(ch) - ord('a')] += 1        if i >= len(s1):            window[ord(s2[i - len(s1)]) - ord('a')] -= 1        if window == need:            return True    return False

题目59：二叉树的右视图

问题描述：给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解题思路：使用 BFS 层序遍历。每层最后一个节点即为从右侧能看到的节点。将每层最后一个节点的值加入结果列表。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import dequedef rightSideView(root):    if not root:        return []    result = []    queue = deque([root])    while queue:        size = len(queue)        for i in range(size):            node = queue.popleft()            if i == size - 1:                result.append(node.val)            if node.left:                queue.append(node.left)            if node.right:                queue.append(node.right)    return result

题目60：最大正方形

问题描述：在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '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
def maximalSquare(matrix):    if not matrix:        return 0    m, n = len(matrix), len(matrix[0])    dp = [[0] * (n + 1) for _ in range(m + 1)]    max_side = 0    for i in range(1, m + 1):        for j in range(1, n + 1):            if matrix[i - 1][j - 1] == '1':                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1                max_side = max(max_side, dp[i][j])    return max_side * max_side