Android中关于递归和二分法的算法实例代码
//1.实现一个函数,在一个有序整型数组中二分查找出指定的值,找到则返回该值的位置,找不到返回-1。
packagedemo; publicclassMytest{ publicstaticvoidmain(String[]args){ int[]arr={1,2,5,9,11,45}; intindex=findIndext(arr,0,arr.length-1,12); System.out.println("index="+index); } //1.实现一个函数,在一个有序整型数组中二分查找出指定的值,找到则返回该值的位置,找不到返回-1。 publicstaticintfindIndext(int[]arr,intleft,intright,intabc){ if(arr==null||arr.length==0){ return-1; } if(left==right){ if(arr[left]!=abc){ return-1; } } intmid=left+(right-left)/2;//3//4 if(arr[mid]>abc){// right=mid-1; returnfindIndext(arr,left,right,abc); }elseif(arr[mid]<abc){//5<45//9<45/11<45 left=mid+1; returnfindIndext(arr,left,right,abc);//2,5//3,5//4.5 }else{ returnmid; } } } /1.实现一个函数,在一个有序整型数组中二分查找出指定的值,找到则返回该值的位置,找不到返回-1。 //array升虚数组 publicintfind(int[]array,intn){ if(array==null){ return-1; } intlen=array.length; if(n<array[0]||n>array[len-1]){ return-1; } intleft=0; intright=len-1; while(left<right){ intmid=left+(right-left)/2; if(array[mid]==n){ returnmid; }elseif(array[mid]<n){ left=mid+1; }else{ right=mid-1; } } if(array[left]==n){ returnleft; }else{ returnright; } } //2.写一个函数将一个数组转化为一个链表。 //要求:不要使用库函数,(如List等) publicstaticclassNode{ Nodenext; intdata; } //返回链表头 publicNodeconvert(int[]array){ if(array==null||array.length==0){ returnnull; } Nodehead=newNode(); head.data=array[0]; intlen=array.length; Nodeend=head; for(inti=1;i<len;i++){ end=addNode(end,array[i]); } returnhead; } //给链表尾部添加一个节点 publicNodeaddNode(Nodeend,intdata){ Nodenode=newNode(); node.data=data; end.next=node; returnnode; } //3.有两个数组,[1,3,4,5,7,9]和[2,3,4,5,6,8],用上面的函数生成两个链表linkA和 //linkB,再将这两个链表合并成一个链表,结果为[1,2,3,4,5,6,7,8,9]. //要求:不要生成第三个链表,不要生成新的节点。 //3.1使用递归方式实现 // publicNodecomb(int[]arrayA,int[]arrayB){ NodelinkA=convert(arrayA); NodelinkB=convert(arrayB); Nodehead; if(linkA.data==linkB.data){ head=linkA; linkA=linkA.next; linkB=linkB.next; head.next=null; }elseif(linkA.data<linkB.data){ head=linkA; linkA=linkA.next; head.next=null; }else{ head=linkB; linkB=linkB.next; head.next=null; } Nodeend=head; comb(end,headA,headB); returnhead; } //实现递归 publicvoidcomb(Nodeend,NodeheadA,NodeheadB){ if(headA==null&&headB==null){ return; }elseif(headA==null){ end.next=headB; return; }elseif(headB==null){ end.next=headA; return; } if(headA.data<headB.data){ end.next=headA; headA=headA.next; end=end.next; end.next=null; comb(end,headA,headB); }elseif(headA.data==headB.data){ end.next=headA; headA=headA.next; headB=headB.next; end=end.next; end.next=null; comb(end,headA,headB); }else{ end.next=headB; headB=headB.next; end=end.next; end.next=null; comb(end,headA,headB); } } //3.2使用循环方式实现 //循环实现 publicNodecomb(int[]arrayA,int[]arrayB){ //转换链表 NodelinkA=convert(arrayA); NodelinkB=convert(arrayB); //获取头节点 Nodehead; if(linkA.data==linkB.data){ head=linkA; linkA=linkA.next; linkB=linkB.next; head.next=null; }elseif(linkA.data<linkB.data){ head=linkA; linkA=linkA.next; head.next=null; }else{ head=linkB; linkB=linkB.next; head.next=null; } Nodeend=head; //依次将较小的节点加到链表尾部 while(headA!=null&&headB!=null){ if(headA.data<headB.data){ end.next=headA; headA=headA.next; end=end.next; end.next=null; }elseif(headA.data==headB.data){ end.next=headA; headA=headA.next; headB=headB.next; end=end.next; end.next=null; }else{ end.next=headB; headB=headB.next; end=end.next; end.next=null; } } //如果其中一个链表为空,将另外一个链表直接添加到合成链表尾部 if(headA==null){ end.next=headB; }elseif(headB==null){ end.next=headA; } returnhead; }
以上所述是小编给大家介绍的Android中关于递归和二分法的算法实例代码,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的,在此也非常感谢大家对毛票票网站的支持!