写点什么

【LeetCode】汉明距离 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 06 月 08 日

题目描述

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


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


示例:
输入: x = 1, y = 4
输出: 2
解释:1 (0 0 0 1)4 (0 1 0 0) ↑ ↑
上面的箭头指出了对应二进制位不同的位置。
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/hamming-distance著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 这个题目是简单题目,主要是对位运算知识的考察。通过题目对汉明距离的解释,发现是异或运算的应用。

  • 异或运算只有对应位置不同是才为 1。

  • 通过异或运算得出临时变量,然后统计位 1 的个数即位题目答案。

  • 在位运算中,n & (n - 1) 可以将最低位的 1 变成 0

AC 代码

    public int hammingDistance(int x, int y) {        int ans = 0;        int n = x ^ y;        while (n != 0) {            ans++;            n &= (n - 1);         }        return ans;    }            public int hammingDistance1(int x, int y) {        int n = x ^ y;        return Integer.bitCount(n);    }
复制代码

总结

  • 上述算法代码的时间复杂度是 O(n), 空间复杂度是 O(1)

  • 在 Java 中,一般使用 bitCount 来统计位 1 的个数。一起来看一下 bitCount 的实现过程。


    /**     * Returns the number of one-bits in the two's complement binary     * representation of the specified {@code int} value.  This function is     * sometimes referred to as the <i>population count</i>.     *     * @param i the value whose bits are to be counted     * @return the number of one-bits in the two's complement binary     *     representation of the specified {@code int} value.     * @since 1.5     */    public static int bitCount(int i) {        // HD, Figure 5-2        i = i - ((i >>> 1) & 0x55555555);        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);        i = (i + (i >>> 4)) & 0x0f0f0f0f;        i = i + (i >>> 8);        i = i + (i >>> 16);        return i & 0x3f;    }
复制代码


bitCount 也是位运算的应用,比我的实现更加深入一些。


  • 这个算法题目我不是第一次做,第二次明显比第一次做的快了很多,算法题目多做几次,能掌握的更好!

  • 坚持每日一题,加油!

发布于: 2021 年 06 月 08 日阅读数: 7
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】汉明距离Java题解