超全网络安全技术练习题(16)

题目51：数组中数字出现的次数

问题描述：一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度为 O(n)，空间复杂度为 O(1)。

解题思路：使用异或运算。先将数组中所有数字异或，得到的结果是两个只出现一次的数字的异或值。由于这两个数字不同，异或结果中至少有一位为 1。找到这一位作为分组依据，将数组分为两组，每组分别异或即可得到两个只出现一次的数字。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def singleNumbers(nums):    xor_result = 0    for num in nums:        xor_result ^= num    diff_bit = xor_result & (-xor_result)    a = b = 0    for num in nums:        if num & diff_bit:            a ^= num        else:            b ^= num    return [a, b]

题目52：数组中数字出现的次数II

问题描述：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

解题思路：使用位运算。统计每个二进制位上所有数字中 1 的个数，对 3 取模，最终剩下的位组成的就是只出现一次的数字。也可以使用状态机（两个变量分别记录模 3 余 1 和余 2 的位），时间复杂度 O(n)，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
8
def singleNumber(nums):    ones = twos = 0    for num in nums:        ones = (ones ^ num) & ~twos        twos = (twos ^ num) & ~ones    return ones

题目53：和为s的两个数字

问题描述：输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，则输出任意一对即可。

解题思路：使用双指针。左指针指向数组开头，右指针指向数组末尾。计算两指针所指元素之和：若等于 s 则返回这两个数；若小于 s 则左指针右移；若大于 s 则右指针左移。由于数组有序，时间复杂度为 O(n)，空间复杂度为 O(1)。

Python代码示例：

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

题目54：和为s的连续正数序列

问题描述：输入一个正整数 target，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

解题思路：使用滑动窗口。维护窗口的左右边界 left 和 right，初始 left = 1，right = 2。计算窗口内数字之和：若等于 target 则记录当前序列，并向右移动左边界；若小于 target 则右边界右移；若大于 target 则左边界右移。当 left 大于等于 target / 2 时停止。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findContinuousSequence(target):    result = []    left, right = 1, 2    while left < right:        total = (left + right) * (right - left + 1) // 2        if total == target:            result.append(list(range(left, right + 1)))            left += 1        elif total < target:            right += 1        else:            left += 1    return result

题目55：翻转单词顺序

问题描述：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串 "I am a student. "，则输出 "student. a am I"。

解题思路：先使用 split() 将字符串按空白字符分割成单词列表，该操作会自动忽略多余空格。然后反转单词列表，再用单个空格连接即可。也可以原地操作：先反转整个字符串，再逐个反转每个单词，最后清理多余空格。

Python代码示例：

1
2
3
def reverseWords(s):    words = s.split()    return ' '.join(reversed(words))

题目56：左旋转字符串

问题描述：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串 "abcdefg" 和数字 2，该函数将返回左旋转两位得到的结果 "cdefgab"。

解题思路：方法一：字符串切片，将前 n 个字符移到末尾，返回 s[n:] + s[:n]。方法二：三次反转。先反转前 n 个字符，再反转剩余字符，最后反转整个字符串。方法二可以在原地操作（对于字符数组），空间复杂度 O(1)。

Python代码示例：

1
2
3
def reverseLeftWords(s, n):    n = n % len(s)    return s[n:] + s[:n]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 三次反转解法（适用于字符数组）def reverseLeftWords(s, n):    s = list(s)    n = n % len(s)    def reverse(left, right):        while left < right:            s[left], s[right] = s[right], s[left]            left += 1            right -= 1    reverse(0, n - 1)    reverse(n, len(s) - 1)    reverse(0, len(s) - 1)    return ''.join(s)

题目57：队列的最大值

问题描述：请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数 max_value、push_back 和 pop_front 的时间复杂度都是 O(1)。若队列为空，pop_front 和 max_value 需要返回 -1。

解题思路：使用两个双端队列：一个普通队列存储所有元素，另一个单调递减队列存储当前最大值。push_back 时，将元素加入普通队列，同时从单调队列尾部弹出所有小于当前元素的元素，再将当前元素加入单调队列。pop_front 时，若普通队列队首元素等于单调队列队首元素，则同时弹出两个队列的队首。max_value 直接返回单调队列的队首。

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
from collections import dequeclass MaxQueue:    def __init__(self):        self.queue = deque()        self.max_deque = deque()    def max_value(self):        if not self.max_deque:            return -1        return self.max_deque[0]    def push_back(self, value):        self.queue.append(value)        while self.max_deque and self.max_deque[-1] < value:            self.max_deque.pop()        self.max_deque.append(value)    def pop_front(self):        if not self.queue:            return -1        value = self.queue.popleft()        if value == self.max_deque[0]:            self.max_deque.popleft()        return value

题目58：n个骰子的点数

问题描述：把 n 个骰子扔在地上，所有骰子朝上一面的点数之和为 s。输入 n，打印出 s 的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

解题思路：使用动态规划。定义 dp[i][j] 表示投掷 i 个骰子后点数和为 j 的次数。初始 dp[1][1..6] = 1。状态转移：dp[i][j] = sum(dp[i-1][j-k])，其中 1 <= k <= 6。可以用两个一维数组滚动更新，优化空间。最终概率为 dp[n][j] / 6^n。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
def dicesProbability(n):    dp = [1 / 6] * 6    for i in range(2, n + 1):        new_dp = [0] * (5 * i + 1)        for j in range(len(dp)):            for k in range(6):                new_dp[j + k] += dp[j] / 6        dp = new_dp    return dp

题目59：扑克牌中的顺子

问题描述：从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。2～10 为数字本身，A 为 1，J 为 11，Q 为 12，K 为 13，而大、小王为 0，可以看成任意数字。A 不能视为 14。

解题思路：先对数组排序，统计 0 的个数（即大小王的数量）。遍历非 0 部分，若出现重复数字则不是顺子。计算相邻非 0 数字之间的间隔总和，若间隔总数小于等于 0 的个数，则可以用大小王补全，是顺子；否则不是。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
def isStraight(nums):    nums.sort()    joker = 0    for i in range(4):        if nums[i] == 0:            joker += 1        elif nums[i] == nums[i + 1]:            return False    return nums[4] - nums[joker] < 5

题目60：圆圈中最后剩下的数字（约瑟夫环变种）

问题描述：0, 1, ···, n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。这是经典的约瑟夫环问题。要求使用 O(n) 时间、O(1) 空间的解法。

解题思路：使用数学递推。设 f(n, m) 表示 n 个数字时最后剩下的数字。第一个被删除的数字是 (m - 1) % n，删除后剩下 n - 1 个数字，问题转化为 f(n - 1, m)。由于删除后从下一个数字开始计数，递推关系为 f(n, m) = (f(n - 1, m) + m) % n。边界条件 f(1, m) = 0。可以从小到大迭代计算，空间复杂度 O(1)。

Python代码示例：

1
2
3
4
5
6
7
def lastRemaining(n, m):    result = 0    for i in range(2, n + 1):        result = (result + m) % i    return result