Day13，Hot100（数学技巧）

136. 只出现一次的数字

两个相同的数异或 --> 00 与任何数异或 --> 结果不变,仍然为数本身异或满足交换律和结合律

eg

[2,2,1]x^2 = 22^2 = 00^1 = 1 class Solution: def singleNumber(self, nums: List[int]) -> int: x = 0 for num in nums: x ^= num return x

---

169. 多数元素

解析

class Solution: def majorityElement(self, nums: List[int]) -> int: votes = 0 x = 0 for num in nums: # 当票数为0时, 假设当前数为众数 if votes == 0: x = num # 当前数为假设的众数时, +1 if x == num: votes += 1 else: votes -= 1 return x

---

75. 颜色分类

要求原地操作，且只扫描一次

三路快排

将区间划分为三个区间区间1：小于 partition 的部分区间2：等于 partition 的部分区间3：大于 partition 的部分

如果设 partition = 1，那么结果刚好是我们需要的

初始化 区间1, all in nums [0 .. zero] = 0，闭区间区间2, all in nums (zero .. i) = 1，开区间区间3, all in nums [two .. n-1] = 2，闭区间为了保证初始时三个区间都为空, zero = -1，two = n 当 nums[i] == 0，需要放到区间 1 的末尾 zero 移动一个位置用于与 i 交换因为第一个区间, zero一定是指向最后一个 0之后 i++，因为区间2中, i 是在zero右边 当 nums[i] ==1，需要放到区间 2 的末尾 而 i 刚好就是区间 2 的末尾由于是开区间, 区间 2 不包含 i，所以i++ 当 nums[i] ==2，需要放到区间 2 的开头 将 two 移动一个位置用于交换此时 i 不用 ++，因为原来的 nums[two] 值是多少，还没有遍历 class Solution: def swap(self, nums, index1, index2): nums[index1], nums[index2] = nums[index2], nums[index1] def sortColors(self, nums: List[int]) -> None: n = len(nums) # 区间1, all in nums[0 .. zero] = 0 # 区间2, all in nums(zero .. i) = 1 # 区间3, all in nums[two .. n-1] = 2 zero = -1 # 保证区间1和2,在初始时为空 two = n # 保证区间3,在初始时为空 i = 0 while i < two: if nums[i] == 0: zero += 1 self.swap(nums, i, zero) i += 1 # 因为 i 在zero的右侧 elif nums[i] == 1: i += 1 else: two -= 1 self.swap(nums, i, two)

冒泡 O(n^2)

class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) for i in range(n - 1): # 进行 n-1 轮冒泡 swapped = False # 用于优化，如果本轮没有交换，则提前结束 for j in range(n - 1 - i): # 每轮比较前 n-1-i 个元素 if nums[j] > nums[j + 1]: # 相邻元素交换 nums[j], nums[j + 1] = nums[j + 1], nums[j] swapped = True if not swapped: # 如果没有发生交换，说明已经有序，提前终止 break return nums

---

31. 下一个排列

排列的顺序就是DFS的顺序

每个分支的最后一个分支，一定是降序的（下图的14320中的 4320）

也就是是说，当遇到降序分支后，就需要转移到下一个分支了

而下一个分支，一定是升序的（每次选当前可选的最小值 2 0134)

如何确定下一个分支开头元素？

1 4320，逆序遍历，0–>2–>3–>4–>1，发现逆序部分下一个点的开头就是，逆序部分中第一个大于它的元素（2）交换 1 和 2然后 sort 2后面的部分 —— 2 0134 class Solution: def nextPermutation(self, nums: List[int]) -> None: n = len(nums) if n <= 1: return nums # 从后往前遍历, 找逆序序列 i = n-2 while i >= 0 and nums[i] >= nums[i+1]: i -= 1 if i < 0: # 说明整个序列都是逆序的, 排列已经到最后一个了 left = 0 right = n -1 else: j = n-1 while i < j and nums[i] >= nums[j]: j -= 1 nums[i], nums[j] = nums[j], nums[i] left = i + 1 right = n -1 while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1

---

287. 寻找重复数

参考<142.环形链表II>，相当于我们要找到环的入口

对于例子 [1, 3, 4, 2, 2]，有如下映射：

0->1

1->3

3->2

2->4

4->2

可以构成下面的带环链表，而重复元素就是环的入口

快慢指针相遇后head 和 慢指针一起走，会在入口相遇 class Solution: def findDuplicate(self, nums: List[int]) -> int: slow = 0 fast = 0 while True: fast = nums[fast] fast = nums[fast] slow = nums[slow] if slow == fast: head = 0 while head != slow: head = nums[head] slow = nums[slow] return head