LeetCode 461. 汉明距离---村雨遥

题目461. 汉明距离[1]描述

两个整数之间的汉明距离[2]指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意： 0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4

输出: 2

解释:1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑

上面的箭头指出了对应二进制位不同的位置。

解题思路将 x, y 转换为二进制字符串；对两个字符串较长的前 两字符串长度差 位进行遍历，若不为 0 则说明不同， 距离加 1；对两字符串比较相同位数上不同的字符，一旦不同，距离加 1；返回最终距离即为汉明距离；实现/** * Created with IntelliJ IDEA. * Version : 1.0 * Author : 村雨遥 * Email : cunyu1024@foxmail.com * Website : https://cunyu1943.github.io * 公众号 : 村雨遥 * Date : 2020/4/11 15:35 * Project : LeetCode * Package : PACKAGE_NAME * Class : FourSixOne * Desc : 461. 汉明距离 */ public class FourSixOne { public static void main(String[] args) throws Exception { FourSixOne fourSixOne = new FourSixOne(); int x = 5; int y = 19; // 3 System.out.println(fourSixOne.hammingDistance(x, y)); } /** * 汉明距离 * * @param x * @param y * @return 汉明距离 */ public int hammingDistance(int x, int y) { int distance = 0; int diff = 0; // 转换为二进制字符串 String strX = Integer.toBinaryString(x); String strY = Integer.toBinaryString(y); int disBetween = Math.abs(strX.length() - strY.length()); // 比较，将长度较长的字符串的不同字符数找出 for (int i = 0; i &lt; disBetween; i++) { if (strX.length() &lt; strY.length()) { if (strY.charAt(i) != &#39;0&#39;) { diff++; } } else { if (strX.charAt(i) != &#39;0&#39;) { diff++; } } } // 通过比较两个二进制字符串，找出不同的位数 if (strX.length() &lt; strY.length()) { for (int j = 0; j &lt; strX.length(); j++) { if (strX.charAt(j) != strY.charAt(j + disBetween)) { distance++; } } } else { for (int k = 0; k &lt; strY.length(); k++) { if (strY.charAt(k) != strX.charAt(k + disBetween)) { distance++; } } } // 返回汉明距离 return distance + diff; } }参考资料

[1]

461. 汉明距离: https://leetcode-cn.com/problems/hamming-distance/

[2]

汉明距离: https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E8%B7%9D%E7%A6%BB

---来自腾讯云社区的---村雨遥