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

题目51：有效的正方形

问题描述：给定2D空间中四个点的坐标 p1, p2, p3 和 p4，如果这四个点构成一个正方形，则返回 true。点的坐标 pi 表示为 [xi, yi]。输入不是按任何顺序排列。一个有效的正方形有四条等边和四个等角（90度角）。

示例：

• • 输入：p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]，输出：true
• • 输入：p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]，输出：false
• • 输入：p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]，输出：true

解题思路：一个正方形的四个点两两之间共有 C(4,2) = 6 条边。计算这 6 条边长的平方，排序后应该满足：最小的 4 条边相等（4 条边），最大的 2 条边相等（2 条对角线），且 对角线长度平方 = 2 × 边长平方。此外，需要排除四个点重合等退化情况。时间复杂度 O(1)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def validSquare(p1, p2, p3, p4):    points = [p1, p2, p3, p4]    def dist_sq(a, b):        return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2    distances = []    for i in range(4):        for j in range(i + 1, 4):            distances.append(dist_sq(points[i], points[j]))    distances.sort()    # 边长不能为 0    if distances[0] == 0:        return False    # 4 条边相等，2 条对角线相等，且对角线是边长的 2 倍    return (distances[0] == distances[1] == distances[2] == distances[3]            and distances[4] == distances[5]            and distances[4] == 2 * distances[0])

题目52：学生出勤记录 II

问题描述：可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

• • 'A'：Absent，缺勤
• • 'L'：Late，迟到
• • 'P'：Present，到场

如果学生能够同时满足下面两个条件，则可以获得出勤奖励：

• • 按总出勤计，学生缺勤（'A'）严格少于两天。
• • 学生不会存在连续 3 天或 3 天以上的迟到（'L'）记录。

给你一个整数 n，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况数量。答案可能很大，所以返回对 10^9 + 7 取余的结果。

示例：

• • 输入：n = 1，输出：3（有 3 种可能：P、L、A）
• • 输入：n = 2，输出：8（有 8 种长度为 2 的记录，其中 1 种记录 AA 无法获得奖励）
• • 输入：n = 10101，输出：183236316

解题思路：动态规划。状态由三个维度决定：当前天数 i、缺勤次数 a（0 或 1）、末尾连续迟到次数 l（0、1、2）。定义 dp[i][a][l] 为长度为 i、缺勤 a 次、末尾连续迟到 l 次的合法记录数。状态转移时分别枚举今天为 'P'、'L'、'A'：

• • 若为 'P'，则 a 不变，l 归 0；
• • 若为 'L'，则 a 不变，l + 1（且 l + 1 < 3）；
• • 若为 'A'，则 a + 1（且 a + 1 < 2），l 归 0。最终答案为所有合法状态的累加。时间复杂度 O(n × 2 × 3)，空间复杂度 O(2 × 3)（滚动数组）。

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
31
32
33
34
def checkRecord(n):    MOD = 10**9 + 7    # dp[a][l]：a 为缺勤次数（0 或 1），l 为末尾连续迟到次数（0, 1, 2）    dp = [[0] * 3 for _ in range(2)]    dp[0][0] = 1    for _ in range(n):        new_dp = [[0] * 3 for _ in range(2)]        for a in range(2):            for l in range(3):                if dp[a][l] == 0:                    continue                # 今天 'P'                new_dp[a][0] = (new_dp[a][0] + dp[a][l]) % MOD                # 今天 'L'                if l < 2:                    new_dp[a][l + 1] = (new_dp[a][l + 1] + dp[a][l]) % MOD                # 今天 'A'                if a == 0:                    new_dp[1][0] = (new_dp[1][0] + dp[a][l]) % MOD        dp = new_dp    total = 0    for a in range(2):        for l in range(3):            total = (total + dp[a][l]) % MOD    return total

题目53：最小时间差

问题描述：给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

示例：

• • 输入：timePoints = ["23:59","00:00"]，输出：1
• • 输入：timePoints = ["00:00","23:59","00:00"]，输出：0

解题思路：将每个时间转换为从 0 点开始的分钟数，得到数组 minutes。先将 minutes 排序，然后计算相邻两个时间的差。特别地，首尾时间也需要比较，因为一天是循环的：(minutes[0] + 1440) - minutes[-1]。最小差值即为答案。时间复杂度 O(n log n)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def findMinDifference(timePoints):    minutes = []    for t in timePoints:        h, m = map(int, t.split(':'))        minutes.append(h * 60 + m)    minutes.sort()    min_diff = float('inf')    n = len(minutes)    for i in range(1, n):        min_diff = min(min_diff, minutes[i] - minutes[i - 1])    # 首尾时间差（跨天）    min_diff = min(min_diff, minutes[0] + 1440 - minutes[-1])    return min_diff

题目54：我的日程安排表 I

问题描述：实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会导致三重预订时，则可以存储这个新的日程安排。当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end)，实数 x 的范围为，start <= x < end。实现 MyCalendar 类：

• • MyCalendar() 初始化日历对象。
• • boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

示例：

• • 输入：

1
2
["MyCalendar", "book", "book", "book"][[], [10, 20], [15, 25], [20, 30]]

• • 输出：[null, true, true, false]

解题思路：使用列表存储所有已预订的日程。每次 book 时，遍历已有日程，统计与新区间 [start, end) 有重叠的次数。如果重叠次数达到 2，说明加入新区间会导致三重预订，返回 false。否则将新区间加入列表并返回 true。重叠判断条件：max(start1, start2) < min(end1, end2)。时间复杂度 O(n) 每次操作，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MyCalendar:    def __init__(self):        self.calendar = []    def book(self, start, end):        overlap_count = 0        for s, e in self.calendar:            if max(start, s) < min(end, e):                overlap_count += 1                if overlap_count >= 2:                    return False        self.calendar.append((start, end))        return True

题目55：最大人工岛

问题描述：给你一个大小为 n x n 二进制矩阵 grid。最多只能将一格 0 变成 1。进行此操作后，网格上最大的岛屿面积是多少？岛屿由一组在四个方向上相邻的 1 构成。返回执行操作后最大的岛屿面积。如果网格上没有岛屿，返回 1。

示例：

• • 输入：grid = [[1, 0], [0, 1]]，输出：3
• • 解释：将一格 0 变成 1，最终岛屿面积为 3。
• • 输入：grid = [[1, 1], [1, 0]]，输出：4
• • 输入：grid = [[1, 1], [1, 1]]，输出：4

解题思路：先对每个岛屿进行编号（从 2 开始），并统计每个岛屿的面积，存入哈希表。然后遍历每个 0 格子，统计它上下左右相邻的不同岛屿面积之和再加上 1（将自身变为陆地）。记录这个过程中的最大值。如果整个网格都是陆地，直接返回 n * n。时间复杂度 O(n²)，空间复杂度 O(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
31
32
33
34
def largestIsland(grid):    n = len(grid)    island_id = 2    island_area = {}    def dfs(r, c, idx):        if r < 0 or r >= n or c < 0 or c >= n or grid[r][c] != 1:            return 0        grid[r][c] = idx        return 1 + dfs(r + 1, c, idx) + dfs(r - 1, c, idx) + dfs(r, c + 1, idx) + dfs(r, c - 1, idx)    for r in range(n):        for c in range(n):            if grid[r][c] == 1:                island_area[island_id] = dfs(r, c, island_id)                island_id += 1    if not island_area:        return 1    max_area = max(island_area.values())    for r in range(n):        for c in range(n):            if grid[r][c] == 0:                neighbors = set()                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):                    nr, nc = r + dr, c + dc                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] >= 2:                        neighbors.add(grid[nr][nc])                area = 1 + sum(island_area[idx] for idx in neighbors)                max_area = max(max_area, area)    return max_area

题目56：二叉树的前序遍历（迭代实现）

问题描述：给你二叉树的根节点 root，返回它节点值的前序遍历结果。要求使用迭代方式实现，而不是递归。

示例：

• • 输入：root = [1,null,2,3]
• • 输出：[1,2,3]
• • 输入：root = []
• • 输出：[]
• • 输入：root = [1]
• • 输出：[1]

解题思路：前序遍历顺序为：根节点 → 左子树 → 右子树。使用栈模拟递归。先将根节点入栈，然后循环执行：

• • 弹出栈顶节点，访问其值；
• • 由于栈是后进先出，先将右子节点入栈，再将左子节点入栈，这样左子节点会先被处理。时间复杂度 O(n)，空间复杂度 O(h)（栈的最大深度）。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def preorderTraversal(root):    if not root:        return []    result = []    stack = [root]    while stack:        node = stack.pop()        result.append(node.val)        if node.right:            stack.append(node.right)        if node.left:            stack.append(node.left)    return result

题目57：二叉树的垂序遍历

问题描述：给你二叉树的根节点 root，请你设计算法计算二叉树的垂序遍历序列。对位于 (row, col) 的每个节点，其左子节点位于 (row + 1, col - 1)，右子节点位于 (row + 1, col + 1)。树的根节点位于 (0, 0)。垂序遍历从最左边的列开始直到最右边的列结束，按列索引顺序，对每一列内的节点按行索引排序。如果有多个节点在同一行和同一列，则按节点值排序。返回按上述规则排序后的节点值列表。

示例：

• • 输入：root = [3,9,20,null,null,15,7]
• • 输出：[[9],[3,15],[20],[7]]
• • 解释：
• • 列 -1：只有节点 9
• • 列 0：节点 3 和 15，按行排序为 [3,15]
• • 列 1：只有节点 20
• • 列 2：只有节点 7

解题思路：使用 DFS 遍历整棵树，记录每个节点的 (col, row, val)。将所有节点按 col 升序、row 升序、val 升序排序。然后按 col 分组，每组内的节点值组成一个列表。时间复杂度 O(n log 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
def verticalTraversal(root):    nodes = []    def dfs(node, row, col):        if not node:            return        nodes.append((col, row, node.val))        dfs(node.left, row + 1, col - 1)        dfs(node.right, row + 1, col + 1)    dfs(root, 0, 0)    nodes.sort(key=lambda x: (x[0], x[1], x[2]))    result = []    prev_col = None    for col, row, val in nodes:        if col != prev_col:            result.append([])            prev_col = col        result[-1].append(val)    return result

题目58：课程表 III

问题描述：这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会持续上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。返回你最多可以修读的课程数目。

示例：

• • 输入：courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
• • 输出：3
• • 解释：可以修读前三门课程。
• • 输入：courses = [[1,2]]，输出：1
• • 输入：courses = [[3,2],[4,3]]，输出：0

解题思路：贪心 + 优先队列（最大堆）。先按课程的截止时间 lastDay 升序排序。维护当前已选课程的总时长 total_time 和一个最大堆存储已选课程的时长。遍历课程：将当前课程加入总时长和堆中；如果总时长超过当前课程的截止时间，则从堆中弹出时长最大的课程，并减少总时长。最终堆的大小即为最多可修读的课程数目。时间复杂度 O(n log n)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import heapqdef scheduleCourse(courses):    courses.sort(key=lambda x: x[1])    max_heap = []    total_time = 0    for duration, last_day in courses:        total_time += duration        heapq.heappush(max_heap, -duration)        if total_time > last_day:            total_time += heapq.heappop(max_heap)  # 弹出最大时长（负数）    return len(max_heap)

题目59：找到所有可能的路径

问题描述：给你一个有 n 个节点的有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）。二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点（译者注：有向图是有方向的，即规定了 a → b 你就不能从 b → a）。空就是没有下一个节点了。

示例：

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

解题思路：使用深度优先搜索（DFS） + 回溯。从节点 0 开始，将当前节点加入路径 path。如果当前节点是 n-1，则将当前路径的副本加入结果集。否则遍历当前节点的所有邻居，递归搜索。回溯时从 path 中移除当前节点。时间复杂度 O(2^n × n)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def allPathsSourceTarget(graph):    n = len(graph)    result = []    path = []    def dfs(node):        path.append(node)        if node == n - 1:            result.append(path[:])        else:            for neighbor in graph[node]:                dfs(neighbor)        path.pop()    dfs(0)    return result

题目60：最大整除子集

问题描述：给你一个由无重复正整数组成的数组 nums，请你找出并返回其中最大的整除子集 answer，子集中每一元素对 (answer[i], answer[j]) 都应当满足：

• • answer[i] % answer[j] == 0，或
• • answer[j] % answer[i] == 0

如果存在多个有效解子集，返回其中任何一个均可。

示例：

• • 输入：nums = [1,2,3]
• • 输出：[1,2]
• • 解释：[1,2] 是最大整除子集。
• • 输入：nums = [1,2,4,8]
• • 输出：[1,2,4,8]
• • 解释：[1,2,4,8] 是最大整除子集。

解题思路：先对数组排序。定义 dp[i] 为以 nums[i] 结尾的最大整除子集的长度。状态转移：对于每个 i，遍历 j < i，如果 nums[i] % nums[j] == 0，则 dp[i] = max(dp[i], dp[j] + 1)。同时记录每个状态的前一个节点下标，方便最后回溯构造子集。最后找到 dp 中的最大值及其对应下标，回溯得到结果。时间复杂度 O(n²)，空间复杂度 O(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 largestDivisibleSubset(nums):    if not nums:        return []    nums.sort()    n = len(nums)    dp = [1] * n    prev = [-1] * n    max_len = 1    max_index = 0    for i in range(1, n):        for j in range(i):            if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:                dp[i] = dp[j] + 1                prev[i] = j        if dp[i] > max_len:            max_len = dp[i]            max_index = i    result = []    index = max_index    while index != -1:        result.append(nums[index])        index = prev[index]    return result[::-1]