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

题目41：删除字符串中的所有相邻重复项

问题描述：给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 s 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

• • 输入：s = "abbaca"，输出："ca"
• • 解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中只有 "aa" 可以再次执行重复项删除操作，所以最后的字符串为 "ca"。
• • 输入：s = "azxxzy"，输出："ay"

解题思路：使用栈。遍历字符串，如果栈不为空且栈顶元素等于当前字符，则弹出栈顶（相当于删除相邻重复项）；否则将当前字符压入栈。遍历结束后，栈中剩余的字符按顺序组成最终字符串。时间复杂度 O(n)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
def removeDuplicates(s):    stack = []    for char in s:        if stack and stack[-1] == char:            stack.pop()        else:            stack.append(char)    return ''.join(stack)

题目42：反转字符串 II

问题描述：给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• • 如果剩余字符少于 k 个，则将剩余字符全部反转。
• • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例：

• • 输入：s = "abcdefg", k = 2，输出："bacdfeg"
• • 解释：每 4 个字符一组："abcd" 反转前 2 个得到 "bacd"，剩余 "efg" 不足 4 个但超过 2 个，反转前 2 个得到 "feg"，最终结果 "bacdfeg"。
• • 输入：s = "abcd", k = 2，输出："bacd"

解题思路：将字符串转为列表，便于原地交换。以 2k 为步长遍历字符串，对于每个起始位置 i，确定需要反转的区间为 [i, min(i + k, n) - 1]。使用双指针反转该区间。时间复杂度 O(n)，空间复杂度 O(n)（列表转换）。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
def reverseStr(s, k):    s_list = list(s)    n = len(s_list)    for i in range(0, n, 2 * k):        left = i        right = min(i + k - 1, n - 1)        while left < right:            s_list[left], s_list[right] = s_list[right], s_list[left]            left += 1            right -= 1    return ''.join(s_list)

题目43：长按键入

问题描述：你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。

示例：

• • 输入：name = "alex", typed = "aaleex"，输出：true
• • 解释：typed 中的 'a' 和 'e' 被长按。
• • 输入：name = "saeed", typed = "ssaaedd"，输出：false
• • 解释：'e' 一定需要被键入两次，但在 typed 中不是。
• • 输入：name = "leelee", typed = "lleeelee"，输出：true

解题思路：使用双指针分别遍历 name 和 typed。当 name[i] == typed[j] 时，两个指针同时后移。否则，如果 typed[j] == typed[j-1]，说明是长按产生的重复字符，j 后移；否则返回 False。最后检查 name 是否遍历完，并且 typed 剩余字符是否都是最后一个字符的重复。时间复杂度 O(n + m)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def isLongPressedName(name, typed):    i = j = 0    n, m = len(name), len(typed)    while j < m:        if i < n and name[i] == typed[j]:            i += 1            j += 1        elif j > 0 and typed[j] == typed[j - 1]:            j += 1        else:            return False    return i == n

题目44：比较含退格的字符串

问题描述：给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true。# 代表退格字符。注意：如果对空文本输入退格字符，文本继续为空。

示例：

• • 输入：s = "ab#c", t = "ad#c"，输出：true
• • 解释：s 和 t 都会变成 "ac"。
• • 输入：s = "ab##", t = "c#d#"，输出：true
• • 解释：s 和 t 都会变成 ""。
• • 输入：s = "a#c", t = "b"，输出：false
• • 解释：s 会变成 "c"，而 t 仍然是 "b"。

解题思路：使用栈处理字符串。遍历字符串，遇到普通字符则压栈，遇到 # 则弹出栈顶（如果栈非空）。分别处理 s 和 t，然后比较两个栈的内容是否相同。时间复杂度 O(n + m)，空间复杂度 O(n + m)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
def backspaceCompare(s, t):    def build(string):        stack = []        for char in string:            if char != '#':                stack.append(char)            elif stack:                stack.pop()        return stack    return build(s) == build(t)

题目45：柠檬水找零

问题描述：在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。给你一个整数数组 bills，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true，否则返回 false。

示例：

• • 输入：bills = [5,5,5,10,20]，输出：true
• • 解释：
• • 前 3 位顾客，我们按顺序收取 3 张 5 美元。
• • 第 4 位顾客，我们收取一张 10 美元，并找零 5 美元。
• • 第 5 位顾客，我们收取一张 20 美元，并找零 10 美元和 5 美元。
• • 由于所有顾客都得到了正确找零，返回 true。
• • 输入：bills = [5,5,10,10,20]，输出：false
• • 解释：前 2 位顾客收取 2 张 5 美元，第 3、4 位顾客各收取 10 美元并找零 5 美元，此时手头有 2 张 10 美元。第 5 位顾客支付 20 美元，我们无法找零 15 美元（只有 2 张 10 美元），返回 false。

解题思路：使用贪心算法。维护两种面额的零钱数量：five 和 ten。遍历账单：

• • 如果收到 5 美元，five += 1；
• • 如果收到 10 美元，需要找零 5 美元，如果 five > 0，则 five -= 1，ten += 1；否则返回 False；
• • 如果收到 20 美元，优先找零一张 10 美元和一张 5 美元（因为 5 美元更灵活），如果不行则找零三张 5 美元。遍历结束返回 True。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def lemonadeChange(bills):    five = ten = 0    for bill in bills:        if bill == 5:            five += 1        elif bill == 10:            if five == 0:                return False            five -= 1            ten += 1        else:  # bill == 20            if ten > 0 and five > 0:                ten -= 1                five -= 1            elif five >= 3:                five -= 3            else:                return False    return True

题目46：验证回文串

问题描述：如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样，则可以认为该短语是一个回文串。字母和数字都属于字母数字字符。给你一个字符串 s，如果它是回文串，返回 true；否则，返回 false。

示例：

• • 输入：s = "A man, a plan, a canal: Panama"，输出：true
• • 解释：移除非字母数字字符并转小写后得到 "amanaplanacanalpanama"，是回文串。
• • 输入：s = "race a car"，输出：false
• • 解释：处理后得到 "raceacar"，不是回文串。
• • 输入：s = " "，输出：true
• • 解释：处理后为空字符串，视为回文串。

解题思路：使用双指针。左指针 left 从字符串开头向右移动，右指针 right 从末尾向左移动。每次移动时跳过非字母数字字符，然后将两个字符都转为小写进行比较。如果字符不相等，返回 False；如果两个指针相遇或交错，返回 True。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def isPalindrome(s):    left, right = 0, len(s) - 1    while left < right:        while left < right and not s[left].isalnum():            left += 1        while left < right and not s[right].isalnum():            right -= 1        if s[left].lower() != s[right].lower():            return False        left += 1        right -= 1    return True

题目47：存在重复元素 II

问题描述：给你一个整数数组 nums 和一个整数 k，判断数组中是否存在两个不同的索引i 和 j，满足 nums[i] == nums[j] 且 abs(i - j) <= k。如果存在，返回 true；否则，返回 false。

示例：

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

解题思路：使用哈希表记录每个元素最近一次出现的下标。遍历数组，对于每个元素 num，如果它已经在哈希表中，且当前下标与上次出现的下标之差 <= k，则返回 True。否则更新哈希表中 num 的下标为当前下标。时间复杂度 O(n)，空间复杂度 O(n)。

Python代码示例：

1
2
3
4
5
6
7
8
9
def containsNearbyDuplicate(nums, k):    index_map = {}    for i, num in enumerate(nums):        if num in index_map and i - index_map[num] <= k:            return True        index_map[num] = i    return False

题目48：汇总区间

问题描述：给定一个无重复元素的有序整数数组 nums。返回恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字。列表中的每个区间范围 [a,b] 应该按如下格式输出：

• • "a->b"，如果 a != b
• • "a"，如果 a == b

示例：

• • 输入：nums = [0,1,2,4,5,7]，输出：["0->2","4->5","7"]
• • 输入：nums = [0,2,3,4,6,8,9]，输出：["0","2->4","6","8->9"]

解题思路：使用双指针或一次遍历。维护当前区间的起始位置 start。遍历数组，如果当前元素与下一个元素不连续（即 nums[i] + 1 != nums[i+1]），则当前区间结束，根据 start 和 i 的关系生成字符串。注意处理数组末尾的最后一个区间。时间复杂度 O(n)，空间复杂度 O(1)（不考虑结果存储）。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def summaryRanges(nums):    result = []    n = len(nums)    i = 0    while i < n:        start = nums[i]        while i + 1 < n and nums[i] + 1 == nums[i + 1]:            i += 1        if start == nums[i]:            result.append(str(start))        else:            result.append(f"{start}->{nums[i]}")        i += 1    return result

题目49：赎金信

问题描述：给你两个字符串：ransomNote 和 magazine，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true；否则返回 false。magazine 中的每个字符只能在 ransomNote 中使用一次。

示例：

• • 输入：ransomNote = "a", magazine = "b"，输出：false
• • 输入：ransomNote = "aa", magazine = "ab"，输出：false
• • 输入：ransomNote = "aa", magazine = "aab"，输出：true

解题思路：使用哈希表或长度为 26 的数组统计 magazine 中每个字符的出现次数。然后遍历 ransomNote，每遇到一个字符就将对应计数减一，如果计数小于 0，说明 magazine 中字符不足，返回 False。遍历结束返回 True。时间复杂度 O(m + n)，空间复杂度 O(1)（字符集固定为小写字母）。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
def canConstruct(ransomNote, magazine):    count = [0] * 26    for char in magazine:        count[ord(char) - ord('a')] += 1    for char in ransomNote:        index = ord(char) - ord('a')        count[index] -= 1        if count[index] < 0:            return False    return True

题目50：找不同

问题描述：给定两个字符串 s 和 t，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。

示例：

• • 输入：s = "abcd", t = "abcde"，输出："e"
• • 解释：'e' 是那个被添加的字母。
• • 输入：s = "", t = "y"，输出："y"

解题思路：方法一：使用哈希表统计 s 中每个字符的频次，然后遍历 t，遇到频次为 0 的字符即为添加的字母。方法二：使用异或运算。将 s 和 t 中所有字符的 ASCII 码进行异或，最终结果就是添加的字母的 ASCII 码。方法三：使用字符的 ASCII 码求和，t 的总和减去 s 的总和即为添加字母的 ASCII 码。时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例（异或法）：

1
2
3
4
5
6
7
8
9
10
def findTheDifference(s, t):    result = 0    for char in s:        result ^= ord(char)    for char in t:        result ^= ord(char)    return chr(result)