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. 實(shí)現(xiàn)一個(gè)函數(shù)，在一個(gè)有序整型數(shù)組中二分查找出指定的值，找到則返回該值的位置，找不到返回 -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. 實(shí)現(xiàn)一個(gè)函數(shù)，在一個(gè)有序整型數(shù)組中二分查找出指定的值，找到則返回該值的位置，找不到返回 -1。
// array 升虛數(shù)組
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. 寫(xiě)一個(gè)函數(shù)將一個(gè)數(shù)組轉(zhuǎn)化為一個(gè)鏈表。
// 要求：不要使用庫(kù)函數(shù)，(如 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;
}
// 給鏈表尾部添加一個(gè)節(jié)點(diǎn)
public Node addNode(Node end, int data){
Node node = new Node();
node.data = data;
end.next = node;
return node;
}
// 3. 有兩個(gè)數(shù)組，[1,3,4,5,7,9] 和 [2,3,4,5,6,8],用上面的函數(shù)生成兩個(gè)鏈表 linkA 和
// linkB，再將這兩個(gè)鏈表合并成一個(gè)鏈表,結(jié)果為[1,2,3,4,5,6,7,8,9].
// 要求：不要生成第三個(gè)鏈表，不要生成新的節(jié)點(diǎn)。
// 3.1 使用遞歸方式實(shí)現(xiàn)
// 
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;
}
// 實(shí)現(xiàn)遞歸
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 使用循環(huán)方式實(shí)現(xiàn)
// 循環(huán)實(shí)現(xiàn)
public Node comb(int[] arrayA, int[] arrayB){
// 轉(zhuǎn)換鏈表
Node linkA = convert(arrayA);
Node linkB = convert(arrayB);
// 獲取頭節(jié)點(diǎn)
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;
// 依次將較小的節(jié)點(diǎn)加到鏈表尾部
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;
}
}
// 如果其中一個(gè)鏈表為空，將另外一個(gè)鏈表直接添加到合成鏈表尾部
if(headA == null){
end.next = headB;
}else if(headB == null){
end.next = headA;
}
return head;
}