汉明距离
难度:
标签:
题目描述
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1：
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
示例 2：
输入：x = 3, y = 1 输出：1
提示：
0 <= x, y <= 231 - 1
代码结果
运行时间: 21 ms, 内存: 16.0 MB
/*
* 思路：
* 1. 使用 Java 8 的 Stream API 来计算汉明距离。
* 2. 将 XOR 操作的结果转换为二进制字符串，然后计算其中 '1' 的数量。
*/
import java.util.stream.Stream;
public class HammingDistanceStream {
public int hammingDistance(int x, int y) {
return (int) Stream.of(Integer.toBinaryString(x ^ y).split(""))
.filter(bit -> bit.equals("1")) // 过滤出 '1' 位
.count(); // 计算 '1' 的数量
}
}解释
方法:
这个题解的思路是先将两个整数x和y转化为32位的二进制字符串表示，不足32位的在左侧用0填充。然后逐位比较这两个二进制字符串，统计有多少个位置的字符不同，即为汉明距离。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择将整数转化为32位二进制字符串来处理而不是直接进行位运算？
▷🦆
在将整数转换为二进制字符串时使用`zfill(32)`确保长度为32位，这是否意味着对于较大的整数（大于2^31）这种方法仍然有效？
▷🦆
在比较两个二进制字符串的对应位置时，是否有可能通过其他数据结构或方法优化这一过程？
▷🦆
在实际应用中，这种基于字符串的处理方式与基于位运算的处理方式在性能上会有怎样的差异？
▷相关问题
位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 3 中，输入表示有符号整数
-3。
示例 1：
输入：n = 00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：n = 00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：n = 11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
- 输入必须是长度为
32的 二进制串 。
进阶：
- 如果多次调用这个函数，你将如何优化你的算法？
汉明距离总和
两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
给你一个整数数组 nums，请你计算并返回 nums 中任意两个数之间 汉明距离的总和 。
示例 1：
输入：nums = [4,14,2] 输出：6 解释：在二进制表示中，4 表示为 0100 ，14 表示为 1110 ，2表示为 0010 。（这样表示是为了体现后四位之间关系） 所以答案为： HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6
示例 2：
输入：nums = [4,14,4] 输出：4
提示：
1 <= nums.length <= 1040 <= nums[i] <= 109- 给定输入的对应答案符合 32-bit 整数范围