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

分析：這道題最直觀地想法是暴力查找，但不用想也知道會超時，于是我想能不能找到規(guī)律，就是從每個生成數(shù)的系數(shù)。但是很遺憾。
于是想到后面的每個ugly數(shù)都是由前面的ugly數(shù)所產(chǎn)生的。那這樣的話就構(gòu)成了一個生成鏈。但是這里有個重要的問題就是，生成鏈必須是有序的。最開始想法是每添加一個元素就排序，但是也會TLE，后來發(fā)現(xiàn)，當我們生成x時，我們下個希望生成的數(shù)肯定是大于x的，那么就可以從前向后查找list，看當2，3，*5后生成的大于x的數(shù)中，找到最小值，然后將其添加到list中，然后更新cur。
這里還有個trick，就是如果每次都從最開始搜索，其實是沒有必要的，直接從上次結(jié)束的位置搜索即可，因為那個位置以前都肯定小于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;
    }
}