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

题目51：搜索插入位置

问题描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

示例：

• • 输入：nums = [1,3,5,6], target = 5，输出：2
• • 输入：nums = [1,3,5,6], target = 2，输出：1
• • 输入：nums = [1,3,5,6], target = 7，输出：4
• • 输入：nums = [1,3,5,6], target = 0，输出：0

解题思路：使用二分查找。维护左右指针 left 和 right，当 left <= right 时，计算中间位置 mid。如果 nums[mid] == target，直接返回 mid；如果 nums[mid] < target，说明目标在右侧，令 left = mid + 1；否则目标在左侧，令 right = mid - 1。循环结束时，left 即为目标应插入的位置。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
def searchInsert(nums, target):    left, right = 0, len(nums) - 1    while left <= right:        mid = (left + right) // 2        if nums[mid] == target:            return mid        elif nums[mid] < target:            left = mid + 1        else:            right = mid - 1    return left

题目52：数组的相对排序

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

示例：

• • 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
• • 输出：[2,2,2,1,4,3,3,9,6,7,19]

解题思路：使用计数排序。由于元素范围有限（0 <= arr1[i] <= 1000），可以创建一个长度为 1001 的计数数组。先统计 arr1 中每个元素的出现次数。然后按照 arr2 的顺序，将对应元素按出现次数加入结果数组。最后遍历计数数组，将剩余未在 arr2 中出现的元素按升序加入结果。时间复杂度 O(n + m + k)，空间复杂度 O(k)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def relativeSortArray(arr1, arr2):    count = [0] * 1001    for num in arr1:        count[num] += 1    result = []    for num in arr2:        result.extend([num] * count[num])        count[num] = 0    for num in range(1001):        if count[num] > 0:            result.extend([num] * count[num])    return result

题目53：删除最外层的括号

问题描述：有效括号字符串为空 ""、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""、"()"、"(())()" 和 "(()(()))" 都是有效的括号字符串。如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语，其中 A 和 B 都是非空有效括号字符串。给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P1 + P2 + ... + Pk，其中 Pi 是有效括号字符串原语。对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s。

示例：

• • 输入：s = "(()())(())"，输出："()()()"
• • 解释：输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，删除每个部分的最外层括号后得到 "()()" + "()" = "()()()"。
• • 输入：s = "(()())(())(()(()))"，输出："()()()()(())"

解题思路：使用一个计数器 balance 记录当前括号的嵌套深度。遍历字符串，遇到 '(' 时 balance += 1，如果 balance > 1，说明不是最外层括号，将其加入结果。遇到 ')' 时，如果 balance > 1，说明不是最外层括号，将其加入结果，然后 balance -= 1。时间复杂度 O(n)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def removeOuterParentheses(s):    result = []    balance = 0    for char in s:        if char == '(':            if balance > 0:                result.append(char)            balance += 1        else:            balance -= 1            if balance > 0:                result.append(char)    return ''.join(result)

题目54：整数的各位积和之差

问题描述：给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。

示例：

• • 输入：n = 234，输出：15
• • 解释：
• • 各位数之积 = 2 * 3 * 4 = 24
• • 各位数之和 = 2 + 3 + 4 = 9
• • 结果 = 24 - 9 = 15
• • 输入：n = 4421，输出：21
• • 解释：
• • 各位数之积 = 4 * 4 * 2 * 1 = 32
• • 各位数之和 = 4 + 4 + 2 + 1 = 11
• • 结果 = 32 - 11 = 21

解题思路：不断取 n 的末位数字，分别累加到乘积和和中，然后 n //= 10。最后返回乘积减去和。时间复杂度 O(log n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
def subtractProductAndSum(n):    product = 1    total = 0    while n > 0:        digit = n % 10        product *= digit        total += digit        n //= 10    return product - total

题目55：统计位数为偶数的数字

问题描述：给你一个整数数组 nums，请你返回其中位数为偶数的数字的个数。

示例：

• • 输入：nums = [12,345,2,6,7896]，输出：2
• • 解释：
• • 12 是 2 位数字（位数为偶数）
• • 345 是 3 位数字（位数为奇数）
• • 2 是 1 位数字（位数为奇数）
• • 6 是 1 位数字（位数为奇数）
• • 7896 是 4 位数字（位数为偶数）因此只有 12 和 7896 是位数为偶数的数字。
• • 输入：nums = [555,901,482,1771]，输出：1
• • 解释：只有 1771 是 4 位数字。

解题思路：遍历数组，对于每个数字，将其转换为字符串并检查长度是否为偶数，或者通过不断除以 10 计算位数。统计满足条件的数字个数。时间复杂度 O(n * log m)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
def findNumbers(nums):    count = 0    for num in nums:        if len(str(num)) % 2 == 0:            count += 1    return count

题目56：有效的山脉数组

问题描述：给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。有效的山脉数组满足：

• • arr.length >= 3
• • 存在下标 i（0 < i < arr.length - 1），使得：
• • arr[0] < arr[1] < ... < arr[i-1] < arr[i]
• • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

示例：

• • 输入：arr = [2,1]，输出：false
• • 输入：arr = [3,5,5]，输出：false
• • 输入：arr = [0,3,2,1]，输出：true

解题思路：使用双指针。左指针从数组开头向右移动，直到不再严格递增；右指针从数组末尾向左移动，直到不再严格递减。如果两个指针相遇于同一个位置，且该位置不是数组的第一个或最后一个元素，则说明存在唯一的峰值，返回 True；否则返回 False。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def validMountainArray(arr):    n = len(arr)    if n < 3:        return False    left = 0    while left + 1 < n and arr[left] < arr[left + 1]:        left += 1    right = n - 1    while right - 1 >= 0 and arr[right - 1] > arr[right]:        right -= 1    return left == right and left != 0 and right != n - 1

题目57：按奇偶排序数组

问题描述：给定一个非负整数数组 nums，返回一个数组，在该数组中，nums 的所有偶数元素之后跟着所有奇数元素。你可以返回任何满足此条件的数组作为答案。

示例：

• • 输入：nums = [3,1,2,4]
• • 输出：[2,4,3,1]（也接受 [4,2,1,3]、[2,4,1,3] 等）

解题思路：使用双指针。左指针 left 从左向右寻找奇数，右指针 right 从右向左寻找偶数。当 left < right 时，交换两个位置的元素，然后继续移动指针。最终所有偶数都在左侧，奇数都在右侧。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def sortArrayByParity(nums):    left, right = 0, len(nums) - 1    while left < right:        while left < right and nums[left] % 2 == 0:            left += 1        while left < right and nums[right] % 2 == 1:            right -= 1        if left < right:            nums[left], nums[right] = nums[right], nums[left]            left += 1            right -= 1    return nums

题目58：最小绝对差

问题描述：给你一个整数数组 arr，其中每个元素都不相同。请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。

示例：

• • 输入：arr = [4,2,1,3]
• • 输出：[[1,2],[2,3],[3,4]]
• • 输入：arr = [1,3,6,10,15]
• • 输出：[[1,3]]

解题思路：先将数组排序。最小绝对差一定出现在相邻元素之间。遍历排序后的数组，计算相邻元素的差值，记录最小差值 min_diff。再次遍历，将所有差值为 min_diff 的元素对加入结果列表。时间复杂度 O(n log n)，空间复杂度 O(1)（不考虑结果存储）。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def minimumAbsDifference(arr):    arr.sort()    min_diff = float('inf')    result = []    for i in range(1, len(arr)):        diff = arr[i] - arr[i - 1]        if diff < min_diff:            min_diff = diff            result = [[arr[i - 1], arr[i]]]        elif diff == min_diff:            result.append([arr[i - 1], arr[i]])    return result

题目59：自除数

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

示例：

• • 输入：left = 1, right = 22
• • 输出：[1,2,3,4,5,6,7,8,9,11,12,15,22]

解题思路：遍历区间 [left, right] 中的每个数。对于每个数，提取其每一位数字，如果存在 0 或者该数不能被某位数字整除，则不是自除数。否则将其加入结果列表。时间复杂度 O(n * log m)，空间复杂度 O(1)（不考虑结果存储）。

Python代码示例：

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

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

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

1
2
3
arr[0] + arr[1] + ... + arr[i] ==arr[i+1] + arr[i+2] + ... + arr[j] ==arr[j+1] + arr[j+2] + ... + arr[arr.length - 1]

就可以将数组三等分。

示例：

• • 输入：arr = [0,2,1,-6,6,-7,9,1,2,0,1]，输出：true
• • 解释：0 + 2 + 1 = 3，-6 + 6 - 7 + 9 + 1 = 3，2 + 0 + 1 = 3
• • 输入：arr = [0,2,1,-6,6,7,9,-1,2,0,1]，输出：false
• • 输入：arr = [3,3,6,5,-2,2,5,1,-9,4]，输出：true

解题思路：首先计算数组总和 total，如果 total % 3 != 0，直接返回 False。目标每部分的和为 target = total // 3。使用一次遍历，累加当前和 current_sum，每当 current_sum == target 时，计数器 count 加一，并将 current_sum 重置为 0。当 count == 2 时，说明已经找到了前两部分，剩余部分自然等于 target（因为总和是 3 的倍数），返回 True。注意：需要在找到两部分后确保剩余部分非空，但题目要求三个非空部分，遍历时只要 count == 2 且当前索引不是最后一个元素即可。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def canThreePartsEqualSum(arr):    total = sum(arr)    if total % 3 != 0:        return False    target = total // 3    count = 0    current_sum = 0    for i in range(len(arr) - 1):        current_sum += arr[i]        if current_sum == target:            count += 1            current_sum = 0            if count == 2:                return True    return False