77 - 丑数

题目

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1:

输入: 6

输出: true

解释: 6 = 2 × 3

示例 2:

输入: 8

输出: true

解释: 8 = 2 × 2 × 2

示例 3:

输入: 14

输出: false

解释: 14 不是丑数，因为它包含了另外一个质因数 7。

说明：

1. 是丑数。

2. 输入不会超过 32 位有符号整数的范围: $[-2^{31}, 2^{31}-1]$

解答

就是说，判断一个数是否能被2、3、5乘起来咯

然后规定了输入整数范围，那么最快的速度就是枚举😂😂

直接除

作者：vailing

链接：https://leetcode-cn.com/problems/ugly-number/solution/lian-xu-pan-duan-zui-hao-by-vailing/

var isUgly = function (num) {
  if (num <= 0) {
    return false;
  }
  while (num != 1) {
    if (num % 2 === 0) {
      num /= 2
    } else if (num % 3 === 0) {
      num /= 3
    } else if (num % 5 === 0) {
      num /= 5
    } else {
      return false
    }
  }
  return true
};

Runtime: 68 ms, faster than 79.32% of JavaScript online submissions for Ugly Number.

Memory Usage: 35.6 MB, less than 33.33% of JavaScript online submissions for Ugly Number.

func isUgly(num int) bool {
    if num <= 0 {
        return false
    }
    for num != 1{
        if num%2==0 {
            num/=2
        } else if num%3==0 {
            num /=3
        } else if num%5==0{
            num /=5
        } else {
            return false
        }
    }
    return true
}

Runtime: 4 ms, faster than 37.27% of Go online submissions for Ugly Number.

Memory Usage: 2.1 MB, less than 100.00% of Go online submissions for Ugly Number.

一次判断完

上面的做法，每次都要判断三个，就很浪费

这种做法能在一次判断完

作者：ge-lu 链接：https://leetcode-cn.com/problems/ugly-number/solution/0msjie-by-ge-lu-3/

func isUgly(num int) bool {
    if num <= 0 {
        return false
    }
    for num%2==0{
        num /=2
    }
    for num%3==0{
        num /=3
    }
    for num%5==0{
        num /=5
    }
    return num==1
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Ugly Number.

Memory Usage: 2.2 MB, less than 50.00% of Go online submissions for Ugly Number.

一下子快了很多

var isUgly = function (num) {
  if (num <= 0) {
    return false;
  }
  while(num%2===0){
    num /= 2
  }
  while(num%3===0){
    num /= 3
  }
  while(num%5===0){
    num /= 5
  }
  return num===1
};

Runtime: 68 ms, faster than 79.32% of JavaScript online submissions for Ugly Number.

Memory Usage: 35.5 MB, less than 66.67% of JavaScript online submissions for Ugly Number.

来，全给你列出来了

全算出来，看看效果怎样

const getAll = function () {
  const result = [1]
  for (let i = 2; i < 231; i++) {
    let item = i
    while (item % 2 === 0) {
      item /= 2
    }
    while (item % 3 === 0) {
      item /= 3
    }
    while (item % 5 === 0) {
      item /= 5
    }
    if (item === 1) {
      result.push(i)
    }
  }
  console.log("result", result)
}

那么结果是啥呢？

const all = [
  1,   2,   3,   4,   5,   6,   8,   9,  10,  12,  15,
   16,  18,  20,  24,  25,  27,  30,  32,  36,  40,  45,
   48,  50,  54,  60,  64,  72,  75,  80,  81,  90,  96,
  100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180,
  192, 200, 216, 225
]

那么速度怎样呢？

var isUgly = function (num) {
  if (all.indexOf(num) !== -1) {
    return true
  }
  return false
};

。。。我发现我看错了

不是231，而是$2^{31}$。

好吧。是枚举不了的了。。

顺便把go的也写了，还用了二分法。。然而由于枚举不完就算了吧。。

go没有现成的算法，只能手写

func isUgly(num int) bool {
    all := []int{
        1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,
        16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45,
        48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96,
        100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180,
        192, 200, 216, 225,
    }
    for _, elem := range all {
        if num == elem {
            return true
        }
    }
    return false
}

但是排序过的切片，可以用二分法查找啊。

func searchInsert(nums []int, target int) bool {
    left := 0
    right := len(nums) - 1
    for left < right {
        mid := (left + right) / 2
        if target > nums[mid] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return nums[right] == target
}
func isUgly(num int) bool {
    all := []int{
        1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,
        16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45,
        48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96,
        100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180,
        192, 200, 216, 225,
    }
    return searchInsert(all, num)
}