codewars--js--Hamming Numbers

问题描述：

A Hamming number is a positive integer of the form 2ⁱ3^j5^k, for some non-negative integers i, j, and k.

Write a function that computes the nth smallest Hamming number.

Specifically:

The first smallest Hamming number is 1 = 2⁰3⁰5⁰
The second smallest Hamming number is 2 = 2¹3⁰5⁰
The third smallest Hamming number is 3 = 2⁰3¹5⁰
The fourth smallest Hamming number is 4 = 2²3⁰5⁰
The fifth smallest Hamming number is 5 = 2⁰3⁰5¹

The 20 smallest Hamming numbers are given in example test fixture.

Your code should be able to compute all of the smallest 5,000 (Clojure: 2000) Hamming numbers without timing out.

我的思路：

本题自己是没有任何思路的，只是知道汉明数肯定是2或3或5的倍数，但是无从下手。后来看别人的答案，主要思路也是如此。

下一个汉明数为已存在汉明数的2x，3x，5x的倍数。

若i2是我们没有用过的汉明数的指数的话，就乘以2；

若i3是我们没有用过的汉明数的指数的话，就乘以3；

若i5是我们没有用过的汉明数的指数的话，就乘以5。

我的答案：无，o(╥﹏╥)o

优秀答案：

（1）

function hamming (n) {

  var seq = [1];

  var i2 = 0, i3 = 0, i5 = 0;

  for (var i = 1; i < n; i++) {

    var x = Math.min(2 * seq[i2], 3 * seq[i3], 5 * seq[i5]);

    seq.push(x);

    if (2 * seq[i2] <= x) i2++;  //<= 可换成 ==

    if (3 * seq[i3] <= x) i3++;

    if (5 * seq[i5] <= x) i5++;

  }

  return seq[n-1];

}

哈哈哈！

巴特西

codewars--js--Hamming Numbers

最新文章

热门文章