超全网络安全技术练习题(18)

题目71：旋转数组

问题描述：给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。要求使用空间复杂度为 O(1) 的原地算法。

解题思路：使用三次反转法。先将整个数组反转，再反转前 k 个元素，最后反转剩余元素。这样即可在原地完成旋转，时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

def rotate(nums, k):    n = len(nums)    k = k % n    def reverse(left, right):        while left < right:            nums[left], nums[right] = nums[right], nums[left]            left += 1            right -= 1    reverse(0, n - 1)    reverse(0, k - 1)    reverse(k, n - 1)

题目72：搜索二维矩阵II

问题描述：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

• • 每行的元素从左到右升序排列
• • 每列的元素从上到下升序排列

解题思路：从矩阵的右上角（或左下角）开始搜索。若当前元素等于 target，返回 True；若当前元素大于 target，则目标值不可能在当前列，向左移动一列；若当前元素小于 target，则目标值不可能在当前行，向下移动一行。每次移动排除一行或一列，时间复杂度 O(m + n)。

Python代码示例：

def searchMatrix(matrix, target):    if not matrix:        return False    rows, cols = len(matrix), len(matrix[0])    r, c = 0, cols - 1    while r < rows and c >= 0:        if matrix[r][c] == target:            return True        elif matrix[r][c] > target:            c -= 1        else:            r += 1    return False

题目73：打开转盘锁

问题描述：你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有 10 个数字：'0'到'9'。每个拨轮可以自由旋转：例如把'9'变为'0'，'0'变为'9'。每次旋转都只能旋转一个拨轮的一位数字。锁的初始数字为'0000'，一个代表四个拨轮的数字的字符串。列表deadends包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再旋转。字符串target代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回-1。

解题思路：使用广度优先搜索（BFS）。从 "0000" 开始，每次将某个拨轮向上或向下拨动一位，得到新的状态。用集合记录已访问的状态和死亡数字，避免重复访问。BFS 按层遍历，每层代表一次旋转，第一次遇到 target 时的层数即为最小旋转次数。

Python代码示例：

from collections import dequedef openLock(deadends, target):    dead = set(deadends)    if "0000" in dead:        return -1    queue = deque([("0000", 0)])    visited = {"0000"}    while queue:        state, steps = queue.popleft()        if state == target:            return steps        for i in range(4):            for d in (-1, 1):                digit = (int(state[i]) + d) % 10                new_state = state[:i] + str(digit) + state[i + 1:]                if new_state not in visited and new_state not in dead:                    visited.add(new_state)                    queue.append((new_state, steps + 1))    return -1

题目74：二叉树的锯齿形层序遍历

问题描述：给你二叉树的根节点 root，返回其节点值的锯齿形层序遍历。即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行。

解题思路：使用层序遍历（BFS）。逐层处理节点，维护一个布尔变量 left_to_right 表示当前层的遍历方向。每层处理完后根据方向决定是否反转该层结果，然后切换方向。

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

from collections import dequedef zigzagLevelOrder(root):    if not root:        return []    result = []    queue = deque([root])    left_to_right = True    while queue:        level = []        for _ in range(len(queue)):            node = queue.popleft()            level.append(node.val)            if node.left:                queue.append(node.left)            if node.right:                queue.append(node.right)        if not left_to_right:            level.reverse()        result.append(level)        left_to_right = not left_to_right    return result

题目75：分割数组为连续子序列

问题描述：给你一个按升序排序的整数数组 nums，请你将它们分割成一个或多个长度至少为 3 的连续子序列。如果可以完成上述分割，则返回 true；否则，返回 false。

解题思路：使用贪心 + 哈希表。用两个哈希表：count 记录每个数字剩余的出现次数，end 记录以某个数字结尾的连续子序列数量。遍历数组，若当前数字已用完则跳过。优先将当前数字接到已有的以 num - 1 结尾的子序列后面；若无法接上，则尝试以当前数字为起点新建一个长度为 3 的连续子序列（需要 num + 1 和 num + 2 都存在）；若都不行则返回 False。

Python代码示例：

from collections import Counterdef isPossible(nums):    count = Counter(nums)    end = Counter()    for num in nums:        if count[num] == 0:            continue        count[num] -= 1        if end[num - 1] > 0:            end[num - 1] -= 1            end[num] += 1        elif count[num + 1] > 0 and count[num + 2] > 0:            count[num + 1] -= 1            count[num + 2] -= 1            end[num + 2] += 1        else:            return False    return True

题目76：寻找旋转排序数组中的最小值II

问题描述：已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后得到输入数组。注意数组中可能存在重复元素。请找出并返回数组中的最小元素。你必须尽可能减少整个操作步骤。

解题思路：使用二分查找。比较中间元素 nums[mid] 与右边界元素 nums[right]：

• • 若 nums[mid] < nums[right]，说明最小值在左半部分，令 right = mid
• • 若 nums[mid] > nums[right]，说明最小值在右半部分，令 left = mid + 1
• • 若 nums[mid] == nums[right]，无法判断最小值在哪一侧，但可以确定 nums[right] 不是唯一最小值，令 right -= 1

最终 left 即为最小值所在位置。

Python代码示例：

def findMin(nums):    left, right = 0, len(nums) - 1    while left < right:        mid = (left + right) // 2        if nums[mid] < nums[right]:            right = mid        elif nums[mid] > nums[right]:            left = mid + 1        else:            right -= 1    return nums[left]

题目77：找到字符串中所有字母异位词

问题描述：给定两个字符串 s 和 p，找到 s 中所有 p 的字母异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。字母异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

解题思路：使用滑动窗口 + 字符计数。先统计 p 中每个字符的出现次数，然后在 s 上维护一个长度为 len(p) 的窗口，记录窗口内字符的计数。每次移动窗口时更新计数，若窗口计数与 p 的计数相同，则记录窗口起始索引。可以用一个变量 matches 记录匹配的字符种类数来优化比较过程。

Python代码示例：

from collections import Counterdef findAnagrams(s, p):    if len(s) < len(p):        return []    p_count = Counter(p)    window = Counter(s[:len(p)])    result = []    if window == p_count:        result.append(0)    for i in range(len(p), len(s)):        window[s[i]] += 1        left_char = s[i - len(p)]        window[left_char] -= 1        if window[left_char] == 0:            del window[left_char]        if window == p_count:            result.append(i - len(p) + 1)    return result

题目78：最短超串

问题描述：假设你有两个数组，一个长数组 A，一个短数组 B。请你在长数组 A 中找到一个最短子数组，使得该子数组包含短数组 B 的所有元素（顺序无关，但元素必须全部包含，且数量满足要求）。如果存在多个最短子数组，返回起始位置最靠左的那一个。如果不存在，返回空数组。

解题思路：使用滑动窗口 + 字符计数。先用哈希表统计 B 中每个元素的需求数量。然后用左右指针维护一个窗口，右指针不断扩展，将元素加入窗口计数；当窗口满足覆盖 B 的所有元素时，尝试收缩左指针以找到最小窗口。每次找到更短的窗口时更新答案。用一个变量 formed 记录当前窗口中有多少元素已经满足需求数量。

Python代码示例：

from collections import Counterdef shortestSupersequence(A, B):    need = Counter(B)    window = {}    required = len(need)    formed = 0    left = 0    min_len = float('inf')    result = []    for right, num in enumerate(A):        window[num] = window.get(num, 0) + 1        if num in need and window[num] == need[num]:            formed += 1        while left <= right and formed == required:            if right - left + 1 < min_len:                min_len = right - left + 1                result = [left, right]            left_num = A[left]            window[left_num] -= 1            if left_num in need and window[left_num] < need[left_num]:                formed -= 1            left += 1    return result

题目79：二叉搜索树中第K小的元素

问题描述：给定一个二叉搜索树的根节点 root，和一个整数 k，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

解题思路：利用二叉搜索树的性质：中序遍历结果是严格递增的序列。使用迭代方式的中序遍历，借助栈模拟递归过程。每次弹出栈顶元素时计数加一，当计数达到 k 时，当前节点即为第 k 小的元素。时间复杂度 O(H + k)，空间复杂度 O(H)，其中 H 为树的高度。

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

def kthSmallest(root, k):    stack = []    curr = root    while curr or stack:        while curr:            stack.append(curr)            curr = curr.left        curr = stack.pop()        k -= 1        if k == 0:            return curr.val        curr = curr.right

题目80：账户合并

问题描述：给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是名称，其余元素是邮箱地址。现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的姓名。一个人可以拥有任意数量的账户，但其所有账户都具有相同的名称。合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是按字符 ASCII 顺序排列的邮箱地址。账户本身可以以任意顺序返回。

解题思路：使用并查集（Union-Find）。将所有邮箱地址映射到唯一的整数 ID，同一个账户内的邮箱通过并查集合并。遍历所有账户，将同一账户内的邮箱进行合并操作。最后按根节点分组，收集每个组内的邮箱，排序后与名称一起组成结果。

Python代码示例：

from collections import defaultdictdef accountsMerge(accounts):    parent = {}    def find(x):        if parent[x] != x:            parent[x] = find(parent[x])        return parent[x]    def union(x, y):        rx, ry = find(x), find(y)        if rx != ry:            parent[ry] = rx    email_to_name = {}    email_to_id = {}    idx = 0    for account in accounts:        name = account[0]        for email in account[1:]:            if email not in email_to_id:                email_to_id[email] = idx                parent[idx] = idx                idx += 1            email_to_name[email] = name    for account in accounts:        first_email = account[1]        for email in account[2:]:            union(email_to_id[first_email], email_to_id[email])    groups = defaultdict(list)    for email, eid in email_to_id.items():        root = find(eid)        groups[root].append(email)    result = []    for root, emails in groups.items():        name = email_to_name[emails[0]]        result.append([name] + sorted(emails))    return result