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

题目1：最长和谐子序列

问题描述：和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是 1。现在，给你一个整数数组 nums，请你在所有可能的子序列中找到最长的和谐子序列的长度。子序列可以通过删除一些元素或不删除元素得到，而不需要改变剩下元素的顺序。

解题思路：使用哈希表统计每个数字出现的次数。然后遍历哈希表中的每个键 x，若 x + 1 也存在，则 count[x] + count[x+1] 可以构成和谐子序列，更新最大值。

Python代码示例：

1
2
3
4
5
6
7
8
9
from collections import Counterdef findLHS(nums):    count = Counter(nums)    max_len = 0    for x in count:        if x + 1 in count:            max_len = max(max_len, count[x] + count[x + 1])    return max_len

题目2：最短补全词

问题描述：给你一个字符串 licensePlate 和一个字符串数组 words，请你找出 words 中的最短补全词。补全词需要满足：包含 licensePlate 中的所有字母（忽略大小写和数字、空格），且字母出现次数不少于 licensePlate 中对应字母的次数。如果有多个满足条件的补全词，返回 words 中最先出现的那个。

解题思路：先统计 licensePlate 中每个字母（忽略大小写，忽略非字母）的出现次数。然后遍历 words，对每个单词统计字母出现次数，检查是否覆盖 licensePlate 的需求。维护长度最短且最先出现的满足条件的单词。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
from collections import Counterdef shortestCompletingWord(licensePlate, words):    need = Counter(ch.lower() for ch in licensePlate if ch.isalpha())    result = None    for word in words:        wc = Counter(word.lower())        if all(wc[ch] >= need[ch] for ch in need):            if result is None or len(word) < len(result):                result = word    return result

题目3：按奇偶排序数组 II

问题描述：给定一个非负整数数组 nums，nums 中一半整数是奇数，一半整数是偶数。对数组进行排序，以便当 nums[i] 为奇数时，i 也是奇数；当 nums[i] 为偶数时，i 也是偶数。返回任何满足上述条件的数组作为答案。

解题思路：双指针。一个指针 even 从 0 开始每次走两步，寻找需要放置偶数的位置；另一个指针 odd 从 1 开始每次走两步，寻找需要放置奇数的位置。遍历时若 nums[even] 为奇数且 nums[odd] 为偶数，则交换两者。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
def sortArrayByParityII(nums):    even, odd = 0, 1    n = len(nums)    while even < n and odd < n:        while even < n and nums[even] % 2 == 0:            even += 2        while odd < n and nums[odd] % 2 == 1:            odd += 2        if even < n and odd < n:            nums[even], nums[odd] = nums[odd], nums[even]            even += 2            odd += 2    return nums

题目4：复写零

问题描述：给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。注意：请不要在超过该数组长度的位置写入元素。请对输入的数组就地修改，不要从函数返回任何东西。

解题思路：先统计数组中零的个数，计算出复写后需要保留的原数组元素范围。然后从后往前遍历，将元素写入正确位置；遇到零时写入两次并跳过。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def duplicateZeros(arr):    n = len(arr)    zeros = arr.count(0)    i = n - 1    j = n + zeros - 1    while i >= 0:        if j < n:            arr[j] = arr[i]        j -= 1        if arr[i] == 0:            if j < n:                arr[j] = 0            j -= 1        i -= 1

题目5：将每个元素替换为右侧最大元素

问题描述：给你一个数组 arr，请你将所有元素替换为它右侧的最大元素。如果某个元素右侧没有元素，则将其替换为 -1。返回替换后的数组。

解题思路：从右往左遍历，维护当前右侧的最大值 max_right（初始为 -1）。对于每个位置 i，先保存 arr[i]，然后将 arr[i] 更新为 max_right，再用保存的值更新 max_right = max(max_right, old_val)。

Python代码示例：

1
2
3
4
5
6
7
def replaceElements(arr):    max_right = -1    for i in range(len(arr) - 1, -1, -1):        old = arr[i]        arr[i] = max_right        max_right = max(max_right, old)    return arr

题目6：回文数

问题描述：给你一个整数 x，如果 x 是一个回文整数，返回 true；否则，返回 false。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

解题思路：负数一定不是回文数。将整数反转一半：当原数字大于反转后的数字时，不断取原数字的末位拼接到反转数字上。循环结束时，若数字位数为偶数，则原数字等于反转数字；若为奇数，则原数字等于反转数字除以 10。也可以直接转为字符串比较，但题目通常要求不转字符串。

Python代码示例：

1
2
3
4
5
6
7
8
def isPalindrome(x):    if x < 0 or (x % 10 == 0 and x != 0):        return False    reversed_half = 0    while x > reversed_half:        reversed_half = reversed_half * 10 + x % 10        x //= 10    return x == reversed_half or x == reversed_half // 10

题目7：位1的个数

问题描述：编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

解题思路：利用位运算技巧 n & (n - 1)，该操作会将 n 的二进制表示中最右边的 1 变为 0。不断执行该操作并计数，直到 n 变为 0。循环次数等于二进制中 1 的个数。

Python代码示例：

1
2
3
4
5
6
def hammingWeight(n):    count = 0    while n:        n &= n - 1        count += 1    return count

题目8：Excel表列名称

问题描述：给你一个整数 columnNumber，返回它在 Excel 表中相对应的列名称。例如：

• • 1 -> "A"
• • 2 -> "B"
• • 3 -> "C"
• • ...
• • 26 -> "Z"
• • 27 -> "AA"
• • 28 -> "AB"
• • ...

解题思路：这是 1-based 的 26 进制转换。每次将 columnNumber 减 1，然后对 26 取余得到当前位字母，再整除 26。重复直到 columnNumber 为 0，最后将结果反转。

Python代码示例：

1
2
3
4
5
6
7
def convertToTitle(columnNumber):    result = []    while columnNumber > 0:        columnNumber -= 1        result.append(chr(ord('A') + columnNumber % 26))        columnNumber //= 26    return ''.join(reversed(result))

题目9：求众数 II

问题描述：给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。要求时间复杂度为 O(n)，空间复杂度为 O(1)。

解题思路：使用摩尔投票法的扩展版本。由于出现次数超过 n/3 的元素最多有两个，维护两个候选元素 cand1、cand2 及其计数 count1、count2。遍历数组进行投票：若当前数等于候选之一则对应计数加一；若某计数为 0 则更换候选；否则两个计数都减一。投票结束后，再遍历一次数组验证两个候选的实际出现次数是否超过 n/3，将满足条件的加入结果。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def majorityElement(nums):    cand1 = cand2 = None    count1 = count2 = 0    for num in nums:        if num == cand1:            count1 += 1        elif num == cand2:            count2 += 1        elif count1 == 0:            cand1 = num            count1 = 1        elif count2 == 0:            cand2 = num            count2 = 1        else:            count1 -= 1            count2 -= 1    result = []    n = len(nums)    for cand in (cand1, cand2):        if cand is not None and nums.count(cand) > n // 3:            result.append(cand)    return result

题目10：二叉树的后序遍历

问题描述：给你一棵二叉树的根节点 root，返回它节点值的后序遍历。后序遍历顺序为：左子树 → 右子树 → 根节点。

解题思路：递归：按左、右、根的顺序访问。迭代：可以使用栈模拟。一种巧妙的方法是按照“根 → 右 → 左”的顺序遍历，然后将结果反转，即得到后序遍历。具体地，用栈存储节点，每次弹出节点并加入结果，然后先将左子节点压栈，再将右子节点压栈（保证右子树先处理），最后反转结果。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
def postorderTraversal(root):    if not root:        return []    stack = [root]    result = []    while stack:        node = stack.pop()        result.append(node.val)        if node.left:            stack.append(node.left)        if node.right:            stack.append(node.right)    return result[::-1]