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

题目21：最长连续递增序列

问题描述：给定一个未经排序的整数数组 nums，找到最长且连续递增的子序列，并返回该序列的长度。连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1]，那么子序列 nums[l:r+1] 就是连续递增子序列。

示例：

• • 输入：nums = [1,3,5,4,7]，输出：3
• • 解释：最长连续递增序列是 [1,3,5]，长度为 3。尽管 [1,3,5,7] 也是递增子序列，但它不连续。
• • 输入：nums = [2,2,2,2,2]，输出：1

解题思路：一次遍历。维护两个变量：current_len 记录当前连续递增序列的长度，max_len 记录历史最大长度。从第二个元素开始遍历，如果 nums[i] > nums[i-1]，则 current_len += 1；否则将 current_len 重置为 1。每次更新 max_len。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findLengthOfLCIS(nums):    if not nums:        return 0    max_len = 1    current_len = 1    for i in range(1, len(nums)):        if nums[i] > nums[i - 1]:            current_len += 1            max_len = max(max_len, current_len)        else:            current_len = 1    return max_len

题目22：两个列表的最小索引总和

问题描述：假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。如果答案不止一个，则返回所有答案且答案顺序不限。你可以假设答案总是存在。

示例：

• • 输入：

1
2
list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]

输出：["Shogun"]

• • 输入：

1
2
list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]list2 = ["KFC", "Shogun", "Burger King"]

输出：["Shogun"]（索引和最小为 1+0=1，而 KFC 为 3+0=3，Burger King 为 2+2=4）

解题思路：用一个哈希表记录 list1 中每个餐厅及其下标。遍历 list2，如果当前餐厅在哈希表中，计算索引和 i + hash[restaurant]。维护一个最小索引和 min_sum 和结果列表 result：

• • 如果当前索引和小于 min_sum，清空结果列表并加入当前餐厅，更新 min_sum；
• • 如果等于 min_sum，直接加入结果列表。时间复杂度 O(n + m)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findRestaurant(list1, list2):    index_map = {restaurant: i for i, restaurant in enumerate(list1)}    min_sum = float('inf')    result = []    for i, restaurant in enumerate(list2):        if restaurant in index_map:            total = i + index_map[restaurant]            if total < min_sum:                min_sum = total                result = [restaurant]            elif total == min_sum:                result.append(restaurant)    return result

题目23：七进制数

问题描述：给定一个整数 num，将其转化为 7 进制 并以字符串的形式返回。输入范围：-10^7 <= num <= 10^7。

示例：

• • 输入：num = 100，输出："202"
• • 输入：num = -7，输出："-10"

解题思路：处理符号：如果 num 为 0，直接返回 "0"；如果为负数，记录符号并取绝对值。然后不断对 7 取余，将余数拼接到结果中，再整除 7，直到商为 0。最后将结果反转，并根据符号添加负号。时间复杂度 O(log₇ n)，空间复杂度 O(log₇ n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def convertToBase7(num):    if num == 0:        return "0"    negative = num < 0    num = abs(num)    digits = []    while num:        digits.append(str(num % 7))        num //= 7    if negative:        digits.append('-')    return ''.join(reversed(digits))

题目24：寻找比目标字母大的最小字母

问题描述：给你一个字符数组 letters，该数组按非递减顺序排序，并包含至少两个不同的字母。给你一个目标字母 target。请找出 letters 中比 target 大的最小字母。如果不存在这样的字母，则返回 letters 中的第一个字母。

示例：

• • 输入：letters = ["c","f","j"], target = "a"，输出："c"
• • 输入：letters = ["c","f","j"], target = "c"，输出："f"
• • 输入：letters = ["x","x","y","y"], target = "z"，输出："x"

解题思路：使用二分查找。维护左右指针 left = 0 和 right = len(letters) - 1。每次取中间位置 mid，如果 letters[mid] > target，则记录当前字符并令 right = mid - 1；否则令 left = mid + 1。如果循环结束没有找到比 target 大的字符，返回 letters[0]。时间复杂度 O(log n)，空间复杂度 O(1)。

Python代码示例：

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

题目25：二叉树中第二小的节点

问题描述：给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点，那么该节点的值等于两个子节点中较小的一个。更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在，则输出 -1。

示例：

• • 输入：root = [2,2,5,null,null,5,7]
• • 输出：5
• • 解释：最小的值是 2，第二小的值是 5。
• • 输入：root = [2,2,2]
• • 输出：-1
• • 解释：最小的值是 2，但是不存在第二小的值。

解题思路：根节点的值一定是整个树的最小值。我们需要找到严格大于根节点值的最小值。使用深度优先搜索（DFS），遍历整棵树。维护一个变量 second_min，初始为无穷大。对于每个节点，如果它的值大于根节点的值，则用 min(second_min, node.val) 更新 second_min。遍历结束后，如果 second_min 仍为无穷大，返回 -1；否则返回 second_min。

Python代码示例（假设 TreeNode 类已定义）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def findSecondMinimumValue(root):    if not root:        return -1    first = root.val    second = float('inf')    def dfs(node):        nonlocal second        if not node:            return        if first < node.val < second:            second = node.val        dfs(node.left)        dfs(node.right)    dfs(root)    return second if second != float('inf') else -1

题目26：最后一个单词的长度

问题描述：给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例：

• • 输入：s = "Hello World"，输出：5
• • 解释：最后一个单词是 "World"，长度为 5。
• • 输入：s = "   fly me   to   the moon  "，输出：4
• • 解释：最后一个单词是 "moon"，长度为 4。
• • 输入：s = "luffy is still joyboy"，输出：6

解题思路：从字符串末尾开始向前遍历，跳过末尾的空格，然后统计连续非空格字符的个数，直到遇到空格或到达字符串开头。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def lengthOfLastWord(s):    i = len(s) - 1    length = 0    while i >= 0 and s[i] == ' ':        i -= 1    while i >= 0 and s[i] != ' ':        length += 1        i -= 1    return length

题目27：二进制求和

问题描述：给你两个二进制字符串 a 和 b，以二进制字符串的形式返回它们的和。

示例：

• • 输入：a = "11", b = "1"，输出："100"
• • 输入：a = "1010", b = "1011"，输出："10101"

解题思路：模拟手工二进制加法。使用双指针从两个字符串的末尾开始逐位相加，维护进位 carry。每次将两个数字（如果存在）与进位相加，当前位为 total % 2，进位为 total // 2。将结果逐位加入列表，最后反转并拼接成字符串。注意处理最高位进位。时间复杂度 O(max(m, n))，空间复杂度 O(max(m, n))。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def addBinary(a, b):    i, j = len(a) - 1, len(b) - 1    carry = 0    result = []    while i >= 0 or j >= 0 or carry:        x = int(a[i]) if i >= 0 else 0        y = int(b[j]) if j >= 0 else 0        total = x + y + carry        carry = total // 2        result.append(str(total % 2))        i -= 1        j -= 1    return ''.join(reversed(result))

题目28：多数元素

问题描述：给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例：

• • 输入：nums = [3,2,3]，输出：3
• • 输入：nums = [2,2,1,1,1,2,2]，输出：2

解题思路：使用 Boyer-Moore 投票算法。维护一个候选元素 candidate 和一个计数器 count。遍历数组，如果 count == 0，则将当前元素设为候选，count = 1；否则如果当前元素等于候选，count += 1；否则 count -= 1。由于多数元素出现次数超过一半，最终候选元素一定是多数元素。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
def majorityElement(nums):    candidate = None    count = 0    for num in nums:        if count == 0:            candidate = num        count += 1 if num == candidate else -1    return candidate

题目29：Excel 表列名称

问题描述：给你一个整数 columnNumber，返回它在 Excel 表中相对应的列名称。例如：

• • 1 -> "A"
• • 2 -> "B"
• • 3 -> "C"
• • ...
• • 26 -> "Z"
• • 27 -> "AA"
• • 28 -> "AB"
• • ...

示例：

• • 输入：columnNumber = 1，输出："A"
• • 输入：columnNumber = 28，输出："AB"
• • 输入：columnNumber = 701，输出："ZY"

解题思路：这本质上是一个 26 进制转换问题，但需要注意没有 0 的表示，因此每次需要将 columnNumber - 1 再对 26 取模。具体步骤：

• • columnNumber -= 1；
• • 取 columnNumber % 26，对应字母 chr(ord('A') + columnNumber % 26)；
• • columnNumber //= 26；
• • 重复直到 columnNumber <= 0。最后将得到的字符反转。时间复杂度 O(log₂₆ n)，空间复杂度 O(log₂₆ n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
def convertToTitle(columnNumber):    result = []    while columnNumber > 0:        columnNumber -= 1        result.append(chr(ord('A') + columnNumber % 26))        columnNumber //= 26    return ''.join(reversed(result))

题目30：两个数组的交集

问题描述：给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

示例：

• • 输入：nums1 = [1,2,2,1], nums2 = [2,2]，输出：[2]
• • 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]，输出：[9,4]（顺序不限）

解题思路：使用两个集合。先将 nums1 转换为集合 set1，然后遍历 nums2，如果元素在 set1 中，则加入结果集合 result。最后将 result 转换为列表返回。时间复杂度 O(m + n)，空间复杂度 O(m + n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
def intersection(nums1, nums2):    set1 = set(nums1)    result = set()    for num in nums2:        if num in set1:            result.add(num)    return list(result)