网络安全技术练习题大全(29)
- 2026-11-09 00:09:19
题目81：在排序数组中查找元素的第一个和最后一个位置
问题描述：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例：
• 输入： nums = [5,7,7,8,8,10], target = 8• 输出： [3,4]• 输入： nums = [5,7,7,8,8,10], target = 6• 输出： [-1,-1]• 输入： nums = [], target = 0• 输出： [-1,-1]
解题思路：使用两次二分查找。第一次查找目标值的左边界：当 nums[mid] == target 时，不立即返回，而是继续向左收缩 right = mid - 1，并记录当前位置。第二次查找目标值的右边界：当 nums[mid] == target 时，继续向右收缩 left = mid + 1，并记录当前位置。两次查找的时间复杂度均为 O(log n)。
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 25 26 27 28 29 30 def searchRange(nums, target): def find_left(): left, right = 0, len(nums) - 1 index = -1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: index = mid right = mid - 1 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return index def find_right(): left, right = 0, len(nums) - 1 index = -1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: index = mid left = mid + 1 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return index return [find_left(), find_right()]
题目82：搜索二维矩阵
问题描述：给你一个满足下述两条属性的 m x n 整数矩阵 matrix：
1. 每行中的整数从左到右按非严格递增顺序排列； 2. 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target，如果 target 在矩阵中，返回 true；否则，返回 false。
示例：
• 输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3• 输出： true• 输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13• 输出： false
解题思路：将二维矩阵视为一个长度为 m * n 的一维有序数组。使用二分查找，中间位置 mid 对应矩阵中的 matrix[mid // n][mid % n]。比较该值与 target，调整左右边界。时间复杂度 O(log(m * n))，空间复杂度 O(1)。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False m, n = len(matrix), len(matrix[0]) left, right = 0, m * n - 1 while left <= right: mid = (left + right) // 2 mid_val = matrix[mid // n][mid % n] if mid_val == target: return True elif mid_val < target: left = mid + 1 else: right = mid - 1 return False
题目83：寻找峰值
问题描述：峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。你必须实现时间复杂度为 O(log n) 的算法。
示例：
• 输入： nums = [1,2,3,1]，输出：2• 解释： 3是峰值元素，返回索引2。• 输入： nums = [1,2,1,3,5,6,4]，输出：5（或1）• 解释：函数可以返回索引 1或5。
解题思路：使用二分查找。维护左右指针 left 和 right，每次取中间位置 mid。如果 nums[mid] < nums[mid + 1]，说明峰值在右侧，令 left = mid + 1；否则峰值在左侧或就是 mid，令 right = mid。最终 left == right，返回 left。时间复杂度 O(log n)，空间复杂度 O(1)。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 def findPeakElement(nums): left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 if nums[mid] < nums[mid + 1]: left = mid + 1 else: right = mid return left
题目84：长度最小的子数组
问题描述：给定一个含有 n 个正整数的数组 nums 和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
• 输入： target = 7, nums = [2,3,1,2,4,3]• 输出： 2• 解释：子数组 [4,3]是该条件下的长度最小的子数组。• 输入： target = 4, nums = [1,4,4]• 输出： 1• 输入： target = 11, nums = [1,1,1,1,1,1,1,1]• 输出： 0
解题思路：使用滑动窗口。维护左右指针 left 和 right，以及窗口内元素之和 window_sum。右指针不断右移，将 nums[right] 加入窗口和；当 window_sum >= target 时，更新最小长度，并尝试右移左指针缩小窗口，直到窗口和小于 target。时间复杂度 O(n)，空间复杂度 O(1)。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def minSubArrayLen(target, nums): left = 0 window_sum = 0 min_len = float('inf') for right in range(len(nums)): window_sum += nums[right] while window_sum >= target: min_len = min(min_len, right - left + 1) window_sum -= nums[left] left += 1 return min_len if min_len != float('inf') else 0
题目85：无重复字符的最长子串
问题描述：给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
示例：
• 输入： s = "abcabcbb"• 输出： 3• 解释：因为无重复字符的最长子串是 "abc"，所以其长度为3。• 输入： s = "bbbbb"• 输出： 1• 解释：因为无重复字符的最长子串是 "b"，所以其长度为1。• 输入： s = "pwwkew"• 输出： 3• 解释：因为无重复字符的最长子串是 "wke"，所以其长度为3。注意答案必须是子串，"pwke"是子序列，不是子串。
解题思路：使用滑动窗口 + 哈希集合。维护左右指针 left 和 right，以及一个集合 window 记录当前窗口内的字符。右指针不断右移，如果遇到重复字符，则移动左指针直到重复字符被移出窗口。每次更新最大长度。时间复杂度 O(n)，空间复杂度 O(min(n, 字符集大小))。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 def lengthOfLongestSubstring(s): window = set() left = 0 max_len = 0 for right in range(len(s)): while s[right] in window: window.remove(s[left]) left += 1 window.add(s[right]) max_len = max(max_len, right - left + 1) return max_len
题目86：轮转数组
问题描述：给你一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例：
• 输入： nums = [1,2,3,4,5,6,7], k = 3• 输出： [5,6,7,1,2,3,4]• 解释： • 向右轮转 1 步： [7,1,2,3,4,5,6]• 向右轮转 2 步： [6,7,1,2,3,4,5]• 向右轮转 3 步： [5,6,7,1,2,3,4]
解题思路：使用三次翻转，空间复杂度 O(1)。
1. 先将整个数组翻转，得到 [7,6,5,4,3,2,1]；2. 翻转前 k个元素，得到[5,6,7,4,3,2,1]；3. 翻转后 n-k个元素，得到[5,6,7,1,2,3,4]。注意k可能大于数组长度，需要先对n取模。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 def rotate(nums, k): n = len(nums) k %= n def reverse(start, end): while start < end: nums[start], nums[end] = nums[end], nums[start] start += 1 end -= 1 reverse(0, n - 1) reverse(0, k - 1) reverse(k, n - 1)
题目87：删除排序数组中的重复项 II
问题描述：给你一个有序数组 nums，请你原地删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例：
• 输入： nums = [1,1,1,2,2,3]• 输出： 5, nums = [1,1,2,2,3]• 解释：函数应返回新长度 5，并且原数组的前五个元素被修改为1,1,2,2,3。• 输入： nums = [0,0,1,1,1,1,2,3,3]• 输出： 7, nums = [0,0,1,1,2,3,3]
解题思路：使用双指针。slow 指向新数组的末尾，fast 用于遍历。同时维护一个计数器 count 记录当前元素出现的次数。遍历时，如果 nums[fast] == nums[slow-1] 且 count >= 2，则跳过；否则将 nums[fast] 写入 nums[slow]，并更新 slow 和 count。时间复杂度 O(n)，空间复杂度 O(1)。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 def removeDuplicates(nums): if len(nums) <= 2: return len(nums) slow = 2 for fast in range(2, len(nums)): if nums[fast] != nums[slow - 2]: nums[slow] = nums[fast] slow += 1 return slow
题目88：无重叠区间
问题描述：给定一个区间的集合 intervals，其中 intervals[i] = [starti, endi]。返回需要移除区间的最小数量，使剩余区间互不重叠。
示例：
• 输入： intervals = [[1,2],[2,3],[3,4],[1,3]]• 输出： 1• 解释：移除 [1,3]后，剩下的区间没有重叠。• 输入： intervals = [[1,2],[1,2],[1,2]]• 输出： 2• 输入： intervals = [[1,2],[2,3]]• 输出： 0
解题思路：贪心算法。要使移除的区间最少，等价于保留尽可能多的不重叠区间。按照区间的右端点升序排序。遍历排序后的区间，维护上一个选中区间的结束位置 end。如果当前区间的起始位置 start >= end，说明不重叠，可以保留，并更新 end = 当前区间的结束位置；否则需要移除该区间，计数器加一。最终返回移除的区间数量。时间复杂度 O(n log n)，空间复杂度 O(1)。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def eraseOverlapIntervals(intervals): if not intervals: return 0 intervals.sort(key=lambda x: x[1]) count = 0 end = intervals[0][1] for start, finish in intervals[1:]: if start < end: count += 1 else: end = finish return count
题目89：划分字母区间
问题描述：给你一个字符串 s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s。返回一个表示每个字符串片段的长度的列表。
示例：
• 输入： s = "ababcbacadefegdehijhklij"• 输出： [9,7,8]• 解释： • 划分结果为 "ababcbaca"、"defegde"、"hijhklij"。• 每个字母最多出现在一个片段中。 • 输入： s = "eccbbbbdec"• 输出： [10]
解题思路：贪心 + 哈希表。先遍历字符串，记录每个字符最后出现的位置 last[char]。再次遍历字符串，维护当前片段的起始位置 start 和结束位置 end。对于当前字符，更新 end = max(end, last[char])。当遍历位置 i == end 时，说明当前片段可以划分，记录长度 end - start + 1，并更新 start = i + 1。时间复杂度 O(n)，空间复杂度 O(1)（字符集固定为小写字母）。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 def partitionLabels(s): last = {char: i for i, char in enumerate(s)} result = [] start = 0 end = 0 for i, char in enumerate(s): end = max(end, last[char]) if i == end: result.append(end - start + 1) start = i + 1 return result
题目90：插入区间
问题描述：给你一个无重叠的、按照区间起始端点排序的区间列表 intervals。在列表中插入一个新的区间 newInterval，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例：
• 输入： intervals = [[1,3],[6,9]], newInterval = [2,5]• 输出： [[1,5],[6,9]]• 输入： intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]• 输出： [[1,2],[3,10],[12,16]]• 解释：新区间 [4,8]与[3,5]、[6,7]、[8,10]重叠，合并为[3,10]。
解题思路：遍历区间列表，分三个阶段处理：
1. 将所有结束位置小于新区间起始位置的区间直接加入结果； 2. 合并所有与新区间重叠的区间：不断更新新区间的起始和结束位置，直到当前区间的起始位置大于新区间的结束位置； 3. 将剩余区间加入结果。时间复杂度 O(n)，空间复杂度 O(n)（结果存储）。
Python代码示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def insert(intervals, newInterval): result = [] i = 0 n = len(intervals) # 1. 添加所有在 newInterval 左侧且不重叠的区间 while i < n and intervals[i][1] < newInterval[0]: result.append(intervals[i]) i += 1 # 2. 合并重叠区间 while i < n and intervals[i][0] <= newInterval[1]: newInterval[0] = min(newInterval[0], intervals[i][0]) newInterval[1] = max(newInterval[1], intervals[i][1]) i += 1 result.append(newInterval) # 3. 添加剩余区间 while i < n: result.append(intervals[i]) i += 1 return result
