19.算法

• 1.冒泡排序
• 2.二分查找法
• 3.插入排序
• 4.选择排序
• 5.数据里有{1,2,3,4,5,6,7,8,9}，请随机打乱顺序，生成一个新的数组（请以代码实现）
• 6.一个问题的最优解是什么意思
• 7.如何不用额外变量交换两个数
• 8.一个数组中只有一个出现了奇数次的数，找出这个数
• 9.提取整形数最右侧的1
• 10.一个数组中出现奇数次的两个数，其它数都是偶数次。
• 11.统计一个数的二进制里有多少个1
• 12.红黑树的性质：
• 13.手写双向链表
• 14.手写一个ArrayList

//1.冒泡排序
public static int[] bubbleSort(int[] arr){
    int temp;
    //用来控制比较的次数为数组长度-1次
    for (int j = 0; j arr[i+1]){
                temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
            }
        }
    }
    return arr;
}

public static int binarySearch(int a,int[] arr){
    int start=0;
    int end=arr.length-1;
    while(start<=end){
        //防止int溢出，所以才不用(end+start)/2
        int mid=start+(end-start)/2;
        if(a==arr[mid]){
            return mid;
        }else if(a 
3.插入排序 
public static int[] insertSort(int[] arr){
    //从数组的第二个数开始插入
    for (int i = 1; i <=arr.length-1 ; i++) {
        int tmp=arr[i];
        //第一个要插入的位置
        int index=i-1;
        while(index>=0&&tmp 
4.选择排序 
public static void selectionSort(int[] arr){
    //如果数组为空或者数组长度小于2,直接退出方法
    if(arr==null||arr.length<2){
        return;
    }
    for (int i = 0; i  
5.数据里有{1,2,3,4,5,6,7,8,9}，请随机打乱顺序，生成一个新的数组（请以代码实现） 
public static int[] srand(int arr[]){
    int b[]=new int[arr.length];
    for (int i = 0; i  
6.一个问题的最优解是什么意思 
一般情况下，解决一个问题的算法流程，在时间复杂度的指标上，一定要尽可能的低，先满足了时间复杂度最低这个指标之后，使用最少的空间的算法流程，叫这个问题的最优解。
 一般说最优解是忽略掉常数项这个因素的，因为这个层次只决定了实现层次的优化和考虑，而和怎么解决这个问题的思想无关。
 
7.如何不用额外变量交换两个数 
public static boolean swap(int arr[],int i,int j){
    //这种交换必须满足一个条件,交换的两个数不能指向同一个内存地址.
    //因为交换相当于两个容器里东西交换,如果只有1个容器谈何交换.
    //所以对于数组而言,下标i和j不能相等.
    if(i!=j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
        return true;
    }
    return false;
}
 
8.一个数组中只有一个出现了奇数次的数，找出这个数 
思路：异或运算满足交换律和结合律。根据N^N=0 0^N=N 出现偶数次的数最后异或后肯定为0，如果只有1个出现奇数次的数，那最后数组所有元素的异或运算就是这个奇数的值。
 
 
public static void printOddTimesNum(int[] arr){
    int eor=0;
    for (int i = 0; i n&(~n+1)
 
public static void main(String[] args) {
    //随机来个偶数,因为奇数的个位数肯定是1
    int a=((int)(Math.random()*500000))<<1;
    //提取整数最右侧的1
    int b=a&(~a+1);
    System.out.println(a);
    System.out.println(Integer.toBinaryString(a));
    System.out.println(Integer.toBinaryString(b));
}
 
10.一个数组中出现奇数次的两个数，其它数都是偶数次。 
public static void printOddTimesNum2(int[] arr){
    int eor=0;
    for (int i = 0; i  f=first;
        for (int i = 0; i <= length-1; i++) {
            sb.append(f.elemnt+",");
            f=f.next;
        }
        sb.deleteCharAt(sb.length()-1);
        sb.append("}");
        return sb.toString();
    }
    public static void main(String[] args) {
        MylinkedList