Lintcode记录

Lintcode记录

Scroll Down

Lintcode
我的Lintcode

39-恢复旋转排序数组

public static void recoverRotatedSortedArray(List nums) {
		if(nums!=null&&nums.size()>1){
			//长度2直接调换
			if(nums.size()==2){
				if(nums.get(0)>nums.get(1)){
					nums.add(0,nums.get(0)+nums.get(1));
					nums.add(1,nums.get(0)-nums.get(1));
					nums.add(0,nums.get(0)-nums.get(1));
				}
				return;
			}
			int f=nums.get(0);
			int l=nums.get(nums.size()-1);
			int m=nums.get(nums.size()/2);
			int min=nums.get(0);
			int index=0;
			int size=nums.size();
			//判断循环起点
			if(f>l){
				if(f		}else {
			if(l<m){
				for (int i=nums.size()/2;i<nums.size();i++){
					if(nums.get(i)<min){
						min=nums.get(i);
						index=i;
					}
				}
			}else {
				for (int i=nums.size()-1;i>=0;i--){
					if(nums.get(i)<min){
						min=nums.get(i);
						index=i;
					}
				}
			}
		}
		//从最小位置开始
		List temp=new ArrayList<Integer>();
		for (int i=index;i<size;i++){
			temp.add(nums.get(i));
		}
		for (int i=0;i<index;i++){
			temp.add(nums.get(i));
		}
		nums.clear();
		nums.addAll(temp);
	}
}

2-尾部的零

//这题我原来是算出递归,却发现在遇到非常大的数时通过不了,后来看了解答,才知道可以通过分解因子来实现
//可以将每个数拆分成其素因子的乘积,可以发现,0是由2*5产生的,而5的数量一定小于2的数量,因此5的个数决定了结尾0的个数。
//只要计算n的阶乘中,5这个素因子出现多少次即可。
public static long trailingZeros(long n) {
        long sum = 0;
        while (n != 0) {
            sum += n / 5;
            n /= 5;
        }
        return sum;
    }