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

题目91：全排列 II

问题描述：给定一个可包含重复数字的序列 nums，按任意顺序返回所有不重复的全排列。

示例：

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

解题思路：使用回溯法 + 剪枝。先将数组排序，使相同元素相邻。在回溯过程中，用 used 数组标记元素是否已被使用。对于重复元素，如果前一个相同元素未被使用，则跳过当前元素，避免产生重复排列。时间复杂度 O(n * 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
def permuteUnique(nums):    nums.sort()    result = []    path = []    used = [False] * len(nums)    def backtrack():        if len(path) == len(nums):            result.append(path[:])            return        for i in range(len(nums)):            if used[i]:                continue            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:                continue            used[i] = True            path.append(nums[i])            backtrack()            path.pop()            used[i] = False    backtrack()    return result

题目92：N 皇后

问题描述：按照国际象棋的规则，皇后可以攻击与之处在同一行、同一列或同一斜线上的棋子。n 皇后问题研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例：

• • 输入：n = 4
• • 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
• • 解释：4 皇后问题存在两个不同的解法。

解题思路：使用回溯法逐行放置皇后。维护三个集合分别记录已占用的列、主对角线（row - col）和副对角线（row + col）。对于每一行，尝试在每个列放置皇后，如果该列和两条对角线都未被占用，则放置并递归下一行。当放置完 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
def solveNQueens(n):    result = []    cols = set()    diag1 = set()    diag2 = set()    board = [['.'] * n for _ in range(n)]    def backtrack(row):        if row == n:            result.append([''.join(r) for r in board])            return        for col in range(n):            if col in cols or (row - col) in diag1 or (row + col) in diag2:                continue            cols.add(col)            diag1.add(row - col)            diag2.add(row + col)            board[row][col] = 'Q'            backtrack(row + 1)            board[row][col] = '.'            cols.remove(col)            diag1.remove(row - col)            diag2.remove(row + col)    backtrack(0)    return result

题目93：解数独

问题描述：编写一个程序，通过填充空格来解决数独问题。数独的解法需遵循如下规则：

1. 1. 数字 1-9 在每一行只能出现一次；
2. 2. 数字 1-9 在每一列只能出现一次；
3. 3. 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例：

• • 输入：

1
2
3
4
5
6
7
8
9
10
11
board = [  ["5","3",".",".","7",".",".",".","."],  ["6",".",".","1","9","5",".",".","."],  [".","9","8",".",".",".",".","6","."],  ["8",".",".",".","6",".",".",".","3"],  ["4",".",".","8",".","3",".",".","1"],  ["7",".",".",".","2",".",".",".","6"],  [".","6",".",".",".",".","2","8","."],  [".",".",".","4","1","9",".",".","5"],  [".",".",".",".","8",".",".","7","9"]]

• • 输出：填充后的数独棋盘。

解题思路：使用回溯法。维护三个二维数组 rows、cols、boxes，分别记录每行、每列、每个 3×3 宫内已出现的数字。遍历棋盘，找到空白格，尝试填入 1-9 中的数字，如果该数字在行、列、宫中都未出现，则填入并递归。如果递归失败，则回溯，恢复空白格。时间复杂度 O(9^(n))，空间复杂度 O(1)（棋盘固定大小）。

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
35
36
37
def solveSudoku(board):    rows = [set() for _ in range(9)]    cols = [set() for _ in range(9)]    boxes = [set() for _ in range(9)]    for i in range(9):        for j in range(9):            num = board[i][j]            if num != '.':                rows[i].add(num)                cols[j].add(num)                boxes[(i // 3) * 3 + j // 3].add(num)    def backtrack():        for i in range(9):            for j in range(9):                if board[i][j] == '.':                    box_index = (i // 3) * 3 + j // 3                    for num in map(str, range(1, 10)):                        if num not in rows[i] and num not in cols[j] and num not in boxes[box_index]:                            board[i][j] = num                            rows[i].add(num)                            cols[j].add(num)                            boxes[box_index].add(num)                            if backtrack():                                return True                            board[i][j] = '.'                            rows[i].remove(num)                            cols[j].remove(num)                            boxes[box_index].remove(num)                    return False        return True    backtrack()

题目94：不同路径 III

问题描述：在二维网格 grid 上，有 4 种类型的方格：

• • 1 表示起始方格。且只有一个起始方格。
• • 2 表示结束方格，且只有一个结束方格。
• • 0 表示我们可以走过的空方格。
• • -1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

示例：

• • 输入：grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
• • 输出：2
• • 输入：grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
• • 输出：4

解题思路：使用深度优先搜索（DFS） + 回溯。先统计网格中所有非障碍方格的数量 total，以及起始位置。从起始位置开始 DFS，记录已访问的方格数 visited。当到达结束方格时，如果 visited == total，说明经过所有非障碍方格，路径数加一。否则继续向四个方向搜索，遇到未访问且非障碍的方格则递归。时间复杂度 O(4^(mn))，空间复杂度 O(mn)。

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
35
def uniquePathsIII(grid):    m, n = len(grid), len(grid[0])    start = None    total = 0    for i in range(m):        for j in range(n):            if grid[i][j] != -1:                total += 1            if grid[i][j] == 1:                start = (i, j)    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]    result = 0    def dfs(i, j, visited):        nonlocal result        if grid[i][j] == 2:            if visited == total:                result += 1            return        for di, dj in directions:            ni, nj = i + di, j + dj            if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] != -1:                if grid[ni][nj] == 0 or grid[ni][nj] == 2:                    if (ni, nj) not in visited_cells:                        visited_cells.add((ni, nj))                        dfs(ni, nj, visited + 1)                        visited_cells.remove((ni, nj))    visited_cells = {start}    dfs(start[0], start[1], 1)    return result

题目95：火柴拼正方形

问题描述：你将得到一个整数数组 matchsticks，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用所有的火柴棍拼成一个正方形。你不能折断任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须使用一次。如果你能使这个正方形，则返回 true，否则返回 false。

示例：

• • 输入：matchsticks = [1,1,2,2,2]
• • 输出：true
• • 解释：能拼成一个边长为 2 的正方形，每边两根火柴。
• • 输入：matchsticks = [3,3,3,3,4]
• • 输出：false
• • 解释：不能用所有火柴拼成一个正方形。

解题思路：先计算所有火柴的总长度 total，如果 total % 4 != 0，直接返回 False。目标边长 target = total // 4，如果最大火柴长度大于 target，也返回 False。将火柴按长度降序排序，便于剪枝。使用回溯法，维护一个长度为 4 的数组 sides，表示四条边当前的长度。尝试将每根火柴放入某条边，如果放入后不超过 target，则递归处理下一根火柴。如果所有火柴都放置完毕且四条边都等于 target，返回 True。时间复杂度 O(4^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 makesquare(matchsticks):    total = sum(matchsticks)    if total % 4 != 0:        return False    target = total // 4    matchsticks.sort(reverse=True)    if matchsticks[0] > target:        return False    sides = [0] * 4    def backtrack(index):        if index == len(matchsticks):            return all(side == target for side in sides)        for i in range(4):            if sides[i] + matchsticks[index] <= target:                sides[i] += matchsticks[index]                if backtrack(index + 1):                    return True                sides[i] -= matchsticks[index]            if sides[i] == 0:                break        return False    return backtrack(0)

题目96：课程表 II

问题描述：现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites，其中 prerequisites[i] = [ai, bi]，表示在选修课程 ai 前 必须 先选修 bi。返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回一个空数组。

示例：

• • 输入：numCourses = 2, prerequisites = [[1,0]]
• • 输出：[0,1]
• • 解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1]。
• • 输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
• • 输出：[0,2,1,3]（或 [0,1,2,3]）

解题思路：使用拓扑排序（BFS）。统计每个节点的入度，将入度为 0 的节点加入队列。不断从队列中取出节点，加入拓扑序列，并将其邻居的入度减 1；若邻居入度变为 0，则加入队列。如果最终拓扑序列长度等于课程数，返回该序列；否则返回空数组，表示有环。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import dequedef findOrder(numCourses, prerequisites):    graph = [[] for _ in range(numCourses)]    indegree = [0] * numCourses    for course, prereq in prerequisites:        graph[prereq].append(course)        indegree[course] += 1    queue = deque([i for i in range(numCourses) if indegree[i] == 0])    order = []    while queue:        node = queue.popleft()        order.append(node)        for neighbor in graph[node]:            indegree[neighbor] -= 1            if indegree[neighbor] == 0:                queue.append(neighbor)    return order if len(order) == numCourses else []

题目97：最小高度树

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

示例：

• • 输入：n = 4, edges = [[1,0],[1,2],[1,3]]
• • 输出：[1]
• • 解释：选择节点 1 作为根节点时，树的高度为 1，这是唯一的最小高度树。
• • 输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
• • 输出：[3,4]

解题思路：使用拓扑排序（逐层剥离叶子节点）。将所有度数为 1 的节点加入队列。每次处理当前层的所有叶子节点，将它们从图中移除，并更新相邻节点的度数。当剩余节点数不超过 2 时，队列中剩余的节点就是最小高度树的根节点。时间复杂度 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
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    leaves = deque([i for i in range(n) if degree[i] == 1])    remaining = n    while remaining > 2:        size = len(leaves)        remaining -= size        for _ in range(size):            leaf = leaves.popleft()            for neighbor in graph[leaf]:                degree[neighbor] -= 1                if degree[neighbor] == 1:                    leaves.append(neighbor)    return list(leaves)

题目98：最大矩形

问题描述：给定一个仅包含 0 和 1、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例：

• • 输入：

1
2
3
4
5
6
matrix = [  ["1","0","1","0","0"],  ["1","0","1","1","1"],  ["1","1","1","1","1"],  ["1","0","0","1","0"]]

• • 输出：6
• • 解释：最大矩形如上图所示。

解题思路：将问题转化为多个“柱状图中最大的矩形”问题。逐行遍历矩阵，维护一个高度数组 heights：如果当前元素为 '1'，则 heights[j] += 1；否则 heights[j] = 0。对每一行的高度数组，使用单调栈计算最大矩形面积。时间复杂度 O(rows * cols)，空间复杂度 O(cols)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def maximalRectangle(matrix):    if not matrix or not matrix[0]:        return 0    cols = len(matrix[0])    heights = [0] * (cols + 1)    max_area = 0    for row in matrix:        for j in range(cols):            heights[j] = heights[j] + 1 if row[j] == '1' else 0        stack = []        for i in range(cols + 1):            while stack and heights[stack[-1]] > heights[i]:                h = heights[stack.pop()]                w = i - stack[-1] - 1                max_area = max(max_area, h * w)            stack.append(i)    return max_area

题目99：单词拆分 II

问题描述：给定一个字符串 s 和一个字符串字典 wordDict，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序返回所有这些可能的句子。注意： 词典中的同一个单词可以在拼接中多次使用。

示例：

• • 输入：s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
• • 输出：["cats and dog","cat sand dog"]
• • 输入：s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
• • 输出：["pine apple pen apple","pineapple pen apple","pine applepen apple"]

解题思路：使用回溯 + 记忆化。对于字符串 s 的每个起始位置，尝试所有可能的结束位置，如果子串在字典中，则递归处理剩余部分。用哈希表 memo 记录从某个位置开始能构成的所有句子，避免重复计算。如果从位置 0 开始没有结果，返回空列表。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def wordBreak(s, wordDict):    word_set = set(wordDict)    memo = {}    def dfs(start):        if start in memo:            return memo[start]        if start == len(s):            return [""]        result = []        for end in range(start + 1, len(s) + 1):            word = s[start:end]            if word in word_set:                for suffix in dfs(end):                    result.append(word + (" " + suffix if suffix else ""))        memo[start] = result        return result    return dfs(0)

题目100：设计推特

问题描述：设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近 10 条推文。实现 Twitter 类：

• • Twitter() 初始化简易版推特对象。
• • void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId。
• • List<Integer> getNewsFeed(int userId) 检索当前用户新闻推送中最近 10 条推文的 ID。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须按照时间顺序由最近到最远排序。
• • void follow(int followerId, int followeeId) ID 为 followerId 的用户关注 ID 为 followeeId 的用户。
• • void unfollow(int followerId, int followeeId) ID 为 followerId 的用户取消关注 ID 为 followeeId 的用户。

示例：

• • 输入：

1
2
["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"][[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]

• • 输出：[null, null, [5], null, null, [6,5], null, [5]]

解题思路：使用全局时间戳记录推文发布顺序。每个用户维护一个推文列表 tweets（存储 (time, tweetId)），以及一个关注集合 followees（包括自己）。getNewsFeed 时，从该用户关注的所有用户中收集最近的推文，使用最大堆按时间戳排序，取出前 10 条。关注和取消关注直接操作集合。时间复杂度：getNewsFeed 为 O(F log F + 10 log F)，其中 F 为关注人数。

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
import heapqfrom collections import defaultdictclass Twitter:    def __init__(self):        self.time = 0        self.tweets = defaultdict(list)  # userId -> [(time, tweetId)]        self.followees = defaultdict(set)    def postTweet(self, userId, tweetId):        self.time += 1        self.tweets[userId].append((self.time, tweetId))    def getNewsFeed(self, userId):        users = self.followees[userId] | {userId}        heap = []        for uid in users:            for tweet in self.tweets[uid][-10:]:                heapq.heappush(heap, tweet)                if len(heap) > 10:                    heapq.heappop(heap)        return [tweetId for _, tweetId in sorted(heap, reverse=True)]    def follow(self, followerId, followeeId):        if followerId != followeeId:            self.followees[followerId].add(followeeId)    def unfollow(self, followerId, followeeId):        self.followees[followerId].discard(followeeId)