网络安全黑客技术练习题大全(48)
- 2026-11-23 00:43:38
题目71:等式方程的可满足性
问题描述:给定一个由表示变量之间关系的字符串方程组成的数组 equations,每个字符串方程的长度都是 4,并采用两种不同的形式之一:"a==b" 或 "a!=b"。在这里,a 和 b 是小写字母(不一定不同),表示单字母变量名。只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false。
解题思路:并查集。第一遍遍历所有 "==" 方程,将相等的变量合并到同一个集合中。第二遍遍历所有 "!=" 方程,检查两个变量是否在同一个集合中;若是,则说明矛盾,返回 False。遍历结束返回 True。
Python代码示例:
def equationsPossible(equations): parent = list(range(26)) 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: parent[rx] = ry for eq in equations: if eq[1] == '=': union(ord(eq[0]) - ord('a'), ord(eq[3]) - ord('a')) for eq in equations: if eq[1] == '!' and find(ord(eq[0]) - ord('a')) == find(ord(eq[3]) - ord('a')): return False return True题目72:钥匙和房间
问题描述:有 n 个房间,房间按从 0 到 n - 1 编号。最初,除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而,你不能在没有获得钥匙的时候进入锁住的房间。当你进入一个房间,你可能会在里面找到一套不同的钥匙,每把钥匙上都有对应的房间号,即表示你可以打开那个房间。给你一个数组 rooms,其中 rooms[i] 是进入 i 号房间后获得的钥匙集合。如果你能进入每一个房间,返回 true,否则返回 false。
解题思路:DFS 或 BFS 图遍历。从房间 0 开始,将获得的钥匙对应的房间加入待访问集合。用一个 visited 数组记录已进入的房间,遍历结束后若所有房间都被访问过则返回 True。
Python代码示例:
def canVisitAllRooms(rooms): visited = set() stack = [0] while stack: room = stack.pop() if room in visited: continue visited.add(room) for key in rooms[room]: stack.append(key) return len(visited) == len(rooms)题目73:移除最多的同行或同列石头
问题描述:n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。如果一块石头的同行或者同列上有其他石头存在,那么就可以移除这块石头。给你一个长度为 n 的数组 stones,其中 stones[i] = [xi, yi] 表示第 i 块石头的位置。返回可以移除的石子的最大数量。
解题思路:并查集。将每个石头视为一个节点,同行或同列的石头连边。可以移除的最大数量等于总石头数减去连通分量数。实现时,将每个坐标的 x 和 y 分别作为并查集的节点(可以用偏移区分,如 x 和 y + 10001)。遍历所有石头,合并其 x 坐标和 y 坐标。最终统计不同连通分量的个数 components,答案为 len(stones) - components。
Python代码示例:
def removeStones(stones): parent = {} def find(x): if x not in parent: parent[x] = 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: parent[rx] = ry for x, y in stones: union(x, y + 10001) components = len(set(find(x) for x, _ in stones)) return len(stones) - components题目74:账户合并
问题描述:给定一个列表 accounts,每个元素 accounts[i] 是一个字符串列表,其中第一个元素 accounts[i][0] 是名称,其余元素是邮箱地址,表示该账户的邮箱列表。现在,我们想合并这些账户。如果两个账户都有一些共同的邮箱地址,则两个账户必定属于同一个人。请注意,即使两个账户具有相同的名称,它们也可能属于不同的人,因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户,但其所有账户都具有相同的名称。合并账户后,按以下格式返回账户:每个账户的第一个元素是名称,其余元素是按字典序排列的邮箱地址。账户本身可以以任意顺序返回。
解题思路:并查集 + 哈希表。
• 用哈希表记录每个邮箱第一次出现的账户索引。 • 遍历所有账户的邮箱,若邮箱已出现过,则将该账户与之前出现该邮箱的账户合并。 • 用并查集维护账户的连通性。 • 最后将同一根节点的账户的所有邮箱合并,排序后加上名称返回。
Python代码示例:
from collections import defaultdictdef accountsMerge(accounts): parent = list(range(len(accounts))) 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: parent[rx] = ry email_to_idx = {} for i, account in enumerate(accounts): for email in account[1:]: if email in email_to_idx: union(i, email_to_idx[email]) else: email_to_idx[email] = i idx_to_emails = defaultdict(list) for email, idx in email_to_idx.items(): idx_to_emails[find(idx)].append(email) result = [] for idx, emails in idx_to_emails.items(): result.append([accounts[idx][0]] + sorted(emails)) return result题目75:冗余连接 II
问题描述:在本问题中,有根树指满足以下条件的有向图:该图中有且仅有一个根节点,所有其他节点都是该根节点的后继,每一个节点只有一个父节点,根节点没有父节点。给定一个有向图,该图由一个有着 n 个节点(节点值不重复)的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间,这条附加的边不属于树中已存在的边。结果图是一个以边组成的二维数组 edges。每个元素是一对 [ui, vi],用以表示有向图中连接顶点 ui 和顶点 vi 的边,其中 ui 是 vi 的一个父节点。返回一条能删除的边,使得剩下的图是有 n 个节点的有根树。若有多个答案,返回最后出现在给定二维数组的答案。
解题思路:并查集 + 分类讨论。
• 首先统计每个节点的入度。若存在入度为 2 的节点,则该节点有两条入边,其中一条是多余的。 • 若不存在入度为 2 的节点,则说明图中存在环,用并查集找到导致环的那条边即可。 • 若存在入度为 2 的节点,记录这两条边,先尝试删除后出现的那条边,判断剩余图是否为树;若不是,则删除另一条。
Python代码示例:
def findRedundantDirectedConnection(edges): n = len(edges) parent = list(range(n + 1)) 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 # 统计入度 indegree = [0] * (n + 1) for u, v in edges: indegree[v] += 1 # 找到入度为 2 的节点 two_parent = None for i in range(1, n + 1): if indegree[i] == 2: two_parent = i break if two_parent is None: # 无入度为 2 的节点,存在环,找到导致环的边 for u, v in edges: if not union(u, v): return [u, v] else: # 存在入度为 2 的节点,记录两条入边 candidates = [] for i, (u, v) in enumerate(edges): if v == two_parent: candidates.append(i) # 尝试删除后出现的那条边 for idx in reversed(candidates): parent = list(range(n + 1)) valid = True for i, (u, v) in enumerate(edges): if i == idx: continue if not union(u, v): valid = False break if valid: return edges[idx] return []题目76:子数组按位或操作
问题描述:我们有一个非负整数数组 arr。对于每个(连续)子数组,计算其中元素的按位或(|)值。返回这些按位或值中不同结果的个数。
解题思路:按位或的结果随子数组长度增加只会增加位数,不会减少,且不同的结果数量有限。维护一个集合 cur 表示以当前元素结尾的所有子数组的按位或结果,更新方式为:new_cur = {x | num for x in cur} ∪ {num}。将所有轮次的 cur 累加到全局结果集合中,最后返回全局集合的大小。
Python代码示例:
def subarrayBitwiseORs(arr): result = set() cur = set() for num in arr: cur = {x | num for x in cur} | {num} result |= cur return len(result)题目77:最大整除子集
问题描述:给你一个由无重复正整数组成的集合 nums,请你找出并返回其中最大的整除子集 answer,子集中每一对 (answer[i], answer[j]) 都应当满足:
• answer[i] % answer[j] == 0,或• answer[j] % answer[i] == 0
如果存在多个有效解子集,返回其中任意一个即可。
解题思路:动态规划。先将数组升序排序,设 dp[i] 表示以 nums[i] 结尾的最大整除子集的长度。状态转移:对于每个 i,遍历 j < i,若 nums[i] % nums[j] == 0,则 dp[i] = max(dp[i], dp[j] + 1)。同时记录前驱节点 prev[i] 以便回溯构建答案。最后从最大长度对应的位置向前回溯即可。
Python代码示例:
def largestDivisibleSubset(nums): if not nums: return [] nums.sort() n = len(nums) dp = [1] * n prev = [-1] * n max_len = 0 max_idx = 0 for i in range(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_idx = i result = [] idx = max_idx while idx != -1: result.append(nums[idx]) idx = prev[idx] return result[::-1]题目78:最长有效括号
问题描述:给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。
解题思路:使用栈。栈底存储最后一个未匹配的右括号的下标(初始为 -1)。遍历字符串:
• 遇到 '('将其下标入栈;• 遇到 ')'弹出栈顶;• 若栈为空,说明当前右括号无法匹配,将其下标入栈作为新的分隔点; • 否则当前有效长度为 i - stack[-1],更新最大值。
Python代码示例:
def longestValidParentheses(s): stack = [-1] max_len = 0 for i, ch in enumerate(s): if ch == '(': stack.append(i) else: stack.pop() if not stack: stack.append(i) else: max_len = max(max_len, i - stack[-1]) return max_len题目79:乘积最大子数组
问题描述:给你一个整数数组 nums,请你找出数组中乘积最大的连续子数组(该子数组最少包含一个数字),返回该子数组的乘积。
解题思路:动态规划。由于负负得正,需要同时维护以当前位置结尾的最大乘积和最小乘积。状态转移:
• cur_max = max(num, cur_max * num, cur_min * num)• cur_min = min(num, cur_max * num, cur_min * num)
每一步更新全局最大值。注意计算 cur_min 时要使用更新前的 cur_max 和 cur_min。
Python代码示例:
def maxProduct(nums): result = cur_max = cur_min = nums[0] for num in nums[1:]: candidates = (num, cur_max * num, cur_min * num) cur_max = max(candidates) cur_min = min(candidates) result = max(result, cur_max) return result题目80:矩阵中的最长递增路径
问题描述:给定一个 m x n 的整数矩阵 matrix,找出其中最长递增路径的长度。对于每个单元格,你可以往上、下、左、右四个方向移动。不能对角线移动或移动到边界外。不能重复经过同一个单元格。
解题思路:记忆化 DFS。用 dp[i][j] 记录以 (i, j) 为起点的最长递增路径长度。遍历每个格子,若未计算则递归计算四个方向中满足递增条件的最大长度加一。避免重复计算,时间复杂度 O(mn)。
Python代码示例:
def longestIncreasingPath(matrix): if not matrix: return 0 m, n = len(matrix), len(matrix[0]) dp = [[0] * n for _ in range(m)] directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(i, j): if dp[i][j]: return dp[i][j] max_len = 1 for di, dj in directions: ni, nj = i + di, j + dj if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] > matrix[i][j]: max_len = max(max_len, 1 + dfs(ni, nj)) dp[i][j] = max_len return max_len return max(dfs(i, j) for i in range(m) for j in range(n))