Leetcode按类型
位操作
位操作包括：
- ¬ 取反（NOT)
- ∩∩ 按位或（OR)
- ⊕⊕ 按位异或（XOR)
- ∪∪ 按位与（AND)
- 移位
移位是一个二元运算符，用来将一个二进制数中的每一位全部都向一个方向移动指定位，溢出的部分将被舍弃，而空缺的部分填入一定的值。
移位又分为
- 算术移位
- 逻辑移位
总结
使用 collection counter 例子
1
2
3
4
5
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
from collections import Counter
hashmap = Counter(nums)
return [x for x in hashmap if hashmap[x] == 1]
🚩421. 数组中两个数的最大异或值
给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。
找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。
你能在O(n)的时间解决这个问题吗？
1
2
3
4
5
6
7
示例:
输入: [3, 10, 5, 25, 2, 8]
输出: 28
解释: 最大的结果是 5 ^ 25 = 28.
1
2
class Solution:
def findMaximumXOR(self, nums: List[int]) -> int:
✅ 260. 只出现一次的数字 III
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
1
2
3
4
5
6
7
8
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
注意：
结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
2️⃣
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
res = 0
for num in nums:
res ^= num
# print(res)
div = 1
while div & res == 0:
print(div & res)
div <<= 1 # 位运算注意要赋值啊！！
res1, res2 = 0, 0
for num in nums:
if num & div:
res1 ^= num
else:
res2 ^= num
return [res1,res2]
✅ 461. 汉明距离
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意： 0 ≤ x, y < 2^31.
1
2
3
4
5
6
7
8
9
10
11
12
示例:
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
1
2
3
4
5
6
7
8
9
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
return bin(x^y).count('1') # .count() 计数
x = 1
y = 14
solution = Solution()
result = solution.hammingDistance(x,y)
result
