LeetCode: 461-Hamming Distance 解題紀錄

Last Updated on 2021-11-19 by Clay

題目

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, return the Hamming distance between them.

Example 1:

Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
The above arrows point to positions where the corresponding bits are different.

Example 2:

Input: x = 3, y = 1
Output: 1

題目解釋得非常清楚：所謂的漢明距離就是兩整數之間在二進制的不同位數總數。

比方說 1 (0001) 和 4 (0100) 就有兩位是不一樣的，故兩數之間的漢明距離為 2。

---

解題思路

我第一感嘗試的方法可說是最暴力的，但時間跟空間看起來還不錯。

1. 首先先計算出 x 或 y 最後大於的 2 次方數 max_n（像是要轉換二進制一般）
2. 分成三種情況：
   1. x >= max_n && y >= max_n
   2. x >= max_n && y < max_n
   3. x < max_n && y >= max_n
3. 只要 x 或 y 大於 max_n 就將其減去。其中後兩種情況需要替漢明距離增加 1，因為這代表 x 和 y 在此位數不同
4. 每次進行判斷後都要將 max_n 除以 2，直到 max_n 等於 1 則跳出判斷
5. 最後要判斷 x 和 y 的尾數，因為可能有 1 和 0 的餘數分別。

文字敘述起來或許有些紊亂，下方直接紀錄程式碼。

C++ 程式碼

class Solution {
public:
    int hammingDistance(int x, int y) {
        // Init
        int max_n = 2;
        int d = 0;
        
        // Count max n
        while (x >= max_n || y >= max_n) {
            if (max_n <= INT_MAX-max_n) max_n = max_n * 2;
            else break;
        }
        
        // Create binary expressions
        while (max_n != 1) {
            if (x >= max_n && y >= max_n) {
                x -= max_n;
                y -= max_n;
            }
            else if (x >= max_n && y < max_n){
                d += 1;
                x -= max_n;
            }
            else if (x < max_n && y >= max_n) {
                d += 1;
                y -= max_n;
            }
            
            max_n /= 2;
        }
        
        if (x != y) ++d;
        
        return d;
    }
};

Python 程式碼

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        # Init
        max_n = 2
        d = 0
        
        # Count max_n
        while x > max_n or y > max_n:
            max_n *= 2
        
        # Count distance
        while (max_n != 1):
            if (x >= max_n and y >= max_n):
                x -= max_n
                y -= max_n
            elif (x >= max_n and y < max_n):
                d += 1
                x -= max_n
            elif (x < max_n and y >= max_n):
                d += 1
                y -= max_n
            
            max_n /= 2
        
        # Complete
        if x != y: d += 1
            
        return d

---

References

• https://leetcode.com/problems/hamming-distance/

---

Read More

• LeetCode 解題紀錄目錄