欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

Android中关于递归和二分法的算法实例代码

程序员文章站 2024-03-31 17:58:10
// 1. 实现一个函数,在一个有序整型数组中二分查找出指定的值,找到则返回该值的位置,找不到返回 -1。 package demo; public cla...

// 1. 实现一个函数,在一个有序整型数组中二分查找出指定的值,找到则返回该值的位置,找不到返回 -1。

package demo;
public class mytest {
public static void main(string[] args) {
int[] arr={1,2,5,9,11,45};
int index=findindext(arr,0,arr.length-1,12);
system.out.println("index="+index);
}
// 1. 实现一个函数,在一个有序整型数组中二分查找出指定的值,找到则返回该值的位置,找不到返回 -1。
public static int findindext(int[] arr,int left,int right,int abc){
if(arr==null||arr.length==0){
return -1;
}
if(left==right){
if(arr[left]!=abc){
return -1;
}
}
int mid=left+(right-left)/2;//3//4
if(arr[mid]>abc){//
right=mid-1;
return findindext(arr,left,right,abc);
}else if(arr[mid]<abc){//5<45//9<45/11<45
left=mid+1;
return findindext(arr,left,right,abc);//2,5//3,5//4.5
}else{
return mid;
}
}
}
/ 1. 实现一个函数,在一个有序整型数组中二分查找出指定的值,找到则返回该值的位置,找不到返回 -1。
// array 升虚数组
public int find(int[] array, int n){
if(array == null){
return -1;
}
int len = array.length;
if(n < array[0] || n > array[len-1]){
return -1;
}
int left = 0;
int right = len -1;
while(left < right){
int mid = left + (right - left) / 2;
if(array[mid] == n){
return mid;
}else if(array[mid] < n){
left = mid + 1;
}else{
right = mid - 1;
}
}
if (array[left] == n){
return left;
} else {
return right;
}
}
// 2. 写一个函数将一个数组转化为一个链表。
// 要求:不要使用库函数,(如 list 等)
public static class node{
node next;
int data;
}
// 返回链表头
public node convert(int[] array){
if(array == null || array.length == 0){
return null;
}
node head = new node();
head.data = array[0];
int len = array.length;
node end = head;
for(int i=1; i< len ; i++){
end = addnode(end, array[i]);
}
return head;
}
// 给链表尾部添加一个节点
public node addnode(node end, int data){
node node = new node();
node.data = data;
end.next = node;
return node;
}
// 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 使用递归方式实现
// 
public node comb(int[] arraya, int[] arrayb){
node linka = convert(arraya);
node linkb = convert(arrayb);
node head;
if(linka.data == linkb.data){
head = linka;
linka = linka.next;
linkb = linkb.next;
head.next = null;
}else if (linka.data < linkb.data){
head = linka;
linka = linka.next;
head.next = null;
}else {
head = linkb;
linkb = linkb.next;
head.next = null;
}
node end = head;
comb(end, heada, headb);
return head;
}
// 实现递归
public void comb(node end, node heada, node headb){
if(heada == null && headb == null){
return;
}else if(heada == null){
end.next = headb;
return;
}else if(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);
}else if(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 使用循环方式实现
// 循环实现
public node comb(int[] arraya, int[] arrayb){
// 转换链表
node linka = convert(arraya);
node linkb = convert(arrayb);
// 获取头节点
node head;
if(linka.data == linkb.data){
head = linka;
linka = linka.next;
linkb = linkb.next;
head.next = null;
}else if (linka.data < linkb.data){
head = linka;
linka = linka.next;
head.next = null;
}else {
head = linkb;
linkb = linkb.next;
head.next = null;
}
node end = head;
// 依次将较小的节点加到链表尾部
while(heada != null && headb != null){
if(heada.data < headb.data){
end.next = heada;
heada = heada.next;
end = end.next;
end.next = null;
}else if(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;
}else if(headb == null){
end.next = heada;
}
return head;
}

以上所述是小编给大家介绍的android中关于递归和二分法的算法实例代码,希望对大家有所帮助