Kata：Hamming number

huhud 發(fā)布于2019-07-30 14:50 / 742人閱讀

摘要：也就是說如果我要求第個的倍數，就讓乘以數列中第個數。同理，的倍數也是如此。知道這個遞增關系，就可以保存當前是第幾個倍數，方便計算下一個數。

題目：求第n個Hamming numbers

Hamming number

$$H = 2^i * 3^j * 5^k$$

其中：

$$i, j, k >= 0$$

解這道題倒是不難，只要暴力循環(huán)就好了，只不過這樣挺蠢的，而且浪費資源也挺多的，所以也沒有通過測試。

我想著Hamming number如何預測某個數的2倍或者3、5倍在整體數列中的位置，想了半天都沒什么頭緒。于是上網看了個解決方案，理解了下，思路大概是這樣的：

Hamming number數列是這樣的：

1，2，3，4，5，6，8，9，10，12，15，16……

觀察其中2的數列，有：

2×1，2×2，2×3，2×4，2×5，2×6，2×8……

可以發(fā)現(xiàn)Hamming number除以2以后仍然在該數列中，觀察可以得出數列第一個2的倍數，其實就是2乘以數列中的第一個數，第二個2的倍數是2乘以數列中的第二個數，后面的數字都是如此。也就是說如果我要求第5個2的倍數，就讓2乘以數列中第5個數。

同理，3、5的倍數也是如此。知道這個遞增關系，就可以保存當前是第幾個倍數，方便計算下一個數。

按上面的思路，有下面這個算法：

def hamming(limit):
    h = [1] * limit
    x2, x3, x5 = 2, 3, 5
    i = j = k = 0

    for n in range(1, limit):
        h[n] = min(x2, x3, x5)
        if x2 == h[n]:
            i += 1
            x2 = 2 * h[i]
        if x3 == h[n]:
            j += 1
            x3 = 3 * h[j]
        if x5 == h[n]:
            k += 1
            x5 = 5 * h[k]
    return h[-1]

云服務器 GPU云服務器 Kata Hamming numberic Numbers

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/40954.html

[LeetCode] 461. Hamming Distance

Problem 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 < ...

import. 2019-08-16 13:25 評論0 收藏0
leetcode7:漢明距離

摘要：題目漢明距離是兩個字符串對應位置的不同字符的個數，這里指二進制的不同位置例子我的解法先將，進行異位或運算再轉化成二進制然后把去掉算出長度其他方法先算出不同位數，然后用右移運算符算出能右移幾次來獲取距離 1題目 The Hamming distance between two integers is the number of positions at which the corresp...

xeblog 2019-08-23 16:46 評論0 收藏0
Leetcode PHP題解--D11 461. Hamming Distance

摘要：漢明距離是使用在數據傳輸差錯控制編碼里面的，漢明距離是一個概念，它表示兩個相同長度字對應位不同的數量，我們以表示兩個字之間的漢明距離。對兩個字符串進行異或運算，并統(tǒng)計結果為的個數，那么這個數就是漢明距離。 461. Hamming Distance 題目鏈接 461. Hamming Distance 題目分析本題要求計算漢明距離。漢明距離是使用在數據傳輸差錯控制編碼里面的，漢明距...

zero 2019-07-01 12:36 評論0 收藏0
LeetCode[191] Number of 1 Bits

摘要：依次移位復雜度思路依次移動位數進行計算。代碼利用性質復雜度，思路代碼 LeetCode[191] Number of 1 Bits Write a function that takes an unsigned integer and returns the number of ’1 bits it has (also known as the Hamming weight). Fo...

Scliang 2019-08-14 15:00 評論0 收藏0
[LeetCode] 191. Number of 1 Bits

Problem Number of 1 BitsWrite a function that takes an unsigned integer and returns the number of ’1 bits it has (also known as the Hamming weight). Example For example, the 32-bit integer 11 has bina...

gitmilk 2019-08-16 12:31 評論0 收藏0