Kata：Hamming number

huhud 发布于2019-07-30 14:50 / 736人阅读

摘要：也就是说如果我要求第个的倍数，就让乘以数列中第个数。同理，的倍数也是如此。知道这个递增关系，就可以保存当前是第几个倍数，方便计算下一个数。

题目：求第n个Hamming numbers

Hamming number

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

其中：

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

解这道题倒是不难，只要暴力循环就好了，只不过这样挺蠢的，而且浪费资源也挺多的，所以也没有通过测试。

我想着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……

可以发现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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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

摘要：汉明距离是使用在数据传输差错控制编码里面的，汉明距离是一个概念，它表示两个相同长度字对应位不同的数量，我们以表示两个字之间的汉明距离。对两个字符串进行异或运算，并统计结果为的个数，那么这个数就是汉明距离。 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