資訊專(zhuān)欄INFORMATION COLUMN
摘要：也就是說(shuō)如果我要求第個(gè)的倍數(shù)，就讓乘以數(shù)列中第個(gè)數(shù)。同理，的倍數(shù)也是如此。知道這個(gè)遞增關(guān)系，就可以保存當(dāng)前是第幾個(gè)倍數(shù)，方便計(jì)算下一個(gè)數(shù)。
題目：求第n個(gè)Hamming numbers
Hamming number
$$H = 2^i * 3^j * 5^k$$
其中：
$$i, j, k >= 0$$
解這道題倒是不難，只要暴力循環(huán)就好了，只不過(guò)這樣挺蠢的，而且浪費(fèi)資源也挺多的，所以也沒(méi)有通過(guò)測(cè)試。
我想著Hamming number如何預(yù)測(cè)某個(gè)數(shù)的2倍或者3、5倍在整體數(shù)列中的位置，想了半天都沒(méi)什么頭緒。于是上網(wǎng)看了個(gè)解決方案，理解了下，思路大概是這樣的：
Hamming number數(shù)列是這樣的：
1，2，3，4，5，6，8，9，10，12，15，16……
觀察其中2的數(shù)列，有：
2×1，2×2，2×3，2×4，2×5，2×6，2×8……
可以發(fā)現(xiàn)Hamming number除以2以后仍然在該數(shù)列中，觀察可以得出數(shù)列第一個(gè)2的倍數(shù)，其實(shí)就是2乘以數(shù)列中的第一個(gè)數(shù)，第二個(gè)2的倍數(shù)是2乘以數(shù)列中的第二個(gè)數(shù)，后面的數(shù)字都是如此。也就是說(shuō)如果我要求第5個(gè)2的倍數(shù)，就讓2乘以數(shù)列中第5個(gè)數(shù)。
同理，3、5的倍數(shù)也是如此。知道這個(gè)遞增關(guān)系，就可以保存當(dāng)前是第幾個(gè)倍數(shù)，方便計(jì)算下一個(gè)數(shù)。
按上面的思路，有下面這個(gè)算法：
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]
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/40954.html
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 < ...
摘要：題目漢明距離是兩個(gè)字符串對(duì)應(yīng)位置的不同字符的個(gè)數(shù)，這里指二進(jìn)制的不同位置例子我的解法先將，進(jìn)行異位或運(yùn)算再轉(zhuǎn)化成二進(jìn)制然后把去掉算出長(zhǎng)度其他方法先算出不同位數(shù)，然后用右移運(yùn)算符算出能右移幾次來(lái)獲取距離 1題目 The Hamming distance between two integers is the number of positions at which the corresp...
摘要：漢明距離是使用在數(shù)據(jù)傳輸差錯(cuò)控制編碼里面的，漢明距離是一個(gè)概念，它表示兩個(gè)相同長(zhǎng)度字對(duì)應(yīng)位不同的數(shù)量，我們以表示兩個(gè)字之間的漢明距離。對(duì)兩個(gè)字符串進(jìn)行異或運(yùn)算，并統(tǒng)計(jì)結(jié)果為的個(gè)數(shù)，那么這個(gè)數(shù)就是漢明距離。 461. Hamming Distance 題目鏈接 461. Hamming Distance 題目分析 本題要求計(jì)算漢明距離。 漢明距離是使用在數(shù)據(jù)傳輸差錯(cuò)控制編碼里面的，漢明距...
摘要：依次移位復(fù)雜度思路依次移動(dòng)位數(shù)進(jìn)行計(jì)算。代碼利用性質(zhì)復(fù)雜度，思路代碼 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...
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...
閱讀 2240·2021-11-22 13:52
閱讀 3888·2021-11-10 11:36
閱讀 1427·2021-09-24 09:47
閱讀 1100·2019-08-29 13:54
閱讀 3372·2019-08-29 13:46
閱讀 1954·2019-08-29 12:16
閱讀 2121·2019-08-26 13:26
閱讀 3479·2019-08-23 17:10
