Android笔记大全（四）

题目

• 翻转单链表
• 合并两个有序链表
  https://www.cnblogs.com/xinShengDaiCaiNiao/p/11380331.html

• 判断一个链表是否有环

  haveCycle(ListNode root){
  	ListNode s = root.next;
  	ListNode q = root.next.next;
  	while (s!=null && q != null){
  		if(s == q){
  			return true;
  		}
  		s = s.next;
  		q = q.next.next;
  	}
  	return false;
  }

• 一组无序数中，找到前k大的数

• 用两个栈实现队列，或者两个队列实现栈
• 二分法

• 冒泡排序

  maopao(int[] arr){
  	for(int i = 0;i < arr.length-1; i++){
  		for(int j = i+1;j <  arr.length ;j++){
  			if(arr[i]< arr[j]){
  				int temp = arr[j];
  				arr[j] = arr[i];
  				arr[i] = temp;
  			}
  		}
  	}
  }

• 快速排序

  //快速排序
  void quick_sort(int s[], int l, int r)
  {
  	if (l < r)
  	{
  		//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
  		int i = l, j = r, x = s[l];
  		while (i < j)
  		{
  			while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
  				j--;  
  			if(i < j) 
  				s[i++] = s[j];
  			
  			while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
  				i++;  
  			if(i < j) 
  				s[j--] = s[i];
  		}
  		s[i] = x;
  		quick_sort(s, l, i - 1); // 递归调用 
  		quick_sort(s, i + 1, r);
  	}
  }

• 二叉树遍历

• 斐波那契数列

• 给定一个数组，将数组里的偶数要在奇数前面，要求时间复杂度位O(n)

  public int[] useWhileOn(int[] data) {
        // 头索引
        int headIndex = 0;
        // 尾索引
        int tailIndex = data.length - 1;
        // 从头到尾
        while (headIndex < tailIndex ) {
            // 找到前面奇数索引时
            if (isOddNumber(data[headIndex])) {
                // 找到后面偶数索引时
                if (isEvenNumber(data[tailIndex])) {
                    // 奇偶交换位置，前后交互位置
                    swap(data, headIndex, tailIndex);
                    headIndex++;
                }
                // 直到找到偶数索引
                tailIndex--;
            } else {
                // 直到找到奇数索引
                headIndex++;
            }
        }
  
        return data;
    }

• 两个二进制字符串相加得到的二进制字符串

  String twoPlus(String num1,String num2){
  	int count = 0;
  	int i = num1.length();
  	int j = num2.length();
  	StringBuidler result = new StringBuidler();
  	while (i>=0 || j >= 0 || count != 0){
  		if(i >= 0)
  			count = count + num1.ChatAt(i--) - '0';
  		if(j >= 0)
  			count = count + num2.ChatAt(j--) - '0';
  		result.append(count % 2);
  		count = count / 2;
  	}
  	return result.reverse().toString();
  }

• 链表中倒数第k个结点

  public class Solution {
  	public ListNode FindKthToTail(ListNode head,int k) {
  		if(head == null || k ==0 ){
  			return null;
  		}
   
  		ListNode slow=head;
  		ListNode fast=head;
  		for(int i=0;i<k;i++){
  			if(fast==null){
  				return null;
  			}
  			fast=fast.next;
   
  		}
  		while(fast!=null){
  			slow=slow.next;
  			fast=fast.next;
  		}
   
  		return slow;
   
  	}
  }

• 镜像二叉树

  public class Solution {
  	public void Mirror(TreeNode root) {
  		if(root == null){
  			return;
  		}
  		TreeNode temp = root.left;
  		root.left = root.right;
  		root.right = temp;
  		Mirror(root.left);
  		Mirror(root.right);
  	}
  }

总结

quick_sort(arr[],int low,int hight) {
int i = low;
int j = hight;
int temp;
if (low < hight){
temp = arr[i];
while (i! = j){
while (i < j && temp < arr[j]){
–j;
}
arr[i] = arr[j];
while (i < j && temp > arr[i]){
++i;
}
arr[j] = arr[i];
}
arr[i] = temp;
quick_sort(arr,low,i-1);
quick_sort(arr,j+1,hight);

}

}