一，分治策略与递归
分治策略：是将规模比较大的问题分割成规模较小的相同问题，问题不变，规模变小。
递归：若一个函数直接的或间接的调用自己，则称则个函数是递归函数。
接下来比较下解决相同的问题，使用递归和分治算法各需要的时间复杂度和空间复杂度。
public static int digiu(int n){//递归运算 if (n<=1){ return 1; }else { return digiu(n-1)*n; } }
时间复杂度：O(n) 空间复杂度：S(n)
通过观察上述代码可知，随着变量n的值不断的变大，所需要递归调用的次数就越多，因此需要开辟的栈帧就越多，所以空间复杂度位S(n)。
递归调用与普通的函数调用一样，每当调用发生时，就要分配新的栈帧，而与普通的函数调用不同的是，由于递推的过程是一个逐层调用的过程，因此存在一个逐层连续的分配栈帧过程，直到遇到递归终止条件时，才开始回归，这时才逐层释放栈帧空间，返回到上一层，直到最后返回到主调函数。
在递归调用时，如果没有终止条件，考虑下函数会不会一直递归下去？答案是不会，因为递归调用时，会不断的往栈中压入栈帧，而栈内存默认大小只有10MB，当递归调用的过程中，栈内存一旦满就会报栈溢出的异常，这时候递归也就会停止。
public static int fun(int n){//分治策略算法 int sum=0; for (int i = 0; i <n; i++) { sum=sum*i; } return sum; }
时间复杂度：O(n) 空间复杂度：S(1)
使用分治策略时，在代码执行的过程中始终只调用了一个方法，因此只开辟了一个栈帧，所以空间复杂度就为S(1)。
1.实例
1.有一个整形数组，数值无序，使用循环和递归完成查询。
public class digiu { public static int fun(int[] arr,int val){ int pos=-1; for (int i = 0; i <arr.length; i++) { if (val==arr[i]){ pos=i; } } return pos; } public static int digiu(int[] arr,int val,int num){ if(num>=0&&arr[num]==val){ return num; } return digiu(arr,val,num-1);//注意先递归在打印的区别 } public static void main(String[] args) { int[] arr={1,8,3,9,0}; System.out.println(fun(arr,1)); System.out.println(digiu(arr,0,arr.length-1)); } }
2.二分查找。
public class partFind { public static int whilefind(int[] arr,int val){//5 6 7 10 int right=0; int left=arr.length-1; while (right<=left){ int mid=(right+left)/2;//当范围数值过大可以采用：mid=left+(right-left)/2 0.618 if (val==arr[mid]){ while (mid>0&&arr[mid-1]==val) --mid;//如果数组中存在相同元素，且要求返回的是最右边值的下标 return mid; } if (val<arr[mid]){ left=mid-1; } if (val>arr[mid]){ right=mid+1; } } return -1; } public static void main(String[] args) { int[] arr={12,12,23,23,23,34,45,56}; System.out.println(whilefind(arr,12)); } }
3.给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将被按顺序插入的位置。
（反复计算可知，如果该数组中存在该数，一般在mid处就可返回，如果不存在，则可以用left的值作为可插入下标返回）
public class digiu1_3 {
//为了方便判断返回的下标是该数在数组中的位置，还是没有找到该数返回的应插入的下标。
//所以就使用IndexNode类型，当返回的值的flag为true，表明找到该值，当flag为false，表明没有找到该值，返回的只是应插入的位置 static class IndexNode{ int value; boolean flag; }
private static IndexNode FindValue(int[] arr,int value) { int left=0; int right=arr.length-1; IndexNode indexNode=new IndexNode(); while (left<=right){ int mid=(right-left)/2+left;//(right+left)/2 if(value==arr[mid]){ indexNode.flag=true; indexNode.value=mid; return indexNode; }else if (value<arr[mid]){ right=mid-1; }else if(value>arr[mid]){ left=mid+1; } } indexNode.flag=false; indexNode.value=left; return indexNode; } public static void main(String[] args) { int[] arr=new int[]{12,23,34,45,56,67,78,85,92,100}; IndexNode indexNode=FindValue(arr,10); System.out.println(indexNode.flag+" "+indexNode.value); } }
4.贪吃的小明
小明的父母要出差N天，走之前给小明留下了M块奶糖，小明决定每天吃的奶糖数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有奶糖吃，请问他第一天最多可以吃多少块？
思路：1.因为要保证第一天吃的最多，所以就要保证后面每天吃的刚好为前一天的一半，但也要注意不能吃一半！！
public class digui1_4 { private static int EatMax(int day, int number) { int day1=(number+2)/2; //第一天要吃的糖的量， //第一天为什么是从对半开始？？？ int sum=day1;//累计吃的糖数 int eatday=sum;//每天要吃的量 while (true){ for (int i = 1; i <day; i++) { sum=sum+((eatday+1)/2);//加一是为解决每天吃半块糖的情况 eatday=eatday/2;//每经过一天，吃的糖数量就会减半 } if(sum<=number){ break; } if(sum>number){//表示给第一天分的太多 day1=day1-1; } } return day1; } public static void main(String[] args) { int day=2; int num=15; int day1=EatMax(day,num); System.out.println("第一天最多吃："+day1); } }
5.旋转数组
寻找旋转数组排序中的最小值，然会返回它的下标，假如：数组{10，11，12，13，14，15，16，17}发生旋转变为{14，15，16，17，10，11，12，13}；可以看出10，11，12，13部分发生了旋转，且10为旋转中的最小值，假设数组中不存在重复元素。
public class digui1_5 { public static int findMin(int[] arr){ int left=0; int right=arr.length-1; while (left<right-1){//因为如果有旋转发生，那么一定为最后两个数中右边的那一个 int mid=(right-left)/2+left; if(arr[left]>arr[mid]){//最左边如果大于中间值，说明旋转的范围在前半部分 right=mid; }else if (arr[right]<arr[mid]){//如果最右边值小于中间值，说明旋转的部分在后半部分 left=mid; }else{//如果最左边不大于中间值，且最右遍不小于中间值，说明此序列中没有发生旋转
return -1; } } return right; } public static void main(String[] args) { int[] arr=new int[]{14,15,16,17,10,11,12,13}; // 0 1 2 3 4 5 6 7 System.out.println(findMin(arr)); } }
6.计算两个数的最大公约数（1，遍历法 2，辗转相除法 3，直接使用库中函数）
public class digui1_6 { public static void main(String[] args) { int value1=15; int value2=15; //1.遍历法 fun1(value1,value2); //2.辗转相除法 System.out.println(fun2(value1,value2)); //3.直接使用库中的函数 fun3(value1,value2); } private static void fun1(int value1, int value2) { int a=value1;//无需区分大小，因为在do中进行一次之后，a就始终为大值，b始终为小值 int b=value2; int r=-1; do{ r=a; a=b; b=r%b; }while (b!=0); System.out.println("最大公约数为："+a); } private static int fun2(int value1, int value2) { if(value1==value2){ return value1; } if (value1==0||value2==0){//当两个数中有一个数为0时，最大公约数为非0数 return value1==0?value2:value1; } int n=value1<value2?value1:value2;//找出较小的一个，使用穷举法 for (;n>0;--n) { if(value1%n==0&&value2%n==0){ break; } } return n; } private static void fun3(int value1, int value2) { BigInteger num1=new BigInteger(String.valueOf(value1)); BigInteger num2=new BigInteger(String.valueOf(value2)); BigInteger num3=num1.gcd(num2); System.out.println("最大公约数："+num3); } }
7.将一个整数反向输出。如：12345，输出之后为54321
public class digui1_7 { public static void main(String[] args) { int value=12345; fun(value); } private static void fun(int value) { while (value!=0){ int n=value%10; value=value/10; System.out.print(n); } } } /* *下面是递归形式 */ public class digui1_7 { public static void main(String[] args) { int value=12345; fun(value); } private static void fun(int value) { if(value==0){ return; } int n=value%10; System.out.print(n); fun(value/10); } }