LeetCode 264. Ugly Number II（丑数II）

题目：

思路1（超时）：
这是最初的思路，因为丑数可以被2和3还有5整除直到为1，所以可以从1开始逐个去找并累加，分别用判断能否被2整除，如果可以就除2，再次重复这样的步骤，直到不能被2整除，再分别拿3和5做同样的事情。最终剩下的是1就说明这是一个丑数，用这样的方式去找第n个就可以了。这种方式很好理解，但是容易超时。因为它做了一些重复的事情，比如每个数都要追溯到不能被2和3还有5整除。
思路2（最优）：
看到了超时，就要想办法优化，优化的思路就是去掉思路1中重复的部分，比如如何利用那些已经获得了的丑数，后面的丑数其实都是建立在前面的某个数的基础上乘2或者3或者5。于是这里维护三个下标，x2下标专门找可以通过乘2得到的下一个丑数，x3下标找可以通过乘3得到的下一个丑数，x5下标找…
思路1的代码，逐个判断获得：

class Solution {
    public int nthUglyNumber(int n) {
    	if(n<0){
    		return 0;
    	}
    	int count=1;
    	int result=1;
    	int i=2;
        while(count<n){
        	int num=i;
        	while(num%2==0){
        		num=num/2;
        	}
        	while(num%3==0){
        		num=num/3;
        	}
        	while(num%5==0){
        		num=num/5;
        	}
        	if(num==1){
        		count++;
        		if(count==n)
        		result=i;
        	}
        	i++;
        }
        return result;
    }
}

思路2的代码，三下标推导新值：

public class Solution2 {	
	public int nthUglyNumber(int n) {
		int x2=0;
		int x3=0;
		int x5=0;
		ArrayList<Integer> arrayList=new ArrayList<>();
		arrayList.add(1);
		int count=1;
		while(count<n){			
			int min=findMin(arrayList.get(x2)*2,arrayList.get(x3)*3,arrayList.get(x5)*5);			
			if(min==arrayList.get(x2)*2){
				x2++;
			}
			if(min==arrayList.get(x3)*3){
				x3++;
			}
			if(min==arrayList.get(x5)*5){
				x5++;
			}			
			arrayList.add(min);
			count++;
		}
		return arrayList.get(arrayList.size()-1);
	}	
	public int findMin(int a,int b,int c){
		if(a<=b&&a<=c){
			return a;
		}else if(b<=a&&b<=c){
			return b;
		}else{
			return c;
		}
	}			
}

小结：
最优的代码往往不是大量地去做重复的事情，而是可以充分利用已有的资源来实现达到新的目标。