leetcode高频题(一):30道

标签: 数据结构与算法

一、出现一次的数字

这一系列的题用哈希很容易做出来,但这些题最想考察的是位运算。

1、出现一次的数字I

此题为leetcode第136题
在这里插入图片描述
思路:利用异或操作

  • 一个数字a和0进行异或操作,得到的是自己:a⨁0=a
  • 一个数字和自己进行异或,得到的是0:a⨁a=0
  • 异或满足交换律和结合律:a⨁b⨁a=(a⨁a)⨁b=0⨁b=b

对所有数字进行异或操作即可得到只出现一次的数。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 位运算
        a = 0
        for i in range(len(nums)):
            a ^= nums[i]
        return a

2、出现一次的数字II

此题为leetcode第137题
在这里插入图片描述
思路:使用掩码,由于a⨁0=a和a⨁a=0,异或两次可以消除出现2次的数字,剩下的为出现1次或3次(奇数次)的数字。为了区分出现1次和3次的数字,我们使用两个掩码:seen_once=0seen_twice=0。仅当seen_twice没变时,改变seen_once;仅当seen_once没变时,改变seen_twice。最后seen_once保留只出现1次的数字。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:        
        # 位运算
        seen_once = seen_twice = 0
        for num in nums:
            seen_once = ~seen_twice & (seen_once ^ num)
            seen_twice = ~seen_once & (seen_twice ^ num)
        return seen_once

3、只出现一次的数字III

此题为leetcode第260题
在这里插入图片描述
思路:使用掩码mask=0,用异或操作遍历一遍后,消除出现2次的数字。此时掩码是出现1次的两个数字的差异,即x⨁y。我们通过diff=mask & (-mask)保留mask最右边的1,这个1要么来自x,要么来自y,然后对于diff & num成立的数字进行x ^ = num操作(x一开始为0),提取出x,那么y=x^mask

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # 位运算
        mask = 0    # 初始化掩码
        # 消除出现2次的数字
        for num in nums:
            mask ^= num
        # 得到掩码最后一位1
        diff = mask & (-mask)
        # 提取x
        x = 0 
        for num in nums:
            if num & diff:
                x ^= num
        return [x, x^mask]

未完待续

版权声明:本文为u014157632原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u014157632/article/details/105740995