263. Ugly Number
class Solution {
public boolean isUgly(int num) {
if(num==1) return true;
if(num==0) return false;
while(num%2==0) num=num>>1;
while(num%3==0) num=num/3;
while(num%5==0) num=num/5;
return num==1;
}
}
264. Ugly Number II
分析：這道題最直觀地想法是暴力查找帘睦，但不用想也知道會(huì)超時(shí)，于是我想能不能找到規(guī)律坦康，就是從每個(gè)生成數(shù)的系數(shù)竣付。但是很遺憾。
于是想到后面的每個(gè)ugly數(shù)都是由前面的ugly數(shù)所產(chǎn)生的滞欠。那這樣的話就構(gòu)成了一個(gè)生成鏈古胆。但是這里有個(gè)重要的問(wèn)題就是，生成鏈必須是有序的仑撞。最開(kāi)始想法是每添加一個(gè)元素就排序赤兴，但是也會(huì)TLE，后來(lái)發(fā)現(xiàn)隧哮，當(dāng)我們生成x時(shí)桶良，我們下個(gè)希望生成的數(shù)肯定是大于x的，那么就可以從前向后查找list沮翔，看當(dāng)2陨帆，3，*5后生成的大于x的數(shù)中采蚀，找到最小值疲牵，然后將其添加到list中，然后更新cur榆鼠。
這里還有個(gè)trick纲爸，就是如果每次都從最開(kāi)始搜索，其實(shí)是沒(méi)有必要的妆够，直接從上次結(jié)束的位置搜索即可识啦，因?yàn)槟莻€(gè)位置以前都肯定小于cur.
class Solution {
public int nthUglyNumber(int n) {
List<Integer> list = new ArrayList<>();
list.add(1);
int cur = 2;
int i1= 0,i2 = 0,i3 = 0;
int min1,min2,min3;
while (list.size()<n){
while(list.get(i1)*2<cur) i1++;
min1 = list.get(i1)*2;
while(list.get(i2)*3<cur) i2++;
min2 = list.get(i2)*3;
while(list.get(i3)*5<cur) i3++;
min3 = list.get(i3)*5;
int next = min1<min2?min1:min2;
next = next<min3?next:min3;
cur = next+1;
list.add(next);
}
return list.get(n-1);
}
}
268. Missing Number
class Solution {
public int missingNumber(int[] nums) {
int sumRes = nums.length * (nums.length + 1) / 2;
for(int num:nums)
sumRes -= num;
return sumRes;
}
}
