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

题目31：找到最终的安全状态

问题描述：有一个有n个节点的有向图，节点按0到n - 1编号。图由一个下标从0开始的二维整数数组graph表示，其中graph[i]是与节点i相邻的节点列表。如果一个节点没有连出的有向边，则它是终端节点。如果从该节点开始的所有可能路径都通向终端节点，则该节点为安全节点。返回一个由图中所有安全节点组成的数组作为答案。答案数组中的元素应当按升序排列。

示例：

• • 输入：graph = [[1,2],[2,3],[5],[0],[5],[]]
• • 输出：[2,4,5,6]
• • 解释：节点 5 是终端节点。节点 2 可以到 5，所以是安全节点；节点 4 也可以到 5，所以是安全节点。
• • 输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
• • 输出：[4]

解题思路：使用反向图 + 拓扑排序。原图中安全节点满足：不存在从该节点出发进入环的路径。因此可以建立反向图，并统计原图中每个节点的出度。将所有出度为 0 的节点加入队列，它们一定是安全节点。不断弹出节点，在反向图中访问其前驱节点，并将前驱节点的出度减一；当某个前驱节点出度变为 0 时，说明它所有路径都通向安全节点，将其加入队列。最后收集所有进入过队列的节点，排序返回。时间复杂度 O(n + m)，空间复杂度 O(n + m)。

Python代码示例：

from collections import dequedef eventualSafeNodes(graph):    n = len(graph)    reverse_graph = [[] for _ in range(n)]    out_degree = [0] * n    for u in range(n):        out_degree[u] = len(graph[u])        for v in graph[u]:            reverse_graph[v].append(u)    queue = deque([i for i in range(n) if out_degree[i] == 0])    safe = [False] * n    while queue:        node = queue.popleft()        safe[node] = True        for prev in reverse_graph[node]:            out_degree[prev] -= 1            if out_degree[prev] == 0:                queue.append(prev)    return [i for i in range(n) if safe[i]]

题目32：01 矩阵

问题描述：给定一个由 0 和 1 组成的矩阵 mat，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。两个相邻元素间的距离为 1。

示例：

• • 输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
• • 输出：[[0,0,0],[0,1,0],[0,0,0]]
• • 输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
• • 输出：[[0,0,0],[0,1,0],[1,2,1]]

解题思路：使用多源广度优先搜索（BFS）。将所有值为 0 的格子作为起点加入队列，并将它们到最近 0 的距离初始化为 0。然后进行 BFS，每次从队列中取出一个格子，向上下左右扩展。如果相邻格子尚未被访问，则其距离为当前格子距离加一，并将其加入队列。时间复杂度 O(m * n)，空间复杂度 O(m * n)。

Python代码示例：

from collections import dequedef updateMatrix(mat):    rows, cols = len(mat), len(mat[0])    dist = [[-1] * cols for _ in range(rows)]    queue = deque()    for i in range(rows):        for j in range(cols):            if mat[i][j] == 0:                dist[i][j] = 0                queue.append((i, j))    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]    while queue:        r, c = queue.popleft()        for dr, dc in directions:            nr, nc = r + dr, c + dc            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:                dist[nr][nc] = dist[r][c] + 1                queue.append((nr, nc))    return dist

题目33：太平洋大西洋水流问题

问题描述：有一个m × n的矩形岛屿，与太平洋和大西洋相邻。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。这个岛被分割成一个由若干方形单元格组成的网格。给定一个m x n的整数矩阵heights，heights[r][c]表示坐标(r, c)上单元格的高度。岛上雨水较多，如果相邻单元格的高度小于或等于当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。返回网格坐标result的2D 列表，其中result[i] = [ri, ci]表示雨水从单元格(ri, ci) 流动既可流向太平洋也可流向大西洋。

示例：

• • 输入：

heights = [  [1,2,2,3,5],  [3,2,3,4,4],  [2,4,5,3,1],  [6,7,1,4,5],  [5,1,1,2,4]]

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

解题思路：分别从太平洋和大西洋的边界开始，进行反向深度优先搜索（DFS）。反向搜索的含义是：如果从单元格 A 可以流向相邻单元格 B，那么从 B 反向也可以到达 A。因此从太平洋边界出发，搜索所有能流向太平洋的单元格；从大西洋边界出发，搜索所有能流向大西洋的单元格。最后取两个集合的交集。时间复杂度 O(m * n)，空间复杂度 O(m * n)。

Python代码示例：

def pacificAtlantic(heights):    if not heights:        return []    m, n = len(heights), len(heights[0])    pacific = set()    atlantic = set()    def dfs(r, c, visited):        visited.add((r, c))        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):            nr, nc = r + dr, c + dc            if (0 <= nr < m and 0 <= nc < n and                (nr, nc) not in visited and                heights[nr][nc] >= heights[r][c]):                dfs(nr, nc, visited)    for i in range(m):        dfs(i, 0, pacific)        dfs(i, n - 1, atlantic)    for j in range(n):        dfs(0, j, pacific)        dfs(m - 1, j, atlantic)    return [list(cell) for cell in pacific & atlantic]

题目34：单词接龙

问题描述：字典 wordList 中从单词 beginWord 和 endWord 的转换序列是一个按下述规格形成的序列：

• • 序列中第一个单词是 beginWord；
• • 序列中最后一个单词是 endWord；
• • 每次转换只能改变一个字母；
• • 转换过程中的中间单词必须是字典 wordList 中的单词。

给你两个单词 beginWord 和 endWord 和一个字典 wordList，找到从 beginWord 到 endWord 的最短转换序列中的单词数目。如果不存在这样的转换序列，返回 0。

示例：

• • 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
• • 输出：5
• • 解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，返回它的长度 5。
• • 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
• • 输出：0

解题思路：使用广度优先搜索（BFS）。将 wordList 转换为集合，便于 O(1) 查找。从 beginWord 开始，每次尝试改变其中一个字符为 'a' 到 'z'，如果新单词在字典中且未被访问过，则加入队列，层数加一。当遇到 endWord 时返回当前层数。时间复杂度 O(N * L * 26)，其中 N 是单词数量，L 是单词长度。

Python代码示例：

from collections import dequedef ladderLength(beginWord, endWord, wordList):    word_set = set(wordList)    if endWord not in word_set:        return 0    queue = deque([(beginWord, 1)])    visited = {beginWord}    while queue:        word, steps = queue.popleft()        if word == endWord:            return steps        for i in range(len(word)):            for ch in 'abcdefghijklmnopqrstuvwxyz':                next_word = word[:i] + ch + word[i + 1:]                if next_word in word_set and next_word not in visited:                    visited.add(next_word)                    queue.append((next_word, steps + 1))    return 0

题目35：添加与搜索单词 - 数据结构设计

问题描述：请你设计一个数据结构，支持添加新单词和查找字符串是否与任何先前添加的字符串匹配。实现词典类 WordDictionary：

• • WordDictionary() 初始化词典对象；
• • void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配；
• • bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true；否则，返回 false。word 中可能包含一些 '.'，每个 '.' 都可以表示任何一个字母。

示例：

• • 输入：

["WordDictionary","addWord","addWord","addWord","search","search","search","search"][[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]

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

解题思路：使用前缀树（Trie）存储单词。addWord 按字符逐层插入，并在单词末尾标记结束。search 时使用深度优先搜索（DFS）：

• • 遇到普通字符，进入对应的子节点；
• • 遇到 '.'，则尝试所有存在的子节点。如果最终到达单词末尾标记，则返回 True。插入时间复杂度 O(L)，搜索最坏 O(26^L)，其中 L 是单词长度。

Python代码示例：

class WordDictionary:    def __init__(self):        self.root = {}        self.end = '#'    def addWord(self, word):        node = self.root        for ch in word:            node = node.setdefault(ch, {})        node[self.end] = True    def search(self, word):        def dfs(node, index):            if index == len(word):                return self.end in node            ch = word[index]            if ch != '.':                if ch not in node:                    return False                return dfs(node[ch], index + 1)            else:                for key in node:                    if key != self.end and dfs(node[key], index + 1):                        return True                return False        return dfs(self.root, 0)

题目36：奇偶链表

问题描述：给定单链表的头节点 head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。第一个节点的索引被认为是奇数，第二个节点的索引为偶数，以此类推。请注意，偶数组和奇数组内部的相对顺序应该与输入中的相对顺序保持一致。你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

示例：

• • 输入：head = [1,2,3,4,5]
• • 输出：[1,3,5,2,4]
• • 输入：head = [2,1,3,5,6,4,7]
• • 输出：[2,3,6,7,1,5,4]

解题思路：使用双指针。维护两个指针 odd 和 even，分别指向奇数位置和偶数位置的节点，同时用 even_head 记录偶数链表的头节点。遍历链表，每次将 odd.next 指向 even.next，将 even.next 指向 odd.next.next，然后分别后移指针。遍历结束后，将奇数链表尾部连接到偶数链表的头部。时间复杂度 O(n)，空间复杂度 O(1)。

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

def oddEvenList(head):    if not head or not head.next:        return head    odd = head    even = head.next    even_head = even    while even and even.next:        odd.next = even.next        odd = odd.next        even.next = odd.next        even = even.next    odd.next = even_head    return head

题目37：旋转字符串

问题描述：给定两个字符串 s 和 goal。如果在若干次旋转操作之后，s 能变成 goal，那么返回 true。s 的旋转操作就是将 s 最左边的字符移动到最右边。例如，若 s = 'abcde'，在旋转一次之后结果就是 'bcdea'。

示例：

• • 输入：s = "abcde", goal = "cdeab"，输出：true
• • 输入：s = "abcde", goal = "abced"，输出：false

解题思路：如果s和goal长度不同，直接返回false。将s与自身拼接得到s + s，如果goal是s + s的子串，则说明s可以通过旋转得到goal。时间复杂度 O(n)，空间复杂度 O(n)。

Python代码示例：

def rotateString(s, goal):    if len(s) != len(goal):        return False    return goal in s + s

题目38：子数组最大平均数 I

问题描述：给你一个由 n 个元素组成的整数数组 nums 和一个整数 k。请你找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。任何误差小于 10^-5 的答案都将被视为正确答案。

示例：

• • 输入：nums = [1,12,-5,-6,50,3], k = 4
• • 输出：12.75
• • 解释：最大平均数 (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75
• • 输入：nums = [5], k = 1，输出：5.00000

解题思路：使用滑动窗口。先计算前 k 个元素的和作为初始窗口和。然后窗口每次向右移动一位，减去离开窗口的元素，加上进入窗口的元素，更新窗口和。记录窗口和的最大值，最终除以 k 即为最大平均数。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

def findMaxAverage(nums, k):    window_sum = sum(nums[:k])    max_sum = window_sum    for i in range(k, len(nums)):        window_sum += nums[i] - nums[i - k]        max_sum = max(max_sum, window_sum)    return max_sum / k

题目39：用 Rand7() 实现 Rand10()

问题描述：给定方法rand7可生成[1,7]范围内的均匀随机整数，试写一个方法rand10生成[1,10]范围内的均匀随机整数。你只能调用rand7()且不能调用其他方法。请不要使用系统的Math.random()方法。每个测试用例将有一个内部参数n，即你实现的函数rand10()在测试时将被调用的次数。请注意，这不是传递给rand10() 的参数。

示例：

• • 输入：1
• • 输出：[2]
• • 输入：2
• • 输出：[2,8]

解题思路：利用拒绝采样。调用两次 rand7()，构造 (rand7() - 1) * 7 + rand7()，得到 [1, 49] 范围内的均匀随机整数。如果结果大于 40，则拒绝并重新采样；否则将结果映射到 [1, 10]：(result - 1) % 10 + 1。期望调用次数为 2 * 49 / 40 ≈ 2.45 次。时间复杂度 O(1)（期望），空间复杂度 O(1)。

Python代码示例（假设 rand7 函数已定义）：

def rand10():    while True:        row = rand7()        col = rand7()        num = (row - 1) * 7 + col        if num <= 40:            return (num - 1) % 10 + 1

题目40：两个字符串的删除操作

问题描述：给定两个单词 word1 和 word2，返回使得 word1 和 word2相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。

示例：

• • 输入：word1 = "sea", word2 = "eat"
• • 输出：2
• • 解释：第一步将 "sea" 变为 "ea"，第二步将 "eat" 变为 "ea"。
• • 输入：word1 = "leetcode", word2 = "etco"
• • 输出：4

解题思路：将问题转化为求两个字符串的最长公共子序列（LCS）。要使两个字符串相同，最少删除次数 = len(word1) + len(word2) - 2 * LCS长度。定义 dp[i][j] 为 word1 前 i 个字符和 word2 前 j 个字符的最长公共子序列长度。状态转移：

• • 如果 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；
• • 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。最终返回 m + n - 2 * dp[m][n]。时间复杂度 O(m * n)，空间复杂度 O(m * n)。

Python代码示例：

def minDistance(word1, word2):    m, n = len(word1), len(word2)    dp = [[0] * (n + 1) for _ in range(m + 1)]    for i in range(1, m + 1):        for j in range(1, n + 1):            if word1[i - 1] == word2[j - 1]:                dp[i][j] = dp[i - 1][j - 1] + 1            else:                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])    return m + n - 2 * dp[m][n]