Home C# LeetCode Programming TDD TDD LeetCode：461. Hamming Distance

TDD LeetCode：461. Hamming Distance

, , , Edit

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
Note:
0 ≤ x, y < 231.
Example:
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.


Step0 題目說明

首先先來看一下維基百科對於漢明距離的說明，「在資訊理論中，兩個等長字符串之間的漢明距離（英語：Hamming distance）是兩個字符串對應位置的不同字符的個數。換句話說，它就是將一個字符串變換成另外一個字符串所需要替換的字符個數。」

如果以下面這個例子為例，這個漢明距離就是 3。
  • 1 0 1 1 1 0 1
  • 1 0 0 1 0 0 0

了解題目之後，我想我大概需要幾個功能

  1. 數字轉2進位
  2. 字串左邊補0
  3. 字串相異判斷

Step1 撰寫2進位測試程式
[TestMethod]
public void ToBinary_TestMethod1()
{
    int input = 1;
    String expected = "1";

    Algorithm alg = new Algorithm();
    string actual = alg.toBinary(input);

    Assert.AreEqual(expected,actual);
}

[TestMethod]
public void ToBinary_TestMethod2()
{
    int input = 4;
    String expected = "100";

    Algorithm alg = new Algorithm();
    string actual = alg.toBinary(input);

    Assert.AreEqual(expected, actual);
}
Step2 撰寫轉換成2進位程式
public String toBinary(int input)
{
    return Convert.ToString(input, 2);
}
Step3 文字左邊補0
[TestMethod]
public void AddZeroInFromt_TestMethond1()
{
    string input = "1";
    int length = 3;
    String expected = "001";

    Algorithm alg = new Algorithm();
    string actual = alg.AddZeroInFront(input, length);

    Assert.AreEqual(expected, actual);
}

Step4 撰寫文字左邊補0程式
public String AddZeroInFront(String input, int length)
{
    return input.PadLeft(length,'0');
}
Step5 撰寫字串相異測試程式
[TestMethod]
public void HammingDistance_TestMethond1()
{
    int x = 1;
    int y = 4;
    int expected = 2;

    Algorithm alg = new Algorithm();
    int actual = alg.HammingDistance(x, y);

    Assert.AreEqual(expected, actual);
}

Step6 撰寫字串相異程式
public int HammingDistance(int x, int y)
{
    string binaryX = toBinary(x);
    string binaryY = toBinary(y);

    if (binaryY.Length > binaryX.Length)
    {
        binaryX = AddZeroInFront(binaryX, binaryY.Length);
    }
    else
    {
        binaryY = AddZeroInFront(binaryY, binaryX.Length);
    }

    int count = 0;
    for (int i = 0; i < binaryX.Length; i++)
    {
        if (  binaryX.Substring(i, 1) != binaryY.Substring(i, 1))
        {
            count ++ ;
        }

    }

    return count;
}

※後記
我一開使在解這個題目的時候，只看範例而沒有認真看題目，我以為是要算第一個和最後一個相異欄位的距離，一直寫到後面才發現原來我根本搞錯題目了 XD 所以除了看範例之外，題目也是要認真看的。
※延伸閱讀

TDD LeetCode：832. Flipping an Image

TDD LeetCode：905. Sort Array By Parity

TDD LeetCode：804. Unique Morse Code Words

    Blogger Comment

0 意見:

張貼留言

訂閱： 張貼留言 ( Atom )