团灭丑数问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/*
    * 第一种思路
    * 在丑数小于 num 时
    * 依次计算，丑数数列的下一个
    * 直到数列的数字 >= 丑数时
    * 当 == 丑数时，true。 当 > 丑数时， false。
    * */
    public static boolean isUgly(int num) {
        if (num <= 0) return false;

        int p2 = 0, p3 = 0, p5 = 0;
        ArrayList<Integer> list = new ArrayList<>();
        list.add(1);

        int i = 0;
        while (list.get(i) < num){
            list.add(Math.min(Math.min(list.get(p2) * 2, list.get(p3) * 3), list.get(p5) * 5));

            i ++;
            if (list.get(i) == list.get(p2) * 2) p2 ++;
            if (list.get(i) == list.get(p3) * 3) p3 ++;
            if (list.get(i) == list.get(p5) * 5) p5 ++;
        }

        return list.get(i) == num;
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/*
* 
* 思路三：
* 递归
* 跟思路二类似
* 迭代 换成 递归
* */
public static boolean isUgly(int num) {
    if (num < 1) return false;
    if (num == 1) return true;
    return search(num);
}

public static boolean search(int num){
    if (num == 1) return true;

    // 如果对 2 3 5都不能整除, 则说明这条路走不通, 返回上一层
    if (num % 2 != 0 && num % 3 != 0 && num % 5 != 0) return false;

    if (num % 2 == 0){
        return search(num >> 1);
    }else if (num % 3 == 0){
        return search(num / 3);
    }
    return search(num / 5);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

 /*
    *
    * 思路一：
    * 最小堆
    * 利用优先队列有自动排序的功能
    * 每次取出队头元素，存入队头元素*2、队头元素*3、队头元素*5
    * 但注意，像12这个元素，可由4乘3得到，也可由6乘2得到，所以要注意去重
    * */
    public int nthUglyNumber1(int n) {

        PriorityQueue<Long> queue = new PriorityQueue<>();

        long answer = 1;
        for (int i = 1; i < n; i++) {
            queue.add(answer * 2);
            queue.add(answer * 3);
            queue.add(answer * 5);

            answer = queue.remove();
            while (!queue.isEmpty() && queue.peek() == answer) queue.remove();
        }

        return (int)answer;
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

    /*
    * 进一步使用 set 优化 去重
    * */
    public int nthUglyNumber2(int n) {

        PriorityQueue<Long> queue = new PriorityQueue<>();
        HashSet<Long> set = new HashSet<>();
        int[] nums = {2,3,5};

        long answer = 1;
        for (int i = 1; i < n; i++) {
            long tmp = queue.peek();
            for (int j = 0; j < nums.length; j++) {
                if (set.contains(nums[i] * tmp)){
                    set.add(nums[i] * tmp);
                    queue.add(nums[i] * tmp);
                }
            }
            answer = queue.remove();
        }
        return (int)answer;
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

    /*
     *
     * 思路三：
     * 动态规划 三指针法
     * 起初三根指针都指向数组 0 位置
     * 当数组的下一个是 *2 得出时， p2++, *3 得出时， p3++, *5 得出时， p5++
     * 注意有可能，同时是 2 和 3的公倍数， 比如6， 当下一个为6时， p2 和 p3同时 ++
     * */
    public int nthUglyNumber(int n) {
        int p2 = 0, p3 = 0, p5 = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(Math.min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5);

            if (dp[i] == dp[p2] * 2) p2 ++;
            if (dp[i] == dp[p3] * 3) p3 ++;
            if (dp[i] == dp[p5] * 5) p5 ++;
        }
        return dp[n - 1];
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

public static int nthUglyNumber(int n, int a, int b, int c) {
    // 看到 n 的范围就应该想到二分
    long low = Math.min(Math.min(a, b), c);

    long high = low * n;

    long res = binarySearch(low, high, a, b, c, n);
    long cnta = res % a;
    long cntb = res % b;
    long cntc = res % c;
    res -= Math.min(cnta, Math.min(cntb, cntc));

    return (int) res;
}


public static long binarySearch(long low , long high, int a, int b, int c, long n){
    if (low >= high) return low;

    long mid = (low + high) >> 1;

    long MCM_a_b = MCM(a, b);
    long MCM_a_c = MCM(a, c);
    long MCM_b_c = MCM(b, c);

    long MCM_a_b_c = MCM(MCM_a_b, c);

    long count = mid / a + mid / b + mid / c - mid / MCM_a_b - mid / MCM_a_c - mid / MCM_b_c + mid / MCM_a_b_c;

    if (count == n) return mid;

    if (count > n) return binarySearch(low, mid - 1, a, b, c, n);
    return binarySearch(mid + 1, high, a, b, c, n);
}

// 求最小公倍数 : 两数相乘 除以 最小公约数
public static long MCM(long m, long n){

    long Multi = m * n;
    while (n > 0){
        long tmp = m % n;
        m = n;
        n = tmp;
    }
    return Multi / m;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int nthSuperUglyNumber(int n, int[] primes) {
        if (n <= 1) return 1;

        // 存放 primes 对应位置的数字 指针指向的位置
        int[] pointers = new int[primes.length];

        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int next = Integer.MAX_VALUE;
            for (int j = 0; j < primes.length; j++) {
                next = Math.min(next, primes[j] * dp[pointers[j]]);
            }

            dp[i] = next;

            for (int j = 0; j < pointers.length; j++) {
                if (next == primes[j] * dp[pointers[j]]) pointers[j]++;
            }

        }
        return dp[n - 1];
    }