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

题目61：无重叠区间

问题描述：给定一个区间的集合 intervals，其中 intervals[i] = [starti, endi]。返回需要移除区间的最小数量，使剩余区间互不重叠。

解题思路：贪心。按区间的结束位置升序排序。遍历区间，维护上一个不重叠区间的结束位置 end。若当前区间的起始位置小于 end，说明重叠，需要移除当前区间（保留结束更早的），移除计数加一；否则更新 end 为当前区间的结束位置。最终移除数量即为答案。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
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

题目62：插入区间

问题描述：给你一个无重叠的，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束。在列表中插入一个新的区间 newInterval = [start, end]，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

解题思路：一次遍历。将区间分为三部分：

1. 1. 所有结束位置小于 newInterval 起始位置的区间，直接加入结果。
2. 2. 与 newInterval 重叠的区间，合并到 newInterval 中（更新起始和结束）。
3. 3. 剩余区间直接加入结果。注意合并时更新 newInterval 的边界。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def insert(intervals, newInterval):    result = []    i = 0    n = len(intervals)    # 添加所有在 newInterval 左侧且不重叠的区间    while i < n and intervals[i][1] < newInterval[0]:        result.append(intervals[i])        i += 1    # 合并重叠区间    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)    # 添加剩余区间    while i < n:        result.append(intervals[i])        i += 1    return result

题目63：复原 IP 地址

问题描述：有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0）组成，整数之间用 '.' 分隔。给定一个只包含数字的字符串 s，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

解题思路：回溯法。将问题视为在字符串中插入三个点，分成四段。递归函数 backtrack(start, path)，start 表示当前处理到的位置，path 存储已分割的段。每段长度 1 到 3，且数值在 0-255 之间，不能有前导 0（除非段本身是 "0"）。当 path 有 4 段且 start == len(s) 时，加入结果。

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
def restoreIpAddresses(s):    result = []    n = len(s)    def backtrack(start, path):        if len(path) == 4:            if start == n:                result.append('.'.join(path))            return        # 剪枝：剩余字符不足以或过多        if n - start < 4 - len(path) or n - start > 3 * (4 - len(path)):            return        for length in range(1, 4):            if start + length > n:                break            segment = s[start:start + length]            if (len(segment) > 1 and segment[0] == '0') or int(segment) > 255:                continue            path.append(segment)            backtrack(start + length, path)            path.pop()    backtrack(0, [])    return result

题目64：子集 II

问题描述：给你一个整数数组 nums，其中可能包含重复元素。请你返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。

解题思路：回溯 + 排序去重。先对数组排序，使相同元素相邻。递归时传入起始下标 start，每次从 start 开始选择元素。若当前元素与前一个元素相同且前一个元素未被使用（即在同一层递归中），则跳过，避免重复子集。每进入一次递归，都将当前路径加入结果（因为所有节点都是子集）。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def subsetsWithDup(nums):    nums.sort()    result = []    def backtrack(start, path):        result.append(path[:])        for i in range(start, len(nums)):            if i > start and nums[i] == nums[i - 1]:                continue            path.append(nums[i])            backtrack(i + 1, path)            path.pop()    backtrack(0, [])    return result

题目65：最长公共子串

问题描述：给定两个字符串 text1 和 text2，返回它们的最长公共子串的长度。子串是连续的子序列。

解题思路：动态规划。设 dp[i][j] 表示以 text1[i-1] 和 text2[j-1] 结尾的最长公共子串长度。若 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = 0。遍历过程中记录最大值。可用一维数组滚动优化空间。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def longestCommonSubstring(text1, text2):    m, n = len(text1), len(text2)    dp = [0] * (n + 1)    max_len = 0    for i in range(1, m + 1):        for j in range(n, 0, -1):            if text1[i - 1] == text2[j - 1]:                dp[j] = dp[j - 1] + 1                max_len = max(max_len, dp[j])            else:                dp[j] = 0    return max_len

题目66：比较版本号

问题描述：给你两个版本号 version1 和 version2，请你比较它们。版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由多位数字组成，可能包含前导零。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0，下一个修订号下标为 1，以此类推。比较规则：

• • 如果 version1 > version2 返回 1；
• • 如果 version1 < version2 返回 -1；
• • 否则返回 0。

解题思路：将两个版本号按 '.' 分割成修订号列表。逐个比较对应位置的修订号，若某个列表较短，则缺失部分视为 0。比较时忽略前导零，转为整数比较即可。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def compareVersion(version1, version2):    v1 = version1.split('.')    v2 = version2.split('.')    n1, n2 = len(v1), len(v2)    for i in range(max(n1, n2)):        num1 = int(v1[i]) if i < n1 else 0        num2 = int(v2[i]) if i < n2 else 0        if num1 > num2:            return 1        elif num1 < num2:            return -1    return 0

题目67：分数到小数

问题描述：给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。如果小数部分为循环小数，则将循环的部分括在括号内。如果存在多个答案，只需返回任意一个。对于所有给定的输入，保证答案字符串的长度小于 10^4。

解题思路：模拟长除法。先处理整数部分，然后处理小数部分。用哈希表记录每个余数出现的位置，若余数重复出现，说明出现了循环节。将循环部分用括号括起来。注意处理正负号。

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 fractionToDecimal(numerator, denominator):    if numerator == 0:        return "0"    result = []    if (numerator < 0) ^ (denominator < 0):        result.append('-')    num, den = abs(numerator), abs(denominator)    result.append(str(num // den))    remainder = num % den    if remainder == 0:        return ''.join(result)    result.append('.')    seen = {}    while remainder:        if remainder in seen:            result.insert(seen[remainder], '(')            result.append(')')            break        seen[remainder] = len(result)        remainder *= 10        result.append(str(remainder // den))        remainder %= den    return ''.join(result)

题目68：有效数字

问题描述：有效数字（按顺序）可以分成以下几个部分：

1. 1. 一个 小数 或者 整数
2. 2. （可选）一个 'e' 或 'E'，后面跟着一个 整数

小数（按顺序）可以分成以下几个部分：

1. 1. （可选）一个符号字符（'+' 或 '-'）
2. 2. 下述格式之一：
• • 至少一位数字，后面跟着一个点 '.'
• • 至少一位数字，后面跟着一个点 '.'，后面再跟着至少一位数字
• • 一个点 '.'，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

1. 1. （可选）一个符号字符（'+' 或 '-'）
2. 2. 至少一位数字

给定一个字符串 s，判断它是否是一个有效数字。

解题思路：有限状态机（DFA）或正则表达式。使用正则表达式匹配：^[+-]?(\d+\.?\d*|\.\d+)([eE][+-]?\d+)?$。注意处理边界情况，如 . 和 e 不能单独出现。

Python代码示例：

1
2
3
4
5
import redef isNumber(s):    pattern = r'^[+-]?(\d+\.?\d*|\.\d+)([eE][+-]?\d+)?$'    return bool(re.match(pattern, s))

题目69：摆动排序 II

问题描述：给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。你可以假设所有输入数组都可以得到满足题目要求的结果。

解题思路：先对数组排序，然后将其分为较小的一半和较大的一半。为了避免相邻元素相等导致不满足摆动条件，需要将较小部分和较大部分交错放置，并且从后往前取元素。具体地：将排序后的数组分为 small = nums[:(n+1)//2] 和 large = nums[(n+1)//2:]，然后分别从末尾开始交替放入结果。

Python代码示例：

1
2
3
4
5
6
7
8
def wiggleSort(nums):    nums.sort()    n = len(nums)    mid = (n + 1) // 2    small = nums[:mid][::-1]    large = nums[mid:][::-1]    nums[::2] = small    nums[1::2] = large

题目70：递增的三元子序列

问题描述：给你一个整数数组 nums，判断这个数组中是否存在长度为 3 的递增子序列。如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k，使得 nums[i] < nums[j] < nums[k]，返回 true；否则，返回 false。

解题思路：贪心。维护两个变量 first 和 second，分别表示当前找到的最小值和第二小的值。遍历数组，若当前数大于 second，则找到了递增三元组，返回 True。若当前数小于等于 first，更新 first；否则若小于 second，更新 second。时间复杂度 O(n)，空间 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
def increasingTriplet(nums):    first = second = float('inf')    for num in nums:        if num <= first:            first = num        elif num <= second:            second = num        else:            return True    return False