网络安全黑客技术练习题大全(40)

题目91：较大分组的位置

问题描述：在一个由小写字母构成的字符串 s 中，包含这样一些字符：它们连续出现，次数大于等于 3 次。我们称这些字符组成的区间为较大分组。返回一个列表，包含所有较大分组的起始和终止位置（下标从 0 开始）。

解题思路：一次遍历。用两个指针 start 和 end 标记当前连续相同字符的区间。当字符发生变化时，若 end - start + 1 >= 3，则将 [start, end] 加入结果。最后注意处理字符串末尾的分组。

Python代码示例：

1
2
3
4
5
6
7
8
9
def largeGroupPositions(s):    result = []    start = 0    for end in range(1, len(s) + 1):        if end == len(s) or s[end] != s[start]:            if end - start >= 3:                result.append([start, end - 1])            start = end    return result

题目92：将数组分成和相等的三个部分

问题描述：给你一个整数数组 arr，只有可以将其划分为三个和都相等的非空部分时才返回 true，否则返回 false。形式上，如果可以找出索引 i + 1 < j 且满足 arr[0] + arr[1] + ... + arr[i] == arr[i+1] + ... + arr[j-1] == arr[j] + ... + arr[n-1]，就可以将数组三等分。

解题思路：先计算数组总和。若总和不能被 3 整除，直接返回 False。设目标和为 total / 3，遍历数组累加当前和，每当当前和等于目标和时，计数加一并重置当前和为 0。若最终计数大于等于 3，则返回 True（注意最后一段也要满足条件，但计数达到 3 即可保证）。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
def canThreePartsEqualSum(arr):    total = sum(arr)    if total % 3 != 0:        return False    target = total // 3    count = 0    cur_sum = 0    for num in arr:        cur_sum += num        if cur_sum == target:            count += 1            cur_sum = 0    return count >= 3

题目93：数组形式的整数加法

问题描述：对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。给定非负整数 X 的数组形式 A，返回整数 X + K 的数组形式。

解题思路：从数组末尾开始，逐位加上 K 的对应位，并处理进位。每次取 K % 10 加上当前位，K //= 10。最终若 K 还有剩余，则继续添加到结果中。最后将结果反转即为答案。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
def addToArrayForm(A, K):    result = []    i = len(A) - 1    carry = 0    while i >= 0 or K > 0 or carry:        x = A[i] if i >= 0 else 0        y = K % 10        total = x + y + carry        result.append(total % 10)        carry = total // 10        K //= 10        i -= 1    return result[::-1]

题目94：重复叠加字符串匹配

问题描述：给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串的子串，如果不存在则返回 -1。注意：字符串 "abc" 重复叠加 0 次成为 ""，重复叠加 1 次成为 "abc"，重复叠加 2 次成为 "abcabc"。

解题思路：若 b 中的字符不在 a 中，直接返回 -1。重复叠加 a，直到长度大于等于 len(b) + len(a)，检查 b 是否为子串。若在叠加次数为 n 时找到，返回 n；否则返回 -1。理论上最多叠加 len(b) // len(a) + 2 次即可判断。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
def repeatedStringMatch(a, b):    if not set(b).issubset(set(a)):        return -1    times = 1    s = a    while len(s) < len(b):        s += a        times += 1    if b in s:        return times    if b in s + a:        return times + 1    return -1

题目95：最小差值 I

问题描述：给你一个整数数组 A，你可以对 A 中的每个元素 A[i] 进行以下操作：选择任意 x 满足 -K <= x <= K，并将 x 加到 A[i] 上。在此过程之后，我们得到一些数组 B。返回 B 的最大值和 B 的最小值之间可能存在的最小差值。

解题思路：对于数组中的最大值 max_val 和最小值 min_val，我们可以通过加减 K 来缩小它们的差距。每个元素可以调整的范围是 [A[i] - K, A[i] + K]。若 max_val - min_val <= 2K，则可以使所有元素相等，最小差值为 0；否则最小差值为 max_val - min_val - 2K。

Python代码示例：

1
2
def smallestRangeI(A, K):    return max(0, max(A) - min(A) - 2 * K)

题目96：只出现一次的数字 III

问题描述：给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。要求线性时间复杂度，且只使用常数级额外空间。

解题思路：先对所有元素异或，得到两个只出现一次元素的异或值 xor。找到 xor 中最低位的 1（即 xor & -xor），用它把所有元素分成两组：该位为 1 的组和该位为 0 的组。两个只出现一次的元素必然分属两组。分别对两组异或，即得到这两个数。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
def singleNumber(nums):    xor = 0    for num in nums:        xor ^= num    # 找到最低位的 1    lowbit = xor & -xor    a = b = 0    for num in nums:        if num & lowbit:            a ^= num        else:            b ^= num    return [a, b]

题目97：错误的集合

问题描述：集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制成了集合里面的另外一个数字，导致集合有一个数字重复并且丢失了一个数字。给定一个数组 nums 代表了集合 S 发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

解题思路：使用哈希表统计每个数字出现的次数。遍历 1 到 n，若某数字出现次数为 2，则为重复数字；若出现次数为 0，则为丢失数字。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
def findErrorNums(nums):    count = [0] * (len(nums) + 1)    for num in nums:        count[num] += 1    duplicate = missing = -1    for i in range(1, len(count)):        if count[i] == 2:            duplicate = i        elif count[i] == 0:            missing = i    return [duplicate, missing]

题目98：寻找重复的子树

问题描述：给你一棵二叉树的根节点 root，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根节点即可。如果两棵树具有相同的结构和相同的节点值，则它们是重复的。

解题思路：DFS + 序列化。对每个子树进行后序遍历，将其序列化为字符串（如 "左子树,右子树,根值"）。用哈希表记录每种序列化字符串出现的次数。当某字符串第二次出现时，将当前节点加入结果。注意使用分隔符和空节点标记，避免歧义。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from collections import defaultdictdef findDuplicateSubtrees(root):    count = defaultdict(int)    result = []    def dfs(node):        if not node:            return "#"        serial = f"{dfs(node.left)},{dfs(node.right)},{node.val}"        count[serial] += 1        if count[serial] == 2:            result.append(node)        return serial    dfs(root)    return result

题目99：摆动序列

问题描述：如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。给你一个整数数组 nums，返回 nums 中作为摆动序列的最长子序列的长度。子序列可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

解题思路：贪心。维护两个变量 up 和 down，分别表示以当前元素结尾且最后一步为上升/下降的最长摆动子序列长度。遍历数组，若 nums[i] > nums[i-1]，则 up = down + 1；若 nums[i] < nums[i-1]，则 down = up + 1。最终答案为 max(up, down)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
def wiggleMaxLength(nums):    if len(nums) < 2:        return len(nums)    up = down = 1    for i in range(1, len(nums)):        if nums[i] > nums[i - 1]:            up = down + 1        elif nums[i] < nums[i - 1]:            down = up + 1    return max(up, down)

题目100：实现 strStr()

问题描述：实现 strStr() 函数。给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1。当 needle 是空字符串时，应当返回 0。

解题思路：暴力匹配。遍历 haystack 的每个起始位置，检查从该位置开始是否与 needle 完全匹配。也可使用 KMP 算法优化到 O(n + m)。

Python代码示例（暴力匹配）：

1
2
3
4
5
6
7
8
def strStr(haystack, needle):    if not needle:        return 0    n, m = len(haystack), len(needle)    for i in range(n - m + 1):        if haystack[i:i + m] == needle:            return i    return -1