一、异或

满足：a ^ 0 = a;

​ a ^ a = 0;

​ (a ^ b) ^ c = a ^ (b ^ c);

1.交换

public static void swap(int a,int b){
    a = a^b;
    b = a^b;
    a = a^b;
    System.out.println("a = "+a);
    System.out.println("b = "+b);
}

2.题

1.找奇数次的数1

数组内有一个数出现了奇数次，其余数出现了偶数次，找出出现奇数次的数（要求时间复杂度0(N),）

public static int problem1(int []a){
    //eor: Exclusive OR
    int eor = 0;
    for (int num: a){
        eor = eor ^ num;
    }
    return eor;
}

原理：

2.找奇数次的数2

数组内有两个数出现了奇数次（这两个数不相等），其余数出现了偶数次，找出出现奇数次的数

/**
 * 这两个出现奇数次的数为num1 num2
 * 1.首先将0和数组内的数从头异或到尾 得到eor = num1 ^ num2
 *   此时需要获取其中一个数。因为两个数不同，所以二进制中肯定有一位不同，那么就可以提取出这一位，从而区分两个数
 * 2.将eor取反，再加一,得到的数再和 eor与运算，最后提取出了最右边的1
 * 3.将数组分为两类，一类这一位为1，另一类为0，将其中一组从头异或到尾，得到num1
 * 4.将num1 ^ eor ,得到num2
 * @param a
 * @return
 */
public static void problem2(int []a){
    //首先将0和数组内的数从头异或到尾 得到eor = num1 ^ num2
    int eor = 0;
    for (int num: a){
        eor = eor ^ num;
    }
    //.将eor取反，再加一,得到的数再和 eor与运算，最后提取出了最右边的1
    int rightOne =  (~eor+1) & eor;
    int onlyOne = 0;
    //将数组分为两类，一类这一位为1，另一类为0，将其中一组从头异或到尾，得到num1
    for (int num: a){
        if ((rightOne & num) == rightOne){
            onlyOne ^= num;
        }
    }
    int num1 = onlyOne;
    //将num1 ^ eor ,得到num2
    int num2 = onlyOne ^ eor;
    System.out.println("num1 = "+ num1);
    System.out.println("num1 = "+ num2);

}

二、二分(不一定有序才二分)

1.题

局部最小值

数组无序，相邻数不相等，求出一个局部最小值（时间复杂度小于O（n））

/**
 * 数组是无序的，相邻数不相等，求出一个局部最小值
 * 1.判断边界是否是局部最小，那么此时左边数下降趋势，右边数上升趋势，中间肯定有一个数处于拐点位置
 * 2.缩小范围看中间的值是否是局部最小，是则返回
 * 3.不是，假设中间值的左数小，那么左边数下降趋势，因此缩小范围，递归看左边，直到找到局部最小
 * @return
 */
public static int getLocalMin(int []a,int first, int last){
    //0.一个数
    if (a.length == 1){
        return a[0];
    }
    //1.判断边界
    if (first == 0 && a[first] < a[first+1]){
        return a[first];
    }
    if (last == a.length-1 && a[last] < a[last - 1]){
        return a[last];
    }
    //2.缩小范围看中间的值是否是局部最小，是则返回
    int medium = first + (last- first)/2;
    if (a[medium] < a[medium +1] && a[medium] < a[medium-1] ){
        return a[medium];
    }
    else {
        if (a[medium] > a[medium+1]){
            //缩小到右边
            return getLocalMin(a, medium+1, last);
        }
        else {
            return getLocalMin(a, first, medium-1);
        }

    }

}

三、递归

1.master公式

递归的子问题大小规模一样，如每次都除二

2.归并排序

/**
 * 归并排序
 */
public static void process(int[] arr,int left,int right){
    //只剩一个元素
    if (left == right){
        return;
    }
    //求中间值
    int medium = left + ( (right - left) >> 1);
    process(arr, left, medium);
    process(arr,medium+1, right);
    //分完后,将左右合并
    merge(arr,left,medium,right);
}

/**
 * 合并
 */
public static void merge(int []arr,int left,int medium,int right){
    //开辟额外空间存放有序数组,长度为合并后数组长度
    int[] help = new int[right -left +1];
    //help数组索引位
    int i = 0;
    //左边数组索引位
    int p1 = left;
    //右边数组索引位
    int p2 = medium +1;
    //将左右两边的数组元素依次比较
    while (p1 <= medium && p2 <= right){
        //小的放入help中
        help[i++] = arr[p1] <= arr[p2]? arr[p1++]: arr[p2++];
    }
    //此时有一方有剩余数组
    //将剩余的数组一方元素全部放入help中
    while (p1 <= medium){
        help[i++] = arr[p1++];
    }
    while (p2 <= right){
        help[i++] = arr[p2++];
    }
    //将help数组拷贝给原数组
    if (help.length >= 0) {
        System.arraycopy(help, 0, arr, left, help.length);
    }

}

3.快速排序3.0

版本1.0：划分一次的结果： 小于等于区，值，大于区

版本2.0：划分一次的结果： 小于区，等于值，大于区

1.0和2.0的时间复杂度都为0（n^2）,因为把目标值当做了最后一个，而最后一个可以人为构造成最大值，即构造成有序数组

版本3.0：随机选择一个数作为比较值，将该值与最后一个位置值互换。这样就变成了概率问题

3.0时间复杂度：O(NlogN)

​ 空间复杂度：最坏：O(n)

​ 最好O(nlogN)

与荷兰国旗问题相同

public static void quickSort(int[] arr,int left,int right){

    if (left < right){
        //随机找出一个数，与最后一个数交换，当做标准值。（3.0）
        int randomIndex = (int)(Math.random() * (right - left + 1));
        swap(arr,left + randomIndex ,right);
        //分割数组，形成小于， 等于， 大于三部分
        //返回值为等于部分的左右边界
        int[] partition = partition(arr, left, right);
        //递归左侧
        quickSort(arr,left,partition[0]-1);
        //递归右侧
        quickSort(arr,partition[1]+1,right);
    }
}
public static int[] partition(int []arr,int left,int right){
    //<界的右边界
    int less = left - 1;
    int bigger = right;
    //当前索引
    int i = left;
    while (i < bigger){
        //当前位置元素小于标准值
        if (arr[i] < arr[right]){
            //与左边界下一个元素交换
            //扩展左边界，索引位++
            swap(arr,++less,i++);
        }
        //大于标准值
        else if (arr[i] > arr[right]){
            //与右边界的上一个元素交换
            //扩展右边界，索引位不变，因为不知道交换后当前位置元素大小
            swap(arr,--bigger,i);
        }
        //等于
        else {
            i++;
        }
    }
    //此时将最右边的标准值与右边界的交换
    swap(arr,right,bigger);
    //返回两个位置，分别是等于标准值的左右边界
    return new int[]{less+1,bigger};
}
/**
 * 交换
 */
public static void swap(int[] arr,int index1,int index2){
    int temp = arr[index1];
    arr[index1] =  arr[index2];
    arr[index2] = temp;
}

4.题

1.小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。

解析：题目要求的是每个数左边有哪些数比自己小，其实不就是右边有多少个数比自己大，那么产生的小和就是当前值乘以多少个

public static int getRes(int[] arr){
    if (arr == null || arr.length == 0 || arr.length == 1){
        return 0;
    }
    return process(arr, 0, arr.length - 1);
}
public static int process(int[] arr,int left,int right){
    //只剩一个数，没有小和
    if (left == right){
        return 0;
    }
    int mid = left + ( (right - left) >> 1);
    return process(arr,left,mid) + process(arr,mid+1, right)+merge(arr,left,mid,right);
}
public static int merge(int[] arr,int left,int mid,int right){
    //额外空间存放有序数组
    int[] help = new int[right - left + 1];
    //help索引
    int i = 0;
    //左边数组索引，右边数组索引
    int p1 = left;
    int p2 = mid+1;
    int res = 0;
    while (p1 <= mid && p2 <= right){
        //计算小和：( right - p2 +1)*arr[p1]
        //right - p2 +1: 右边有几个比左边当前元素大的数
        res += arr[p1] < arr[p2]?( right - p2 +1)*arr[p1]: 0;
        //排序
        //此时和归并不同的是，当元素相同时，将右边数组拷贝下来，才可以更快的算出右边数组有多少比左边数组大的元素
        help[i++] = arr[p1] < arr[p2]?arr[p1++]:arr[p2++];

    }
    //将剩余数组拷贝
    while (p1 <= mid){
        help[i++] = arr[p1++];
    }
    while (p2 <= right){
        help[i++] = arr[p2++];
    }
    if (help.length >= 0) {
        System.arraycopy(help, 0, arr, left, help.length);
    }
    return res;
}

2.荷兰国旗

/**
 * 交换
 */
public static void swap(int[] arr,int index1,int index2){
    int temp = arr[index1];
    arr[index1] =  arr[index2];
    arr[index2] = temp;
}
/**
 * 荷兰国旗问题
 * @param arr
 * @param target
 */
public static void FlagProblem(int []arr,int target,int left,int right){
    //小于目标值的右边界
    int lessBorder = left-1;
    //大于目标值的左边界
    int biggerBorder = right+1;
    //当前索引位
    int i = left;
    while (i < biggerBorder ){
        //小于
        if (arr[i] < target){
            //与<界的下一个元素交换，索引位++
            //边界扩张
            swap(arr,++lessBorder,i++);
        }
        //大于
        else if (arr[i] > target){
            //索引位不变
            //边界扩张
            swap(arr,--biggerBorder,i);
        }
        else {
            //等于
            i++;
        }
    }
}

四、堆

1.顺序存储二叉树

i节点的左孩子：2i+1

​ 右孩子：2i+2

​ 父节点：（i-1）/2

2.操作

heapInsert

//某个数处在index位置，向上移动直到形成堆
public static void heapInsert(int[] arr,int index){
    //父节点索引
    int parentIndex;
    //当前节点元素大于父节点元素
    while (arr[index] > arr[ parentIndex = (index - 1) >> 1]){
        //交换元素
        swap(arr,index,parentIndex);
        //更新索引位，继续判断
        index = parentIndex;
    }
}

heapity

/**
 *元素在index位置，向下移动形成堆
 */
public static void heapify(int[]arr,int index,int heapSize){
    //左孩子索引位
    int leftIndex = (index << 1) + 1;
    //存在孩子
    while (leftIndex < heapSize){
        int rightIndex = leftIndex +1;
        //选出孩子较大的一方
        int largest = rightIndex<heapSize && arr[rightIndex]>arr[leftIndex]?rightIndex:leftIndex;
        //和父节点比较
        largest = arr[index] > arr[largest]?index:largest;
        //父节点比孩子节点大
        if (largest == index){
            break;
        }
        else {
            //交换
            swap(arr,index,largest);
            //更新索引位置，判断下一个节点
            index = largest;
            //更新左孩子索引位
            leftIndex = (index << 1) + 1;
        }
    }
}

3.堆排序

/**
 * 堆排序
 * @param arr
 */
public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2){
        return;
    }
    //将数组变换为大顶堆
    for (int i = 0; i < arr.length; i++){
        heapInsert(arr,i);
    }
    //堆管理容量
    int heapSize = arr.length;
    //将末尾元素与堆顶交换，
    //减少heapSize,此时已经得到最大值，并保存到数组最后
    //swap(arr,0,--heapSize);
    while (heapSize > 0){
        swap(arr,0,--heapSize);
        heapify(arr,0,heapSize);
    }
}

4.题

获取中位数的结构

//一个快速获取中位数的数据结构
public static class MedianHolder {
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((x,y)->y-x);
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(x -> x));


    /**
     * 维持两堆的大小差值小于二
     *
     */
    private void modifyTwoHeapsSize() {
        if (maxHeap.size() - minHeap.size() >= 2){
            //弹出加入到小根堆
            minHeap.add(maxHeap.poll());
        }
        if (minHeap.size() - maxHeap.size() >= 2){
            //弹出加入到大根堆
            maxHeap.add(minHeap.poll());
        }
    }
    /**
     * 加入数字：
     * 如果大根堆为null,数字加入到大根堆
     * 如果数字小于大根堆的堆顶数字，加入到大根堆
     * 否则，加入到小根堆
     */
    public void addNum(int num){
        if (maxHeap.isEmpty() || num <= maxHeap.peek()){
            maxHeap.add(num);
        }
        else {
            minHeap.add(num);
        }
        //加入后，调整两堆的大小
        modifyTwoHeapsSize();
    }
    public void addNum(int[] nums){
        for (int num: nums){
            addNum(num);
        }
    }

    /**
     * 获取中位值
     * 如果大小相等，都弹出堆顶元素，求平均值
     * 不相等则弹出size大的堆顶元素
     */
    public Integer getMedian() {
        int maxHeapSize = this.maxHeap.size();
        int minHeapSize = this.minHeap.size();
        //判null
        if (maxHeapSize + minHeapSize == 0) {
            return null;
        }
        Integer maxHeapHead = this.maxHeap.peek();
        Integer minHeapHead = this.minHeap.peek();
        if (maxHeapSize == minHeapSize){
            return (maxHeapHead+minHeapHead) / 2;
        }
        return maxHeapSize > minHeapSize?maxHeapHead:minHeapHead;
    }
}

五、桶排序

//digit: 最大数是 几位数
public static void radixSort(int []arr,int left,int right,int digit){
    final int radix = 10;
    int i = 0, j = 0;
    int []bucket = new int[right - left + 1];
    for (int d = 1; d <= digit; d++){
        //count[i] 代表当前位d,是i的数有多少个
        int []count = new int[radix];
        for (i = left; i <= right;i++){
            j = getNumInDigit(arr[i], d);
            count[j]++;
        }
        //count[i] 代表当前位d,是0-i的数有多少个
        for (i = 1; i < radix; i++){
            count[i] = count[i]+ count[i-1];
        }
        //此时都放入了count中，再放入bucket
        //从右向左遍历（保证先入先出）
        for (i = right; i >= left; i--){
            j = getNumInDigit(arr[i],d);
            bucket[ count[j]-1] = arr[i];
            count[j]--;
        }
        for (i = left,j =0; i <= right;i++,j++){
            arr[i] = bucket[j];
        }
    }
}
public static int getNumInDigit(int num,int digit){
    int x =  (int)Math.pow(10,digit-1);
    return (num / x) % 10;

}
public static int getDigit(int []arr){
    int max = Integer.MIN_VALUE;
    for (int num: arr){
        max = Math.max(num,max);
    }
    int digit = 0;
    while (max != 0){
        digit++;
        max/= 10;
    }
    return digit;
}

六、排序总结

七、链表

反转

//反转单链表
public static Node reverseList(Node head){
    Node pre = null;
    Node next = null;
    while (head != null){
        //保存next
        next = head.next;
        //更新连接
        head.next = pre;
        //更新前一个节点
        pre = head;
        //更新头结点
        head = next;
    }
    return pre;
}

题

判断是否回文(3种)

/**
 * 空间复杂度O(N)
 * 使用栈
 */
public static boolean isPalindrome1(Node head){
    //进栈
    Stack<Node> nodes = new Stack<>();
    Node help = head;
    while (help != null){
        nodes.push(help);
        help = help.next;
    }
    help = head;
    //出栈比较
    while (help != null){
        if (help.value != nodes.pop().value){
            return false;
        }
        help = help.next;
    }
    return true;
}
/**
 * 空间复杂度O(1/2n)
 * 快慢指针
 */
public static boolean isPalindrome2(Node head) {
    if (head == null || head.next == null) {
        return true;
    }
    Node fast = head;
    Node slow = head.next;
    while (fast.next != null && fast.next.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    //此时满指针之后的node就可以进行折叠比较了
    Stack<Node> nodes = new Stack<>();
    Node help = slow;
    while (help != null){
        nodes.push(help);
        help = help.next;
    }
    help = head;
    while ( !nodes.isEmpty()){
        if (help.value != nodes.pop().value ){
            return false;
        }
        help = help.next;
    }
    return true;
}
/**
 * 空间复杂度O(1)
 * 使用快慢指针，反转链表
 */
public static boolean isPalindrome3(Node head){
    if (head == null || head.next == null) {
        return true;
    }
    Node n1 = head;
    Node n2 = head;
    // find mid node
    while (n2.next != null && n2.next.next != null) {
        // n1 -> mid
        n1 = n1.next;
        // n2 -> end
        n2 = n2.next.next;
    }
    //把慢指针为头结点的后续指针反转
    //右半部分的头指针
    n2 = n1.next;
    n1.next = null;
    Node next = null;
    while (n2 != null){
        next = n2.next;
        n2.next = n1;
        n1 = n2;
        n2 = next;
    }
    next = n1;
    n2 = head;
    //比较
    boolean res = true;
    while (n1 .next != null && n2.next != null){
        if (n1.value != n2.value) {
            res = false;
            break;
        }
        n1 = n1.next;
        n2 = n2.next;
    }
    n1 = next.next;
    next.next = null;
    //还原
    while (n1 != null){
        n2 = n1.next;
        n1.next = next;
        next = n1;
        n1 = n2;
    }
    return true;
}

排序

【题目】给定一个单链表的头节点head，节点的值类型是整型，再给定一个整 数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的 节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。

【进阶】在实现原问题功能的基础上增加如下的要求

【要求】调整后所有小于pivot的节点之间的相对顺序和调整前一样
【要求】调整后所有等于pivot的节点之间的相对顺序和调整前一样
【要求】调整后所有大于pivot的节点之间的相对顺序和调整前一样
【要求】时间复杂度请达到O(N)，额外空间复杂度请达到O(1)

解析

  /**
    * 排序 非进阶()
    * 空间复杂度O(n)
    */
   public static Node listPartition1(Node head, int pivot){
       //类似于荷兰国旗和快排
       if (head == null){
           return head;
       }
       Node help = head;
       int i = 0;
       //计算链表长度
       while (help != null){
           i++;
           help = help.next;
       }
       Node[] nodes = new Node[i];
       //将节点放入数组中
       i = 0;
       help = head;
       for (i = 0; i != nodes.length; i++) {
           nodes[i] = help;
           help = help.next;
       }
       //进行分区patition
       arrPartition(nodes,pivot);
       //将链表连接
       for (i =1; i < nodes.length; i++){
           nodes[i-1].next = nodes[i];
       }
       nodes[i-1].next= null;
       return nodes[0];
   }

   /**
    * 分区处理
    */
   public static void arrPartition(Node[] nodes, int pivot){
       //<界的右边界
       int less = -1;
       //>界的左边界
       int bigger = nodes.length;
       //当前索引位
       int i = 0;
       //当前位置没有到左边界
       while (i != bigger){
           //当前位置node与<界的右边界的下一个node交换
           if (nodes[i].value < pivot){
               swap(nodes,i++,++less);
           }
           //当前位置node与>界的左边界的上一个node交换
           else if (nodes[i].value > pivot){
               swap(nodes,--bigger,i);
           }
           else {
               i++;
           }
       }
   }
   //交换
   public static void swap(Node[] nodeArr, int a, int b) {
   Node tmp = nodeArr[a];
   nodeArr[a] = nodeArr[b];
   nodeArr[b] = tmp;
}

//进阶
public static Node listPartition2(Node head, int pivot) {
		Node sH = null; // small head
		Node sT = null; // small tail
		Node eH = null; // equal head
		Node eT = null; // equal tail
		Node bH = null; // big head
		Node bT = null; // big tail
		Node next = null; // save next node
		// every node distributed to three lists
		while (head != null) {
			next = head.next;
			head.next = null;
			if (head.value < pivot) {
				if (sH == null) {
					sH = head;
					sT = head;
				} else {
					sT.next = head;
					sT = head;
				}
			} else if (head.value == pivot) {
				if (eH == null) {
					eH = head;
					eT = head;
				} else {
					eT.next = head;
					eT = head;
				}
			} else {
				if (bH == null) {
					bH = head;
					bT = head;
				} else {
					bT.next = head;
					bT = head;
				}
			}
			head = next;
		}
		// small and equal reconnect
		if (sT != null) {
			sT.next = eH;
			eT = eT == null ? sT : eT;
		}
		// all reconnect
		if (eT != null) {
			eT.next = bH;
		}
		return sH != null ? sH : eH != null ? eH : bH;
	}

复制含有随机指针节点的链表

【题目】一种特殊的单链表节点类描述如下 class Node {

int value;

Node next;

Node rand;

Node(int val) { value = val; } }

rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节 点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点 head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点

/**
    使用hashmap
    key 存储老链表
    value 存储新链表
    这样就可以实现对应关系
 */
public static Node copyList(Node head){
    Map<Node,Node> map = new HashMap<>();
    Node helpNode = head;
    while (helpNode != null){
        //添加key和value进入map中
        map.put(helpNode,new Node(helpNode.value));
        helpNode = helpNode.next;
    }
    helpNode = head;
    while (helpNode != null){
        //设置新节点的next和rand
        map.get(helpNode).next = map.get(helpNode.next);
        map.get(helpNode).rand = map.get(helpNode.rand);
        helpNode = helpNode.next;
    }
    return map.get(head);
}

获取有环链表的第一个入环节点

/**
 *
 * 快慢指针法，
 * 快指针一次两步，慢指针一次一步
 * 1.如果快指针走到了最后，则无环
 * 2.如果快慢指针相遇了，此时将快指针回到head节点，
 *  然后快指针也一次走一步，慢指针继续从相遇节点开始走，相遇时候就是入环的第一个节点。
 * @param head
 * @return 入环的第一个节点
 */
public static Node hasCricle(Node head){
    if (head == null || head.next == null || head.next.next == null){
        return null;
    }
    Node slow = head.next;
    Node fast = head.next.next;
    //当快慢指针相遇时
    while (slow != fast){
        if (fast.next == null || fast.next.next == null){
            return null;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    //此时已经相遇(fast回到head节点)
    fast = head;
    while (slow!=fast){
        slow = slow.next;
        fast = fast.next;
    }
    //相遇节点
    return fast;
}

两个链表获取第一个相交节点(无环)

/**
 * 获取第一个相交节点
 * 两个链表分别走到末尾，记录len,end
 * 1.end是一个内存地址，则存在相交问题
 *   将长链表先走到和短链表一样长，然后一起走，相遇就是第一个相交节点
 * 2.不是一个内存地址，不相交
 */
public static Node noLoop(Node head1, Node head2) {
    if (head1 == null || head2 == null){
        return null;
    }
    int len = 0;
    Node cur1 = head1;
    Node cur2 = head2;
    //分别走到尾节点
    while (cur1.next != null){
        len++;
        cur1 = cur1.next;
    }
    while (cur2.next != null){
        len--;
        cur2 = cur2.next;
    }
    //不相交
    if (cur1 != cur2){
        return null;
    }
    //此时len就是长度的差值（可能为负）
    //判断谁长，cur1设置为长链表头
    cur1 = len > 0?head1: head2;
    //cur2设置为短头
    cur2  = cur1 == head1?head2:head1;
    len = Math.abs(len);
    while (len != 0){
        len--;
        cur1 = cur1.next;
    }
    //一起向交点走
    while (cur1 != cur2){
        cur1 = cur1.next;
        cur2 = cur2.next;
    }
    return cur1;
}