丑數(shù)
編寫一個(gè)程序判斷給定的數(shù)是否為丑數(shù)。
丑數(shù)就是只包含質(zhì)因數(shù) 2, 3, 5 的正整數(shù)。
示例 1:
輸入: 6
輸出: true
解釋: 6 = 2 × 3
示例 2:
輸入: 8
輸出: true
解釋: 8 = 2 × 2 × 2
示例 3:
輸入: 14
輸出: false
解釋:14不是丑數(shù)户辱，因?yàn)樗肆硗庖粋€(gè)質(zhì)因數(shù)7
說明：
-
1是丑數(shù)糙臼。 - 輸入不會(huì)超過 32 位有符號整數(shù)的范圍: [?231, 231 ? 1]
任何一個(gè)丑數(shù)都可以表示為2i3j5k
迭代
public boolean isUgly(int num) {
while (true) {
int pre = num;
if (num % 2 == 0) {
num /= 2;
}
if (num % 3 == 0) {
num /= 3;
}
if (num % 5 == 0) {
num /= 5;
}
if (num == 1) {
return true;
}
if (pre == num) {
return false;
}
}
}
遞歸
public boolean isUgly(int num) {
if (num == 1) {
return true;
}
if (num == 0) {
return false;
}
if (num % 2 == 0) {
return isUgly(num / 2);
}
if (num % 3 == 0) {
return isUgly(num / 3);
}
if (num % 5 == 0) {
return isUgly(num / 5);
}
return false;
}
新代碼：
public boolean isUgly(int n) {
if (n <= 0) {
return false;
}
int[] factors = {2, 3, 5};
for (int factor : factors) {
while (n % factor == 0) {
n /= factor;
}
}
return n == 1;
}
丑數(shù) II
編寫一個(gè)程序弓摘，找出第 n 個(gè)丑數(shù)。
丑數(shù)就是質(zhì)因數(shù)只包含 2, 3, 5 的正整數(shù)韧献。
示例:
輸入: n = 10
輸出: 12
解釋:1, 2, 3, 4, 5, 6, 8, 9, 10, 12是前 10 個(gè)丑數(shù)
說明:
-
1是丑數(shù)。 -
n不超過1690璧针。
方法一：暴力(超時(shí)）
public int nthUglyNumber(int n) {
int i=0;
int count=0;
while (count<n){
i++;
if(isUgly(i)){
count++;
}
}
return i;
}
public boolean isUgly(int num) {
while (true) {
int pre = num;
if (num % 2 == 0) {
num /= 2;
}
if (num % 3 == 0) {
num /= 3;
}
if (num % 5 == 0) {
num /= 5;
}
if (num == 1) {
return true;
}
if (pre == num) {
return false;
}
}
}
方法二：堆
預(yù)先計(jì)算 1690 個(gè)丑數(shù)
堆中包含一個(gè)數(shù)字開始：1渊啰，去計(jì)算下一個(gè)丑數(shù)
將 1 從堆中彈出然后將三個(gè)數(shù)字添加到堆中：1×2, 1 1×3申屹，1×5
現(xiàn)在堆中最小的數(shù)字是 2哗讥，為了計(jì)算下一個(gè)丑數(shù)胞枕，要將 2 從堆中彈出然后添加三個(gè)數(shù)字：2×2, 2×3，2×5
重復(fù)該步驟計(jì)算所有丑數(shù)腐泻。在每個(gè)步驟中，彈出堆中最小的丑數(shù) k构诚，并在堆中添加三個(gè)丑數(shù)：k×2, k×3铆惑，k×5
int[] nums = new int[1690];
Solution() {
PriorityQueue<Long> queue = new PriorityQueue<>();//要用long范嘱，因?yàn)殛?duì)列中的元素比數(shù)組中要多员魏，*2、*3可能會(huì)越界
queue.offer(1L);
Set<Long> set = new HashSet<>();//用于去重 如6可能由彈出的2*3組成逆趋，也可能由彈出的3*2組成
set.add(1L);
int[] primes = {2, 3, 5};
int i = 0;
while (i < 1690) {
long num = queue.poll();
for (int prime : primes) {
if (!set.contains(num * prime)) {
queue.offer(num * prime);
set.add(num * prime);
}
}
nums[i++] = (int) num;
}
}
public int nthUglyNumber(int n) {
return nums[n - 1];
}
方法三：動(dòng)態(tài)規(guī)劃
從數(shù)組中只包含一個(gè)丑數(shù)數(shù)字 1 開始闻书，使用三個(gè)指針p2,p3,p5，標(biāo)記所指向丑數(shù)要乘以的因子
在2×nums[p2]魄眉，3×nums[p3]坑律，5×nums[p5]中選取最小的添加到數(shù)組中，并移動(dòng)相應(yīng)位置的指針
重復(fù)該步驟直到計(jì)算完 1690 個(gè)丑數(shù)
int[] nums = new int[1690];
Solution() {
int p2 = 0, p3 = 0, p5 = 0;
nums[0] = 1;
int i = 1;
while (i < 1690) {
int num = Math.min(2 * nums[p2], Math.min(3 * nums[p3], 5 * nums[p5]));
nums[i++] = num;
if (num == nums[p2] * 2) {
p2++;
}
if (num == nums[p3] * 3) {
p3++;
}
if (num == nums[p5] * 5) {
p5++;
}
}
}
public int nthUglyNumber(int n) {
return nums[n - 1];
}
不用預(yù)先計(jì)算
public int nthUglyNumber(int n) {
int[] dp = new int[n];//表示第i+1個(gè)丑數(shù)
int p2 = 0, p3 = 0, p5 = 0;
dp[0] = 1;
for (int i=1;i <n;i++) {
int num = Math.min(2 * dp[p2], Math.min(3 * dp[p3], 5 * dp[p5]));
dp[i] = num;
if (num == dp[p2] * 2) {
p2++;
}
if (num == dp[p3] * 3) {
p3++;
}
if (num == dp[p5] * 5) {
p5++;
}
}
return dp[n - 1];
}
丑數(shù) III
請你幫忙設(shè)計(jì)一個(gè)程序冀值，用來找出第 n 個(gè)丑數(shù)宫屠。
丑數(shù)是可以被 a 或 b 或 c 整除的 正整數(shù)。
示例 1：
輸入：n = 3, a = 2, b = 3, c = 5
輸出：4
解釋：丑數(shù)序列為 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 個(gè)是 4
示例 2：
輸入：n = 4, a = 2, b = 3, c = 4
輸出：6
解釋：丑數(shù)序列為 2, 3, 4, 6, 8, 9, 12... 其中第 4 個(gè)是 6
輸入：n = 5, a = 2, b = 11, c = 13
輸出：10
解釋：丑數(shù)序列為 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 個(gè)是 10
示例 4：
輸入：n = 1000000000, a = 2, b = 217983653, c = 336916467
輸出：1999999984
提示：
1 <= n, a, b, c <= 10^91 <= a * b * c <= 10^18- 本題結(jié)果在
[1, 2 * 10^9]的范圍內(nèi)
思考：對于一個(gè)丑數(shù)x抵栈，如何確定它是第幾個(gè)丑數(shù)——只需要計(jì)算X中包含了多少個(gè)丑數(shù)因子
即只需要知道在[0,X]范圍內(nèi),還有多少個(gè)丑數(shù)古劲，而這些丑數(shù)，無非就是一些能被a或者b或者c所整除的數(shù)
那么用X/a产艾、X/b、X/c就能計(jì)算出[0,X]范圍內(nèi)有多少數(shù)能被a或者b或者c整除，然后把它們加起來就是答案
但是可能存在重復(fù)計(jì)算：如果一個(gè)數(shù)既能被a整除蹬挤，又能被b整除焰扳，那么實(shí)際上該數(shù)在先前的計(jì)算中就被重復(fù)計(jì)算了一次(分別是在計(jì)算X/a和X/b時(shí))。
分析情況：
- 該數(shù)只能被a整除 (該數(shù)一定是a 的整數(shù)倍)
- 該數(shù)只能被b整除 (該數(shù)一定是b 的整數(shù)倍)
- 該數(shù)只能被c整除 (該數(shù)一定是c 的整數(shù)倍)
- 該數(shù)只能被a和b同時(shí)整除 (該數(shù)一定是a吨悍、b最小公倍數(shù)的整數(shù)倍)
- 該數(shù)只能被a和c同時(shí)整除 (該數(shù)一定是a育瓜、c最小公倍數(shù)的整數(shù)倍)
- 該數(shù)只能被b和c同時(shí)整除 (該數(shù)一定是b、c最小公倍數(shù)的整數(shù)倍)
- 該數(shù)只能被a和b和c同時(shí)整除（該數(shù)一定是a躏仇、b、c的最小公倍數(shù)的整數(shù)倍）
所以糟描，我們只需要分別計(jì)算以上七項(xiàng)就能得到結(jié)果了书妻！讓我們分別來看（用MCM+下標(biāo)表示最小公倍數(shù)）：
情況1 = X/a - 情況4 - 情況5 - 情況7
情況2 = X/b - 情況4 - 情況6 - 情況7
情況3 = X/c - 情況5 - 情況6 - 情況7
情況4 = X/MCM_a_b - 情況7
情況5 = X/MCM_a_c - 情況7
情況6 = X/MCM_b_c - 情況7
情況7 = X/MCM_a_b_c
讓我們整理上述方程后也就得到：
sum(情況) =X/a + X/b + X/c - X/MCM_a_b - X/MCM_a_c - X/MCM_b_c + X/MCM_a_b_c
最小公倍數(shù) = a*b/(a和b的最大公約數(shù))，最大公約數(shù)可以通過輾轉(zhuǎn)相除法得到
二分搜索
在得到了計(jì)算任意數(shù)中包含了多少個(gè)丑數(shù)因子的方法后见间，我們實(shí)際上只需要通過二分法工猜，不斷縮小邊界范圍，直到某個(gè)位置所對應(yīng)的數(shù)恰好包含了n個(gè)丑數(shù)因子為止荒辕。
- 先找到a,b,c里最小的那個(gè)數(shù)，比如是a弛针，那么第n個(gè)丑數(shù)肯定是<= n * a
- 然后就開始二分法的做法了李皇，將n*a置為上限high，a置為下限low
- 求解mid = (low+high)/2這個(gè)數(shù)里包含了多少丑數(shù)(并且mid也為丑數(shù))：
- 如果上一步的數(shù)字等于n,那最好啦掉房，判斷當(dāng)前的mid是否是丑數(shù)，如果是瘾杭，直接返回mid哪亿，如果不是，將high=mid - 1
- 如果上一步的數(shù)字大于n,將high=mid - 1
- 如果上一步的數(shù)字小于n,將low=mid + 1
public int nthUglyNumber(int n, int a, int b, int c) {
long low = Math.min(a, Math.min(b, c));//用long防止乘法 low+high溢出
long high = n * low;
return binarySearch(low, high, n, a, b, c);
}
public int binarySearch(long low, long high, long n, int a, int b, int c) {
while (low < high) {
long mid = (low + high) / 2;
int num = (int) (mid / a + mid / b + mid / c - mid / mcm(a, b) - mid / mcm(a, c) - mid / mcm(b, c) + mid / mcm(a, mcm(b, c)));
if (num == n && (mid % a == 0 || mid % b == 0 || mid % c == 0)) {
return (int) mid;
} else if (num < n) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return (int) low;
}
public long mcm(long a, long b) {
long s = a * b;
while (b > 0) {
long tmp = a % b;
a = b;
b = tmp;
}
return s / a;
}
