1、汉明距离（461）
题目描述：
【简单】
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
0
≤
x
,
y
<
2
31
.
0 ≤ x, y < 2^{31}.
0≤x,y<231.
示例：
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
思路分析：
1、首先是二进制
2、想到二进制的按位异或运算：当两个对应位不同时结果才为1，相同时得0.
3、那么我们就可以对这两数进行异或操作，然后统计1的个数
解答：
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
return bin(x^y).count("1")#进行异或操作然后转换成二进制
-
时间复杂度：
O
(
1
)
O(1)
O(1)
-
空间复杂度：
O
(
1
)
O(1)
O(1)
2、只出现一次的数字（136）
题目描述：
【简单】
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
思路分析：
1、由于题目要求使用常数空间复杂度
2、因此我们可以运用位运算的异或操作解决
3、对于这道题，可使用异或运算 。异或运算有以下三个性质：
- 任何数和 0 做异或运算，结果仍然是原来的数，
- 任何数和其自身做异或运算，结果是 0
- 异或运算满足交换律和结合律
4、两个相同的数异或的结果为 0，对所有数进行异或操作，最后的结果就是单独出现的那个数。
解答：
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return reduce(lambda x, y: x ^ y, nums)
-
时间复杂度：
O
(
1
)
O(1)
O(1)
-
空间复杂度：
O
(
1
)
O(1)
O(1)