网络安全技术练习题大全(22)

题目11：寻找数组的中心下标

问题描述：给你一个整数数组 nums，请计算数组的中心下标。数组中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。如果中心下标位于数组最左端，那么左侧数之和视为 0，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标，返回 -1。

示例：

• • 输入：nums = [1, 7, 3, 6, 5, 6]，输出：3
• • 解释：中心下标是 3。左侧数之和 1 + 7 + 3 = 11，右侧数之和 5 + 6 = 11，二者相等。
• • 输入：nums = [1, 2, 3]，输出：-1
• • 输入：nums = [2, 1, -1]，输出：0

解题思路：先计算数组的总和 total。然后遍历数组，维护一个变量 left_sum 表示当前下标左侧的元素之和。对于下标 i，右侧元素之和为 total - left_sum - nums[i]。如果 left_sum == total - left_sum - nums[i]，则 i 就是中心下标，直接返回。否则将 nums[i] 累加到 left_sum 中，继续遍历。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
def pivotIndex(nums):    total = sum(nums)    left_sum = 0    for i, num in enumerate(nums):        if left_sum == total - left_sum - num:            return i        left_sum += num    return -1

题目12：至少是其他数字两倍的最大数

问题描述：给你一个整数数组 nums，其中总是存在唯一的一个最大整数。请你找出数组中的最大元素并检查它是否至少是数组中每个其他数字的两倍。如果是，则返回最大元素的下标，否则返回 -1。

示例：

• • 输入：nums = [3, 6, 1, 0]，输出：1
• • 解释：6 是最大的整数，对于数组中的其他整数，6 大于数组中其他元素的两倍。6 的下标是 1，所以返回 1。
• • 输入：nums = [1, 2, 3, 4]，输出：-1
• • 解释：4 没有超过 3 的两倍，所以返回 -1。

解题思路：一次遍历找到最大值 max_val 及其下标 max_index，同时找到第二大的值 second_max。然后判断 max_val >= 2 * second_max 是否成立。如果成立，返回 max_index；否则返回 -1。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def dominantIndex(nums):    max_val = -1    max_index = -1    second_max = -1    for i, num in enumerate(nums):        if num > max_val:            second_max = max_val            max_val = num            max_index = i        elif num > second_max:            second_max = num    return max_index if max_val >= 2 * second_max else -1

题目13：托普利茨矩阵

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

示例：

• • 输入：matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]，输出：true
• • 解释：在上述矩阵中，其左上到右下的对角线分别为 [1,2,3,4]、[5,1,2,3]、[9,5,1,2]，每条对角线上的元素都相同。
• • 输入：matrix = [[1,2],[2,2]]，输出：false

解题思路：遍历矩阵中除最后一行和最后一列以外的所有元素。对于每个元素 matrix[i][j]，检查它是否等于其右下方的元素 matrix[i+1][j+1]。如果所有元素都满足，则返回 true；否则返回 false。时间复杂度 O(m * n)，空间复杂度 O(1)。

Python代码示例：

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

题目14：图像渲染

问题描述：有一幅以 m x n 的二维整数数组表示的图画 image，其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr、sc 和 color。你需要从坐标 (sr, sc) 开始对图像进行上色填充。为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 color。最后返回经过上色渲染后的图像。

示例：

• • 输入：image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, color = 2
• • 输出：[[2,2,2],[2,2,0],[2,0,1]]

解题思路：使用深度优先搜索（DFS）或广度优先搜索（BFS）。记录起始像素的原始颜色 original_color。如果 original_color == color，直接返回原图像，避免死循环。从 (sr, sc) 开始，将其颜色改为 color，然后递归访问上下左右四个相邻像素，如果相邻像素的颜色等于 original_color，则继续修改并递归。时间复杂度 O(m * n)，空间复杂度 O(m * n)（递归栈）。

Python代码示例（DFS）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def floodFill(image, sr, sc, color):    original_color = image[sr][sc]    if original_color == color:        return image    rows, cols = len(image), len(image[0])    def dfs(r, c):        if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != original_color:            return        image[r][c] = color        dfs(r + 1, c)        dfs(r - 1, c)        dfs(r, c + 1)        dfs(r, c - 1)    dfs(sr, sc)    return image

题目15：岛屿的周长

问题描述：给定一个 row x col 的二维网格地图 grid，其中 grid[i][j] = 1 表示陆地，grid[i][j] = 0 表示水域。网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。岛屿中没有“湖”（“湖”指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100。计算这个岛屿的周长。

示例：

• • 输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
• • 输出：16

解题思路：遍历整个网格，对于每个陆地格子 grid[i][j] == 1，初始周长贡献为 4。然后检查其上下左右四个相邻格子，如果相邻格子也是陆地，则每有一个相邻陆地，周长减 2（因为相邻的边被共享了）。将所有陆地格子的贡献相加即为岛屿的周长。时间复杂度 O(m * n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def islandPerimeter(grid):    rows, cols = len(grid), len(grid[0])    perimeter = 0    for i in range(rows):        for j in range(cols):            if grid[i][j] == 1:                perimeter += 4                if i > 0 and grid[i - 1][j] == 1:                    perimeter -= 2                if j > 0 and grid[i][j - 1] == 1:                    perimeter -= 2    return perimeter

题目16：数组拆分 I

问题描述：给定长度为 2n 的整数数组 nums，你的任务是将这些数分成 n 对，例如 (a1, b1), (a2, b2), ..., (an, bn)，使得从 1 到 n 的 min(ai, bi) 总和最大。返回该最大总和。

示例：

• • 输入：nums = [1,4,3,2]
• • 输出：4
• • 解释：所有可能的分法（忽略元素顺序）为：
• • (1,4), (2,3) -> min(1,4) + min(2,3) = 1 + 2 = 3
• • (1,3), (2,4) -> min(1,3) + min(2,4) = 1 + 2 = 3
• • (1,2), (3,4) -> min(1,2) + min(3,4) = 1 + 3 = 4最大总和为 4。

解题思路：将数组排序后，相邻两个数组成一对，这样每对的最小值就是较小的那个数。为了使总和最大，应该让较小的数尽可能大，因此排序后取下标为偶数的元素（即第 0、2、4... 个）相加即可。时间复杂度 O(n log n)，空间复杂度 O(1)（不考虑排序所需空间）。

Python代码示例：

1
2
3
def arrayPairSum(nums):    nums.sort()    return sum(nums[::2])

题目17：翻转图像

问题描述：给定一个 n x n 的二进制矩阵 image，先水平翻转图像，然后反转图像并返回结果。

• • 水平翻转图像：将图像每一行左右翻转。
• • 反转图像：将图像中的 0 全部替换为 1，1 全部替换为 0。

示例：

• • 输入：image = [[1,1,0],[1,0,1],[0,0,0]]
• • 输出：[[1,0,0],[0,1,0],[1,1,1]]
• • 解释：
• • 水平翻转：[[0,1,1],[1,0,1],[0,0,0]]
• • 反转：[[1,0,0],[0,1,0],[1,1,1]]

解题思路：遍历每一行，使用双指针同时从两端向中间移动。交换左右元素后，再分别对两个元素取反（1 - x）。如果左右指针相遇（奇数长度），则只对中间元素取反。时间复杂度 O(n²)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
def flipAndInvertImage(image):    for row in image:        left, right = 0, len(row) - 1        while left <= right:            row[left], row[right] = 1 - row[right], 1 - row[left]            left += 1            right -= 1    return image

题目18：最大三角形面积

问题描述：给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。

示例：

• • 输入：points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
• • 输出：2.0
• • 解释：最大的三角形由 (0,0), (0,2), (2,0) 组成，面积为 2.0。

解题思路：三角形的面积可以通过叉积计算：给定三个点 A(x1,y1), B(x2,y2), C(x3,y3)，面积 = 0.5 * |x1(y2-y3) + x2(y3-y1) + x3(y1-y2)|。遍历所有可能的三点组合，计算面积并记录最大值。点数 n 通常较小，三重循环 O(n³) 可接受。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def largestTriangleArea(points):    max_area = 0    n = len(points)    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.0                max_area = max(max_area, area)    return max_area

题目19：单调数列

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

示例：

• • 输入：nums = [1,2,2,3]，输出：true
• • 输入：nums = [6,5,4,4]，输出：true
• • 输入：nums = [1,3,2]，输出：false

解题思路：一次遍历。维护两个布尔变量 increasing 和 decreasing，初始均为 True。遍历数组，如果当前元素大于前一个元素，则 decreasing = False；如果当前元素小于前一个元素，则 increasing = False。遍历结束后，只要 increasing 或 decreasing 有一个为 True，则返回 True。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

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

题目20：非递减数列

问题描述：给你一个长度为 n 的整数数组 nums，请你判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。我们是这样定义一个非递减数列的：对于数组中所有的 i（0 <= i <= n-2），总满足 nums[i] <= nums[i + 1]。

示例：

• • 输入：nums = [4,2,3]，输出：true
• • 解释：你可以通过把第一个 4 变成 1 来使数组变成非递减数列。
• • 输入：nums = [4,2,1]，输出：false

解题思路：遍历数组，当发现 nums[i] > nums[i+1] 时，说明出现了一个“下降”。如果下降次数超过 1 次，直接返回 False。对于唯一的下降位置，有两种修改方式：

• • 将 nums[i] 改小，使其 <= nums[i+1]，即 nums[i] = nums[i+1]；
• • 将 nums[i+1] 改大，使其 >= nums[i]，即 nums[i+1] = nums[i]。需要检查修改后是否满足非递减。通常优先修改 nums[i]，但如果 i > 0 且 nums[i-1] > nums[i+1]，则必须修改 nums[i+1] 为 nums[i]。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def checkPossibility(nums):    count = 0    for i in range(len(nums) - 1):        if nums[i] > nums[i + 1]:            count += 1            if count > 1:                return False            if i > 0 and nums[i - 1] > nums[i + 1]:                nums[i + 1] = nums[i]            else:                nums[i] = nums[i + 1]    return True