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

题目81：转置矩阵

问题描述：给你一个二维整数数组 matrix，返回 matrix 的转置矩阵。矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

解题思路：创建一个新的 n x m 矩阵（原矩阵为 m x n）。遍历原矩阵，将 matrix[i][j] 放到新矩阵的 [j][i] 位置。

Python代码示例：

1
2
3
4
5
6
7
def transpose(matrix):    m, n = len(matrix), len(matrix[0])    result = [[0] * m for _ in range(n)]    for i in range(m):        for j in range(n):            result[j][i] = matrix[i][j]    return result

题目82：旋转字符串

问题描述：给定两个字符串 s 和 goal。如果 s 在若干次旋转之后，能变为 goal，那么返回 true。否则，返回 false。旋转操作：将 s 最左边的字符移动到最右边。例如，若 s = 'abcde'，在旋转一次之后结果就是 'bcdea'。

解题思路：若 s 和 goal 长度不同，直接返回 False。将 s 与自身拼接得到 s + s，若 goal 是 s + s 的子串，则说明可以通过旋转得到。可直接使用字符串查找。

Python代码示例：

1
2
3
4
def rotateString(s, goal):    if len(s) != len(goal):        return False    return goal in (s + s)

题目83：卡牌分组

问题描述：给定一副牌，每张牌上都写着一个整数。此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

• • 每组都有 X 张牌。
• • 组内所有的牌上都写着相同的整数。

仅当你可选的 X >= 2 时返回 true。

解题思路：统计每种牌的数量，然后求所有数量的最大公约数 g。若 g >= 2，则可以分组，返回 True；否则返回 False。

Python代码示例：

1
2
3
4
5
6
7
8
9
from collections import Counterimport mathdef hasGroupsSizeX(deck):    count = Counter(deck)    g = 0    for v in count.values():        g = math.gcd(g, v)    return g >= 2

题目84：森林中的兔子

问题描述：森林中有未知数量的兔子。我们只知道一部分兔子给出了回答：每只兔子都回答了自己有多少只同色兔子的回答。给你一个数组 answers，其中 answers[i] 是第 i 只兔子的回答。请你根据这些回答，求出森林中兔子的最少数量。

解题思路：相同回答的兔子可能属于同一颜色组。若某只兔子回答 x，则说明与它同色的兔子共有 x + 1 只（包括自己），即每组最多有 x + 1 只兔子。对于回答 x 的兔子，若共有 count 只，则至少需要 ceil(count / (x + 1)) 个组，每组 x + 1 只兔子。累加所有组的总数即可。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
from collections import Counterimport mathdef numRabbits(answers):    count = Counter(answers)    total = 0    for x, c in count.items():        group_size = x + 1        groups = math.ceil(c / group_size)        total += groups * group_size    return total

题目85：最大三角形面积

问题描述：给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。点用二维坐标表示，例如 points = [[0,0],[0,1],[1,0],[0,2],[2,0]]。

解题思路：枚举所有三个点的组合，使用向量叉积计算三角形面积：area = 0.5 * abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))。维护最大面积。时间复杂度 O(n³)，适用于 n 较小的情况。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def largestTriangleArea(points):    n = len(points)    max_area = 0    for i in range(n):        for j in range(i + 1, n):            for k in range(j + 1, n):                x1, y1 = points[i]                x2, y2 = points[j]                x3, y3 = points[k]                area = abs(x1*(y2 - y3) + x2*(y3 - y1) + x3*(y1 - y2)) / 2                max_area = max(max_area, area)    return max_area

题目86：汉明距离

问题描述：两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

解题思路：先计算 x ^ y，结果中为 1 的二进制位就是 x 和 y 对应位不同的位置。然后统计异或结果中 1 的个数。常用技巧是 n & (n - 1) 每次消除最低位的 1，直到 n 为 0。

Python代码示例：

1
2
3
4
5
6
7
def hammingDistance(x, y):    n = x ^ y    count = 0    while n:        n &= n - 1        count += 1    return count

题目87：数组的度

问题描述：给定一个非空且只包含非负数的整数数组 nums，数组的度定义为数组里任一元素出现频数的最大值。你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

解题思路：用哈希表记录每个元素第一次出现的位置、最后一次出现的位置以及出现次数。先求出数组的度 degree，然后遍历所有出现次数等于 degree 的元素，计算它们第一次和最后一次出现位置构成的子数组长度，取最小值。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def findShortestSubArray(nums):    first = {}    last = {}    count = {}    for i, num in enumerate(nums):        if num not in first:            first[num] = i        last[num] = i        count[num] = count.get(num, 0) + 1    degree = max(count.values())    min_len = len(nums)    for num in count:        if count[num] == degree:            min_len = min(min_len, last[num] - first[num] + 1)    return min_len

题目88：托普利茨矩阵

问题描述：给你一个 m x n 的矩阵 matrix。如果这个矩阵是托普利茨矩阵，返回 true；否则，返回 false。如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是托普利茨矩阵。

解题思路：遍历矩阵中除第一行和第一列以外的每个元素 matrix[i][j]，检查它是否等于其左上方的元素 matrix[i-1][j-1]。若存在不相等的情况，则返回 False；遍历结束返回 True。

Python代码示例：

1
2
3
4
5
6
7
def isToeplitzMatrix(matrix):    m, n = len(matrix), len(matrix[0])    for i in range(1, m):        for j in range(1, n):            if matrix[i][j] != matrix[i - 1][j - 1]:                return False    return True

题目89：单调数列

问题描述：如果数组是单调递增或单调递减的，那么它是单调的。如果对于所有 i <= j，nums[i] <= nums[j]，那么数组 nums 是单调递增的。如果对于所有 i <= j，nums[i] >= nums[j]，那么数组 nums 是单调递减的。当给定的数组 nums 是单调数组时返回 true，否则返回 false。

解题思路：一次遍历，同时维护两个布尔变量 increasing 和 decreasing，初始都为 True。遍历相邻元素，若 nums[i] > nums[i+1]，则 increasing = False；若 nums[i] < nums[i+1]，则 decreasing = False。最终返回 increasing or decreasing。

Python代码示例：

1
2
3
4
5
6
7
8
def isMonotonic(nums):    increasing = decreasing = True    for i in range(len(nums) - 1):        if nums[i] > nums[i + 1]:            increasing = False        if nums[i] < nums[i + 1]:            decreasing = False    return increasing or decreasing

题目90：公平的糖果交换

问题描述：爱丽丝和鲍勃拥有不同总数的糖果。给你两个数组：aliceSizes 和 bobSizes，其中 aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量，bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。两人想要交换一盒糖果，使得交换后他们拥有相同的糖果总数。返回一个整数数组 answer，其中 answer[0] 是爱丽丝必须交换的糖果盒中的糖果数量，answer[1] 是鲍勃必须交换的糖果盒中的糖果数量。如果有多个答案，你可以返回其中任何一个。保证答案存在。

解题思路：设爱丽丝的糖果总数为 sumA，鲍勃的糖果总数为 sumB。若爱丽丝给出 x，鲍勃给出 y，交换后满足：sumA - x + y = sumB - y + x，化简得 y = x + (sumB - sumA) / 2。用集合存储鲍勃的糖果数量，遍历爱丽丝的糖果 x，检查 x + diff 是否在鲍勃的集合中，其中 diff = (sumB - sumA) // 2。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
def fairCandySwap(aliceSizes, bobSizes):    sumA = sum(aliceSizes)    sumB = sum(bobSizes)    diff = (sumB - sumA) // 2    bob_set = set(bobSizes)    for x in aliceSizes:        y = x + diff        if y in bob_set:            return [x, y]    return []