0 Basic

  1. 位运算基础
 1# 基本操作
 2a & b     # 按位与：两个都是 1 才为 1
 3a | b     # 按位或：有一个 1 就为 1
 4a ^ b     # 按位异或：不同为 1，相同为 0
 5~a        # 按位取反
 6a << n    # 左移 n 位（×2^n）
 7a >> n    # 右移 n 位（÷2^n）
 8
 9# 异或的重要性质
10a ^ 0 = a          # 任何数异或 0 不变
11a ^ a = 0          # 任何数异或自身为 0
12a ^ b ^ a = b      # 异或可以"消除"成对出现的数

1. 只出现一次的数字 | Easy

题目：非空数组，除一个元素只出现一次外，其余元素均出现两次。找出那个数。要求 O(n) 时间、O(1) 空间

思路分析：

  • 朴素做法：哈希表/Counter统计每个数字出现次数，空间为O(n)
  • 位运算异或：a ^ 0 = a, a ^ a = 0, a ^ b ^ a = b

踩坑记录：

  • 初始值为0（从第一个开始遍历），或者nums[0](从第二个开始遍历)

代码：

1
2class Solution:
3    def singleNumber(self, nums: List[int]) -> int:
4        cnt = Counter(nums)
5        for k, v in cnt.items():
6            if v == 1:
7                return k

1class Solution:
2    def singleNumber(self, nums: List[int]) -> int:
3        res = 0
4        for num in nums:
5            res ^= num
6        return res

1from functools import reduce
2from operator import xor
3
4def singleNumber(nums: list[int]) -> int:
5    return reduce(xor, nums)

复杂度：

  • 时间O(n)
  • 空间O(1)

2. 多数元素 | Easy

题目：数组中出现次数 > ⌊n/2⌋ 的元素，保证存在

思路分析： 排序法：排序后直接返回nums[len(nums) // 2]

哈希法：记录每个数出现次数

候选法：维护一个候选人 candidate 和一个"血量" cnt：

  • 遇到和 candidate 相同的数 → cnt += 1（援军）
  • 遇到不同的数 → cnt -= 1（同归于尽）
  • cnt == 0 时 → 当前候选人被全歼，下一个数直接接任候选人

踩坑记录：

  • cnt 归零那一刻要立刻换人，不要写成"先减再判断"导致漏换

代码：

1class Solution:
2    def majorityElement(self, nums: List[int]) -> int:
3        nums.sort()
4        return nums[len(nums) // 2]

1class Solution:
2    def majorityElement(self, nums: List[int]) -> int:
3        count = Counter(nums)
4        n = len(nums) // 2
5        for k, v in count.items():
6            if v > n:
7                return k

1class Solution:
2    def majorityElement(self, nums: List[int]) -> int:
3        candidate, count = 0, 0
4        for num in nums:
5            if count == 0:
6                candidate = num
7            count += 1 if candidate == num else -1
8        return candidate

复杂度：

排序：

  • 时间O(nlogn)
  • 空间O(1)

哈希：

  • 时间O(n)
  • 空间O(n)

候选：

  • 时间O(n)
  • 空间O(1)

3. 颜色分类 | Medium

题目：数组只含 0、1、2，原地排序。要求一趟扫描、常数空间

思路分析： 排序计数：数0/1/2各有多少个，然后原地修改，但是需要两趟

指针：三个指针zero, i, two把数组切成了四段

[0, zero)   全是 0
[zero, i)   全是 1
[i, two]    未知区（还没看过）
(two, n-1]  全是 2

遇到 0 和遇到 2，处理方式不对称:

  • 遇到 0：和 nums[zero] 交换。nums[zero] 处于 [zero, i) 段，必然是 1（已验过身），换到 i 位置后直接 i++ 安全
  • 遇到 2：和 nums[two] 交换。nums[two] 来自未知区，没验过身，所以 i 绝对不能动，下一轮还要重新检查它

踩坑记录：

  • 遇到 2 交换后 i 不能 ++
  • 循环条件是 while i <= two，不是 i < n。two 右边已经排好了，越过去会把 2 又搬回
  • zero 和 i 在遇到 0 时同时 ++（因为 zero <= i 恒成立，交换的是一个 1 和一个 0）

代码：

 1class Solution:
 2    def sortColors(self, nums: List[int]) -> None:
 3        count = [0] * 3
 4        for num in nums:
 5            count[num] += 1
 6
 7        i = 0
 8        for color in range(3):
 9            for _ in range(count[color]):
10                nums[i] = color
11                i += 1

 1class Solution:
 2    def sortColors(self, nums: List[int]) -> None:
 3        zero, i, two = 0, 0, len(nums) - 1
 4        while i <= two:
 5            if nums[i] == 0:
 6                nums[zero], nums[i] = nums[i],  nums[zero]
 7                zero += 1
 8                i += 1
 9            elif nums[i] == 1:
10                i += 1
11            else:
12                nums[two], nums[i] = nums[i], nums[two]
13                two -= 1

复杂度：

计数法：

  • 时间O(n)
  • 空间O(1)

指针法：

  • 时间O(n)
  • 空间O(1)

4. 下一个排列 | Medium

题目：原地把数组变成字典序的下一个更大排列；如果不存在（已是降序），变成最小排列（升序）

思路分析：

踩坑记录：

  • 找 i 的条件是 nums[i] >= nums[i+1] 才继续左移（带等号），否则遇到重复元素会停错位置
  • 找 j 的条件是 nums[j] <= nums[i] 才继续左移（带等号），必须找严格大于的
  • 最后是 reverse 不是 sort，写 sort 虽然结果对但复杂度退化成 O(n log n)
  • i = -1 的分支不要漏，靠 if i >= 0 包住交换，反转永远执行

代码：

 1class Solution:
 2    def nextPermutation(self, nums: List[int]) -> None:
 3        n = len(nums)
 4        
 5        i = n - 2
 6        while i >= 0 and nums[i] >= nums[i + 1]:
 7            i -= 1
 8
 9        if i >= 0:
10            j = n - 1
11            while j >= 0 and nums[j] <= nums[i]:
12                j -= 1
13            nums[i], nums[j] = nums[j], nums[i]
14
15        l, r = i + 1, n - 1
16        while l < r:
17            nums[l], nums[r] = nums[r], nums[l]
18            l += 1
19            r -= 1

复杂度：

  • 时间O(n)
  • 空间O(1)

5. 寻找重复数 | Medium

题目：长度 n+1 的数组，元素在 [1, n]，只有一个重复数（可能重复多次）。要求不修改数组、O(1) 额外空间

思路分析：

踩坑记录：

  • 起点必须是 0，不能是 nums[0]。因为 0 是唯一保证不在环上的节点
  • 第一阶段用 while True + break，不能用 while slow != fast：初始时两者都在 0，会直接退出

代码：

1class Solution:
2    def findDuplicate(self, nums: List[int]) -> int:
3        count = Counter(nums)
4        for k, v in count.items():
5            if v > 1:
6                return k

 1class Solution:
 2    def findDuplicate(self, nums: List[int]) -> int:
 3        slow = fast = 0
 4
 5        while True:
 6            slow = nums[slow]
 7            fast = nums[nums[fast]]
 8            if slow == fast:
 9                break
10
11        slow = 0
12        while slow != fast:
13            slow = nums[slow]
14            fast = nums[fast]
15            if slow == fast:
16                return slow

复杂度：

  • 时间O(n)
  • 空间O(1)