LeetCode 461.汉明距离 - Java

该题原址:​​https://leetcode-cn.com/problems/hamming-distance/​​

问题描述

问题分析

找出两个数二进制相同位置的不同的个数之和.

考察位运算.

可以想到异或,两个数异或后不同为1,相同为0,因此就转换为求1的问题.

对于求1的问题可以看此文:​​计算二进制中1的个数-Java____[位运算思维]​​

代码演示

1. 使用java自带方法求解

/**
   * 执行用时 : 1 ms, 在Hamming Distance的Java提交中击败了99.49% 的用户
     * 内存消耗 : 32.2 MB, 在Hamming Distance的Java提交中击败了92.20% 的用户
   * 
   */
  public static int hammingDistance(int x, int y) {
    if(x == y) { return 0; } // 这条判断很关键,可以节省大部分内存,提高效率
    return Integer.bitCount(x^y);
  }
}      

2. 异或后,利用求二进制中1的个数

public static int hammingDistance(int x, int y) {
    int num = 0;
    int temp = x^y;
      while (temp != 0) { 
         temp = (temp - 1) & temp; 
         num++; 
      }
    return num;
  }      

3.首先想出的笨方法(忘了异或那回事)

class Solution {
  /**
   * 执行用时 : 2 ms, 在Hamming Distance的Java提交中击败了68.93% 的用户 
   * 内存消耗 : 33.4 MB, 在Hamming Distance的Java提交中击败了77.38% 的用户
   */
  public int hammingDistance(int x, int y) {
    int num = 0;
    int bigLen = 0;
    if (x > y) {
      bigLen = x;
    } else {
      bigLen = y;
    }
    int len = Integer.toBinaryString(bigLen).length();
    for (int i = 0; i < len; i++) {
      if ((x & 1) != (y & 1)) {
        num++;
      }
      x = x >> 1;
      y = y >> 1;
    }
    return num;
  }
}      

4. 上一种方法的优化(实际上性能一点没有提高)

public static int hammingDistance(int x, int y) {
    int num = 0;
    int temp;
    if(x == y) { return 0; }
    if(x>y) { // 保证y>x
      temp = x;
      x = y;
      y = temp;
    }
    
    int len = Integer.toBinaryString(x).length(); // 先将小数的二进制位的不同的位数列出
    for (int i = 0; i < len; i++) {
      if ((x & 1) != (y & 1)) {
        num++;
      }
      x = x >> 1;
      y = y >> 1; // 比较之后两个数同时向右移一位
    }
    
    while(y!=0) { // 求出大数剩余位数的1的个数
      y = (y-1)&y;
      num++; 
    }
    return num;
  }      

总结

要想有一个好的解决办法,看你能否想出他要考察的是什么知识.