网络安全技术练习题大全(28)

题目71：旋转链表

问题描述：给你一个链表的头节点 head，旋转链表，将链表每个节点向右移动 k 个位置。

示例：

• • 输入：head = [1,2,3,4,5], k = 2
• • 输出：[4,5,1,2,3]
• • 解释：向右旋转 1 步：[5,1,2,3,4]，向右旋转 2 步：[4,5,1,2,3]
• • 输入：head = [0,1,2], k = 4
• • 输出：[2,0,1]

解题思路：

1. 1. 计算链表长度 n，并将链表首尾相连形成环。
2. 2. 由于向右移动 k 个位置等价于将倒数第 k % n 个节点作为新的头节点，所以实际需要移动 k % n 步。
3. 3. 找到新的尾节点：从原头节点出发，走 n - (k % n) - 1 步到达新尾节点。
4. 4. 新头节点为新尾节点的下一个节点，断开环即可。

时间复杂度 O(n)，空间复杂度 O(1)。

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

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 rotateRight(head, k):    if not head or not head.next or k == 0:        return head    # 计算链表长度，并找到尾节点    n = 1    tail = head    while tail.next:        tail = tail.next        n += 1    # 形成环    tail.next = head    # 计算实际移动步数    k = k % n    if k == 0:        tail.next = None        return head    # 找到新的尾节点：从 head 走 n - k - 1 步    new_tail = head    for _ in range(n - k - 1):        new_tail = new_tail.next    new_head = new_tail.next    new_tail.next = None    return new_head

题目72：路径总和 II

问题描述：给你二叉树的根节点 root 和一个整数目标和 targetSum，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。叶子节点是指没有子节点的节点。

示例：

• • 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
• • 输出：[[5,4,11,2],[5,8,4,5]]

解题思路：使用深度优先搜索（DFS） + 回溯。从根节点开始遍历，维护当前路径 path 和当前路径和 current_sum。当到达叶子节点时，如果 current_sum == targetSum，则将当前路径加入结果集。递归遍历左右子树，回溯时移除当前节点。

时间复杂度 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
def pathSum(root, targetSum):    result = []    path = []    def dfs(node, current_sum):        if not node:            return        path.append(node.val)        current_sum += node.val        if not node.left and not node.right and current_sum == targetSum:            result.append(path[:])        dfs(node.left, current_sum)        dfs(node.right, current_sum)        path.pop()    dfs(root, 0)    return result

题目73：一和零

问题描述：给你一个二进制字符串数组 strs 和两个整数 m 和 n。请你找出并返回 strs 的最大子集的大小，该子集中最多有 m 个 0 和 n 个 1。如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例：

• • 输入：strs = ["10","0001","111001","1","0"], m = 5, n = 3
• • 输出：4
• • 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"}，因此答案是 4。
• • 输入：strs = ["10","0","1"], m = 1, n = 1
• • 输出：2

解题思路：这是一个二维 0-1 背包问题。定义 dp[i][j] 为最多有 i 个 0 和 j 个 1 时能选出的最大子集大小。对于每个字符串，统计其 0 和 1 的个数 zeros 和 ones。然后从后向前遍历 i 从 m 到 zeros，j 从 n 到 ones，更新 dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)。最终返回 dp[m][n]。

时间复杂度 O(len(strs) * m * n)，空间复杂度 O(m * n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def findMaxForm(strs, m, n):    dp = [[0] * (n + 1) for _ in range(m + 1)]    for s in strs:        zeros = s.count('0')        ones = len(s) - zeros        for i in range(m, zeros - 1, -1):            for j in range(n, ones - 1, -1):                dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)    return dp[m][n]

题目74：翻转字符串里的单词

问题描述：给你一个字符串 s，请你反转字符串中单词的顺序。单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例：

• • 输入：s = "the sky is blue"，输出："blue is sky the"
• • 输入：s = "  hello world  "，输出："world hello"
• • 输入：s = "a good   example"，输出："example good a"

解题思路：方法一：使用 split() 分割字符串（默认按空白字符分割并忽略空字符串），然后反转列表，最后用单个空格连接。方法二：原地反转（如果要求 O(1) 空间），但 Python 中字符串不可变，通常用方法一即可。时间复杂度 O(n)，空间复杂度 O(n)。

Python代码示例：

1
2
3
def reverseWords(s):    words = s.split()    return ' '.join(reversed(words))

题目75：盛最多水的容器

问题描述：给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。

示例：

• • 输入：height = [1,8,6,2,5,4,8,3,7]
• • 输出：49
• • 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
• • 输入：height = [1,1]，输出：1

解题思路：使用双指针。左指针 left 指向数组开头，右指针 right 指向数组末尾。容器的水量由 min(height[left], height[right]) * (right - left) 决定。每次移动高度较小的一侧的指针，因为如果移动高度较大的一侧，宽度减小，而高度不会增加，水量不可能增大。遍历过程中记录最大水量。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def maxArea(height):    left, right = 0, len(height) - 1    max_water = 0    while left < right:        h = min(height[left], height[right])        w = right - left        max_water = max(max_water, h * w)        if height[left] < height[right]:            left += 1        else:            right -= 1    return max_water

题目76：合并两个有序链表

问题描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

• • 输入：l1 = [1,2,4], l2 = [1,3,4]
• • 输出：[1,1,2,3,4,4]
• • 输入：l1 = [], l2 = []
• • 输出：[]
• • 输入：l1 = [], l2 = [0]
• • 输出：[0]

解题思路：使用哑节点 dummy 作为新链表的头，维护一个指针 curr。同时遍历两个链表，每次比较当前节点的值，将较小者接到 curr.next，并移动对应链表的指针。当其中一个链表遍历完后，将另一个链表剩余部分直接接到末尾。时间复杂度 O(m + n)，空间复杂度 O(1)。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def mergeTwoLists(l1, l2):    dummy = ListNode(0)    curr = dummy    while l1 and l2:        if l1.val <= l2.val:            curr.next = l1            l1 = l1.next        else:            curr.next = l2            l2 = l2.next        curr = curr.next    curr.next = l1 if l1 else l2    return dummy.next

题目77：爬楼梯

问题描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例：

• • 输入：n = 2，输出：2
• • 解释：有两种方法可以爬到楼顶。1 阶 + 1 阶，2 阶。
• • 输入：n = 3，输出：3
• • 解释：有三种方法可以爬到楼顶。1 阶 + 1 阶 + 1 阶，1 阶 + 2 阶，2 阶 + 1 阶。

解题思路：动态规划。第 n 阶的方法数等于第 n-1 阶和第 n-2 阶方法数之和。可以用两个变量滚动更新，优化空间。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
def climbStairs(n):    if n <= 2:        return n    first, second = 1, 2    for _ in range(3, n + 1):        first, second = second, first + second    return second

题目78：买卖股票的最佳时机

问题描述：给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出。设计一个算法来计算你所能获取的最大利润。如果你不能获取任何利润，返回 0。

示例：

• • 输入：prices = [7,1,5,3,6,4]，输出：5
• • 解释：在第 2 天（价格 = 1）买入，在第 5 天（价格 = 6）卖出，最大利润 = 6 - 1 = 5。
• • 输入：prices = [7,6,4,3,1]，输出：0
• • 解释：在这种情况下，没有交易完成，所以最大利润为 0。

解题思路：一次遍历。维护当前最小价格 min_price 和最大利润 max_profit。每天计算如果今天卖出能获得的利润，并更新最大利润。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
def maxProfit(prices):    min_price = float('inf')    max_profit = 0    for price in prices:        min_price = min(min_price, price)        max_profit = max(max_profit, price - min_price)    return max_profit

题目79：二叉树的最大深度

问题描述：给定一个二叉树 root，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明：叶子节点是指没有子节点的节点。

示例：

• • 输入：root = [3,9,20,null,null,15,7]
• • 输出：3

解题思路：递归。当前节点的最大深度等于左右子树最大深度的较大值加 1。也可以使用层序遍历（BFS）逐层计数。时间复杂度 O(n)，空间复杂度 O(h)（递归栈深度）。

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

1
2
3
4
5
6
7
8
def maxDepth(root):    if not root:        return 0    left_depth = maxDepth(root.left)    right_depth = maxDepth(root.right)    return max(left_depth, right_depth) + 1

题目80：环形链表

问题描述：给你一个链表的头节点 head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos = -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true；否则，返回 false。

示例：

• • 输入：head = [3,2,0,-4], pos = 1，输出：true
• • 解释：链表中有一个环，其尾部连接到第二个节点。
• • 输入：head = [1,2], pos = 0，输出：true
• • 输入：head = [1], pos = -1，输出：false

解题思路：使用快慢指针。慢指针每次走一步，快指针每次走两步。如果存在环，快慢指针最终会相遇；如果快指针走到 None，则无环。时间复杂度 O(n)，空间复杂度 O(1)。

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

1
2
3
4
5
6
7
8
9
10
def hasCycle(head):    slow = fast = head    while fast and fast.next:        slow = slow.next        fast = fast.next.next        if slow == fast:            return True    return False