蓝桥 第二周 递归

递归

        找重复->找重复中的变化量->参数变化趋势

数组求和

public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        int n = arr.length;
        System.out.println(sum(arr,0,n));
    }
    public static int sum(int arr[],int start,int end){
        if(start == end-1)return arr[start];
        else return arr[start] + sum(arr,start+1, end);
    }

翻转字符串

public static void main(String[] args) {
        StringBuffer s = new StringBuffer("abcdef");
        System.out.println(reversestr(s,0,s.length()));
    }
    public static StringBuffer reversestr(StringBuffer str,int start,int end){
        if(start==end-1){
            StringBuffer res = new StringBuffer(String.valueOf(str.charAt(start)));
            return res;
        }else{
            return reversestr(str,start+1,end).append(str.charAt(start));
        }
    }

斐波那契数列

public static void main(String[] args) {
        for(int i=1;i<10;i++) System.out.println(fib(i));
    }
public static int fib(int n){
    if(n==1)return 1;
    else if(n==2)return 1;
    else return fib(n-1)+fib(n-2);
}

最大公约数

    public static void main(String[] args) {
        System.out.println(gcd(10,20));
    }
    public static int gcd(int m,int n){
        if(n==0)return m;
        else return gcd(n,m%n);
    }

递归形式进行插入排序

    public static void main(String[] args) {
        int[] arr = {1,5,2,6,3,9,11};
        sort1(arr,arr.length-1);
        for(int i=0;i<arr.length;i++)         System.out.println(arr[i]);
    }
    public static void sort1(int arr[],int idx){
        if(idx==0) return;
        else{
            sort1(arr,idx-1);
            int temp = arr[idx];
            int i=idx-1;
            while(arr[i]>arr[idx]){
                arr[i+1]=arr[i];
                i--;
            }
            arr[i+1]=temp;
        }
    }

汉诺塔

    public static void main(String[] args) {
        hanoi(3,'a','b','c');
    }
    public static void hanoi(int n,char c1, char c2, char c3){
        if(n==1)System.out.println(""+c1+"->"+c3);
        else{
            hanoi(n-1,c1,c3,c2);
            System.out.println(""+c1+"->"+c3);
            hanoi(n-1,c2,c1,c3);
        }
    }

递归二分查找

	public static int binarySearch(int[] arr,int target, int low,int high) {
		if(low>high)return -1;
		int mid = low + (high - low)/2;
		if(arr[mid]==target) return mid;
		else if(arr[mid]>target)return binarySearch(arr,target,low,mid-1);
		else return binarySearch(arr,target,mid+1,high);
	}

希尔排序

	public static void shellSort(int[] arr) {
		int n = arr.length;		
		for(int interval = arr.length/2;interval>0;interval/=2) {
			for(int i=interval;i<n;i++) {
				int j=i-interval;
				int target = arr[i];
				while(j>=0&&arr[j]>target) {
					arr[j+interval] = arr[j];
					j-=interval;
				}
				arr[j+interval] = target;
			}
		}		
	}

算法复杂度

        线性、平方、对数

题1：小白上楼梯

	public static int f(int n) {
		if(n==0)return 1;
		else if(n==1)return 1;
		else if(n==2) return 2;
		else return f(n-1)+f(n-2)+f(n-3);
	}

题2：旋转数组的最小数字

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {4,5,6,7,8,9,10,11,12,1,2,3};
		System.out.println(getMin(arr,0,arr.length-1));
//		int low = 0,high = arr.length-1;
//		while(low+1<high) {
//			int mid = low + (high - low+1)/2;
//			if(arr[mid]>arr[high]) {
//				low = mid+1;
//			}else if(arr[low]>arr[mid]){
//				high = mid;
//			}
//		}
//		System.out.println(arr[high]);
	}
	public static int getMin(int[] arr,int low,int high) {
		int mid = low + (high - low + 1)/2;
		if(low+1>=high)return arr[high];
		if(arr[mid]>arr[high]) {
			return getMin(arr,mid+1,high);
		}else {
			return getMin(arr,low,mid);
		}
	}

题3：在有空字符串中的有序数组中查找

题4：最长连续递增子序列

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = {1,9,2,5,7,3,4,6,8,9,10};
		int n = arr.length;
		int maxLen = 1;
		int l=0,r=l+1;
		while(r<n) {
			while(r<n&&arr[r]>arr[r-1]) {
				r++;
				if(r==n) {
					maxLen = Math.max(maxLen, r-l-1);
					break;
				}
			}
			maxLen = Math.max(maxLen, r-l);
			l = r;
			r = l+1;

		}
		System.out.println(maxLen);
	}

题5：高效a的n次幂（快速幂）

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(quickPow(2,10));
		

	}
	public static long quickPow(long x,int n) {
		if(n==1)return x;
		else {
			long res = quickPow(x,n/2);
			if(n%2==1)return res*res*x;
			else return res*res;
		}
	}