📚 plmblog

Appearance

16-技巧

📅 发表于 2026/06/25
🔄 更新于 2026/06/25
👁️ -- 次访问
📝 0 字
⏳ 0 分钟

总结 ​

异或操作 ​

异或操作

异或特性

  • 任何数与0异或，任是原数。a⊕0 = a
  • 任何数 与自身异或，结果为0。a⊕a = 0
  • 异或运算满足交换律和结合律。a⊕b = b⊕a

异或本质

  • 各二进制位的开关旋转，变1变0，相同为0，不同保留1。

示例

  • 1⊕3：二进制 1=001, 3=011，各位依次异或 --> 010 --> 2

题目 ​

01-136-只出现一次的数字 ​

01-136-只出现一次的数字

leetcode-136

  • 输入：整数数组nums。某1个元素只出现1次，其余均出现2次。
  • 输出：只出现1次的数字。
  • 要求：常量空间，O(n)复杂度

异或操作相同为0不同保留 ​

提示
  • 依次对所有数做异或操作，两个相同数的二进制位全部为0抵消，留下仅出现1次的数。
  • python 异或操作：^
python
def singleNumber(self, nums: List[int]) -> int:
    res = 0
    # 不断做异或操作，两个相同的数会抵消掉，仅留下出现1次的数
    for x in nums:
        # python 异或操作 ^
        res ^= x
    return res

02-169-多数元素 ​

02-169-多数元素

leetcode-169

  • 输入：nums数组，长度为n
  • 返回：数组中的多数元素，出现次数 > ⌊n/2⌋
  • 要求：时间复杂度O(n)，空间复杂度O(1)

特点

  • A：多数元素；B：其他元素。
  • Count(A) > Count(B)

Boyer-Moore 投票对抗抵消法 ​

Boyer-Moore 投票对抗法

候选人和count 变量

  • candidate：候选人
  • count：候选人的出现次数

遍历数组 变换条件

  • x == candiate：count += 1
  • x != candidate：
    • count -= 1
    • 若count=0：更换候选人，candidate=x，count=1

注意

  • 更换候选人时，count=1，已有1次。
python
def majorityElement(self, nums: List[int]) -> int:
    if not nums:
        return 0
    n = len(nums)

    # 初始化候选人及其计数
    candidate = nums[0]
    count = 1

    for i in range(1, n):
        x = nums[i]
        if x == candidate:
            count += 1
        else:
            count -= 1
            if count == 0:
                # 重置候选人，计数为1
                candidate = x  
                count = 1
    return candidate

03-75-颜色分类 ​

03-75-颜色分类

leetcode-75

  • 输入：包含红色0、白色1、蓝色2的数组nums
  • 目标：原地对nums，按红白蓝排序。
  • 输出：排序后的nums，即把数组分成3段。

LowMidHigh三指针分块Mid交换法 ​

三指针法

三指针

  • low=0： 0的右边界。左边永远是0。
  • mid=0：当前遍历数字，探索未知数字。
  • high=n-1：2的左边界。右边永远是2。

遍历mid做交换

  • nums[mid] == 0
    • 交换到前面，swap(low, mid)，low += 1，mid += 1
  • nums[mid] == 1
    • 不用管, mid+=1
  • nums[mid] == 2
    • 交换到后面，swap(mid, high), high -= 1，mid 保持不变!!!，换来的元素还没看。

注意

  • 从high交换到mid位置的数字，还没有看过，mid需保持不变。
python
def sortColors_low_mid_high_swap(self, nums: List[int]) -> None:
    """颜色排序，012依次排序，使用三指针，原地交换"""
    if not nums:
        return
    n = len(nums)

    def swap(i, j):
        """交换函数"""
        nums[i], nums[j] = nums[j], nums[i]

    # 分0,1,2 3块
    # low左边全是0，都看过；high 右边全是1。mid是当前探索值
    low, mid, high = 0, 0, n-1

    # 遍历mid
    while mid <= high:
        if nums[mid] == 0:
            # 交换到前面去
            swap(low, mid)
            low += 1
            mid += 1
        elif nums[mid] == 1:
            # 不用管，正好在mid位置上
            mid += 1
        elif nums[mid] == 2:
            # 交换到后面去
            swap(mid, high)
            high -= 1
            # mid 不能动，因为从high交换来的数字，还没有被探索过，可能是0呢？
            # mid += 1
    return

04-31-下一个排列 ​

04-31-下一个排列

leetcode-31

  • 输入：nums数组 1,2,3
  • nums有多种排列顺序
    • 从小到大列举：1,2,3, 1,3,2, 2,1,3, 2,3,1, 3,1,2, 3,2,1
  • 输出：从小到大顺序中，原始nums排列的下一个排列
    • 如：1,2,3 -> 1,3,2；3,1,2 -> 3,2,1；3,2,1(最大) -> 1,2,3(最小)
    • 即：第一个比当前排列大的排列 或 最小排列

从右至左找破点做交换再翻转法 ​

示例

全减推导示例

  • 6,5,4 -> 全递减 最大排列 -> 逆序 变最小排列 -> 4,5,6

推导示例

  • 1,2,3,6,5,4 -> 1,2, 3,6,5,4 -> 1,2, 4,6,5,3 -> 1,2, 4,3,5,6 (i=2, j=1)

具体步骤

  • Step1：i从右到左(按理递增)，找到第1个降低点，作为次大替换点，即3。3,6,5,4
    • nums[i] < nums[i+1]。找不到i：说明全递减，直接逆序。
  • Step2：j从右到左，找到第1个比替换点大的数，即4，做交换 。4, 6,5, 3
    • 第1个 nums[j] > nums[i]。i和j做交换。j一定存在
  • Step3：替换点后面是递增，做逆序变递减，即作为全局次大值。4 3,5,6
    • i后面翻转由最大变最小值。
更多示例
  • 1,1,5 -> 1, 1,5 -> 1, 5,1 -> 1, 5,1 (i=1,j=2)
  • 1,3,2 -> 1,3,2 -> 2,3,1 -> 2,1,3 (i=0, j=2)
  • 2,3,1 -> 2,3,1 -> 3,2,1 -> 3,1,2 (i=0, j=1)
python
def nextPermutation(self, nums: List[int]) -> None:
    """下一个排列。
    step1：i从右到左，找到第1个变小点i，nums[i]<nums[i+1]
    step2：j从右到左，找到第1个小于i的值，nums[i]>nums[j]，交换nums[j]和nums[i]，位置i由次大值替换
    step3：i后面的值翻转下，由最大变最小。作为全局次大排列。
    """

    n = len(nums)

    # step1：从右到左，找替换位置i，第一个变小点, nums[i]<nums[i+1]
    i = n - 2
    while i >= 0 and nums[i] >= nums[i+1]:
        i -= 1

    if i < 0:
        # nums 右到左，纯递增，为最大排列，逆序为最小排列
        nums.reverse()
        return

    # step2：从右到左，找到可替换的值j，第一个nums[i]<nums[j]
    j = n - 1
    while j > i and nums[i] >= nums[j]:
        j -= 1

    # j必然有值
    nums[i], nums[j] = nums[j], nums[i]

    # step3: nums[i+1:]后面的全部逆序
    # 逆序，左右做交换即可
    l, r = i + 1, n - 1
    while l < r:
        nums[l], nums[r] = nums[r], nums[l]
        l += 1
        r -= 1
    return

05-287-寻找重复数 ​

05-287-寻找重复数

leetcode-287

  • 输入：nums数组，n+1长度，值在[1,n]内，只有1个数重复。
  • 输出：重复数字。
  • 要求：不修改nums，O(1)空间。

有环

  • n+1长度，范围[1,n]内，一定有环。

有环数组快慢指针寻找环入口 ​

重要

快慢指针判断有环

  • fast=slow=0, fast走2步，slow走1步
  • fast和slow相遇：说明有环。

fast slow 同步走再次相遇点为环入口

  • fast 从0开始走，slow 仍在相遇点
  • fast和slow 都走1步，fast和slow再次相遇，即为环入口
python
def findDuplicate(self, nums: List[int]) -> int:
    """环入口
    nums长度为n+1，值范围在[1, n]内，找到重复数字
    快慢指针判断有环，快慢指针再次相遇为
    """

    # 寻找环相遇点，快慢指针先各自走1下
    slow = nums[0]
    fast = nums[nums[0]]
    while slow != fast:
        # 慢指针走1步
        slow = nums[slow] 
        # 快指针走2步
        fast = nums[nums[fast]] 

    # 快慢指针同步走，再次相遇为环入口
    fast = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    # 相遇点为环入口，本身就是值
    return slow
总访客数：   ·   总访问量：
PLM's Blog @ 2016 - 2026