263 - 丑数(ugly-number)

Create by jsliang on 2019-07-18 17:15:35
Recently revised in 2019-07-18 17:43:26

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
3.1 解法 - 数学
3.2 解法 - 递归

二 前言

返回目录

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

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

示例 1:
输入: 6
输出: true
解释: 6 = 2 × 3

示例 2:
输入: 8
输出: true
解释: 8 = 2 × 2 × 2

示例 3:
输入: 14
输出: false 
解释: 14 不是丑数,因为它包含了另外一个质因数 7。

说明:
1 是丑数。
输入不会超过 32 位有符号整数的范围: [−231,  231 − 1]。

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

3.1 解法 - 数学

返回目录

  • 解题代码
var isUgly = function(num) {
  if (!num) {
    return false;
  }
  while (num % 2 === 0 || num % 3 === 0 || num % 5 === 0) {
    if (num % 2 === 0) {
      num = num / 2;
    }
    if (num % 3 === 0) {
      num = num / 3;
    }
    if (num % 5 === 0) {
      num = num / 5;
    }
  }
  if (num === 1) {
    return true;
  }
  if (num !== 2 || num !== 3 || num !== 5) {
    return false;
  }
  return true;
};
  • 执行测试

  • num14

  • returnfalse

  • LeetCode Submit

✔ Accepted
  ✔ 1012/1012 cases passed (92 ms)
  ✔ Your runtime beats 94.63 % of javascript submissions
  ✔ Your memory usage beats 43.01 % of javascript submissions (35.4 MB)
  • 解题思路

最复杂的思路,有可能是你最原始的思路

首先,虽然我这个题解可能复杂,但是我觉得我开始的思维是极其简单的。

  1. 如果这个 num === 0,那么它不是丑数。
  2. 如果这个数 % 2 === 0 或者 % 3 === 0 或者 %5 === 0,那么证明这个数是 2/3/5 的公倍数,那么我们就将它除于 2/3/5,同时这个数还可能是丑数。(例如 30 / 2 = 15,15 可能是丑数,所以可以继续循环)
  3. 循环这个数,直到它不能 %2%3 或者 %5 得出的结果为 0。
  4. while 后,这个数已经不能整除 2/3/5 了,所以我们最终判断它的值为多少。如果是 2/3/5,表明它是丑数;如果不是,则它不是丑数。
var isUgly = function(num) {
  if (!num) {
    return false;
  }
  while (num % 2 === 0 || num % 3 === 0 || num % 5 === 0) {
    if (num % 2 === 0) {
      num = num / 2;
    }
    if (num % 3 === 0) {
      num = num / 3;
    }
    if (num % 5 === 0) {
      num = num / 5;
    }
  }
  if (num === 1) {
    return true;
  }
  if (num !== 2 || num !== 3 || num !== 5) {
    return false;
  }
  return true;
};

最后,将结果值返回出去。

3.2 解法 - 递归

返回目录

  • 解题代码
var isUgly = function (num) {
  var list = [1, 2, 3, 5];

  if (num <= 0) {
    return false;
  }

  if (list.includes(num)) {
    return true;
  } else {
    for (li in list) {
      if (num % list[li] === 0 && list[li] !== 1) {
        return isUgly(num / list[li]);
      }
    }
  }

  return false;
};
  • 执行测试

  • num14

  • returnfalse

  • LeetCode Submit

✔ Accepted
  ✔ 1012/1012 cases passed (104 ms)
  ✔ Your runtime beats 76.45 % of javascript submissions
  ✔ Your memory usage beats 7.53 % of javascript submissions (35.8 MB)
  • 知识点

  • includes()includes() 方法用来判断一个数组是否包含一个指定的值,根据情况,如果包含则返回 true,否则返回 false。includes() 详细介绍

  • 解题思路

判断这个数,是否属于 1、2、3、5,如果不属于,则按照丑数规则进行递归,最后返回这个数的结果即可。


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-18 19:23:47

results matching ""

    No results matching ""