263.UglyNumber

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

题目: 263. Ugly Number

题目地址：https://leetcode.com/problems/ugly-number/

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example 1:

Input: 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2

Example 3:

Input: 14
Output: false 
Explanation: 14 is not ugly since it includes another prime factor 7.

Note:

  1. 1 is typically treated as an ugly number.

  2. Input is within the 32-bit signed integer range: [−231,  231 − 1].

解题思路

解决ugly number的原题：

已经被leetcode更新过，原题和上面的描述类似，但原题应该稍微更容易想一些。因此在解上面道题之前，让我们先来看看原题的解法，原题是这样的：它跟上面这道题只有唯一一个不同的地方，那就是输入k，然后要我们求出第k个（或者可以理解为第k小的）ugly number。

我们先看看第一个ugly number是什么呢？题目已经说了，是1。注意到接下来的ugly number可以通过用2, 3, 5乘以前面的ugly number得到。现在ugly number的序列里面已经有一个1了，设这个ugly number的序列为uglyNums，则现在有uglyNums=[1]，所以那第二个ugly number就看三个质因素(prime factors)2, 3, 5乘以1得到的值哪个最小，发现2*1=2最小，所以第二个ugly number也就是2了，现在uglyNums=[1, 2]，如下图所示。由于2*1=2已经被记录到uglyNums里面了，所以接下来与2这个质因数相乘得到的ugly number应该是2*2=4，也就是要让2乘以列表中已记录的下一个ugly number才有意义了。如此类推，下一个uglyNums应该是3了，因为在{3*1=3, 5*1=5, 2*2=4}里面，3*1=3最小，uglyNums更新为[1, 2, 3]，同样地，质因素3要指向它对应的下一个ugly number，即uglyNums[1]=2。

重复这个过程，可以得到uglyNums=[1, 2, 3, 4, 5]，如下面第一幅图所示。注意到会出现一种情况：两个质因素乘以不同ugly number得出相同的值。例如我们看下第二幅图，3*2=6，同时又有2*3=6，这时候因为它们都比5*2=10小，所以它们同时最小，uglyNums的下一个ugly number（即uglyNums[5]）设为6，同时要让3和2都与它们对应的下一个ugly number相乘，质因素将3和2分别与uglyNums[2]和uglyNums[3]相乘，如最后一幅图所示。

至此，ugly number的原题就被解决掉了。写程序的时候要注意第一个ugly number是1，要作为特殊条件判断一下。接下来解决现在的题目：263. Ugly Number https://leetcode.com/problems/ugly-number/

解决现在的题目263. Ugly Number：

现在的题目是：给定一个数，判断它是不是ugly number。设这个给定的数是n，首先考虑到小于x的数不可能多于n个（更准确地说，小于n的ugly number个数不超过n个），因此，只要生成k(令k=n)个ugly number，再判断一下这n个ugly number里面有没有包含n即可，如果包含则说明n是ugly number，否则就不是ugly number。

时间复杂度

按照上面的解法，本题的时间复杂度实际上等于生成n个ugly number的时间复杂度，设质因数的个数m，则生成n个ugly number的时间复杂度是O(mn)

最终实现

Java实现

import java.util.ArrayList;
import java.util.List;
public class Solution {
    private List<Long> uglyNums = new ArrayList<>();
    /**
     *
     * The solution for the old problem 263
     * @param k the input of the problem
     * @return the kth ugly number
     */
    public long calcUglyNumber(int k) {
        uglyNums.clear();
        uglyNums.add(1L);
        FactorRecord factorTwo = new FactorRecord(2, 0);
        FactorRecord factorThree = new FactorRecord(3, 0);
        FactorRecord factorFive = new FactorRecord(5, 0);
        for (int i = 0; i < k; i++) {
            long minVal = Math.min(factorFive.calcCurrentVal(uglyNums),
                    Math.min(factorTwo.calcCurrentVal(uglyNums), factorThree.calcCurrentVal(uglyNums)));
            if (minVal == factorTwo.calcCurrentVal(uglyNums)) {
                if (uglyNums.get(uglyNums.size() - 1) != minVal) {
                    uglyNums.add(minVal);
                }
                factorTwo.setIndex(factorTwo.getIndex() + 1);
            }
            if (minVal == factorThree.calcCurrentVal(uglyNums)) {
                if (uglyNums.get(uglyNums.size() - 1) != minVal) {
                    uglyNums.add(minVal);
                }
                factorThree.setIndex(factorThree.getIndex() + 1);
            }
            if (minVal == factorFive.calcCurrentVal(uglyNums)) {
                if (uglyNums.get(uglyNums.size() - 1) != minVal) {
                    uglyNums.add(minVal);
                }
                factorFive.setIndex(factorFive.getIndex() + 1);
            }
        }
        return uglyNums.get(k);
    }
    public boolean isUgly(int num) {
        if (num == 1) {
            return true;
        }
        uglyNums.clear();
        uglyNums.add(1L);
        FactorRecord factorTwo = new FactorRecord(2, 0);
        FactorRecord factorThree = new FactorRecord(3, 0);
        FactorRecord factorFive = new FactorRecord(5, 0);
        int k = num;
        for (int i = 0; i < k; i++) {
            long minVal = Math.min(factorFive.calcCurrentVal(uglyNums),
                    Math.min(factorTwo.calcCurrentVal(uglyNums), factorThree.calcCurrentVal(uglyNums)));
            if (minVal == num) {
                return true;
            }
            if (minVal > num) {
                return false;
            }
            if (minVal == factorTwo.calcCurrentVal(uglyNums)) {
                if (uglyNums.get(uglyNums.size() - 1) != minVal) {
                    uglyNums.add(minVal);
                }
                factorTwo.setIndex(factorTwo.getIndex() + 1);
            }
            if (minVal == factorThree.calcCurrentVal(uglyNums)) {
                if (uglyNums.get(uglyNums.size() - 1) != minVal) {
                    uglyNums.add(minVal);
                }
                factorThree.setIndex(factorThree.getIndex() + 1);
            }
            if (minVal == factorFive.calcCurrentVal(uglyNums)) {
                if (uglyNums.get(uglyNums.size() - 1) != minVal) {
                    uglyNums.add(minVal);
                }
                factorFive.setIndex(factorFive.getIndex() + 1);
            }
        }
        return false;
    }
    class FactorRecord {
        long factor; // 2, 3, 5
        int index;
        public FactorRecord(long factor, int index) {
            this.factor = factor;
            this.index = index;
        }
        public void setFactor(long factor) {
            this.factor = factor;
        }
        public void setIndex(int index) {
            this.index = index;
        }
        public long getFactor() {
            return factor;
        }
        public int getIndex() {
            return index;
        }
        public long calcCurrentVal(List<Long> uglyNums) {
            return factor * uglyNums.get(index);
        }
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        boolean res = solution.isUgly(2144843814);
        System.out.println(res);
    }
}

 

以上是 263.UglyNumber 的全部内容， 来源链接： utcz.com/z/518324.html

回到顶部