你的位置:首页 > 操作系统

[操作系统]Android 算法 关于递归和二分法的小算法


 // 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;}