网络安全黑客技术练习题大全(46)
- 2026-11-17 04:29:10
题目51:网络延迟时间
问题描述:有 n 个网络节点,标记为 1 到 n。给你一个列表 times,表示信号经过有向边的传递时间。times[i] = (ui, vi, wi),其中 ui 是源节点,vi 是目标节点,wi 是一个信号从源节点传递到目标节点的时间。现在,从某个节点 k 发出一个信号。需要多久才能使所有节点都收到信号?如果不能使所有节点收到信号,返回 -1。
解题思路:单源最短路径问题,使用 Dijkstra 算法。构建邻接表,从节点 k 开始运行 Dijkstra,求出到所有节点的最短时间。最终答案为所有最短时间中的最大值;若存在节点不可达(距离仍为无穷大),则返回 -1。
Python代码示例:
import heapqfrom collections import defaultdictdef networkDelayTime(times, n, k): graph = defaultdict(list) for u, v, w in times: graph[u].append((v, w)) dist = {i: float('inf') for i in range(1, n + 1)} dist[k] = 0 heap = [(0, k)] while heap: d, u = heapq.heappop(heap) if d > dist[u]: continue for v, w in graph[u]: if d + w < dist[v]: dist[v] = d + w heapq.heappush(heap, (dist[v], v)) max_dist = max(dist.values()) return max_dist if max_dist < float('inf') else -1题目52:连接所有点的最小费用
问题描述:给你一个 points 数组,表示 2D 平面上的一些点,其中 points[i] = [xi, yi]。连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的曼哈顿距离:|xi - xj| + |yi - yj|。请你返回将所有点连接的最小总费用。只有任意两点之间存在一条路径时,所有点才被视为连接在一起。
解题思路:最小生成树问题。使用 Kruskal 算法:
• 枚举所有点对,计算曼哈顿距离,生成所有边并按费用升序排序。 • 使用并查集维护连通性,依次选择费用最小的边,若两端点不在同一集合则合并并累加费用。 • 当选择的边数达到 n - 1时结束。
Python代码示例:
def minCostConnectPoints(points): n = len(points) edges = [] for i in range(n): for j in range(i + 1, n): cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) edges.append((cost, i, j)) edges.sort() parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x def union(x, y): rx, ry = find(x), find(y) if rx == ry: return False parent[rx] = ry return True total = 0 count = 0 for cost, u, v in edges: if union(u, v): total += cost count += 1 if count == n - 1: break return total题目53:LFU 缓存
问题描述:请你为最不经常使用(LFU)缓存算法设计并实现数据结构。实现 LFUCache 类:
• LFUCache(capacity):用数据结构的容量capacity初始化对象。• get(key):如果键存在于缓存中,则获取键的值,否则返回-1。• put(key, value):如果键已存在,则变更其值;如果键不存在,则插入键值对。当缓存达到其容量时,则应该在插入新项之前,移除最不经常使用的项。在此问题中,当存在平局(即两个或更多个键具有相同使用频率)时,应该移除最近最少使用的键。为了确定最不常使用的键,可以为缓存增加一个使用计数器。使用计数最小的键是最久未使用的键。当一个键首次插入到缓存中时,它的使用计数器被设置为1。对缓存中的键执行get或put操作,使用计数器的值将会递增。要求get和put的时间复杂度为 O(1)。
解题思路:使用两个哈希表 + 双向链表。
• key_table:键到节点的映射。• freq_table:频率到双向链表(存储该频率下的所有节点,链表头部为最近使用)。• 维护一个 min_freq记录当前最小频率。插入或访问时更新节点的频率,将其从旧频率链表移到新频率链表,并更新min_freq。当容量满时,从min_freq对应的链表尾部移除节点。
Python代码示例:
class Node: def __init__(self, key, value): self.key = key self.value = value self.freq = 1 self.prev = None self.next = Noneclass LFUCache: def __init__(self, capacity): self.capacity = capacity self.key_table = {} self.freq_table = {} self.min_freq = 0 def _add_to_head(self, freq, node): if freq not in self.freq_table: self.freq_table[freq] = (Node(0, 0), Node(0, 0)) self.freq_table[freq][0].next = self.freq_table[freq][1] self.freq_table[freq][1].prev = self.freq_table[freq][0] head, tail = self.freq_table[freq] node.next = head.next node.prev = head head.next.prev = node head.next = node def _remove_node(self, freq, node): node.prev.next = node.next node.next.prev = node.prev if self.freq_table[freq][0].next == self.freq_table[freq][1]: del self.freq_table[freq] def get(self, key): if key not in self.key_table: return -1 node = self.key_table[key] self._remove_node(node.freq, node) if node.freq == self.min_freq and node.freq not in self.freq_table: self.min_freq += 1 node.freq += 1 self._add_to_head(node.freq, node) return node.value def put(self, key, value): if self.capacity == 0: return if key in self.key_table: node = self.key_table[key] node.value = value self.get(key) return if len(self.key_table) == self.capacity: head, tail = self.freq_table[self.min_freq] victim = tail.prev self._remove_node(self.min_freq, victim) del self.key_table[victim.key] node = Node(key, value) self.key_table[key] = node self._add_to_head(1, node) self.min_freq = 1题目54:二叉树的垂序遍历
问题描述:给你二叉树的根节点 root,请你设计算法计算二叉树的垂序遍历序列。对位于 (row, col) 的每个节点而言,其左子节点位于 (row + 1, col - 1),右子节点位于 (row + 1, col + 1)。树的根节点位于 (0, 0)。二叉树的垂序遍历从最左边的列开始直到最右边的列结束,按列索引每一列上的所有节点,形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个节点,则按节点的值从小到大进行排序。返回二叉树的垂序遍历序列。
解题思路:DFS 遍历树,记录每个节点的 (col, row, val)。按 col 升序、row 升序、val 升序排序。然后按 col 分组,每组的值组成一个列表,最终返回所有组的列表。
Python代码示例(假设 TreeNode 类已定义):
from collections import defaultdictdef 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() 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题目55:设计推特
问题描述:设计一个简化版的推特(Twitter),可以让用户实现发送推文,关注/取消关注其他用户,能够看见关注人(包括自己)的最近 10 条推文。实现 Twitter 类:
• Twitter():初始化简易版推特对象。• postTweet(userId, tweetId):用户userId发送一条新推文tweetId。每条推文都有一个唯一的tweetId。• getNewsFeed(userId):检索当前用户新闻推送中最近 10 条推文的 ID。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须按照时间顺序由最近到最远排序。• follow(followerId, followeeId):用户followerId关注用户followeeId。• unfollow(followerId, followeeId):用户followerId取消关注用户followeeId。
解题思路:使用哈希表存储每个用户的关注列表和推文列表。推文带有一个全局递增的时间戳,用于排序。getNewsFeed 时,收集用户自己及所有关注者的最近推文,按时间戳降序排序,取前 10 条。为了高效,可以对每个用户的推文列表使用链表或数组,合并时使用堆。
Python代码示例:
import heapqfrom collections import defaultdictclass Twitter: def __init__(self): self.time = 0 self.tweets = defaultdict(list) # userId -> [(time, tweetId)] self.following = defaultdict(set) # userId -> set of followeeIds def postTweet(self, userId, tweetId): self.time += 1 self.tweets[userId].append((self.time, tweetId)) def getNewsFeed(self, userId): heap = [] # 自己 for t, tid in self.tweets[userId][-10:]: heapq.heappush(heap, (-t, tid)) # 关注的人 for followee in self.following[userId]: for t, tid in self.tweets[followee][-10:]: heapq.heappush(heap, (-t, tid)) result = [] while heap and len(result) < 10: result.append(heapq.heappop(heap)[1]) return result def follow(self, followerId, followeeId): if followerId != followeeId: self.following[followerId].add(followeeId) def unfollow(self, followerId, followeeId): self.following[followerId].discard(followeeId)题目56:找到最终的安全状态
问题描述:有一个有 n 个节点的有向图,节点编号为 0 到 n - 1。给定一个整数 n 和一个由 n 个整数组成的数组 graph,其中 graph[i] 是节点 i 指向的所有节点的列表(即从 i 到 graph[i] 中每个节点都存在一条有向边)。如果一个节点没有出边,则该节点是终端节点。如果一个节点所有的出边都指向安全节点,则该节点是安全节点。返回一个由所有安全节点组成的数组,按升序排列。
解题思路:反向图 + 拓扑排序。从终端节点(出度为 0)出发,在反向图上进行拓扑排序,能到达的节点都是安全节点。
• 构建反向图,并统计每个节点的出度。 • 将所有出度为 0 的节点入队。 • 依次出队,加入安全节点集合,并遍历其反向邻居,将邻居的出度减一;若邻居出度变为 0 则入队。 • 最终安全节点集合排序后返回。
Python代码示例:
from collections import dequedef eventualSafeNodes(graph): n = len(graph) reverse_graph = [[] for _ in range(n)] outdegree = [0] * n for u in range(n): outdegree[u] = len(graph[u]) for v in graph[u]: reverse_graph[v].append(u) queue = deque([i for i in range(n) if outdegree[i] == 0]) safe = [False] * n while queue: node = queue.popleft() safe[node] = True for prev in reverse_graph[node]: outdegree[prev] -= 1 if outdegree[prev] == 0: queue.append(prev) return [i for i in range(n) if safe[i]]题目57:最大频率栈
问题描述:设计一个类似堆栈的数据结构,将元素推入堆栈,并从堆栈中弹出出现频率最高的元素。实现 FreqStack 类:
• FreqStack():构造一个空的堆栈。• push(val):将一个整数val压入栈顶。• pop():删除并返回堆栈中出现频率最高的元素。如果出现频率最高的元素不只一个,则移除并返回最接近栈顶的元素。
解题思路:哈希表 + 每个频率对应一个栈。
• freq_map:记录每个元素当前的出现频率。• group:记录每个频率对应的元素栈,栈顶为最近压入的该频率元素。• max_freq:记录当前最大频率。压入时更新频率,将元素压入对应频率的栈,并更新max_freq。弹出时从max_freq对应的栈顶弹出元素,更新其频率,若该频率栈为空则max_freq减一。
Python代码示例:
from collections import defaultdictclass FreqStack: def __init__(self): self.freq_map = defaultdict(int) self.group = defaultdict(list) self.max_freq = 0 def push(self, val): f = self.freq_map[val] + 1 self.freq_map[val] = f if f > self.max_freq: self.max_freq = f self.group[f].append(val) def pop(self): val = self.group[self.max_freq].pop() self.freq_map[val] -= 1 if not self.group[self.max_freq]: self.max_freq -= 1 return val题目58:蛇梯棋
问题描述:给你一个大小为 n x n 的整数矩阵 board,方格按从 1 到 n² 编号,编号遵循转行交替方式,从左下角开始(即,从 board[n-1][0] 开始)。你从棋盘的方格 1 开始出发。每一步,你都可以从当前方格 x 移动到以下方格之一:
• 选择目标方格 next,其中x + 1 <= next <= min(x + 6, n²)。• 如果 next处有蛇或梯子,你必须移动到蛇或梯子的目的地。
返回达到方格 n² 所需的最少移动次数。如果不可能到达,返回 -1。
解题思路:BFS。先将棋盘编号映射为一维坐标,便于计算。从位置 1 开始 BFS,每次尝试投掷 1~6 步,若目标位置有蛇或梯子则跳转。用 visited 数组避免重复访问,记录步数。若到达 n² 则返回步数,队列为空仍未到达则返回 -1。
Python代码示例:
from collections import dequedef snakesAndLadders(board): n = len(board) # 将编号转为坐标 def get_pos(num): r, c = divmod(num - 1, n) row = n - 1 - r col = c if r % 2 == 0 else n - 1 - c return row, col visited = [False] * (n * n + 1) queue = deque([(1, 0)]) visited[1] = True while queue: pos, steps = queue.popleft() if pos == n * n: return steps for nxt in range(pos + 1, min(pos + 6, n * n) + 1): r, c = get_pos(nxt) if board[r][c] != -1: nxt = board[r][c] if not visited[nxt]: visited[nxt] = True queue.append((nxt, steps + 1)) return -1题目59:字典序排数
问题描述:给你一个整数 n,按字典序返回范围 [1, n] 内所有整数。你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
解题思路:将数字视为十叉树的前序遍历。从 1 开始,依次尝试向下(x * 10)或向右(x + 1)。
• 若 x * 10 <= n,则进入子节点;• 否则若 x + 1 <= n且x % 10 != 9,则进入兄弟节点;• 否则回溯到父节点( x // 10),直到找到下一个有效节点。整个过程只使用常数额外空间。
Python代码示例:
def lexicalOrder(n): result = [] num = 1 for _ in range(n): result.append(num) if num * 10 <= n: num *= 10 else: while num % 10 == 9 or num + 1 > n: num //= 10 num += 1 return result题目60:水位上升的泳池中游泳
问题描述:在一个 n x n 的整数矩阵 grid 中,每一个方格的值 grid[i][j] 表示在位置 (i, j) 的平台高度。当时间为 t 时,此时水池中的水位高度也为 t。你可以在任何一个平台高度不超过水位高度的平台上游泳。你从左上角 (0, 0) 出发,目标是到达右下角 (n-1, n-1)。返回你到达目的地所需的最少时间。
解题思路:Dijkstra 算法(最小最大路径)。从 (0, 0) 出发,每次选择当前路径上最大高度最小的节点扩展。维护 dist[i][j] 表示到达 (i, j) 所需的最小时间(即路径上最大平台高度的最小值)。使用优先队列,按 dist 升序处理。最终 dist[n-1][n-1] 即为答案。
Python代码示例:
import heapqdef swimInWater(grid): n = len(grid) dist = [[float('inf')] * n for _ in range(n)] dist[0][0] = grid[0][0] heap = [(grid[0][0], 0, 0)] directions = [(1,0), (-1,0), (0,1), (0,-1)] while heap: time, i, j = heapq.heappop(heap) if time > dist[i][j]: continue if i == n - 1 and j == n - 1: return time for di, dj in directions: ni, nj = i + di, j + dj if 0 <= ni < n and 0 <= nj < n: new_time = max(time, grid[ni][nj]) if new_time < dist[ni][nj]: dist[ni][nj] = new_time heapq.heappush(heap, (new_time, ni, nj)) return dist[n - 1][n - 1]