本系列为Leetcode刷题笔记，刷题平台为Leetcode中文站， 刷题按Tag分类。本系列题解汇总如下 (持续更新…)：
本文主要是位运算相关题目题解总结。
[TOC]
位运算
基本原理
0s表示一串0，1s表示一串1。1
2
3x^0s = x x&0s = 0 x|0s = x
x^1s = ~x x&1s = x x|1s = 1s
x^x = 0 x&x = x x|x = x
- 利用x^1s=~x的特点，可以将位级表示翻转；
- 利用x^x=0的特点，可以将三个数中重复的两个数去除，只留下另一个数；
- 利用x&0s=0和x&1s=x的特点，可以实现掩码操作，一个数num与mask进行位与操作，只保留num中与mask的1部分相对应的位；例如num:10101010和mask:00111100，进行位与操作得00101000。
- 利用x|0s=x和x|1s=1s的特点，可以实现设值操作，一个数num与mask进行位或操作，将num中与mask中的1部分相对应的位都设置为1；例如num:10101010和mask:00111100，进行位或操作得10111110。
位与运算技巧：
- n&(n-1) 表示去掉n的位级表示中最低位的1。例如n:10110100，减去1得到10110011，将这两个数相与得到10110000。
- n&(-n)表示n的位级表示中的最低位的1，-n得到n的反码加1，对于二进制表示10110100，-n得到01001100，相与得到00000100。
- n-n&(~n+1)表示去掉n的位级表示中的最高位的1。例如n:10110100，则n-n&(~n+1): ???
移位运算：
>>n为算术右移，相当于除以2^n；>>n为无符号右移，左边会补上0；<<n为算术左移，相当于乘以2^n。
mask计算：
- 要获取11111111，将0取反即可，~0；
- 要得到只有第i位为1的mask，将1向左移动i-1位即可，1<<(i-1)。例如1<<4得到只有第5位为1的mask：00010000；
- 要得到1到i位为1的mask，(1<<(i+1))-1即可，例如将1<<(4+1)-1=00010000-1=00001111；
- 要得到1到i位为0的mask，只需将 1 到 i 位为 1 的 mask 取反，即 ~(1<<(i+1)-1)。
136. 只出现一次的数字
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:1
2输入: [2,2,1]
输出: 1
示例 2:1
2输入: [4,1,2,1,2]
输出: 4
解题思路
方法1：使用异或操作，一个数自己异或自己等于0, 一个数异或0等于数本身，即把所有数字进行异或操作，如果一个数出现两次，则变为0消失，最后剩下只出现一次的数字。
1 | class Solution(object): |
方法2：使用字典保存每个数字出现的次数，最后遍历字典返回出现次数等于1的数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
Dict = {}
for x in nums:
if x not in Dict:
Dict[x] = 1
else:
Dict[x] += 1
for key in Dict:
if Dict[key] == 1:
return key
137. 只出现一次的数字 II
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:1
2输入: [2,2,3,2]
输出: 3
示例 2:1
2输入: [0,1,0,1,0,1,99]
输出: 99
解题思路
方法1：位运算，把32位的二进制数进行遍历，统计所有数字的每一位出现0或1的次数。因为每个数字出现3次或者1次，当某一位出现次数不为3时，则一定是出现1次，使用或操作将每个位置叠加起来。
python的整形没有最大值，当输入是负数时，会认为是很大的正数，如果大于2^31-1时，则需要减去2^32。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
res = 0
mask = 1
for i in range(32):
count = 0
for x in nums:
if x & mask:
count += 1
if count % 3 == 1:
res |= mask
mask <<= 1
return res if res >> 31 == 0 else res-(1<<32)
方法2：使用字典保存每个数字出现的次数，最后遍历字典返回出现次数等于1的数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
Dict = {}
for x in nums:
if x not in Dict:
Dict[x] = 1
else:
Dict[x] += 1
for key, val in Dict.items():
if val == 1:
return key
169. 求众数
题目描述
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:1
2输入: [3,2,3]
输出: 3
示例 2:1
2输入: [2,2,1,1,1,2,2]
输出: 2
解题思路
方法1：将原数组排序nums.sort()， 返回nums[len(nums)//2];
方法2：使用字典记录每个数出现的次数，返回出现次数大于len(nums)//2的数；优化：在计数时同时判断数字出现的次数，只用一个for循环；
方法3：位运算，遍历二进制的每一位，每一位上的1或0（代码使用1）出现次数大于一半，即为所求的值在该位上的值，统计每一位的1或0组合即可，减去2^32对负数进行处理。以后出现位运算的时候，需要对结果进行判断一下最好。如果不在这个范围内，说明了结果被认为是无符号的数了，需要减去2 ^ 32。
1 | class Solution(object): |
方法4：摩尔投票法，待续。
187. 重复的DNA序列
题目描述
所有 DNA 由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来查找 DNA 分子中所有出现超多一次的10个字母长的序列（子串）。
示例:1
2
3输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出: ["AAAAACCCCC", "CCCCCAAAAA"]
解题思路
方法1：遍历+set，从头到尾把字符串遍历，然后判断这10个字母是否已经出现过，如果出现过，则加入结果中，否则，加入辅助集合中。用set是因为一个字符串可能出现多次，为了防止重复添加到结果中，使用set去重。时间空间复杂度均为O(N)。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution(object):
def findRepeatedDnaSequences(self, s):
"""
:type s: str
:rtype: List[str]
"""
if len(s) < 10:
return []
res = set()
seen = set()
for i in range(len(s)-9):
if s[i:i+10] in seen:
res.add(s[i:i+10])
else:
seen.add(s[i:i+10])
return list(res)
方法2：位运算，待续
190. 颠倒二进制位
题目描述
颠倒给定的 32 位无符号整数的二进制位。
示例 1：1
2
3
4输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：1
2
3
4输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。
提示：1
2请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
解题思路
使用python二进制转换。1
2
3
4
5
6
7
8class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
res = '{0:032b}'.format(n) # 032b的0用于填充，0:32b为' 10100101000001111010011100'，0:032b为'00000010100101000001111010011100'
res = res[::-1]
res = int(res,2)
return res
位运算。从n的最后一位向前遍历，放到res的后面，并且res向左移动。
1 | class Solution: |
1 | class Solution: |
191. 位1的个数
题目描述
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例 1：1
2
3输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：1
2
3输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：1
2
3输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：1
2请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
进阶:
如果多次调用这个函数，你将如何优化你的算法？
解题思路
1 | class Solution(object): |
1 | class Solution(object): |
