Topic

• Math
• Dynamic Programming
• Heap

Description

https://leetcode.com/problems/ugly-number-ii/

Analysis

方法一：遍歷自然數(shù)，逐個判斷是否是丑數(shù)。這方法很低效。

方法二：動態(tài)數(shù)組。

We have an array k of first n ugly number. We only know, at the beginning, the first one, which is 1. Then

k[1] = min( k[0]x2, k[0]x3, k[0]x5). The answer is k[0]x2. So we move 2’s pointer to 1. Then we test:

k[2] = min( k[1]x2, k[0]x3, k[0]x5). And so on. Be careful about the cases such as 6, in which we need to forward both pointers of 2 and 3.

x here is multiplication.

方法三：用使用堆。

方法四：使用紅黑樹。

Submission

import java.util.PriorityQueue; import java.util.TreeSet;public class UglyNumberII {public int nthUglyNumber1(int n) {if (n < 1 || n > 1690)throw new IllegalArgumentException();int index = 0, result = 1;while (true) {if (isUgly(result))index++;if (index < n) {result++;} elsebreak;}return result;}private boolean isUgly(int num) {for (int i = 2; i < 6 && num > 0; i++)while (num % i == 0)num /= i;return num == 1;}public int nthUglyNumber2(int n) {if (n < 1 || n > 1690)throw new IllegalArgumentException();int[] uglyNumbers = new int[n];uglyNumbers[0] = 1;int index2 = 0, index3 = 0, index5 = 0, uglyNumbersIndex = 1;while (uglyNumbersIndex < n) {int maybeNextUglyNumber2 = uglyNumbers[index2] * 2, //maybeNextUglyNumber3 = uglyNumbers[index3] * 3, //maybeNextUglyNumber5 = uglyNumbers[index5] * 5;int min = min(maybeNextUglyNumber2, maybeNextUglyNumber3, maybeNextUglyNumber5);uglyNumbers[uglyNumbersIndex++] = min;if (maybeNextUglyNumber2 == min)index2++;if (maybeNextUglyNumber3 == min)index3++;if (maybeNextUglyNumber5 == min)index5++;}return uglyNumbers[n - 1];}private int min(int a, int b, int c) {return Math.min(Math.min(a, b), c);}public int nthUglyNumber3(int n) {if (n == 1)return 1;PriorityQueue<Long> q = new PriorityQueue<>();q.add(1l);for (long i = 1; i < n; i++) {long tmp = q.poll();while (!q.isEmpty() && q.peek() == tmp)// 去重tmp = q.poll();q.add(tmp * 2);q.add(tmp * 3);q.add(tmp * 5);}return q.poll().intValue();}public int nthUglyNumber4(int n) {TreeSet<Long> ans = new TreeSet<>();ans.add(1L);for (int i = 0; i < n - 1; ++i) {long first = ans.pollFirst();ans.add(first * 2);ans.add(first * 3);ans.add(first * 5);}return ans.first().intValue();}}

Test

import static org.junit.Assert.*; import org.junit.Test;public class UglyNumberIITest {@Testpublic void test() {UglyNumberII obj = new UglyNumberII();assertEquals(12, obj.nthUglyNumber1(10));assertEquals(12, obj.nthUglyNumber2(10));assertEquals(12, obj.nthUglyNumber3(10));assertEquals(12, obj.nthUglyNumber4(10));} } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的LeetCode - Medium - 264. Ugly Number II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。