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

题目71：数字范围按位与

问题描述：给你两个整数 left 和 right，表示区间 [left, right]，返回此区间内所有数字按位与的结果（包含 left、right 端点）。

解题思路：按位与的性质：只要区间内某一位上出现过 0，该位的结果就是 0。从 left 和 right 的二进制最高位开始比较，找到它们的公共前缀。公共前缀部分保持不变，后面的位全部为 0。实现上，不断将 left 和 right 右移直到相等，再左移回原来的位数。

Python代码示例：

1
2
3
4
5
6
7
def rangeBitwiseAnd(left, right):    shift = 0    while left < right:        left >>= 1        right >>= 1        shift += 1    return left << shift

题目72：对角线遍历

问题描述：给你一个大小为 m x n 的矩阵 mat，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

解题思路：按对角线分组。每条对角线上的元素满足 i + j = d（d 从 0 到 m + n - 2）。当 d 为偶数时，从下往上遍历（i 从大到小）；当 d 为奇数时，从上往下遍历（i 从小到大）。注意 i 和 j 的边界条件。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def findDiagonalOrder(mat):    m, n = len(mat), len(mat[0])    result = []    for d in range(m + n - 1):        if d % 2 == 0:            # 从下往上            i = min(d, m - 1)            j = d - i            while i >= 0 and j < n:                result.append(mat[i][j])                i -= 1                j += 1        else:            # 从上往下            j = min(d, n - 1)            i = d - j            while j >= 0 and i < m:                result.append(mat[i][j])                i += 1                j -= 1    return result

题目73：子域名访问计数

问题描述：网站域名 domain 由子域名及其上级域名组成。例如 "discuss.leetcode.com" 由子域名 "leetcode.com"、"com" 和顶级域名 "discuss.leetcode.com" 组成。给定一个计数数组 cpdomains，其中 cpdomains[i] = "count domain" 表示该域名被访问了 count 次。返回所有域名及其访问次数，格式为 "count domain" 的列表。

解题思路：使用哈希表统计每个域名的访问次数。对于每个 "count domain"，拆分出计数和域名，然后将域名逐级拆分（从完整域名到顶级域名），每一级都累加计数。最后将哈希表转换为结果列表。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
def subdomainVisits(cpdomains):    count = {}    for item in cpdomains:        num, domain = item.split()        num = int(num)        parts = domain.split('.')        for i in range(len(parts)):            sub = '.'.join(parts[i:])            count[sub] = count.get(sub, 0) + num    return [f"{v} {k}" for k, v in count.items()]

题目74：分糖果

问题描述：Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i]。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。给你一个长度为 n 的整数数组 candyType，返回 Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的最多种类数。

解题思路：设糖果总数为 n，种类数为 unique。Alice 最多能吃的糖果数为 n / 2。若 unique >= n / 2，她可以吃到 n / 2 种不同的糖；否则她最多只能吃到 unique 种。因此答案为 min(unique, n // 2)。

Python代码示例：

1
2
def distributeCandies(candyType):    return min(len(set(candyType)), len(candyType) // 2)

题目75：最富有客户的资产总量

问题描述：给你一个 m x n 的整数网格 accounts，其中 accounts[i][j] 是第 i 位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的资产总量。客户的资产总量就是他们在各家银行托管的资产数量之和。最富有客户就是资产总量最大的客户。

解题思路：遍历每一行，计算每行的元素之和，维护最大值即可。时间复杂度 O(mn)。

Python代码示例：

1
2
def maximumWealth(accounts):    return max(sum(row) for row in accounts)

题目76：有序数组的平方

问题描述：给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

解题思路：双指针。原数组可能有负数，平方后负数会变大。用左右两个指针分别指向数组两端，每次比较两端平方后的大小，将较大者从结果数组的末尾往前填入。这样可以在 O(n) 时间内完成，无需额外排序。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def sortedSquares(nums):    n = len(nums)    result = [0] * n    left, right = 0, n - 1    pos = n - 1    while left <= right:        if nums[left] ** 2 > nums[right] ** 2:            result[pos] = nums[left] ** 2            left += 1        else:            result[pos] = nums[right] ** 2            right -= 1        pos -= 1    return result

题目77：自除数

问题描述：自除数是指可以被它包含的每一位数整除的数。例如，128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。自除数不允许包含 0。给定两个整数 left 和 right，返回一个列表，列表的元素是范围 [left, right] 内所有的自除数。

解题思路：遍历区间内的每个数，对每个数逐位检查：

• • 若某一位为 0，则该数不是自除数；
• • 若该数不能被某一位整除，则不是自除数。满足所有条件则加入结果。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def selfDividingNumbers(left, right):    result = []    for num in range(left, right + 1):        temp = num        valid = True        while temp:            digit = temp % 10            if digit == 0 or num % digit != 0:                valid = False                break            temp //= 10        if valid:            result.append(num)    return result

题目78：数组的相对排序

问题描述：给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按升序放在 arr1 的末尾。

解题思路：使用计数排序。先统计 arr1 中每个元素的出现次数。然后按照 arr2 的顺序，将对应元素按出现次数依次放入结果。最后将未在 arr2 中出现的元素按升序追加到结果末尾。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
from collections import Counterdef relativeSortArray(arr1, arr2):    count = Counter(arr1)    result = []    for num in arr2:        result.extend([num] * count[num])        del count[num]    for num in sorted(count):        result.extend([num] * count[num])    return result

题目79：高度检查器

问题描述：学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照非递减的高度顺序排成一行。排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是排在第 i 位的学生的高度。给你一个整数数组 heights，表示当前学生排列的高度情况。返回满足 heights[i] != expected[i] 的下标数量。

解题思路：将 heights 复制一份并排序得到 expected。然后逐个比较 heights[i] 与 expected[i]，统计不同的下标数量。时间复杂度 O(n log n)。

Python代码示例：

1
2
3
def heightChecker(heights):    expected = sorted(heights)    return sum(1 for h, e in zip(heights, expected) if h != e)

题目80：二叉树的堂兄弟节点

问题描述：在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。给你一棵具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true；否则返回 false。

解题思路：BFS 或 DFS 遍历。记录每个节点的深度和父节点。找到值为 x 和 y 的节点后，比较它们的深度是否相同且父节点是否不同。可以用一次遍历同时记录两个节点的信息。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
def isCousins(root, x, y):    info = {}  # val -> (depth, parent_val)    def dfs(node, depth, parent):        if not node:            return        if node.val == x or node.val == y:            info[node.val] = (depth, parent.val if parent else None)        dfs(node.left, depth + 1, node)        dfs(node.right, depth + 1, node)    dfs(root, 0, None)    return (info[x][0] == info[y][0] and info[x][1] != info[y][1])