compareTo()方法：
1.还原单字符asc码的差值，相等返回0，小于大于分别返回差值
2.比较两个字符串，如果两个字符串首字母相同则进行比较下一个
注：int类型不能直接使用，得转换成String类型
1.递归-汉诺塔
在经典汉诺塔问题中，有 3 根柱子下x,y,z及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子x上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
第一步将x柱子上的圆盘分成第N个和其余N-1个，将y柱子为辅助柱，z柱子为目标柱，借助辅助柱z，将N-1个盘子移动到y上，第二步移动第N个盘子，将其移动到z柱子上，第三步将z柱子作为辅助柱子，将y中的N-1个盘子移动到z上，x柱子作为辅助柱。
这里用到分治思想，将相同问题统一化。2
package exercise; class two_searc { //将x作为源柱子，y作为辅助柱子，z作为目标柱子 public static int count =0; public static void move(char x,int n, char z) { System.out.println("Move "+n+"from"+x+"to "+z); } public static void hanio(int n,char x,char y,char z) { count++; if(n==1) { move(x, n, z); }else { hanio(n-1,x,y,z); move(x, n, z); hanio(n-1,y,z,x); } } }
1.2递归-二分查找
将while循环条件转换成了递归
package exercise; class two_search { static int binarySearch(int [] arr,int low ,int high,int key) { if(low>high) return -1; int mid = low+((high-low)>>1); int midVal = arr[mid]; if(midVal<key) { return binarySearch(arr, mid+1, high, key); }else if(midVal>key) { return binarySearch(arr, low, mid-1, key); }else { return mid; } } }
递归练习题： 小白上楼梯
//根据题中所给的前三步，可以将n>3之后的问题转化为与之相关的 package exercise; import java.util.Scanner; class two_search { public static void main(String[]args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); } static int num(int n) { if(n==1) return 1; if(n==2) return 2; if(n==3) return 4; return num(n-1)+num(n-2)+num(n-3); } }
package exercise; import java.util.Scanner; class two_search { static int num(int [] a) { int begin =0,end = a.length; if(a[begin]<a[end]) return a[begin]; while(begin<end-1) { int mid = begin+(end-begin)>>1; if(a[begin] < a[mid]) { begin = mid+1; }else{ end = mid; } } return a[begin]; } }
static int indexof(String s [],String target) { int begin = 0,end = s.length; while(begin<end) { int mid = begin+((end-begin)>>1); while(s[mid].equals("")){ mid++; } if(s[mid].campareTo(target)>0) { end = mid-1; }else if(s[mid].campareTo(target)<0){ { begin = mid+1; }else{ return mid; } } return -1; }
public static int num(int a []) { if(a.length == 0) return 0; int count = 1,max = 0; for(int i = 0;i<a.length-1;i++) { if(a[i]<a[i+1]) { count++; }e;se{ max = Math.max(count,max); count = 1; } } max = Math.max(count,max); return max; }
//常规递归： public static int num(int a,int n) { if(n==0) return 1; return a*num(a,n-1); } //位运算做法 static int pow(int a,int n) { if(n==0) return 1; int chu = a; int num = 1; while((num<<1)<=n) { chu = chu*chu; num <<=1; } return chu*pow(a, n-num); }
