高频算法题目总结.md

Ctrl+Shift+P（MacOS：cmd+shift+p）呼出命令面板，输入Markdown Preview Enhanced: Create Toc会生成一段类似，保存生成目录。


<!-- @import "[TOC]" {cmd="toc" depthFrom=1 depthTo=6 orderedList=false} -->

<!-- code_chunk_output -->

- [Java API整理](#java-api整理)
- [Go API整理](#go-api整理)
- [链表](#链表)
  - [排序](#排序)
  - [翻转链表, NC78](#翻转链表-nc78)
  - [LFU缓存结构设计](#lfu缓存结构设计)
  - [设计LRU缓存结构, NC93](#设计lru缓存结构-nc93)
  - [合并有序链表, NC33](#合并有序链表-nc33)
  - [链表中的节点每K个一组翻转](#链表中的节点每k个一组翻转)
  - [判断链表中是否有环](#判断链表中是否有环)
  - [链表中环的入口结点](#链表中环的入口结点)
  - [删除链表的倒数第n个节点](#删除链表的倒数第n个节点)
  - [两个链表的第一个公共结点](#两个链表的第一个公共结点)
  - [两个链表生成相加链表](#两个链表生成相加链表)
  - [合并k个已排序的链表](#合并k个已排序的链表)
  - [单链表的排序，NC70](#单链表的排序nc70)
  - [判断链表是否为回文结构](#判断链表是否为回文结构)
  - [链表内指定区间反转](#链表内指定区间反转)
  - [删除有序链表中重复出现的元素](#删除有序链表中重复出现的元素)
  - [环形链表的约瑟夫问题](#环形链表的约瑟夫问题)
  - [链表的奇偶重排](#链表的奇偶重排)
  - [重排链表（1->n->2->n-1）](#重排链表1-n-2-n-1)
  - [二叉搜索树与双向链表](#二叉搜索树与双向链表)
- [队列、栈](#队列栈)
  - [用两个栈实现队列](#用两个栈实现队列)
  - [有效括号序列](#有效括号序列)
  - [包含 min 函数的栈](#包含-min-函数的栈)
  - [表达式求值](#表达式求值)
  - [最长括号子串](#最长括号子串)
  - [括号生成](#括号生成)
- [二叉树](#二叉树)
  - [实现二叉树先序，中序和后序遍历](#实现二叉树先序中序和后序遍历)
  - [二叉树的层序遍历](#二叉树的层序遍历)
  - [二叉树的之字形层序遍历](#二叉树的之字形层序遍历)
  - [在二叉树中找到两个节点的最近公共祖先](#在二叉树中找到两个节点的最近公共祖先)
  - [重建二叉树](#重建二叉树)
  - [输出二叉树的右视图（先重建，再输出右视图）](#输出二叉树的右视图先重建再输出右视图)
  - [二叉树的最大深度](#二叉树的最大深度)
  - [判断是不是平衡二叉树](#判断是不是平衡二叉树)
  - [二叉树根节点到叶子节点的所有路径和](#二叉树根节点到叶子节点的所有路径和)
  - [二叉树中和为某一值的路径，返回所有路径](#二叉树中和为某一值的路径返回所有路径)
  - [判断一棵二叉树是否为搜索二叉树和完全二叉树](#判断一棵二叉树是否为搜索二叉树和完全二叉树)
  - [二叉树的最大路径和](#二叉树的最大路径和)
  - [判断二叉树是否对称](#判断二叉树是否对称)
  - [二叉树中是否存在节点和为指定值的路径](#二叉树中是否存在节点和为指定值的路径)
  - [序列化二叉树](#序列化二叉树)
  - [二叉搜索树的第k个结点](#二叉搜索树的第k个结点)
  - [把二叉树打印成多行](#把二叉树打印成多行)
  - [二叉树的镜像](#二叉树的镜像)
  - [判断t1树中是否有与t2树拓扑结构完全相同的子树](#判断t1树中是否有与t2树拓扑结构完全相同的子树)
  - [合并二叉树](#合并二叉树)
  - [字典树的实现](#字典树的实现)
  - [找到二叉搜索树中的两个错误节点](#找到二叉搜索树中的两个错误节点)
- [堆](#堆)
  - [最小的K个数](#最小的k个数)
  - [字符串出现次数的TopK问题](#字符串出现次数的topk问题)
  - [寻找第K大](#寻找第k大)
- [双指针](#双指针)
  - [最长无重复子数组的长度](#最长无重复子数组的长度)
  - [滑动窗口的最大值](#滑动窗口的最大值)
  - [合并区间（区间重叠）](#合并区间区间重叠)
  - [反转字符串](#反转字符串)
  - [数组中相加和为0的三元组](#数组中相加和为0的三元组)
  - [接雨水问题](#接雨水问题)
  - [最小覆盖子串（T包含S的最小子串）](#最小覆盖子串t包含s的最小子串)
  - [两数之和](#两数之和)
  - [最长重复子串（连续两个相同的字符串）](#最长重复子串连续两个相同的字符串)
- [动态规划](#动态规划)
  - [跳台阶](#跳台阶)
  - [连续子数组的最大和（sum < 0置为0）](#连续子数组的最大和sum--0置为0)
  - [最长公共子串（返回具体字符串/长度）](#最长公共子串返回具体字符串长度)
  - [斐波那契数列](#斐波那契数列)
  - [最长回文子串的长度](#最长回文子串的长度)
  - [最长递增子序列](#最长递增子序列)
  - [买卖股票的最佳时机](#买卖股票的最佳时机)
  - [矩阵的最小路径和](#矩阵的最小路径和)
  - [编辑距离](#编辑距离)
  - [不同路径的数目](#不同路径的数目)
  - [最长公共子序列](#最长公共子序列)
  - [最长的括号子串](#最长的括号子串)
  - [高空扔鸡蛋](#高空扔鸡蛋)
  - [兑换零钱](#兑换零钱)
  - [最大正方形](#最大正方形)
  - [通配符匹配](#通配符匹配)
  - [正则表达式匹配](#正则表达式匹配)
  - [矩阵最长递增路径](#矩阵最长递增路径)
  - [最长上升子序列](#最长上升子序列)
  - [目标和（完全背包）](#目标和完全背包)
  - [打家劫舍](#打家劫舍)
  - [带权值的最小路径和](#带权值的最小路径和)
  - [最长不含重复字符的子字符串](#最长不含重复字符的子字符串)
  - [把数字翻译成字符串](#把数字翻译成字符串)
- [二分](#二分)
  - [求平方根](#求平方根)
  - [在旋转过的有序数组中寻找目标值](#在旋转过的有序数组中寻找目标值)
  - [在两个长度相等的排序数组中找到上中位数](#在两个长度相等的排序数组中找到上中位数)
  - [有序矩阵元素查找](#有序矩阵元素查找)
  - [二分查找](#二分查找)
  - [旋转数组的最小数字](#旋转数组的最小数字)
  - [数字在升序数组中出现的次数](#数字在升序数组中出现的次数)
  - [峰值](#峰值)
- [数组](#数组)
  - [数组中只出现一次的数字](#数组中只出现一次的数字)
  - [合并两个有序的数组](#合并两个有序的数组)
  - [子数组最大乘积](#子数组最大乘积)
  - [数组中最长连续子序列](#数组中最长连续子序列)
  - [数组中未出现的最小正整数](#数组中未出现的最小正整数)
  - [顺时针旋转数组](#顺时针旋转数组)
  - [旋转数组](#旋转数组)
  - [逆序对](#逆序对)
  - [调整数组顺序使奇数位于偶数前面](#调整数组顺序使奇数位于偶数前面)
  - [矩阵乘法](#矩阵乘法)
- [回溯](#回溯)
  - [字符串的全排列](#字符串的全排列)
  - [岛屿的数量](#岛屿的数量)
  - [没有重复项数字的所有排列(全排列)](#没有重复项数字的所有排列全排列)
  - [集合的所有子集](#集合的所有子集)
  - [重复项数字的所有排列](#重复项数字的所有排列)
  - [N皇后问题](#n皇后问题)
  - [把数组字符串转换为 ip 地址](#把数组字符串转换为-ip-地址)
  - [加起来和为目标值的组合](#加起来和为目标值的组合)
- [其他](#其他)
  - [螺旋矩阵](#螺旋矩阵)
  - [顺时针旋转矩阵](#顺时针旋转矩阵)
  - [进制转换](#进制转换)
  - [反转数字](#反转数字)
  - [大数加法](#大数加法)
  - [把字符串转换成整数(atoi)](#把字符串转换成整数atoi)
  - [最长公共前缀](#最长公共前缀)
  - [回文数字](#回文数字)
  - [字符串变形（反序，大写）](#字符串变形反序大写)
  - [最大值（数组拼接最大数）](#最大值数组拼接最大数)
  - [验证ip地址](#验证ip地址)
  - [二进制中1的个数](#二进制中1的个数)
  - [第一个只出现一次的字符](#第一个只出现一次的字符)
- [其他编程题（golang、java）](#其他编程题golangjava)
  - [单例模式](#单例模式)
  - [实现线程安全的生产者消费者](#实现线程安全的生产者消费者)
  - [一个10G的文件，里面全部是自然数，一行一个，乱序排列，对其排序。在32位机器上面完成，内存限制为 2G（bitmap原理知道吗？）](#一个10g的文件里面全部是自然数一行一个乱序排列对其排序在32位机器上面完成内存限制为-2gbitmap原理知道吗)
  - [实现使用字符串函数名，调用函数](#实现使用字符串函数名调用函数)
  - [负载均衡算法。（一致性哈希）](#负载均衡算法一致性哈希)
  - [（Goroutine）有三个函数，分别打印"cat", "fish","dog"要求每一个函数都用一个goroutine，按照顺序打印100次](#goroutine有三个函数分别打印cat-fishdog要求每一个函数都用一个goroutine按照顺序打印100次)
  - [两个协程交替打印10个字母和数字](#两个协程交替打印10个字母和数字)
  - [启动 2个groutine 2秒后取消， 第一个协程1秒执行完，第二个协程3秒执行完。](#启动-2个groutine-2秒后取消-第一个协程1秒执行完第二个协程3秒执行完)
  - [当select监控多个chan同时到达就绪态时，如何先执行某个任务？](#当select监控多个chan同时到达就绪态时如何先执行某个任务)

<!-- /code_chunk_output -->

## Java API整理

- api

https://blog.csdn.net/qq_34756156/article/details/120713595

## Go API整理

- api

https://www.pseudoyu.com/zh/2021/05/29/algorithm_data_structure_go/
https://greyireland.gitbook.io/algorithm-pattern/ru-men-pian/golang

- 刷题模板

https://greyireland.gitbook.io/algorithm-pattern/

## 链表

### 排序

```java
import java.util.*;


public class Solution {
    
    public int[] MySort(int[] arr) {
//             选择排序
//             return selectSort(arr);
//             冒泡排序
//             return bubbleSort(arr);
//             插入排序
//             return insertSort(arr);
//             希尔排序
//             return shellSort(arr);
//             归并排序
//             return mergeSort(arr,0,arr.length-1);
//             快速排序
//             quickSort(arr,0,arr.length-1);
//             return arr;
//             计数排序
//             return countSort(arr);
//             基数排序
//             return radixSort(arr);
//             桶排序
            return bucketSort(arr);
    }
    // 选择排序---选择最小的数与当前数交换
    public int[] selectSort(int[] arr){
        if(arr.length<2)return arr;
        for(int i=0;i<arr.length;i++){
            int min = i;
            for(int j=i+1;j<arr.length;j++){
                // 与当前最小值比
                if(arr[j]<arr[min])min=j;
            }
            swap(arr,i,min);
        }
        return arr;
    }
    
    //冒泡排序---两两比较交换
    public int[] bubbleSort(int[] arr){
        if(arr.length<2) return arr;
        for(int i = 0;i<arr.length;i++){
            for(int j = i+1;j<arr.length;j++){
                if(arr[i]>arr[j])swap(arr,i,j);
            }
        }
        return arr;
    }
    
    // 插入排序---与当前位置之前的所有元素比较，交换元素
    public int[] insertSort(int[] arr){
        if(arr.length<2)return arr;
        for(int i=1;i<arr.length;i++){
            for(int j=i;j>0;j--){
                if(arr[j]<arr[j-1])swap(arr,j,j-1);
            }
        }
        return arr;
    }
    
    // 希尔排序---以间隔分组分别排序，间隔缩短再排序，
    // 直至缩短成间隔为1，升级版插入排序
    public int[] shellSort(int[] arr){
        // gap的设定，根据Knuth序列定义，左程云视频
        int h = 1;
        while(h <= arr.length / 3){
            h = h*3 + 1;
        }
        for(int gap =h;gap>0;gap=(gap-1)/3){
            for(int i=gap;i<arr.length;i++){
                for(int j=i;j-gap>=0;j=j-gap){
                    if(arr[j]<arr[j-gap])swap(arr,j,j-gap);
                }
            }
        }
        return arr;
    }
    
    // 归并排序---找个中间轴，左边排序好，右边排序好，
    // 然后左边右边合并起来，其中每一边排序时再划中间轴，直到相隔两个数进行排序
    public int[] mergeSort(int[] arr,int left,int right){
        if(left==right)return arr;
        int mid = left + (right - left)/2;
        // 左边排序
        mergeSort(arr,left,mid);
        // 右边排序
        mergeSort(arr,mid+1,right);
        // 合并
        merge(arr,left,mid+1,right);
        return arr;
    }
    // 两个排好序的数组合并，start 左数组起点，end 右数组起点，right 右数组终点
    public void merge(int[] arr,int start,int end,int right){
        // mid为两个有序数组的分界点
        int i = start,j=end,k=0,mid=end-1;
        int[] temp = new int[right-start+1];
        while(i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[k] = arr[i];
                k++;i++;
            }else{
                temp[k] = arr[j];
                k++;j++;
            }
        }
        // 剩余数组直接接龙
        while(i<=mid)temp[k++]=arr[i++];
        while(j<=right)temp[k++]=arr[j++];
        
        // 赋值原数组
        for(int m=0;m<k;m++){
            arr[start+m] = temp[m];
        }
    }
    
    // 快速排序---选择中轴数，左边向右，右边向左，分别与中轴数比较，
    // 大小交换，中轴数与左指针交换，左边递归，右边递归
    public void quickSort(int[] arr,int left,int right){
        if(left >= right) return ;
        int pivot = arr[left];
        int i = left,j = right;
        while(i < j){
            while(arr[j] >= pivot && j>i){
                j--;
            }
            while(arr[i] <= pivot && i<j){
                i++;
            }
            if(i < j){
                swap(arr,i,j);
            }
        }
        swap(arr,left,i);
        //左子数组
        quickSort(arr,left,j-1);
        //右子数组
        quickSort(arr,j+1,right);
    }
    
    // 计数排序---不适合，数据量比数据范围小
    public int[] countSort(int[] arr){
        int[] newArr = new int[arr.length];
        int[] countArr = new int[6];
        for(int i=0;i<arr.length;i++){
            countArr[arr[i]]++;
        }
        for(int i=1,j=0;i<countArr.length;i++,j++){
            while(countArr[i]--!=0){
                newArr[j++]=i;
            }
        }
        return newArr;
    }
    
    // 基数排序---二维数组，10*数组长度，从个位数一直到最大位数，分别排序重组
    public int[] radixSort(int[] arr){
        // 找到最大位数
        int max = 1;
        for(int i=0;i<arr.length;i++){
            int count = 1;
            int temp = arr[i];
            while(temp/10>0){count++;temp = temp/10;}
            if(count>max)max = count;
        }
        
        for(int m=0;m<max;m++){
            int[][] countArr = new int[10][arr.length];
            for(int i=0;i<arr.length;i++){
                int n = m;
                int temp = arr[i];
                while(n-->0){temp=temp/10;}
                int result = temp%10;
                for(int k=0;k<countArr[result].length;k++){
                    if(countArr[result][k]==0){
                        countArr[result][k]=arr[i];
                        break;
                    }
                }
            }
            // 重组数组
            arr = reGroup(countArr,arr.length);
        }
        return arr;
    }
    // 重组数组
    public int[] reGroup(int[][] countArr,int length){
        int[] arr = new int[length];
        int k=0;
        for(int i=0;i<countArr.length;i++){
            for(int j=0;j<countArr[i].length;j++){
                if(countArr[i][j]>0){
                    arr[k++] = countArr[i][j];
                }
            }
        }
        return arr;
    }
    
    // 桶排序---给定n个桶，找到最大数与最小数，
    // 计算出每个桶能装的数的范围，将数分别放入符合条件的桶中，
    // 对每个桶进行快速排序，最后合并
    public int[] bucketSort(int[] arr){
        // 设置桶的个数
        int bucket = 4;
        // 找到数组中的最大最小值
        int min = arr[0],max=arr[0];
        for(int i=0;i<arr.length;i++){
            if(arr[i]>max)max=arr[i];
            if(arr[i]<min)min=arr[i];
        }
        // 每个桶盛数的范围
        int range = (max-min)/bucket;
        int[][] newArr = new int[bucket][arr.length];
        for(int i =0;i<arr.length;i++){
            int temp = arr[i];
            if(temp >= min && temp < min+range){
                for(int k =0;k<newArr[0].length;k++){
                    if(newArr[0][k]==0){
                        newArr[0][k] = arr[i];
                        break;
                    }
                }
            }
            if(temp >= min+range && temp < min+2*range){
                for(int k =0;k<newArr[0].length;k++){
                    if(newArr[1][k]==0){
                        newArr[1][k] = arr[i];
                        break;
                    }
                }
            }
            if(temp >= min+2*range && temp < max - range){
                for(int k =0;k<newArr[0].length;k++){
                    if(newArr[2][k]==0){
                        newArr[2][k] = arr[i];
                        break;
                    }
                }
            }
            if(temp >= max - range && temp <= max){
                for(int k =0;k<newArr[0].length;k++){
                    if(newArr[3][k]==0){
                        newArr[3][k] = arr[i];
                        break;
                    }
                }
            }       
        }
        // 对每个桶进行排序
        for(int i=0;i<newArr.length;i++){
            quickSort(newArr[i],0,newArr[i].length-1);
        }
        // 重组数组
        return reGroup(newArr,arr.length);
    }
        
    
    // 交换位置
    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
```

### 翻转链表, NC78

```java
// 非递归
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

// 递归
ListNode reverse(ListNode head) { 
    if (head.next == null) return head; 
    ListNode last = reverse(head.next); 
    head.next.next = head; 
    head.next = null; 
    return last; 
}
```

### LFU缓存结构设计

```java
class LFUCache {
    Map<Integer, Node> cache;  // 存储缓存的内容
    Map<Integer, LinkedHashSet<Node>> freqMap; // 存储每个频次对应的双向链表
    int size;
    int capacity;
    int min; // 存储当前最小频次

    public LFUCache(int capacity) {
        cache = new HashMap<> (capacity);
        freqMap = new HashMap<>();
        this.capacity = capacity;
    }
    
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        freqInc(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        Node node = cache.get(key);
        if (node != null) {
            node.value = value;
            freqInc(node);
        } else {
            if (size == capacity) {
                Node deadNode = removeNode();
                cache.remove(deadNode.key);
                size--;
            }
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addNode(newNode);
            size++;     
        }
    }

    void freqInc(Node node) {
        // 从原freq对应的链表里移除, 并更新min
        int freq = node.freq;
        LinkedHashSet<Node> set = freqMap.get(freq);
        set.remove(node);
        if (freq == min && set.size() == 0) { 
            min = freq + 1;
        }
        // 加入新freq对应的链表
        node.freq++;
        LinkedHashSet<Node> newSet = freqMap.get(freq + 1);
        if (newSet == null) {
            newSet = new LinkedHashSet<>();
            freqMap.put(freq + 1, newSet);
        }
        newSet.add(node);
    }

    void addNode(Node node) {
        LinkedHashSet<Node> set = freqMap.get(1);
        if (set == null) {
            set = new LinkedHashSet<>();
            freqMap.put(1, set);
        } 
        set.add(node); 
        min = 1;
    }

    Node removeNode() {
        LinkedHashSet<Node> set = freqMap.get(min);
        Node deadNode = set.iterator().next();
        set.remove(deadNode);
        return deadNode;
    }
}

class Node {
    int key;
    int value;
    int freq = 1;

    public Node() {}
    
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}
```

### 设计LRU缓存结构, NC93

- lru-k算法：https://blog.csdn.net/love254443233/article/details/82598381

```java
import java.util.*;

public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        ArrayList<Integer> list = new ArrayList<Integer>();
        LRUCache cache = new LRUCache(k);
        for(int[] op : operators){
            if(op[0]==1){
                cache.put(op[1],op[2]);
            }else{
                int val = cache.get(op[1]);
                list.add(val);
            }
        }
        int[] ans = new int[list.size()];
        for(int i=0;i<list.size();i++){
            ans[i] = list.get(i);
        }
        return ans;
    }
}
 
class Node {
    public int key;
    public int value;
    Node pre,next;
     
    public Node(int key , int value){
        this.key = key;
        this.value = value;
    }
}
 
class LRUCache{
    public HashMap<Integer,Node> map;
    public LinkedList<Node> list;
    public int capacity;
     
    public LRUCache(int capacity){
        this.capacity = capacity;
        map = new HashMap<>();
        list = new LinkedList<>();
    }
     
    public int get(int key){
        if(!map.containsKey(key)){
            return -1;
        }
        Node temp = map.get(key);
        put(key,temp.value);
        return temp.value;
    }
            
    public void put(int key, int value){
        Node node = new Node(key,value);
        if(map.containsKey(key)){
            Node temp = map.get(key);
            list.remove(temp);
            list.addFirst(node);
            map.put(key,node);
        } else {
            if(map.size() == capacity){
                Node last = list.removeLast();
                map.remove(last.key);
            }
            list.addFirst(node);
            map.put(key,node);
        }
    }
     
}
```

```go
type LRUCache struct {
    capacity int
    m map[int]*Node
    head, tail *Node
}

type Node struct {
    Key int
    Value int
    Pre, Next *Node
}

func (this *LRUCache) Get(key int) int {
    if v, ok := this.m[key]; ok {
        this.moveToHead(v)
        return v.Value
    }
    return -1
}

func (this *LRUCache) moveToHead(node *Node) {
    this.deleteNode(node)
    this.addToHead(node)
}

func (this *LRUCache) deleteNode(node *Node) {
    node.Pre.Next = node.Next
    node.Next.Pre = node.Pre
}

func (this *LRUCache) removeTail() int {
    node := this.tail.Pre
    this.deleteNode(node)
    return node.Key
}

func (this *LRUCache) addToHead(node *Node) {
    this.head.Next.Pre = node
    node.Next = this.head.Next
    node.Pre = this.head
    this.head.Next = node
}

func (this *LRUCache) Put(key int, value int)  {
    if v, ok := this.m[key]; ok {
        v.Value = value
        this.moveToHead(v)
        return
    }

    if this.capacity == len(this.m) {
        rmKey := this.removeTail()
        delete(this.m, rmKey)
    }

    newNode := &Node{Key: key, Value: value}
    this.addToHead(newNode)
    this.m[key] = newNode
}

func Constructor(capacity int) LRUCache {
    head, tail := &Node{}, &Node{}
    head.Next = tail
    tail.Pre = head
    return LRUCache{
        capacity: capacity, 
        m: map[int]*Node{}, 
        head: head, 
        tail: tail,
    }
}
```

### 合并有序链表, NC33

```java
import java.util.*;
 
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
 
public class Solution {
    /**
     *
     * @param l1 ListNode类
     * @param l2 ListNode类
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0);
        ListNode res = node;
        while(l1 != null && l2 != null){
            if(l1.val > l2.val){
                node.next = l2;
                l2 = l2.next;
            } else {
                node.next = l1;
                l1 = l1.next;
            }
            node = node.next;
        }
         
        if(l1 != null){
            node.next = l1;
        }
         
        if(l2 != null){
            node.next = l2;
        }
         
        return res.next;
    }
}
```

### 链表中的节点每K个一组翻转

```java
//明显递归解决，翻转第一组之后，以第二组的开头为头节点，继续翻转，转翻到最后，返回。
public ListNode reverseKGroup(ListNode head, int k) {
    if(head==null||head.next==null)
        return head;
    ListNode h=new ListNode(0);
    h.next=head;
    ListNode next=null,tmp=head,cur=head;
    for(int i=1;i<k;i++){
        cur=cur.next;
        if(cur==null)
            return head;
    }
    next=cur.next;
    while(head.next!=next){
        tmp=head.next;
        head.next=tmp.next;
        tmp.next=h.next;
        h.next=tmp;
    }
    head.next=reverseKGroup(next,k);
    return h.next;
}
```

### 判断链表中是否有环

```java
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        ListNode p1 = head, p2 = head;
        while(p1.next != null && p1.next.next != null){
            p1 = p1.next.next;
            p2 = p2.next;
            if(p1 == p2){
                return true;
            }
        }
        return false;
    }
}
```

### 链表中环的入口结点

1、设置快慢指针，假如有环，他们最后一定相遇。
2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。

```java
public class Solution {

    ListNode EntryNodeOfLoop(ListNode pHead){
        if(pHead == null || pHead.next == null)
            return null;
        ListNode p1 = pHead;
        ListNode p2 = pHead;
        while(p2 != null && p2.next != null ){
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2){
                p2 = pHead;
                while(p1 != p2){
                    p1 = p1.next;
                    p2 = p2.next;
                }
                if(p1 == p2)
                    return p1;
            }
        }
        return null;
    }
}
```

### 删除链表的倒数第n个节点

```java
import java.util.*;
 
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
 
public class Solution {
    /**
     *
     * @param head ListNode类
     * @param n int整型
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode fast = dummyNode;
        ListNode slow = dummyNode;
        for(int i = 0; i <= n; i++){
            fast = fast.next;
        }
         
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
         
        slow.next = slow.next.next;
         
        return dummyNode.next;
    }
}
```

### 两个链表的第一个公共结点

```java
/*
public class ListNode {
    int val;
    ListNode next = null;
 
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null){
            return null;
        }
         
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
         
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
            if(p1 != p2){
                if(p1 == null) p1 = pHead2;
                if(p2 == null) p2 = pHead1;
            }
        }
         
        return p1;
          
    }
}
```

### 两个链表生成相加链表

```java
import java.util.*;
 
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
 
public class Solution {
    /**
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1==null) return head2;
        if(head2==null) return head1;
        ListNode l1=reverse(head1);
        ListNode l2=reverse(head2);
        ListNode result=new ListNode(0);
        int c=0;
        while(l1!=null||l2!=null||c!=0)
        {
            int v1=l1!=null?l1.val:0;
            int v2=l2!=null?l2.val:0;
            int val=v1+v2+c;
            c=val/10;
            ListNode cur=new ListNode(val%10);
            cur.next=result.next;
            result.next=cur;
            if(l1!=null)
                l1=l1.next;
            if(l2!=null)
                l2=l2.next;
        }
        return result.next; 
    }
     
    public ListNode reverse(ListNode node)
    {
        if(node==null) return node;
        ListNode pre=null,next=null;
        while(node!=null)
        {
            next=node.next;
            node.next=pre;
            pre=node;
            node=next;
        }
        return pre;
    }
}
```

### 合并k个已排序的链表

```java
import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists == null || lists.size() == 0){
            return null;
        }
         
        return mergeList(lists,0,lists.size()-1);
    }
     
    public ListNode mergeList(ArrayList<ListNode> lists, int low, int high){
        if(low >= high){
            return lists.get(low);
        }
         
        int mid = low + (high - low)/2;
        ListNode left = mergeList(lists,low,mid);
        ListNode right = mergeList(lists,mid+1,high);
        return merge(left,right);
    }
     
    public ListNode merge(ListNode left, ListNode right){
        ListNode h = new ListNode(-1);
        ListNode tmp = h;
        while(left != null && right != null){
            if(left.val < right.val){
                tmp.next = left;
                left = left.next;
            } else {
                tmp.next = right;
                right = right.next;
            }
            tmp = tmp.next;
        }
         
        if(left != null){
            tmp.next = left;
        }
         
        if(right != null){
            tmp.next = right;
        }
         
        return h.next;
    }
}
```

### 单链表的排序，NC70

- 堆排序

```java
import java.util.*;

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        PriorityQueue<ListNode> heap = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);
        while (head != null) {
            heap.add(head);
            head = head.next;
        }
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (!heap.isEmpty()) {
            cur.next = heap.poll();
            cur = cur.next;
        }
        cur.next = null;
        return dummy.next;
    }
}
```

- 归并排序

```java
import java.util.*;
public class Solution {
    //合并两段有序链表
    ListNode merge(ListNode pHead1, ListNode pHead2) { 
        //一个已经为空了，直接返回另一个
        if(pHead1 == null) 
            return pHead2;
        if(pHead2 == null)
            return pHead1;
        //加一个表头
        ListNode head = new ListNode(0); 
        ListNode cur = head;
        //两个链表都要不为空
        while(pHead1 != null && pHead2 != null){ 
            //取较小值的节点
            if(pHead1.val <= pHead2.val){ 
                cur.next = pHead1;
                //只移动取值的指针
                pHead1 = pHead1.next; 
            }else{
                cur.next = pHead2;
                //只移动取值的指针
                pHead2 = pHead2.next; 
            }
            //指针后移
            cur = cur.next; 
        }
        //哪个链表还有剩，直接连在后面
        if(pHead1 != null) 
            cur.next = pHead1;
        else
            cur.next = pHead2;
        //返回值去掉表头
        return head.next; 
    }
    
    public ListNode sortInList (ListNode head) {
        //链表为空或者只有一个元素，直接就是有序的
        if(head == null || head.next == null) 
            return head;
        ListNode left = head; 
        ListNode mid = head.next;
        ListNode right = head.next.next;
        //右边的指针到达末尾时，中间的指针指向该段链表的中间
        while(right != null && right.next != null){ 
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }
        //左边指针指向左段的左右一个节点，从这里断开
        left.next = null; 
        //分成两段排序，合并排好序的两段
        return merge(sortInList(head), sortInList(mid)); 
    }
}
```

### 判断链表是否为回文结构

```java
import java.util.*;

public class Solution {
    /**
     *
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        
        Stack<Integer> stack = new Stack<>();
        while(slow != null){
            stack.add(slow.val);
            slow = slow.next;
        }
        
        while(!stack.isEmpty()){
            if(stack.pop() != head.val){
                return false;
            }
            
            head = head.next;
        }
        
        return true;
    }
}
```

### 链表内指定区间反转

```java
public class Solution {
    /**
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        if(head == null || n == m){
            return head;
        }
         
        ListNode dummy = new ListNode(0);
        dummy.next = head;
         
        ListNode cur = dummy;
        for(int i = 1; i < m; i++){
            cur = cur.next;
        }
         
        // t1代表头，t2代表尾
        ListNode t1 = cur;
        ListNode t2 = cur.next;
        cur = t2;
         
        ListNode pre = null;
        // 翻转链表
        for(int i = 0; i <= n - m; i++){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
         
        t1.next = pre;
        t2.next = cur;
         
        return dummy.next;
    }
}
```

### 删除有序链表中重复出现的元素

```java
public ListNode deleteDuplicates (ListNode head) {
    ListNode dummy=new ListNode(0);
    dummy.next=head;
    ListNode pre=dummy;
    ListNode p=head;
    while(p!=null&&p.next!=null){
        if(p.val==p.next.val){
            while(p.next!=null&&p.val==p.next.val){
                p=p.next;                   
            }
            pre.next=p.next;
            p=p.next;
        }           
        else{
            pre=p;
            p=p.next;              
        }       
    }
    return dummy.next;
}
```

### 环形链表的约瑟夫问题

```java
public int ysf (int n, int m) {
    // write code here
    ListNode head = new ListNode(1) ,p1=head;
    for(int i=2;i<=n;i++){
        ListNode temp = new ListNode(i);
        p1.next=temp;
        p1=p1.next;
    }
    p1.next=head;
    while(n-->1){
        int num=m;
        while(num-->1){
            p1=p1.next;
        }
        p1.next=p1.next.next;
    }
    return p1.val;
}
```

### 链表的奇偶重排

```java
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;
        /*
          odd 指向奇数节点的指针
          oddHead 指向初始奇数节点的头指针
          even 指向偶数节点的指针
          evenHead 指向初始偶数节点的头指针
         */
        ListNode odd = head, oddHead = head, even = head.next, evenHead = head.next;

        while (even != null && even.next != null) {
            // 奇数节点指向偶数节点的 next
            odd.next = even.next;
            // 奇数节点指针后移
            odd = odd.next;
            // 偶数节点指向奇数节点的 next
            even.next = odd.next;
            // 偶数节点指针后移
            even = even.next;
        }
        // 将奇数节点的 next 指向 偶数节点的初始头指针
        odd.next = evenHead;
        // 返回奇数节点的初始头指针
        return oddHead;
    }
}
```

### 重排链表（1->n->2->n-1）

```java
import java.util.*;
public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        List<ListNode> list = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            list.add(cur);
            cur = cur.next;
        }
        int l = 0, r = list.size() - 1;
        while (l < r) {
            list.get(l).next = list.get(r);
            l++;
            list.get(r).next = list.get(l);
            r--;
        }
        list.get(l).next = null;
    }
}
```

### 二叉搜索树与双向链表

```java
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}
*/
public class Solution {
    public TreeNode head = null;
    public TreeNode dummy = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        ConvertSub(pRootOfTree);
        return dummy;
    }
    
    public void ConvertSub(TreeNode root){
        if(root == null) return;
        ConvertSub(root.left);
        
        if(head == null){
            head = root;
            dummy = root;
        } else {
            head.right = root;
            root.left = head;
            head = root;
        }
 
        ConvertSub(root.right);
    }
}
```

## 队列、栈

### 用两个栈实现队列

```java
import java.util.Stack;
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.add(node);
    }
     
    public void pushToPop(){
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.add(stack1.pop());
            }
        }
    }
     
    public int pop() {
        pushToPop();
        return stack2.pop();
    }
}
```

### 有效括号序列

```java
import java.util.*;
public class Solution {
   
    public boolean isValid (String s) {
        // write code here
        Stack<Character> stack = new Stack<>();
        char[] chs = s.toCharArray();
        for(int i = 0; i < chs.length; i++){
            if(stack.isEmpty()){
                stack.push(chs[i]);
            } else if(chs[i] == '{' || chs[i] == '[' 
                || chs[i] == '('){
                stack.push(chs[i]);
            } else if((chs[i] == '}' && stack.peek() == '{') || 
                      (chs[i] == ']' && stack.peek() == '[') ||
                      (chs[i] == ')' && stack.peek() == '(')){
                stack.pop();
            }
        }
        
        return stack.isEmpty() ? true : false;
    }
}
```

### 包含 min 函数的栈

```java
import java.util.Stack;

public class Solution {
    Stack<Integer> minStack = new Stack<>();
    Stack<Integer> stack = new Stack<>();
    
    public void push(int node) {
        if(minStack.isEmpty()){
            minStack.push(node);
        }
        
        if(node < minStack.peek().intValue()){
            minStack.push(node);
        } else {
            minStack.push(minStack.peek());
        }
        
        stack.push(node);
    }
    
    public void pop() {
        if(stack.isEmpty()){
            return;
        }
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return minStack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}
```

### 表达式求值

step 1：使用栈辅助处理优先级，默认符号为加号。
step 2：遍历字符串，遇到数字，则将连续的数字字符部分转化为int型数字。
step 3：遇到左括号，则将括号后的部分送入递归，处理子问题；
遇到右括号代表已经到了这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。
step 4：当遇到符号的时候如果是+，得到的数字正常入栈，如果是-，则将其相反数入栈，
如果是*，则将栈中内容弹出与后一个元素相乘再入栈。
step 5：最后将栈中剩余的所有元素，进行一次全部相加。


```java
import java.util.*;
public class Solution {
    public ArrayList<Integer> function(String s, int index){
        Stack<Integer> stack = new Stack<Integer>(); 
        int num = 0;
        char op = '+';
        int i;
        for(i = index; i < s.length(); i++){
            //数字转换成int数字
            //判断是否为数字
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){ 
                num = num * 10 + s.charAt(i) - '0';
                if(i != s.length() - 1)
                    continue;
            }
            //碰到'('时，把整个括号内的当成一个数字处理
            if(s.charAt(i) == '('){
                //递归处理括号
                ArrayList<Integer> res = function(s, i + 1);
                num = res.get(0);
                i = res.get(1);
                if(i != s.length() - 1)
                    continue;
            }            
            switch(op){
            //加减号先入栈
            case '+': 
                stack.push(num);
                break;
            case '-':
                //相反数
                stack.push(-num);
                break;
            //优先计算乘号
            case '*':  
                int temp = stack.pop();
                stack.push(temp * num);
                break;
            }
            num = 0;
            //右括号结束递归
            if(s.charAt(i) == ')') 
                break; 
            else 
                op = s.charAt(i);
        }
        int sum = 0;
        //栈中元素相加
        while(!stack.isEmpty())  
            sum += stack.pop();
        ArrayList<Integer> temp = new ArrayList<Integer>();
        temp.add(sum);
        temp.add(i);
        return temp; 
    }
    public int solve (String s) {
        ArrayList<Integer> res = function(s, 0);
        return res.get(0);
    }
}
```

### 最长括号子串

step 1：可以使用栈来记录左括号下标。
step 2：遍历字符串，左括号入栈，每次遇到右括号则弹出左括号的下标。
step 3：然后长度则更新为当前下标与栈顶下标的距离。
step 4：遇到不符合的括号，可能会使栈为空，因此需要使用start记录上一次结束的位置，
这样用当前下标减去start即可获取长度，即得到子串。
step 5：循环中最后维护子串长度最大值。

```java
import java.util.*;
public class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int[] dp = new int[s.length()];
        int ans = 0;
        for (int i = 1; i < s.length(); i++) {
            // 如果是'('直接跳过，默认为0
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(')
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                // 说明s.charAt(i - 1)==')'
                else if (i - dp[i - 1] > 0 
                    && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = (i - dp[i - 1] > 1 
                    ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
                    // 因为加了一个左括号和一个右括号，所以是加2
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
```

```java
import java.util.*;
public class Solution {
    public int longestValidParentheses (String s) {
        int res = 0;
        //记录上一次连续括号结束的位置
        int start = -1; 
        Stack<Integer> st = new Stack<Integer>();
        for(int i = 0; i < s.length(); i++){
            //左括号入栈
            if(s.charAt(i) == '(') 
                st.push(i);
            //右括号
            else{ 
                //如果右括号时栈为空，不合法，设置为结束位置
                if(st.isEmpty()) 
                    start = i;
                else{
                    //弹出左括号
                    st.pop(); 
                    //栈中还有左括号，说明右括号不够，减去栈顶位置就是长度
                    if(!st.empty()) 
                        res = Math.max(res, i - st.peek());
                    //栈中没有括号，说明左右括号行号，减去上一次结束的位置就是长度
                    else 
                        res = Math.max(res, i - start);
                }
            }
        }
        return res;
    }
}
```

### 括号生成

对于括号的题，核心基本都是:
"一个字符串是合法的括号组合"的*充分必要*条件是:

1. 字符串中开口数等于闭口数 (这是废话)
2. 字符串的所有prefix都满足: 开口数>=闭口数
举个栗子，比如 "()(())":
prefix: "(", "()", "()(", "()((", "()(()", "()(())".

那么对与这道题，为满足1,2, 每一个位置可以有的permutation就是:

1. 如果有多余的开口 -> 可以选开口
2. 如果有多余未闭合的开口 -> 可以选闭口

剩下的就是正常的递归+回溯了
时间: O(2^n), 每一位最多2个permutation
空间: O(n), 栈高是n

```java
import java.util.*;

public class Solution {
    ArrayList<String> ans = new ArrayList<>();
    
    public ArrayList<String> generateParenthesis (int n) {
      permute(n, n, 0, new StringBuilder());
      return ans;
    }
  
    void permute(int open, int close, int unclosedOpen, StringBuilder sb) {
      // base case，开口闭口都用完了
      if (open == 0 && close == 0) {
        ans.add(sb.toString());
        return;
      }
      
      // always ok to pick an open bracket if there are any open-bracket
      if (open > 0) {
        sb.append("(");
        permute(open-1, close, unclosedOpen+1, sb);
        sb.deleteCharAt(sb.length()-1);
      }
      // can pick close bracket if there is any unclosed open-bracket
      if (unclosedOpen > 0) {
        sb.append(")");
        permute(open, close-1, unclosedOpen-1, sb);
        sb.deleteCharAt(sb.length()-1);
      }
    }
}
```

## 二叉树

### 实现二叉树先序，中序和后序遍历

```java
import java.util.*;
 
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
 
public class Solution {
    /**
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {
        // write code here
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        ArrayList<Integer> list3 = new ArrayList<>();
        front(root,list1,list2,list3);
        int[][] ints = new int[3][list1.size()];
        for (int i = 0; i < list1.size(); i++) {
            ints[0][i] = list1.get(i);
            ints[1][i] = list2.get(i);
            ints[2][i] = list3.get(i);
        }
        return ints;
    }
     
    public void front(TreeNode root,ArrayList<Integer> list1,
            ArrayList<Integer> list2,ArrayList<Integer> list3){
        if(root == null){
            return;
        }
         
        list1.add(root.val);
        front(root.left,list1,list2,list3);
        list2.add(root.val);
        front(root.right,list1,list2,list3);
        list3.add(root.val);
    }
}
```

- 非递归遍历

- 前序遍历

用栈来保存信息，但是遍历的时候，是：**先输出根节点信息，然后压入右节点信息，然后再压入左节点信息。**

```java
public void pre(Node head){
    if(head == null){
        return;
    }
    Stack<Integer> stack = new Stack<>();
    stack.push(head);
    while(!stack.isEmpty()){
        head = stack.poll();
        System.out.println(head.value + " ");
        if(head.right != null){
            stack.push(head.right);
        }
        if(head.left != null){
            stack.push(head.left);
        }
    }
    System.out.println();
}
```

- 中序遍历

中序遍历的顺序是**左中右**，先一直左节点遍历，并压入栈中，当做节点为空时，输出当前节点，往右节点遍历。

```java
public void inorder(Node head){
    if(head == null){
        return;
    }
    Stack<Integer> stack = new Stack<>();
    stack.push(head);
    while(!stack.isEmpty() || head != null){
        if(head != null){
            stack.push(head);
            head = head.left
        } else {
            head = stack.poll();
            System.out.println(head.value + " ");
            head = head.right;
        }
    }
    System.out.println();
}
```

- 后序遍历

用两个栈来实现，压入栈1的时候为**先左后右**，栈1弹出来就是**中右左**，栈2收集起来就是**左右中**。

```java
// 后序遍历-迭代
public void postIteOrders(TreeNode root, List<Integer> postList) {
    if (root == null) {
        return;
    }
    // 用两个栈来实现
    // 通过 stack1 和 stack2 来配合可以实现 左 - 右 - 中的顺序
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);
        // 先入左节点
        if (node.left != null) {
            stack1.push(node.left);
        }
        // 在入右节点
        if (node.right != null) {
            stack1.push(node.right);
        }

    }
    // 弹出元素
    while (!stack2.isEmpty()) {
        postList.add(stack2.pop().val);
    }
}
```

### 二叉树的层序遍历

```java
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
    // write code here
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    // 队列，用于存储元素
    Queue<TreeNode> queue = new LinkedList<>();
    // 根节点先入队
    queue.offer(root);
    // 当队列不为空的时候
    while(!queue.isEmpty()) {
        // 队列的大小就是这一层的元素数量
        int size = queue.size();
        ArrayList<Integer> list = new ArrayList<>();
        // 开始遍历这一层的所有元素
        for (int i = 0; i < size; i ++) {
            TreeNode node = queue.poll();
            // 如果左节点不为空，则入队，作为下一层来遍历
            if(node.left != null) {
                queue.offer(node.left);
            }
            // 同上
            if (node.right != null) {
                queue.offer(node.right);
            }
            // 存储一层的节点
            list.add(node.val);
        }
        // 将一层所有的节点汇入到总的结果集中
        result.add(list);
    }
    return result;
}
```

### 二叉树的之字形层序遍历

```java
import java.util.Queue;
import java.util.LinkedList;
 
public class Solution {
 
    public ArrayList<ArrayList<Integer>> Print(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean leftToRight = true;
        while (!queue.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<>();
            //统计这一行有多少个节点
            int count = queue.size();
            //遍历这一行的所有节点
            for (int i = 0; i < count; i++) {
                //poll移除队列头部元素（队列在头部移除，尾部添加）
                TreeNode node = queue.poll();
                //判断是从左往右打印还是从右往左打印。
                if (leftToRight) {
                    level.add(node.val);
                } else {
                    level.add(0, node.val);
                }
                //左右子节点如果不为空会被加入到队列中
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            res.add(level);
            leftToRight = !leftToRight;
        }
        return res;
    }
}
```

### 在二叉树中找到两个节点的最近公共祖先

```java
import java.util.*;

public class Solution {
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // root为空则说明越过了叶子节点
        if(root == null) return -1;
        // 如果root为o1或o2中任意一个，则root就是公共祖先
        if(root.val == o1 || root.val == o2) return root.val;

        //root不为o1或o2
        int left = lowestCommonAncestor(root.left, o1, o2);
        int right = lowestCommonAncestor(root.right, o1, o2);
        //如果left=-1，说明在左子树中一直找到叶子节点，也没找到最近公共祖先
        //所以最近公共祖先，必在右子树中，right即为最近公共祖先
        if(left == -1) return right;
        //同理，最近公共祖先必在左子树中，left即为最近公共祖先
        else if(right == -1) return left;
        //若left和right都不为-1，则说明o1,o2节点在root的异侧，则root为最近公共祖先
        else return root.val;
    }
}
```

### 重建二叉树

```java

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
       if(pre.length == 0||in.length == 0){
            return null;
        }
        TreeNode node = new TreeNode(pre[0]);
        for(int i = 0; i < in.length; i++){
            if(pre[0] == in[i]){
                node.left = reConstructBinaryTree(
                Arrays.copyOfRange(pre, 1, i+1), 
                Arrays.copyOfRange(in, 0, i));
                node.right = reConstructBinaryTree(
                Arrays.copyOfRange(pre, i+1, pre.length), 
                Arrays.copyOfRange(in, i+1,in.length));
            }
        }
        return node;
    }
}
```

```java
public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
    TreeNode root = rebuild(pre, 0, pre.length - 1, 
        in, 0, in.length - 1);
    return root;
}

public TreeNode rebuild(int[] preorder, int preStart, 
    int preEnd, int[] inorder, int inStart, int inEnd) {
    if (preStart < 0 || inStart < 0 || 
        preStart > preEnd || inStart > inEnd) {
        return null;
    }
    TreeNode root = new TreeNode(preorder[preStart]);
    
    int index = 0;
    for (int i = 0; i < inorder.length; i++) {
        if (inorder[i] == root.val) {
            index = i;
            break;
        }
    }
    int leftLen = index - inStart;
    int rightLen = inEnd - index;
    root.left = rebuild(preorder, preStart + 1, 
        leftLen + preStart, inorder, inStart, index - 1);
    root.right = rebuild(preorder, leftLen + preStart + 1, 
        preEnd, inorder, index + 1, inEnd);
    return root;
}
```

### 输出二叉树的右视图（先重建，再输出右视图）

```java
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] preorder, int[] inorder) {
        // write code here
        if (preorder == null || preorder.length < 1 
            || inorder == null || inorder.length < 1) {
            return new int[0];
        }
        TreeNode root = rebuild(preorder, 0, preorder.length - 1, 
            inorder, 0, inorder.length - 1);
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode cur = root;
        queue.offer(cur);
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            list.add(queue.peekLast().val);
            for (int i = 0; i < size; i++) {
                cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    
    public TreeNode rebuild(int[] preorder, int preStart, 
        int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart < 0 || inStart < 0 || 
            preStart > preEnd || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        
        int index = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root.val) {
                index = i;
                break;
            }
        }
        int leftLen = index - inStart;
        int rightLen = inEnd - index;
        root.left = rebuild(preorder, preStart + 1, 
            leftLen + preStart, inorder, inStart, index - 1);
        root.right = rebuild(preorder, leftLen + preStart + 1, 
            preEnd, inorder, index + 1, inEnd);
        return root;
    }
    
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        
        public TreeNode(int val) {
            this.val = val;
        }
    }
}
```

### 二叉树的最大深度

```java
public int maxDepth(TreeNode root) {
    return root==null? 0 : 
    Math.max(maxDepth(root.left), maxDepth(root.right))+1;
}
```

### 判断是不是平衡二叉树

```java
import java.util.*;
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        //可以分别求出左右子树的高度，然后进行对比
        return TreeDepth(root) >= 0;
    }
    //求二叉树深度的方法
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = TreeDepth(root.left);
        int rightHeight = TreeDepth(root.right);
        if (leftHeight == -1 || rightHeight == -1 
            || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}
```

### 二叉树根节点到叶子节点的所有路径和

```java
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int sumNumbers (TreeNode root) {
        // 调用dfs
        return dfs(root,0);
    }
    //深度优先搜索
    public int dfs(TreeNode root,int sum){
        if(root==null){
            return 0;
        }
        int total = sum*10+root.val;
        //已达到叶子节点，返回结果
        if(root.left==null && root.right==null){
            return total;
        }else{
            //递归调用
             return dfs(root.left,total)+dfs(root.right,total);
        }

    }
}
```

### 二叉树中和为某一值的路径，返回所有路径

```java
import java.util.ArrayList;
public class Solution {
    ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null){
            return lists;
        }
        list.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null 
            && root.right == null){
            lists.add(new ArrayList<Integer>(list));
        }
        FindPath(root.left,target);
        FindPath(root.right,target);
        list.remove(list.size() - 1);
        return lists;
    }
}
```

### 判断一棵二叉树是否为搜索二叉树和完全二叉树

```java
int num=-1;
boolean flag = false;
public boolean[] judgeIt (TreeNode root) {
    // write code here
    return new boolean[]{isSearch(root) ,isFull(root)};
}

public boolean isSearch(TreeNode root){
    if(root==null){
        return true;
    }
    boolean left = isSearch(root.left);
    if(num>=root.val){
        return false;
    }
    num=root.val;
    boolean right = isSearch(root.right);
    return left && right;
}

public boolean isFull(TreeNode root){
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()){
        TreeNode node = queue.poll();
        if(node==null){
            flag=true;
        }else{
            if(flag){
                return false;
            }else{
                queue.add(node.left);
                queue.add(node.right);
            }
        }
    }
    return true;
}
```

### 二叉树的最大路径和

```java
public class Solution {
    int max = Integer.MIN_VALUE;
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxPathSum (TreeNode root) {
        // write code here
        maxSum(root);
        return max;
    }
    
    public int maxSum(TreeNode root){
        if(root == null){
            return 0;
        }
        
        //三种情况：1.包含一个子树和顶点，2.仅包含顶点，3.包含左子树和右子树以及顶点。
        int left = Math.max(maxSum(root.left),0);
        int right = Math.max(maxSum(root.right),0);
        
        max = Math.max(max,left+right+root.val);
        
        //对于每一个子树，返回包含该子树顶点的深度方向的路径和的最大值。
        return root.val + Math.max(left,right);
    }
}
```

### 判断二叉树是否对称

```java
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isSymmetric (TreeNode root) {
        // write code here
        return isSymmetricNode(root,root);
    }
    
    public boolean isSymmetricNode(TreeNode node1, TreeNode node2){
        if(node1 == null && node2 == null){
            return true;
        }
        if(node1 == null || node2 == null){
            return false;
        }
        if(node1.val != node2.val){
            return false;
        }
        return isSymmetricNode(node1.left,node2.right)
            && isSymmetricNode(node1.right,node2.left);
    }
}
```

### 二叉树中是否存在节点和为指定值的路径

```java
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root == null){
            return false;
        }
        
        if(root.left == null && root.right == null){
            return sum - root.val == 0;
        }
        
        return hasPathSum(root.left,sum - root.val) || 
                hasPathSum(root.right,sum - root.val);
    }
}
```

### 序列化二叉树

```java
import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
   private int index = -1;

    public String Serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        intervalSerialize(builder, root);
        return builder.toString();
    }

    private void intervalSerialize(StringBuilder builder, TreeNode root) {
        if (root == null) {
            builder.append("#,");
            return;
        }
        builder.append(root.val).append(",");
        intervalSerialize(builder, root.left);
        intervalSerialize(builder, root.right);
    }

    public TreeNode Deserialize(String str) {
        if (str == null || str.isEmpty()) {
            return null;
        }
        String[] words = str.split(",");
        return internalDeserialize(words);
    }

    private TreeNode internalDeserialize(String[] words) {
        index++;
        if (index == words.length) {
            return null;
        }
        if ("#".equals(words[index])) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(words[index]));
        root.left = internalDeserialize(words);
        root.right = internalDeserialize(words);
        return root;
    }
}
```

### 二叉搜索树的第k个结点

```java
public class Solution {
    int index = 0;
    TreeNode target = null;
    TreeNode KthNode(TreeNode pRoot, int k){
        getKthNode(pRoot,k);
        return target;
    }
    
    public void getKthNode(TreeNode pRoot, int k){
        if(pRoot == null){
            return;
        }
        getKthNode(pRoot.left,k);
        index++;
        if(index == k){
            target = pRoot;
            return;
        }
        getKthNode(pRoot.right,k);
    }
}
```

### 把二叉树打印成多行

```java
import java.util.*;
 
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        if(pRoot == null){
            return new ArrayList<ArrayList<Integer>>();
        }
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
         
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        while(!queue.isEmpty()){
            ArrayList<Integer> temp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--){
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            list.add(temp);
        }
         
        return list;
    }
     
}
```

### 二叉树的镜像

```java
public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
             
            if(node.left != null || node.right != null){
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
            }
             
            if(node.left != null){
                stack.push(node.left);
            }
             
            if(node.right != null){
                stack.push(node.right);
            }
        }
    }
}
 
/*
public class Solution {
    public void Mirror(TreeNode root) {
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            return;
        }
         
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
         
        if(root.left != null){
            Mirror(root.left);
        }
         
        if(root.right != null){
            Mirror(root.right);
        }
    }
}
*/

```

### 判断t1树中是否有与t2树拓扑结构完全相同的子树

```java
/**
    * 
    * @param root1 TreeNode类 
    * @param root2 TreeNode类 
    * @return bool布尔型
    */
public boolean isContains (TreeNode root1, TreeNode root2) {
    // write code here
    if(root1 == null || root2 == null){
        return false;
    }
    return recur(root1, root2) || isContains(root1.left,root2) 
                                || isContains(root1.right,root2);
}

public boolean recur(TreeNode root1, TreeNode root2){
    if(root2 == null){
        return true;
    }
    if(root1 == null || root1.val != root2.val){
        return false;
    }
    return recur(root1.left,root2.left) && 
                    recur(root1.right,root2.right);
}
```

### 合并二叉树

```java
import java.util.*;

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if(t1==null) return t2;
        if(t2==null) return t1;
        TreeNode temp=new TreeNode(t1.val+t2.val);
        temp.left=mergeTrees(t1.left,t2.left);
        temp.right=mergeTrees(t1.right,t2.right);
        return temp;
    }
}
```

### 字典树的实现

![](http://image.ouyangsihai.cn/Fm_RgyVyr-Q8xgXGWHyrkrfRBukX)

```java
import java.util.*;

public class Solution {
    /**
     * 
     * @param operators string字符串二维数组 the ops
     * @return string字符串一维数组
     */
    public String[] trieU (String[][] operators) {
        //计算结果集长度，并进行初始化
        int len=0;
        for(String[] opera:operators){
            if(opera[0].equals("3")||opera[0].equals("4")){
                len++;
            }
        }
        String[] res=new String[len];
        Trie trie=new Trie();
        int id=0;

        for(String[] opera:operators){
            if(opera[0].equals("1")){
                //添加单词
                trie.insert(opera[1]);
            }
            else if(opera[0].equals("2")){
                //删除单词
                trie.delete(opera[1]);
            }
            else if(opera[0].equals("3")){
                //查询单词是否存在
                res[id++]=trie.search(opera[1])?"YES":"NO";
            }
            else if(opera[0].equals("4")){
                //查找以word为前缀的单词数量
                String preNumber=String.valueOf(trie.prefixNumber(opera[1]));
                res[id++]=preNumber;
            }
        }
        return res;
    }

    class Trie{
        //构建字典树节点
        class TrieNode{
            //child数组记录所有子节点
            TrieNode[] child;
            //pre_number表示插入单词时，当前节点被访问次数
            int pre_number;
            //end表示当前节点是否是某个单词的末尾
            boolean end;
            TrieNode(){
                child=new TrieNode[26];
                pre_number=0;
                end=false;
            }
        }

        Trie(){}

        //初始化根节点
        TrieNode root=new TrieNode();

        //添加单词
        void insert(String word){
            TrieNode node=root;
            char[] arr=word.toCharArray();
            for(char c:arr){
                //如果子节点不存在，则新建
                if(node.child[c-'a']==null){
                    node.child[c-'a']=new TrieNode();
                }
                //往子节点方向移动
                node=node.child[c-'a'];
                node.pre_number++;
            }
            node.end=true;
        }

        void delete(String word){
            TrieNode node=root;
            char[] arr=word.toCharArray();
            for(char c:arr){
                //往子节点方向移动，将访问次数减一
                node=node.child[c-'a'];
                node.pre_number--;
            }
            //如果访问次数为0，说明不存在该单词为前缀的单词，以及该单词
            if(node.pre_number==0){
                node.end=false;
            }
        }

        boolean search(String word){
            TrieNode node=root;
            char[] arr=word.toCharArray();
            for(char c:arr){
                //如果子节点不存在，说明不存在该单词
                if(node.child[c-'a']==null){
                    return false;
                }
                node=node.child[c-'a'];
            }

            //如果前面的节点都存在，并且该节点末尾标识为true，则存在该单词
            return node.end;
        }

        int prefixNumber(String pre){
            TrieNode node=root;
            char[] arr=pre.toCharArray();
            for(char c:arr){
                //如果子节点不存在，说明不存在该前缀
                if(node.child[c-'a']==null){
                    return 0;
                }
                node=node.child[c-'a'];
            }

            //返回以该单词为前缀的数量
            return node.pre_number;
        }
    }
}
```

### 找到二叉搜索树中的两个错误节点

![](http://image.ouyangsihai.cn/FgMj1e8uJv5aZqSy__ZFJ2aN4cCZ)

```java
import java.util.*;
public class Solution {
    /**
     * 
     * @param root TreeNode类 the root
     * @return int整型一维数组
     */

      //存储结果集的二维数组
    int[] result = new int[2];
    int index = 1;
    TreeNode preNode;
    public int[] findError (TreeNode root) {
        // 特判
        if(root == null) {
            return result;
        }
        // 递归左子树，寻找该树符合条件的节点
        findError(root.left);
        if(preNode == null) {
            preNode = root;
        }
        // 判断是否是出错的节点
        if(index == 1 && root.val < preNode.val) {
            result[index] = preNode.val;
            index--;
        }
        if(index == 0 && root.val < preNode.val) {
            result[index] = root.val;
        }
        preNode = root;
        // 递归右子树，寻找该树符合条件的节点
        findError(root.right);
        return result;
    }
}
```

## 堆

### 最小的K个数

```java
import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //排除特殊情况
        if(k == 0 || input.length == 0) 
            return res;
        //大根堆 
        PriorityQueue<Integer> q = 
            new PriorityQueue<>((o1, o2)->o2.compareTo(o1));
        //构建一个k个大小的堆  
        for(int i = 0; i < k; i++)
            q.offer(input[i]);
        for(int i = k; i < input.length; i++){
            //较小元素入堆
            if(q.peek() > input[i]){  
                q.poll();
                q.offer(input[i]);
            }
        }
        //堆中元素取出入数组
        for(int i = 0; i < k; i++) 
            res.add(q.poll());
        return res;
    }
}

// 自己实现堆排序
public class Solution {
    public ArrayList<Integer> 
        GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input == null || input.length == 0 
            || k > input.length || k == 0)
            return list;
        int[] arr = new int[k + 1];//数组下标0的位置作为哨兵，不存储数据
        //初始化数组
        for (int i = 1; i < k + 1; i++)
            arr[i] = input[i - 1];
        buildMaxHeap(arr, k + 1);//构造大根堆
        for (int i = k; i < input.length; i++) {
            if (input[i] < arr[1]) {
                arr[1] = input[i];
                adjustDown(arr, 1, k + 1);//将改变了根节点的二叉树继续调整为大根堆
            }
        }
        for (int i = 1; i < arr.length; i++) {
            list.add(arr[i]);
        }
        return list;
    }
     /**
     * @Author: ZwZ
     * @Description: 构造大根堆 
     * @Param: [arr, length]  length:数组长度 作为是否跳出循环的条件
     * @return: void 
     * @Date: 2020/1/30-22:06
     */
    public void buildMaxHeap(int[] arr, int length) {
        if (arr == null || arr.length == 0 || arr.length == 1)
            return;
        for (int i = (length - 1) / 2; i > 0; i--) {
            adjustDown(arr, i, arr.length);
        }
    }
    /**
     * @Author: ZwZ
     * @Description: 堆排序中对一个子二叉树进行堆排序 
     * @Param: [arr, k, length] 
     * @return:  
     * @Date: 2020/1/30-21:55
     */
    public void adjustDown(int[] arr, int k, int length) {
        arr[0] = arr[k];//哨兵
        for (int i = 2 * k; i <= length; i *= 2) {
            if (i < length - 1 && arr[i] < arr[i + 1])
                i++;//取k较大的子结点的下标
            if (i > length - 1 || arr[0] >= arr[i])
                break;
            else {
                arr[k] = arr[i];
                k = i; //向下筛选
            }
        }
        arr[k] = arr[0];
    }
}
```

### 字符串出现次数的TopK问题

```java
public class Solution {
    public String[][] topKstrings (String[] strings, int k) {
        String[][] res = new String[k][2];
        //记录字符出现次数
        HashMap<String,Integer> map = new HashMap<>();
        for(int i = 0; i < strings.length; i++){
            if(map.containsKey(strings[i])){
                map.put(strings[i], map.get(strings[i]) + 1);
            }else{
                map.put(strings[i], 1);
            }
        }
        //建立小根堆，自定义比较器(次数值value相同，
        // 比较key的字典序，不相同直接比较次数值value)
        PriorityQueue<Map.Entry<String,Integer>> pq = 
            new PriorityQueue<>((o1,o2) -> o1.getValue().equals(o2.getValue()) 
            ? o2.getKey().compareTo(o1.getKey()) : o1.getValue()-o2.getValue());
        int size = 0;
        //维护size为k的小根堆
        for(Map.Entry<String,Integer> m : map.entrySet()){
            if(size < k){
                pq.offer(m);
                size++;
            }
            //大于堆顶元素插入
            else if((m.getValue().equals(pq.peek().getValue()) 
                ? pq.peek().getKey().compareTo(m.getKey()) 
                : m.getValue() - pq.peek().getValue()) > 0){
                pq.poll();
                pq.offer(m);
            }
        }
        //取出堆中元素，从后向前放置
        for(int i = k - 1; i >= 0; i--){
            Map.Entry<String,Integer> entry =(Map.Entry)pq.poll();
            res[i][0] = entry.getKey();
            res[i][1] = String.valueOf(entry.getValue());
        }
        return res;
    }
}
```

### 寻找第K大

```java
public int findKth(int[] a, int n, int K){
    // 暂存K个较大的值，优先队列默认是自然排序（升序），
    // 队头元素（根）是堆内的最小元素，也就是小根堆
    PriorityQueue<Integer> queue = new PriorityQueue<>(K);
    // 遍历每一个元素，调整小根堆
    for (int num : a) {
        // 对于小根堆来说，只要没满就可以加入（不需要比较）；
        // 如果满了，才判断是否需要替换第一个元素
        if (queue.size() < K) {
            queue.add(num);
        } else {
            // 在小根堆内，存储着K个较大的元素，根是这K个中最小的，
            // 如果出现比根还要大的元素，说明可以替换根
            if (num > queue.peek()) {
                queue.poll(); // 高个中挑矮个，矮个淘汰
                queue.add(num);
            }
        }
    }
    return queue.isEmpty() ? 0 : queue.peek();
}
```

```java
import java.util.*;
 
public class Finder {
    public int findKth(int[] a, int n, int K) {
        // write code here
        return find(a, 0, n-1, K);
    }
     
    public int find(int[] a, int low, int high, int K){
        int pivot = partition(a, low, high);
         
        if(pivot + 1 < K){
            return find(a, pivot + 1, high, K);
        } else if(pivot + 1 > K){
            return find(a, low, pivot - 1, K);
        } else {
            return a[pivot];
        }
    }
     
    int partition(int arr[], int startIndex, int endIndex){
        int small = startIndex - 1;
        for (int i = startIndex; i < endIndex; ++i) {
            if(arr[i] > arr[endIndex]) {
                swap(arr,++small, i);
            }
        }
        swap(arr,++small,endIndex);
        return small;
    }
     
    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

```

## 双指针

### 最长无重复子数组的长度

```java
// 方法1
public int maxLength (int[] arr) {
    int left = 0, right = 0;
    Set<Integer> set = new HashSet<>();
    int res = 1;
    while(right < arr.length){
        if(!set.contains(arr[right])){
            set.add(arr[right]);
            right++;
        }else{
            set.remove(arr[left]);
            left++;
        }
        res = Math.max(res, set.size());
    }
    return res;
}

// 方法2
public int maxLength(int[] arr) {
    if (arr.length == 0)
        return 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    int max = 0;
    for (int i = 0, j = 0; i < arr.length; ++i) {
        if (map.containsKey(arr[i])) {
            j = Math.max(j, map.get(arr[i]) + 1);
        }
        map.put(arr[i], i);
        max = Math.max(max, i - j + 1);
    }
    return max;
}
```

### 滑动窗口的最大值

```java
import java.util.*;
/**
用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次
1.判断当前最大值是否过期
2.新增加的值从队尾开始比较，把所有比他小的值丢掉
*/
public class Solution {
   public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> res = new ArrayList<>();
        if(size == 0) return res;
        int begin;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for(int i = 0; i < num.length; i++){
            begin = i - size + 1;
            if(q.isEmpty())
                q.add(i);
            else if(begin > q.peekFirst())
                q.pollFirst();
        
            while((!q.isEmpty()) && num[q.peekLast()] <= num[i])
                q.pollLast();
            q.add(i);
            if(begin >= 0)
                res.add(num[q.peekFirst()]);
        }
        return res;
    }
}
```

### 合并区间（区间重叠）

首先将各个区间进行排序，排序规则为首先根据start进行排序，
如果start相等则根据end从小到大排序new一个新的List result存放结果，
遍历给定的intervals，比较当前interval的start是否大于result中最后一个元素的end，
若大于，说明从开了一个区间，若区间有重叠，则更新result中最后一个元素的end。

```java
import java.util.*;
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        // 首先根据start排序，如果start相等，根据end排序
        Collections.sort(intervals, 
        (o1, o2) -> (o1.start != o2.start 
        ? o1.start - o2.start : o1.end - o2.end));
        ArrayList<Interval> result = new ArrayList<>();
        if(intervals.size() == 0) {
            return result;
        }
        // 放入第一个区间
        result.add(intervals.get(0));
        int count = 0;
        // 遍历后续区间，查看是否与末尾有重叠
        for(int i = 1; i < intervals.size(); i++) {
            Interval o1 = intervals.get(i);
            Interval origin = result.get(result.size() - 1);
            // 如果当前Interval的start比List里面最后一个元素的end大，说明从开一个区间
            if(o1.start > origin.end) {
                result.add(o1);
            } else { // 区间有重叠，更新结尾
                if(o1.end > origin.end) {
                    result.get(result.size() - 1).end = o1.end;
                }
            }
        }
        return result;
    }
}
```

### 反转字符串

```java
import java.util.*;
public class Solution {
    /**
     * 反转字符串
     * @param str string字符串 
     * @return string字符串
     */
    public String solve (String str) {
        // write code here
        if(str == null){
            return null;
        }
        char[] c = new char[str.length()];
        int left = 0, right = str.length() - 1;
        
        while(left <= right){
            c[left] = str.charAt(right);
            c[right] = str.charAt(left);
            left++;
            right--;
        }
        return new String(c);
    }
}
```

### 数组中相加和为0的三元组

```java
import java.util.*;
 
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        Arrays.sort(num);
        int left,right,sum;
        for(int i = 0; i < num.length - 2; i++){
            if(i > 0 && num[i] == num[i-1]) continue;
            left = i + 1;
            right = num.length - 1;
            while(left < right){
                sum = num[i] + num[left] + num[right];
                if(sum == 0){
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(num[i]);
                    temp.add(num[left]);
                    temp.add(num[right]);
                    list.add(temp);
                    right--;
                    left++;
                    while(left < right && num[left] == num[left-1]){
                        left++;
                    }
                    while(left < right && num[right] == num[right+1]){
                        right--;
                    }
                } else if(sum < 0){
                    left++;
                } else {
                    right--;
                }
            }
        }
        return list;
    }
}
```

### 接雨水问题

```java
  public long maxWater(int[] arr) {
      if (arr.length <= 2)
          return 0;
      //找到最高的柱子的下标
      int max = Integer.MIN_VALUE;
      int maxIndex = -1;
      for (int i = 0; i < arr.length; i++) {
          if (arr[i] > max) {
              max = arr[i];
              maxIndex = i;
          }
      }

      //统计最高柱子左边能接的雨水数量
      int left = arr[0];
      int right = 0;
      long water = 0;
      for (int i = 1; i < maxIndex; i++) {
          right = arr[i];
          if (right > left) {
              left = right;
          } else {
              water += left - right;
          }
      }

      //统计最高柱子右边能接的雨水数量
      right = arr[arr.length - 1];
      for (int i = arr.length - 2; i > maxIndex; i--) {
          left = arr[i];
          if (arr[i] > right) {
              right = left;
          } else {
              water += right - left;
          }
      }

      //返回盛水量
      return water;
  }
```

```java
public long maxWater (int[] arr) {
    int l = 0, r = arr.length-1;
    int maxL = 0, maxR = 0;
    long res = 0;
    while(l < r){
        maxL = Math.max(arr[l],maxL); // 求出左边界的最大值
        maxR = Math.max(arr[r],maxR); // 求出右边界的最大值
        if(maxR > maxL){ // 如果
            res += maxL - arr[l++];
        }else{
            res += maxR - arr[r--];
        }
    }
    return res;
}
```

### 最小覆盖子串（T包含S的最小子串）

```java
import java.util.*;

public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    public String minWindow (String s, String t) {
        HashMap<Character, Integer> window = new HashMap<>();
        HashMap<Character, Integer> need = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            Integer count = need.get(t.charAt(i));
            count = count == null ? 1 : ++count;
            need.put(t.charAt(i),count);
        }
        int left =0 , right = 0;
        int vaild = 0;
        int len = Integer.MAX_VALUE,start = 0;
        //最小覆盖字串起始索引
        while (right < s.length()){
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)){
                Integer count = window.get(c);
                count = count == null ? 1 : ++count;
                window.put(c,count);
                if (window.get(c).equals(need.get(c))){
                    vaild++;
                }
            }

            //都包含了，right找到了，可以考虑收缩
            while (vaild == need.size()){
                if (right -left < len){
                    start = left;
                    len = right - left;
                }
                //d是将要移出窗口的字符
                char d = s.charAt(left);
                //左移窗口
                left++;
                //数据更新
                if (need.containsKey(d)){
                    if (window.get(d).equals(need.get(d))){
                        vaild--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }
        }
        return len == Integer.MAX_VALUE 
                ? "" : s.substring(start,start+len);
    }
}
```

### 两数之和

```java
import java.util.HashMap;
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                return new int[]{map.get(nums[i])+1,i+1};
            }
            map.put(target - nums[i],i);
        }
        return null;
    }
}
```

### 最长重复子串（连续两个相同的字符串）

```java
import java.util.*;
public class Solution {
    // 使用滑动窗口  滑动窗口中的字符串是重复字符串的一半
    public int solve (String a) {
        //枚举长度为i的窗口(按窗口大小倒序枚举)，找到第一个满足条件的窗口(窗口为重复子串)
        char[] cs = a.toCharArray();
        int len = cs.length;
        int cnt = 0;
        // 滑动窗口的大小不可能大于数组长度的一半
        for (int i=len/2; i>0; i--) { //枚举一半窗口大小
            //窗口右侧节点范围len-i
            for (int j=0; j<len-i; j++) {
                if (cs[j] == cs[j+i]) {
                    cnt++;
                }else {
                    cnt=0;
                }
                //最先找到符合条件的窗口，即为所求的窗口
                if (cnt == i) { //相等字符的个数等于半窗口大小
                    return 2*cnt;
                }
            }
        }
        return 0;
    }
}
```

## 动态规划

### 跳台阶

```java
public class Solution {
    public int jumpFloor(int target) {
        if (target < 2) {
            return 1;
        }
        int[] a = new int[target + 1];
        a[0] = 1;
        a[1] = 1;
        for (int i = 2; i <= target; i++) {
            a[i] = a[i-1] + a[i-2];
        }
        return a[target];
    }
}
```

### 连续子数组的最大和（sum < 0置为0）

```java

// dp
public int FindGreatestSumOfSubArray(int[] array) {
    if(array.length == 0){
        return 0;
    }
    
    int max = Integer.MIN_VALUE;
    int[] dp = new int[array.length];
    for(int i = 0; i < array.length; i++){
        dp[i] = array[i];
    }
    for(int i = 1; i < array.length; i++){
        dp[i] = Math.max(dp[i-1] + array[i],dp[i]);
    }
    
    for(int i = 0; i < dp.length; i++){
        if(dp[i] > max){
            max = dp[i];
        }
    }
    return max;
}

// sum < 0置为0
public int FindGreatestSumOfSubArray(int[] array) {
    if(array.length == 0){
        return 0;
    }
    
    int max = Integer.MIN_VALUE;
    int cur = 0; 
    for(int i = 0; i < array.length; i++){
        cur += array[i];
        max = Math.max(max,cur);
        cur = cur < 0 ? 0 : cur;
    }
    return max;
}
```

### 最长公共子串（返回具体字符串/长度）

```java
// 返回字符串
public class Solution {
    public String LCS (String str1, String str2) {
        // write code here
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m][n];
        int maxLength = 0;
        int lastIndex = 0;     
        //用来记录str1中最长公共串的最后一个字符的下标
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(str1.charAt(i) == str2.charAt(j)){   
                    //判断str1中第i个字符是否和str2中第j个字符相等
                    if(i == 0 || j == 0){               
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = dp[i - 1][j - 1] + 1;     
                    }
                    
                    if(dp[i][j] > maxLength){    
                        //判断是否需要更新最长公共子串
                        maxLength = dp[i][j];
                        lastIndex = i;
                    }
                }
            }
        }
        
        //通过str1来截取长度为maxLength, 最后字符坐标为lastIndex的子串
        return str1.substring(lastIndex - maxLength + 1, 
                        lastIndex + 1);     
    }
}

// 返回长度
public class Solution {
    public int LCS (String s1, String s2) {
        // write code here
        int mLength = s1.length();
        int nLength = s2.length();
        int[][] dp = new int[mLength + 1][nLength + 1];
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        for (int i = 0; i <= mLength; i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= nLength; j++) {
            dp[0][j] = 0;
        }
        for (int i = 1; i <= mLength; i++) {
            for (int j = 1; j <= nLength; j++) {
                if (c1[i - 1] != c2[j - 1]) {
                    dp[i][j] = 
                    Math.max(dp[i- 1][j], dp[i][j - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
        }
        return dp[mLength][nLength];
    }
}
```

### 斐波那契数列

```java
public class Solution {
    public int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }
        if(n == 1 || n == 2){
            return 1;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}
```

### 最长回文子串的长度

```java
public String longestPalindrome1(String s) {
    if (s == null || s.length() == 0) {
        return "";
    }
    int strLen = s.length();
    int left = 0;
    int right = 0;
    int len = 1;
    int maxStart = 0;
    int maxLen = 0;

    for (int i = 0; i < strLen; i++) {
        left = i - 1;
        right = i + 1;
        while (left >= 0 && 
            s.charAt(left) == s.charAt(i)) {
            len++;
            left--;
        }
        while (right < strLen && 
            s.charAt(right) == s.charAt(i)) {
            len++;
            right++;
        }
        while (left >= 0 && right < strLen 
            && s.charAt(right) == s.charAt(left)) {
            len = len + 2;
            left--;
            right++;
        }
        if (len > maxLen) {
            maxLen = len;
            maxStart = left;
        }
        len = 1;
    }
    return s.substring(maxStart + 1, 
        maxStart + maxLen + 1);

}
```

### 最长递增子序列

```java
// 求长度
class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int res = 0;
        Arrays.fill(dp, 1);
        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) 
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
```

```java
public int[] LIS (int[] arr) {
    // write code here
    if(arr == null || arr.length <= 0){
        return null;
    }

    int len = arr.length;
    int[] count = new int[len];             // 存长度
    int[] end = new int[len];               // 存最长递增子序列

    //init
    int index = 0;                          // end 数组下标
    end[index] = arr[0];
    count[0] = 1;

    for(int i = 0; i < len; i++){
        if(end[index] < arr[i]){
            end[++index] = arr[i];
            count[i] = index;
        }
        else{
            int left = 0, right = index;
            while(left <= right){
                int mid = (left + right) >> 1;
                if(end[mid] >= arr[i]){
                    right = mid - 1;
                }
                else{
                    left = mid + 1;
                }
            }
            end[left] = arr[i];
            count[i] = left;
        }
    }

    //因为返回的数组要求是字典序，所以从后向前遍历
    int[] res = new int[index + 1];
    for(int i = len - 1; i >= 0; i--){
        if(count[i] == index){
            res[index--] = arr[i];
        }
    }
    return res;
}
```

### 买卖股票的最佳时机

base case： 
dp[-1][k][0] = dp[i][0][0] = 0 
dp[-1][k][1] = dp[i][0][1] = -infinity 

状态转移⽅程： 
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) 
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])

- k == 1

```java
public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        if(prices.length == 0) return 0;
        // write code here
        int n = prices.length;
        int[][] dp = new int[n][2];
        for(int i = 0; i < n; i++){
            if(i - 1 == -1){
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            dp[i][0] = Math.max(dp[i-1][0], 
                            dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
        }
        
        return dp[n-1][0];
    }
}

// 空间复杂度优化版本
int maxProfit(int[] prices) {
    int n = prices.length;
    // base case: dp[-1][0] = 0, dp[-1][1] = -infinity
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        // dp[i][1] = max(dp[i-1][1], -prices[i])
        dp_i_1 = Math.max(dp_i_1, -prices[i]);
    }
    return dp_i_0;
}
```

- k 为正无穷

```java
// 原始版本
int maxProfit_k_inf(int[] prices) {
    int n = prices.length;
    int[][] dp = new int[n][2];
    for (int i = 0; i < n; i++) {
        if (i - 1 == -1) {
            // base case
            dp[i][0] = 0;
            dp[i][1] = -prices[i];
            continue;
        }
        dp[i][0] = Math.max(dp[i-1][0], 
                    dp[i-1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i-1][1], 
                    dp[i-1][0] - prices[i]);
    }
    return dp[n - 1][0];
}

// 空间复杂度优化版本
int maxProfit_k_inf(int[] prices) {
    int n = prices.length;
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
    }
    return dp_i_0;
}
```

- k == 2

```java
// 原始版本
int maxProfit(int[] prices) {
    int max_k = 2, n = prices.length;
    int[][][] dp = new int[n][max_k + 1][2];
    for (int i = 0; i < n; i++) {
        for (int k = max_k; k >= 1; k--) {
            if (i - 1 == -1) {
                // 处理 base case
                dp[i][k][0] = 0;
                dp[i][k][1] = -prices[i];
                continue;
            }
            dp[i][k][0] = Math.max(dp[i-1][k][0], 
                        dp[i-1][k][1] + prices[i]);
            dp[i][k][1] = Math.max(dp[i-1][k][1], 
                        dp[i-1][k-1][0] - prices[i]);
        }
    }
    // 穷举了 n × max_k × 2 个状态，正确。
    return dp[n - 1][max_k][0];
}

// 空间复杂度优化版本
int maxProfit_k_2(int[] prices) {
    // base case
    int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;
    int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;
    for (int price : prices) {
        dp_i20 = Math.max(dp_i20, dp_i21 + price);
        dp_i21 = Math.max(dp_i21, dp_i10 - price);
        dp_i10 = Math.max(dp_i10, dp_i11 + price);
        dp_i11 = Math.max(dp_i11, -price);
    }
    return dp_i20;
}
```

- k 为正无穷，但含有交易冷冻期

```java
// 原始版本
int maxProfit_with_cool(int[] prices) {
    int n = prices.length;
    int[][] dp = new int[n][2];
    for (int i = 0; i < n; i++) {
        if (i - 1 == -1) {
            // base case 1
            dp[i][0] = 0;
            dp[i][1] = -prices[i];
            continue;
        }
        if (i - 2 == -1) {
            // base case 2
            dp[i][0] = Math.max(dp[i-1][0], 
                        dp[i-1][1] + prices[i]);
            // i - 2 小于 0 时根据状态转移方程推出对应 base case
            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
            //   dp[i][1] 
            // = max(dp[i-1][1], dp[-1][0] - prices[i])
            // = max(dp[i-1][1], 0 - prices[i])
            // = max(dp[i-1][1], -prices[i])
            continue;
        }
        dp[i][0] = Math.max(dp[i-1][0], 
                    dp[i-1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i-1][1], 
                    dp[i-2][0] - prices[i]);
    }
    return dp[n - 1][0];
}

// 空间复杂度优化版本
int maxProfit_with_cool(int[] prices) {
    int n = prices.length;
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    int dp_pre_0 = 0; // 代表 dp[i-2][0]
    for (int i = 0; i < n; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
        dp_pre_0 = temp;
    }
    return dp_i_0;
}
```

- k 为正无穷且考虑交易手续费

```java
// 原始版本
int maxProfit_with_fee(int[] prices, int fee) {
    int n = prices.length;
    int[][] dp = new int[n][2];
    for (int i = 0; i < n; i++) {
        if (i - 1 == -1) {
            // base case
            dp[i][0] = 0;
            dp[i][1] = -prices[i] - fee;
            //   dp[i][1]
            // = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)
            // = max(dp[-1][1], dp[-1][0] - prices[i] - fee)
            // = max(-inf, 0 - prices[i] - fee)
            // = -prices[i] - fee
            continue;
        }
        dp[i][0] = Math.max(dp[i - 1][0], 
                    dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], 
                    dp[i - 1][0] - prices[i] - fee);
    }
    return dp[n - 1][0];
}

// 空间复杂度优化版本
int maxProfit_with_fee(int[] prices, int fee) {
    int n = prices.length;
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
    }
    return dp_i_0;
}
```

- 指定 k

```java
int maxProfit_k_any(int max_k, int[] prices) {
    int n = prices.length;
    if (n <= 0) {
        return 0;
    }
    if (max_k > n / 2) {
        // 复用之前交易次数 k 没有限制的情况
        return maxProfit_k_inf(prices);
    }

    // base case：
    // dp[-1][...][0] = dp[...][0][0] = 0
    // dp[-1][...][1] = dp[...][0][1] = -infinity
    int[][][] dp = new int[n][max_k + 1][2];
    // k = 0 时的 base case
    for (int i = 0; i < n; i++) {
        dp[i][0][1] = Integer.MIN_VALUE;
        dp[i][0][0] = 0;
    }

    for (int i = 0; i < n; i++) 
        for (int k = max_k; k >= 1; k--) {
            if (i - 1 == -1) {
                // 处理 i = -1 时的 base case
                dp[i][k][0] = 0;
                dp[i][k][1] = -prices[i];
                continue;
            }
            dp[i][k][0] = Math.max(dp[i-1][k][0], 
                    dp[i-1][k][1] + prices[i]);
            dp[i][k][1] = Math.max(dp[i-1][k][1], 
                    dp[i-1][k-1][0] - prices[i]);     
        }
    return dp[n - 1][max_k][0];
}
```

### 矩阵的最小路径和

```java
import java.util.*;
public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int m = matrix.length, n = matrix[0].length;
        if (m == 0 || n == 0) return 0;
        
        for (int i = 1; i < m; i++) 
            matrix[i][0] += matrix[i-1][0];
        for (int i = 1; i < n; i++) 
            matrix[0][i] += matrix[0][i-1];
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                matrix[i][j] += 
                Math.min(matrix[i-1][j], matrix[i][j-1]);
            }
        }
        return matrix[m-1][n-1];
    }
}
```

### 编辑距离

```java
import java.util.*;


public class Solution {
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    public int minEditCost (String str1, String str2, 
                            int ic, int dc, int rc) {
        // write code here
        int len1=str1.length();
        int len2=str2.length();
        char[] char1=str1.toCharArray();
        char[] char2=str2.toCharArray();
        int[][] dp=new int[len1+1][len2+1];
        for(int i=1;i<=len1;i++){
            dp[i][0]=dp[i-1][0]+dc;
        }
        for(int i=1;i<=len2;i++){
            dp[0][i]=dp[0][i-1]+ic;
        }
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                if(char1[i]==char2[j])
                    dp[i+1][j+1]=dp[i][j];
                else {
                    dp[i+1][j+1]=
                        Math.min(Math.min(dp[i][j]+rc,
                        dp[i][j+1]+dc),dp[i+1][j]+ic);
                }
            }
        }
        return dp[len1][len2];
    }
}
```

### 不同路径的数目

```java
import java.util.*;
public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here
        int[][] dp = new int[m][n];
        for(int i=0,j=0;i<m;i++){
            dp[i][j]=1;
        }
        for(int i=0,j=0;j<n;j++){
            dp[i][j]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
        
    }
}
```

### 最长公共子序列

```java
public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        // write code here
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m+1][n+1];
               
        StringBuilder res = new StringBuilder();
        for(int i = 1; i <= m;i++){
            for(int j = 1; j <= n;j++){
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res.append(s1.charAt(i-1));
                }else{
                    dp[i][j] = 
                        Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return res.toString();
    }
}
```

### 最长的括号子串

```java
public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int longestValidParentheses (String s) {
        // write code here
        if(s == null || s.length() <= 0){
            return 0;
        }
        
        Stack<Integer> stack = new Stack<>();
        int last = -1;
        int maxLen = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            } else {
                if(stack.isEmpty()){
                    last = i;
                } else {
                    stack.pop();
                    if(stack.isEmpty()){
                        maxLen = 
                        Math.max(maxLen, i - last);
                    } else {
                        maxLen = 
                        Math.max(maxLen, i - stack.peek());
                    }
                }
            }
        }
        
        return maxLen;
    }
}

// 动态规划
public int longestValidParentheses2(String s) {
    if (s == null || s.length() == 0)
        return 0;
    int[] dp = new int[s.length()];
    int ans = 0;
    for (int i = 1; i < s.length(); i++) {
        // 如果是'('直接跳过，默认为0
        if (s.charAt(i) == ')') {
            if (s.charAt(i - 1) == '(')
                dp[i] = 
                (i >= 2 ? dp[i - 2] : 0) + 2;
            // 说明s.charAt(i - 1)==')'
            else if (i - dp[i - 1] > 0 && 
                s.charAt(i - dp[i - 1] - 1) == '(') {
                dp[i] = 
                (i - dp[i - 1] > 1 ? 
                dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
                // 因为加了一个左括号和一个右括号，所以是加2
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}
```

### 高空扔鸡蛋

```java
// 如果棋子碎了，那么棋子的个数K应该减一，
// 搜索的楼层区间应该从[1..N]变为[1..i-1]共i-1层楼；
// 如果棋子没碎，那么棋子的个数K不变，
// 搜索的楼层区间应该从 [1..N]变为[i+1..N]共N-i层楼。
import java.util.*;
public class Solution {
    /**
     * 返回最差情况下扔棋子的最小次数
     * @param k int整型 棋子数
     * @param n int整型 楼层数
     * @return int整型
     */
    int[][] memo;
    public int solve (int n, int k) {
        memo = new int[k + 1][n + 1];
        for(int[] m : memo) {
            Arrays.fill(m, -1);
        }
        return dp(k, n);
    }
    
    // 定义：有K个棋子面对N层楼，最少需要扔 dp(K, N) 次
    int dp(int k, int n) {
        // 状态：棋子数k，需要测试的楼层n
        if(k == 1) {
            return n;
        }
        // 尝试到底层
        if(n == 0) {
            return 0;
        }
        if(memo[k][n] != -1) {
            return memo[k][n];
        }
        int res = Integer.MAX_VALUE;
        // 寻找第一层到第n层的最少扔的次数
        for(int i = 1; i <= n; i++) {
            res = Math.min(res,
            // 取决于最差情况（碎了，没碎）
            Math.max(dp(k-1, i-1), dp(k, n-i)) + 1);
        }
        memo[k][n] = res;
        return res;
    }
}
```

### 兑换零钱

```java
public class Solution {
    /**
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] arr, int aim) {
        // write code here
        //如何使用最少arr元素 构成 aim值
        //dp[i] 代表给定钱数为i的时候最少货币数 
        // 就是凑成 i 元钱，需要dp[i] 张arr中面值纸币
        //没办法兑换 arr[i]  dp[i] = dp[i]
        //可以dp[i] = dp[i - arr[i]] + 1
        //dp[i] = min(dp[i], dp[i-a[j]])
        if(arr == null || arr.length == 0){
            return -1;
        }
        int[] dp = new int[aim+1];
        for(int i = 0;i<=aim;i++){
            dp[i] = aim+1;
        }
        
        dp[0] = 0;
        for(int i = 1;i<=aim;i++){
            for(int j = 0;j< arr.length;j++){
                if(arr[j] <= i){
                    //给了一张 3 元钱，小于 需要找零的4 元钱，
                    // 那 就等于 1 + 需要找零剩下的钱dp[i -arr[j]] 4 - 3
                    dp[i] = 
                    Math.min(dp[i], dp[i-arr[j]] +1);
                }
            }
        }
        return (dp[aim] > aim) ?-1 : dp[aim];
    }
}
```

### 最大正方形

1.确定dp[][]数组的含义

此题的dp[i][j]，代表以坐标为(i,j)的元素为右下角的正方形的边长。

2.状态转移方程

dp[i][j]的值取决于dp[i-1][j],dp[i-1][j-1],dp[i][j-1]的最小值
即左方正方形的边长，左上方正方形的边长，上方正方形的边长三者的最小值。

```java
import java.util.*;

// dp[i][j]，代表以坐标为(i,j)的元素为右下角的正方形的边长
public class Solution {
    /**
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] matrix) {
        // write code here
        if(matrix.length ==0 || matrix[0].length == 0) return 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int maxSquareLength = 0;
        for(int i = 0; i < rows; i++){
            if(matrix[i][0] == '1') dp[i][0] = 1;
        }
        for(int i = 0; i < cols; i++){
            if(matrix[0][i] == '1') dp[0][i] = 1;
         }
        for(int  i =1; i < rows; i++){
            for(int j = 1; j < cols; j++){
                if(matrix[i][j] == '1'){
                    dp[i][j] = 
                        Math.min(Math.min(dp[i-1][j-1],
                            dp[i-1][j]),dp[i][j-1])+1;
                    if(dp[i][j] > maxSquareLength) 
                        maxSquareLength = dp[i][j];
                }
            }
        }
        return maxSquareLength*maxSquareLength;
    }
}
```

### 通配符匹配

![](http://image.ouyangsihai.cn/FtLlLxIBxM4nN1yyIi7VqfxsAXMB)

```java
import java.util.*;
public class Solution {
    public boolean isMatch(String s, String p) {
        if (p == null || p.isEmpty())return s == null || s.isEmpty();
        int slen = s.length(), plen = p.length();
        boolean[][] dp = new boolean[slen + 1][plen + 1];
        //初始化dp数组,dp[1][0]~dp[s.length][0]默认值flase不需要显式初始化为false
        dp[0][0] = true;
        //dp[0][1]~dp[0][p.length]只有p的j字符以及前面所有字符都为'*'才为true
        for (int j = 1; j <= plen; j++)dp[0][j] = p.charAt(j - 1) == '*' &&
                    dp[0][j - 1];
        //填写dp数组剩余部分
        for (int i = 1; i <= slen; i++) {
            for (int j = 1; j <= plen; j++) {
                char si = s.charAt(i - 1), pj = p.charAt(j - 1);
                if (si == pj || pj == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pj == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
            }
        }
        return dp[slen][plen];
    }
}
```

### 正则表达式匹配

![](http://image.ouyangsihai.cn/FsEkqX8hk4n_JgGhpWxZgFGtV5Qs)

```java
import java.util.*;
public class Solution {
    public boolean match (String str, String pattern) {
        int n=str.length();
        int m=pattern.length();
        boolean[][] dp=new boolean[n+1][m+1];

        //初始化
        dp[0][0]=true;
        for(int i=1;i<=n;i++){
            dp[i][0]=false;
        }

        //分模式串的后一个位置是否为*进行讨论,为*时，
        // 将*与前一个位置合并起来进行考虑
        for(int i=0;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(pattern.charAt(j-1)!='*'){
                    //当前模式串字符和原串字符匹配
                    if(i>0
                        &&(str.charAt(i-1)==pattern.charAt(j-1)
                        ||(pattern.charAt(j-1)=='.'))){
                        dp[i][j]=dp[i-1][j-1];
                    }
                }
                else{
                    if(j>=2){
                        //不管是否匹配，都可以将当前字符绑定上*匹配原串字符0次
                        dp[i][j]=dp[i][j-2];
                        //当前模式串字符和原串字符匹配
                        if(i>0
                            &&(str.charAt(i-1)==pattern.charAt(j-2)
                            ||(pattern.charAt(j-2)=='.'))){
                            dp[i][j]=dp[i-1][j]||dp[i][j-2];
                        }
                    }
                }
            }
        }
        return dp[n][m];
    }
}
```

### 矩阵最长递增路径

```java
class Solution {
    public  int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int ans = 0;
        int[][] dp = new int[m][n];//储存当前节点最长路径
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] == 0) {
                    ans = Math.max(ans, dfs(matrix, dp, i, j));
                }
            }
        }
        return ans;
    }
    public  int dfs(int[][] matrix , int[][] dp,  int i , int j){
       if (dp[i][j] == 0) {
            int dir1 = 0, dir2 = 0, dir3 = 0, dir4 = 0;
            if (i > 0 && matrix[i - 1][j] > matrix[i][j]) {
                dir1 = dfs(matrix, dp, i - 1, j);
            }
            if (j > 0 && matrix[i][j - 1] > matrix[i][j]) {
                dir2 = dfs(matrix, dp, i, j - 1);
            }
            if (i < matrix.length - 1 
                && matrix[i + 1][j] > matrix[i][j]) {
                dir3 = dfs(matrix, dp, i + 1, j);
            }
            if (j < matrix[0].length - 1 
                && matrix[i][j + 1] > matrix[i][j]) {
                dir4 = dfs(matrix, dp, i, j + 1);
            }
            //选出四个方向的最长子串，加1后赋值给当前节点
            dp[i][j] = 1 + Math.max(dir1, 
                Math.max(dir2, Math.max(dir3, dir4)));
        }
        return dp[i][j];
    }
}
```

### 最长上升子序列

- 返回长度
  
```java
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here
        int len = arr.length;
        if (arr == null && len == 0){
            return 0;
        }
        int maxLen = 0;
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        for (int i = 1; i < len; i++) {
            for (int j = i-1; j >=0 ; j--) {
                if (arr[i]> arr[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            maxLen = Math.max(maxLen,dp[i]);
        }
        return  maxLen;
    }
}
```

- 返回字符串

// 方法一：dp
状态定义：dp[i]表示以i位置元素结尾的最长上升子序列长度。
状态初始化：以每个位置结尾的上升子序列长度至少为1。
状态转移：遍历arr数组，假设当前位置为i，
比较当前位置i之前的每一个元素与当前位置元素的大小，
如果小于当前位置元素arr[i]，说明可以接在arr前面。
即 dp[i]=Math.max(dp[i],dp[j]+1)。

// 方法二：dp+数组
与方法一相同的是，也需要建立一个dp数组找到每一个位置对应的最长上升子序列长度，
最后再通过逆序遍历arr数组的方式，找到每一个长度对应的那个元素，赋值给结果序列。
不过确定dp数组的方式有所不同。

为了找到最长的上升子序列，我们可以维护一个单调递增的数组tail记录当前的最长上升子序列，
如果后面出现的数arr[i]比tail数组末尾元素大，则可以直接加在后面；
如果不是，则找到tail数组中第一个大于等于arr[i]的元素位置，
并将该位置的元素替换为arr[i]，因为在长度相同的情况下，当前值越小，则后面出现更长子序列的概率越大。

```java
// 方法一：dp
public class Solution {
    public int[] LIS (int[] arr) {
        int n=arr.length;
        //dp[i]表示以i位置元素结尾的最长上升子序列长度
        int[] dp=new int[n+1];
        //初始化为1
        Arrays.fill(dp,1);
        //记录最长子序列的长度
        int len=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                //如果小于arr[i]，则可以接在arr[i]前面
                if(arr[j]<arr[i]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            //计算最长子序列的长度
            len=Math.max(len,dp[i]);
        }
        
        int[] res=new int[len];
        //从后往前确定目标子序列的每一个值
        for(int i=n-1;i>=0;i--){
            if(dp[i]==len){
                res[--len]=arr[i];
            }
        return res;
    }
}

// 方法二：dp+二分
public class Solution {
    public int[] LIS (int[] arr) {
        int n=arr.length;
        //维护一个单调递增tail数组
        int[] tail=new int[n];
        //dp[i]表示以i位置结尾的最长上升子序列长度
        int[] dp=new int[n];
        //最长上升子序列长度
        int len=0;
        for(int i=0;i<n;i++){
            //如果tail数组为空，或者tail数组最后一个元素小于arr[i]
            if(i==0||tail[len-1]<arr[i]){
                //直接加在最后面
                tail[len++]=arr[i];
                //记录当前长度
                dp[i]=len;
            }
            else{
                //二分法找到tail数组中第一个大于等于arr[i]的元素位置
                int index=search(tail,len,arr[i]);
                //跟新index处的值
                tail[index]=arr[i];
                //记录当前长度
                dp[i]=index+1;
            }
        }
        int[] res=new int[len];
        //从后向前依次给子序列赋值
        for(int i=n-1;i>=0;i--){
            if(dp[i]==len){
                res[--len]=arr[i];
            }
        }
        return res;
    }
    
    //二分法找tail数组中第一个大于等于arr[i]的元素位置
    private int search(int[] nums,int len,int k){
        int low=0,high=len-1;
        while(low<high){
            int mid=(high+low)/2;
            //如果大于等于k，排除mid往右的所有元素
            if(nums[mid]>=k){
                high=mid;
            }
            //否则排除mid以及mid往左的所有元素
            else{
                low=mid+1;
            }
        }
        return low;
    }
}
```

### 目标和（完全背包）

```java
public class Solution {
    public int findTargetSumWays (int[] nums, int target) {
        //边界情况判断
        int n=nums.length;
        if(n==0) return 0;
        //记录累加和
        int sum=0;
        //遍历nums数组
        for(int num:nums){
            sum+=num;
        }
        //计算背包容量
        int V=(sum+target)/2;
        //如果为奇数，说明nums数组中找不打和为(sum+target)/2的若干数字
        if((sum+target)%2==1) return 0;
        
        //dp[j]表示有多少种不同的组合，其累加和为j
        int[] dp=new int[V+1];
        //初始化
        dp[0]=1;
        for(int i=0;i<nums.length;i++){
            //每个数字只选一次，所以需要倒序遍历，避免重复
            for(int j=V;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[V];
    }
}
```

### 打家劫舍

```java
public class Solution {
    public int rob (int[] nums) {
        // write code here
        
        // 一些特殊情况的处理
        if (1 == nums.length) {
            return nums[0];
        }
        if (2 == nums.length) {
            return Math.max(nums[0], nums[1]);
        }
        
        int l = nums.length;
        int[] dp = new int[l];
        
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < l; i++) {
            dp[i] = Math.max(dp[i - 2] 
                    + nums[i], dp[i - 1]);
        }
        return dp[l - 1];
    }
}

// 圆形情况
public class Solution {
    public int rob (int[] nums) {
        int n=nums.length;
        //在0到n-2范围内找
        int rob1=getRob(Arrays.copyOfRange(nums,0,n-1));
        //在1到n-1范围内找
        int rob2=getRob(Arrays.copyOfRange(nums,1,n));
        
        return Math.max(rob1,rob2);       
    }
    
    private int getRob(int[] nums){  
        int n=nums.length;
        //边界情况处理
        if(n==0) return 0;
        if(n==1) return nums[0];
        if(n==2) return Math.max(nums[0],nums[1]);
        //定义dp数组
        int[] dp=new int[n];
        //初始化
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<n;i++){
            //状态转移
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
}

// 二叉树情况
public class Solution {
    public int rob (TreeNode root) {
        if(root==null) return 0;
        //dp[0]表示选择当前节点的最大金额，
        // dp[1]表示不选择当前节点的最大金额
        int[] dp=dfs(root);
        return Math.max(dp[0],dp[1]);
    }
    
    private int[] dfs(TreeNode root){
        if(root==null){
            return new int[]{0,0};
        }
        //左子节点情况
        int[] left=dfs(root.left);
        //右子节点情况
        int[] right=dfs(root.right);
        //当前节点的情况
        int[] dp=new int[2];
        //选择当前节点
        dp[0]=root.val+left[1]+right[1];
        //不选择当前节点
        dp[1]=Math.max(left[0],left[1])
                +Math.max(right[0],right[1]);
        return dp;        
        
    }
}
```

### 带权值的最小路径和

```java
public class Solution {
    /**
     * 
     * @param grid int整型二维数组 
     * @return int整型
     */
    public int minPathSum (int[][] grid) {
        // write code here
        int row = grid.length;
        int col = grid[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < row; i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j = 1; j < col; j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        
        for(int i = 1; i < row; i++){
            for(int j = 1; j < col; j++){
                dp[i][j] = Math.min(dp[i][j-1],
                    dp[i-1][j]) + grid[i][j];
            }
        }
        
        return dp[row-1][col-1];
    }
}
```

### 最长不含重复字符的子字符串

```java

思路：
dp[i]表示的是以i结尾的最长不含重复字符的子字符串。使用了hashmap这个数据结构记录<char,index>
如果map中没有当前这个元素，那么dp[i]=dp[i-1]+1
如果map中存在当前的元素，一开始的想法是 dp[i]=i-map.get(array[i]),
但是这样想有点问题，如果当前的字符串是abba的时候,按照刚才的思路dp[0]=1 dp[1]=2 dp[2]=1 dp[3]=3
但是dp[3]是错误的，因为中间存在了重复的字符。所以要加一种情况。
dp[i]=Math.min(dp[i-1]+1,i-map.get(array[i]))

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int lengthOfLongestSubstring (String s) {
        if(s==null) return 0;
        char[]array=s.toCharArray();
        if(array.length==1){
            return 1;
        }
        int[]dp=new int[array.length];
        int maxLength=1;
        HashMap<Character, Integer>map=new HashMap<>();
        dp[0]=1;
        map.put(array[0],0);
        for(int i=1;i<array.length;i++){
            dp[i]=1;
            if(!map.containsKey(array[i])){
                dp[i]=dp[i-1]+1;
            }
            else{
                dp[i]=Math.min(dp[i-1]+1,i-map.get(array[i]));
            }
            map.put(array[i],i);
            maxLength=Math.max(maxLength,dp[i]);
        }
        return maxLength;
    }
}
```

### 把数字翻译成字符串

![](http://image.ouyangsihai.cn/FrcG8hDYMAUfq6EmSp0mxdFEHk-C)

```java
public int solve (String nums) {
        if(nums.length() == 0 || nums.charAt(0) == '0')
            return 0;
        int[] dp = new int[nums.length()];
        dp[0] = 1;
        for(int i = 1; i < dp.length; i++){
            if(nums.charAt(i) != '0'){
                dp[i] = dp[i-1];
            }
            //  3 2 4 
            int num = (nums.charAt(i-1)-'0')*10 + (nums.charAt(i)-'0');
            if(num >= 10 && num <= 26){
                if(i == 1){
                    dp[i] += 1;
                }else{
                    dp[i] += dp[i-2];
                }
            }
        }
        return dp[nums.length()-1];

    }
```

## 二分

### 求平方根

```java
import java.util.*;
 
 
public class Solution {
    /**
     *
     * @param x int整型
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        if(x < 2){
            return x;
        }
        int left = 1;
        int right = x / 2;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(x / mid == mid){
                return mid;
            } else if(x / mid < mid){
                right = mid - 1;
            } else if(x / mid > mid){
                left = mid + 1;
            }
        }
         
        return right;
    }
}
```

### 在旋转过的有序数组中寻找目标值

```java
public class Solution {
    public int search (int[] nums, int target) {
        // write code here
        if (nums == null || nums.length < 1) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }

        int start = 0, end = nums.length - 1;
        while (end >= start) {
            // 找到 左右指针中间位置
            int mid = (end + start) >> 1;
            if (nums[mid] == target) {
                return mid;
            }
            // 在左侧升序数组中
            if (nums[0] <= nums[mid]) {
                // 在开头和 mid 之间，那么 右指针则为 mid -1
                if (target >= nums[0] 
                    && target < nums[mid]) {
                    end = mid -1;
                } else {
                    start = mid + 1;
                }
            } else {
                // 如果在 mid 和end 之间，更新 start 为 mid = 1
                if (target > nums[mid] 
                    && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}
```

### 在两个长度相等的排序数组中找到上中位数

```java
// 普通
public class Solution {
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        // write code here
        int length1 = arr1.length;
        int length2 = arr2.length;
        int i=0;
        int j=0;
        int[] arr = new int[length1+length2];
        int index = 0;
        //合并数组
        for(;i<length1 && j<length2;){
            if(arr1[i]<arr2[j]){
                arr[index] = arr1[i];
                i++;
            }else{
                arr[index] = arr2[j];
                j++;
            }
            index++;
        }
        
        if(i == length1){//数组1已经合并
            while(j<length2){
                arr[index] = arr2[j];
                j++;
                index++;
            }
        }
        if(j == length2){//数组2已经合并
            while(i<length1){
                arr[index] = arr1[i];
                i++;
                index++;
            }
        }
        //返回上中位数
        return arr[(length1+length2-1)/2];
    }
}

// 二分
public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
    // write code here
    int n = arr1.length;
    if(n==0){
        return 0;
    }
    //arr1左右两端
    int l1=0,r1=n-1;
    //arr2左右两端
    int l2=0,r2=n-1;
    int mid1,mid2;
    //终止条件为l1=r1，即两个数组都只有一个元素，
    // 此时的上中位数为两数的最小值
    while(l1 < r1){ 
        //arr1中位数
        mid1 = l1+((r1-l1)>>1);
        //arr2中位数
        mid2 = l2+((r2-l2)>>1);
        int k = r1-l1+1;
        if(arr1[mid1] == arr2[mid2]){ 
            //若两数组中位数相等，整体中位数也是这个
            return arr1[mid1];
        }
        else if(arr1[mid1] > arr2[mid2]){
            if(k%2 == 0){//区间元素个数为偶数
                r1 = mid1; //整体中位数在arr1左区间,包括mid1
                l2 = mid2+1; //整体中位数在arr2右区间，不包括mid2
            }
            else if(k%2 == 1){ //区间元素个数为奇数
                r1 = mid1; //整体中位数在arr1左区间,包括mid1
                l2 = mid2; //整体中位数在arr2右区间，包括mid2
            }
        }
        else if (arr1[mid1] < arr2[mid2]){
            if(k%2 == 0){//区间元素个数为偶数
                r2 = mid2; //整体中位数在arr2左区间,包括mid2
                l1 = mid1+1; //整体中位数在arr1右区间，不包括mid1
            }
            else if(k%2 == 1){ //区间元素个数为奇数
                r2 = mid2; //整体中位数在arr2左区间,包括mid2
                l1 = mid1; //整体中位数在arr1右区间，包括mid1
            }
        }
    }
    //当区间内只有一个元素时，两个区间中最小值即为整体中位数
    return Math.min(arr1[l1],arr2[l2]);
}
```

### 有序矩阵元素查找

```java
public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
        int[] result = new int[2];
        int row = 0;
        int col = m - 1;
        while(row < n && col >= 0) {
            if(mat[row][col] == x) {
                result[0] = row;
                result[1] = col;
                break;
            }
            if(x > mat[row][col]) {
                row ++;
            } else {
                col --;
            }
        }
        return result;
    }
}
```

### 二分查找

```java
public int binarySearch(int target, int[] nums) {
    int left = 0;
    int right = nums.length-1;  //取最后一个下标
    int mid = 0;
    //左下标大于右下标，直接返回-1
    if (left > right || nums.length == 0 || nums == null) {
        return -1;
    }
    // 初始化 right 的赋值是 nums.length - 1，
    // 即最后一个元素的索引，而不是 nums.length
    while (left <= right) { 
        mid = left + (right - left) / 2; //如果下标之和除以2有小数，则直接去掉
        if (target == nums[mid]) {
            return mid; //找到目标值，然后返回
        } else if (target > nums[mid]) {    //目标值大于中间值，向右遍历
            left = mid + 1; //所以向右遍历的第一个下标是：中间下标+1
        } else if (target < nums[mid]) {    //目标值小于中间值，向左遍历
            right = mid - 1;    //所以向左遍历的最后一个下标是：中间下标-1
        }
    }
    return -1;  //找不到对应目标值，直接返回-1
}
```

```java
// 查找最右值
public class Solution {
    public int upper_bound_search (int n, int v, int[] a) {
        // write code here
        int left = 0, right = n;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(a[mid] == v){
                right = mid;
            } else if(a[mid] > v){
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left+1;
    }
}
```

```java
// 查找最左值
public class Solution {
    public int left_bound_search (int[] nums, int target) {
        // write code here
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0, right = nums.length - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[right] == target ? right : -1;
    }
}
```

### 旋转数组的最小数字

1.如果mid>right，说明mid-right之间存在被旋转数组，left = mid+1
2.如果mid<right,说明mid右侧整体有序，最小的定在mid（包含）及其左边
3.如果mid=right，无法判断，只能缩小范围right --；

```java
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            //说明mid-right为被旋转的部分，最小的应该在mid之前可能包含mid 561234
            if(array[mid] < array[right]){
                right = mid;
            }
            else if(array[mid] > array[right]){
                left = mid + 1;
            }
            else{
                right = right - 1;
            }
        }
        return array[left];
    }
}
```

### 数字在升序数组中出现的次数

```java
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array.length == 0 || k < array[0] 
            || k > array[array.length-1]){
            return 0;
        }
        int left = 0;
        int right = array.length -1;
        int count = 0;
        int found = 0;
        int mid = -1;
        while(left < right){
            mid = (left+right)/2;
            if(array[mid] > k){
                right = mid-1;
            }else if(array[mid] < k){
                left = mid+1;
            }else{
                count++;
                found = mid;
                break;
            }
        }

        int prev = mid-1;
        int foll = mid+1;
        while(prev >= left){
            if(array[prev] == k){
                count++;
                prev--;
            }else{
                break;
            }
        }

        while(foll <= right){
            if(array[foll] == k){
                count++;
                foll++;
            }else{
                break;
            }
        }
        return count;
    }
}
```

### 峰值

本题之所以可以使用二分，使复杂度讲到lgn，是因为题目中的nums[i] != nums[i + 1]条件，
当中间元素mid不是峰时，一定有一边比mid中间值大，
假设右边的值，即mid+1位置的值大于mid的值，则右边一定存在峰，
因为右边的值从mid开始要么是 /\ 这个单调性，要么是 / 这种单调性，两种都一定存在峰

```java
import java.util.*;
public class Solution {
    public int findPeakElement (int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        //二分法
        while(left < right){ 
            int mid = (left + right) / 2;
            //右边是往下，不一定有坡峰
            if(nums[mid] > nums[mid + 1])
                right = mid;
            //右边是往上，一定能找到波峰
            else
                left = mid + 1;
        }
        //其中一个波峰
        return right; 
    }
}
```

## 数组

### 数组中只出现一次的数字

```java
public class Solution {
     
    public void FindNumsAppearOnce(int [] array,
                    int num1[] , int num2[]) {
        int num = 0;
        for(int i = 0; i < array.length; i++){
            num^=array[i];
        }
         
        int count = 0;
        // 标志位，记录num中的第一个1出现的位置
        for(;count < array.length; count++){
            if((num&(1<<count)) != 0){
                break;
            }
        }
        num1[0] = 0;
        num2[0] = 0;
        for(int i = 0; i < array.length; i++){
            // 标志位为0的为一组，异或后必得到一个数字（
            // 这里注意==的优先级高于&，需在前面加（））
            if((array[i] & (1 << count)) == 0){
                num1[0] ^= array[i];
            } else {
                // 标志位为1的为一组
                num2[0] ^= array[i];
            }
        }
    }
     
    /*
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < array.length; i++){
            if(!set.add(array[i])){
                set.remove(array[i]);
            }
        }
         
        Object[] temp = set.toArray();
        num1[0] = (int)temp[0];
        num2[0] = (int)temp[1];
    }*/
}

```

### 合并两个有序的数组

```java
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int i = m-1, j = n-1, k = m+n-1;
        while(i >= 0 && j >= 0){
            if(A[i] > B[j]){
                A[k--] = A[i--];
            } else {
                A[k--] = B[j--];
            }
        }
         
        while(j >= 0){
            A[k--] = B[j--];
        }
    }
}
```

### 子数组最大乘积

```java
public class Solution {
    public double maxProduct(double[] arr) {
        if(arr.length == 0 || arr == null){
            return 0.0;
        }
        double[] max = new double[arr.length];
        double[] min = new double[arr.length];
        max[0] = min[0] = arr[0];
        for(int i = 1; i < arr.length; i++){
            max[i] = 
                Math.max(Math.max(max[i-1]*arr[i],
                    min[i-1]*arr[i]),arr[i]);
            min[i] = 
                Math.min(Math.min(max[i-1]*arr[i],
                        min[i-1]*arr[i]),arr[i]);
        }
        
        double ans = max[0];
        for(int i = 0; i < max.length; i++){
            if(max[i] > ans){
                ans = max[i];
            }
        }
        return ans;
    }
}

public int maxProduct (int[] nums) {
    int max = nums[0];
    int min = nums[0];
    int result =  nums[0];
    for (int i = 1; i < nums.length; i++) {
        int t = max;
        max = Math.max(nums[i], 
            Math.max(max * nums[i], min * nums[i]));
        min = Math.min(nums[i], 
            Math.min(t * nums[i], min * nums[i]));
        result = Math.max(result,max);
    }
    return result;
}
```

### 数组中最长连续子序列

```java
public int MLS(int[] arr) {
    if (arr == null || arr.length == 0)
        return 0;
    int longest = 1;//记录最长的有序序列
    int count = 1;//目前有序序列的长度
    //先对数组进行排序
    Arrays.sort(arr);
    for (int i = 1; i < arr.length; i++) {
        //跳过重复的
        if (arr[i] == arr[i - 1])
            continue;
        //比前一个大1，可以构成连续的序列，count++
        if ((arr[i] - arr[i - 1]) == 1) {
            count++;
        } else {
            //没有比前一个大1，不可能构成连续的，
            //count重置为1
            count = 1;
        }
        //记录最长的序列长度
        longest = Math.max(longest, count);
    }
    return longest;
}
```

### 数组中未出现的最小正整数

时间复杂度O(n),空间复杂度O(n)的做法：开辟一个新的数组arr，长度为nums.length+1，遍历nums数组，
如果非负且值小于nums的长度，则把arr[nums[i]]置1。然后遍历辅助数组，找到下标不为1的第一个元素即可。

```java
public class Solution {
    public int minNumberDisappeared (int[] nums) {
        int []arr = new int [nums.length+1];
        for(int i=0;i<nums.length;++i){
            if(nums[i]<=nums.length&&nums[i]>0){
                arr[nums[i]] =1;
            }
        }
        for(int i=1;i<arr.length;++i)
            if(arr[i]==0)return i;
      return arr.length;
    }
}
```

### 顺时针旋转数组

```java
// 找规律：mat[i][j]被旋转到了mat[j][n-i-1]的位置
public class Rotate {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        int[][] temp=new int[n][n];
        
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                temp[j][n-1-i]=mat[i][j];                
            }
        }        
        return temp;    
    }
}
```

### 旋转数组

```java
import java.util.*;
public class Solution {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve(int n, int m, int[] a) {
        m = m % n;
        //相当于不平移
        if (m % n == 0) {
            return a;
        }
        reverse(a, 0, n-1);
        reverse(a,0,m-1);
        reverse(a,m,n-1);
        return a;
    }

    //反转数组函数
    void reverse(int a[], int begin, int end) {
        int left = begin, right = end, t;
        while (left < right) {
            t = a[left];
            a[left] = a[right];
            a[right] = t;
            left++;
            right--;
        }
    }
}
```

### 逆序对

合并时，出现前面的数组值array[i]大于后面数组值array[j]时；则前面
数组array[i]~array[mid]都是大于array[j]的，count += mid+1 - i

```java
public class Solution {
    int res = 0;
    public int InversePairs(int [] array) {
        if(array.length != 0){
            mergeSort(array,0,array.length-1);
        }
        return res;
    }
    
    public void mergeSort(int[] array,int start,int end){
        if(start >= end){
            return;
        }
        int mid = start + (end - start)/2;
        
        mergeSort(array,start,mid);
        mergeSort(array,mid + 1,end);
        
        merge(array,start,mid,end);
    }
    
    public void merge(int[] array,int start,int mid,int end){
        int[] temp = new int[end-start+1];
        int k = 0;
        int i = start;
        int j = mid + 1;
        while(i <= mid && j <= end){
            if(array[i] < array[j]){
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
                res = (res + mid - i + 1) % 1000000007;
            }
        }
        
        while(i <= mid){
            temp[k++] = array[i++];
        }
        
        while(j <= end){
            temp[k++] = array[j++];
        }
        
        for(k = 0; k < temp.length; k++){
            array[start + k] = temp[k];
        }
    }
    
    
    /*
    public int InversePairs(int [] array) {
        int sum = 0;
        for(int i = 0; i < array.length - 1; i++){
            for(int j = i + 1; j < array.length; j++){
                if(array[i] > array[j]){
                    sum ++;
                }
            }
        }
        return sum % 1000000007;
    }
    */
}
```

### 调整数组顺序使奇数位于偶数前面

```java
// 方法一：先记录下技术的个数，然后遍历数组，用另外一个数组接收奇数和偶数
import java.util.*;
public class Solution {
    public int[] reOrderArray (int[] array) {
        // write code here
        int[] arr=new int[array.length];
        int num=0;
        for(int a:array){
            if((a&1)==1) num++;//奇数
        }
        int i=0;
        for(int a:array){
            if((a&1)==1){ //奇数
                arr[i++]=a;            
            }else{
                arr[num++]=a;
            }
        }
        return arr;
    }
}

// 方法二：记录已经是奇数的位置下标（视作为有序区域），然后向后遍历，
// 一经发现是奇数则进行“插入排序”，然后有序区下标加1。
public class Solution {
    public int[] reOrderArray (int[] array) {
        // 首先是对数值长度进行特判
        if(array==null||array.length==0) return array;
        //记录已经是奇数的位置
        int j=0;
        int temp = 0;
        for(int i =0;i<array.length;i++){
            temp = array[i];
            //如果该值为偶数
            if(array[i]%2==0){
                continue;
            }else{//该值为奇数
                int k =i;
                while(k>j){
                    //这区间整体向后移动一位
                    array[k] = array[k-1];
                    k--;
                }
                //移位之后将对应的值赋值
                array[k] = temp;
                j++;
            }
        }
        //返回结果数数组
        return array;
    }
}
```

### 矩阵乘法

```java
import java.util.*;
public class Solution {
    public int[][] solve (int[][] a, int[][] b) {
        // write code here
        //矩阵相乘条件：a的列和b的行必须相等
        //记录a的行、a的列(b的行)、b的列
        int aRow = a.length;
        int aColumn = a[0].length;
        int bColumn = b[0].length;
        //新矩阵行为a的行，列为b的列
        int[][] res = new int[aRow][bColumn];
        for(int i=0; i<aRow; i++) {
            for(int j=0; j<bColumn; j++) {
                for(int k=0; k<aColumn; k++) {
                    res[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return res;
    }
}
```

## 回溯

### 字符串的全排列

```java
class Solution {
    //存放结果
    List<List<Integer>> result = new ArrayList<>();
    //暂存结果
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backTrack(nums, used);
        return result;
    }

    private void backTrack(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            //如果同⼀树⽀nums[i]没使⽤过开始处理
            if (used[i] == false) {
                used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树支重复使用
                path.add(nums[i]);
                backTrack(nums, used);
                //回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                path.remove(path.size() - 1);
                used[i] = false;//回溯
            }
        }
    }
}
```

### 岛屿的数量

```java
class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    
    public void bfs(char[][] grid, int i, int j){
        Queue<int[]> list = new LinkedList<>();
        list.add(new int[] { i, j });
        while(!list.isEmpty()){
            int[] cur = list.remove();
            i = cur[0]; j = cur[1];
            if(inArea(i,j,grid) 
                && grid[i][j] == '1') {
                grid[i][j] = '0';
                list.add(new int[] { i + 1, j });
                list.add(new int[] { i - 1, j });
                list.add(new int[] { i, j + 1 });
                list.add(new int[] { i, j - 1 });
            }
        }
    }

    public boolean inArea(int i, int j, char[][] grid){
        return i >=0 && j >= 0 
                && i < grid.length 
                && j < grid[0].length;
    }
}
```

### 没有重复项数字的所有排列(全排列)

```java
public class Demo1 {
    ArrayList<ArrayList<Integer>> res;

    public ArrayList<ArrayList<Integer>> permute(int[] nums) {
        res = new ArrayList<ArrayList<Integer>>();
        if (nums == null || nums.length < 1)
            return res;
        //对数组元素进行从小到大排序
        Arrays.sort(nums);
        ArrayList<Integer> list = new ArrayList<Integer>();

        solve(list, nums);

        return res;
    }

    private void solve(ArrayList<Integer> list, int[] nums) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!list.contains(nums[i])) {
                list.add(nums[i]);
                solve(list, nums);
                list.remove(list.size() - 1);
            }
        }
    }
}
```

### 集合的所有子集

```java
import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        Arrays.sort(S);
        LinkedList<Integer> list=new LinkedList<>();
        dfs(res,list,0,S);
        return res;
    }
    public void dfs(ArrayList<ArrayList<Integer>> res,
                LinkedList<Integer> list, int k, int[] S){
        res.add(new ArrayList<>(list));
        for(int i=k;i<S.length;i++){
            list.add(S[i]);
            dfs(res,list,i+1,S);
            list.removeLast();
        }
    }
}
```

### 重复项数字的所有排列

```java
public class Solution {
    private ArrayList<ArrayList<Integer>> res;
    private boolean[] visited;

    public ArrayList<ArrayList<Integer>> permute(int[] nums) {
        res = new ArrayList<>();
        visited = new boolean[nums.length];
        List<Integer> list = new ArrayList<>();
        backtrace(nums, list);
        return res;
    }

    private void backtrace(int[] nums, List<Integer> list) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            list.add(nums[i]);
            backtrace(nums, list);
            visited[i] = false;
            list.remove(list.size() - 1);
        }
    }
}
```

### N皇后问题

```java
public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
     public int Nqueen (int n) {
        // write code here
        List<Integer> res=new ArrayList<>();
        char[][] chess=new char[n][n];
        for(int i=0;i<n;i++){ //棋盘
            for(int j=0;j<n;j++){
                chess[i][j]='.';
            }
        }
      
        backtrack(0,chess,res);
        return res.size();
    }
    
    // 回溯
    public void backtrack(int row,
            char[][] chess,List<Integer> res){
        if(row==chess.length){
            res.add(1);
            return;
        }
        for(int col=0;col<chess.length;col++){
            if(!isValid(row,col,chess)) continue;
            
            chess[row][col]='Q';
            backtrack(row+1,chess,res);
            chess[row][col]='.';
        }
    }
    
    public boolean isValid(int row,
                int col,char[][] chess){
        for(int i=0;i<chess.length;i++){
            if(chess[i][col]=='Q'){
                return false;
            }
        }
        for(int i=row-1,j=col+1;
                i>=0&&j<chess.length;i--,j++){
            if(chess[i][j]=='Q'){
                return false;
            }
        }
        for(int i=row-1,j=col-1;
                j>=0&&i>=0;i--,j--){
            if(chess[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }
}
```

### 把数组字符串转换为 ip 地址

回溯法插入'.'，每次可以插入到1个，2个或者3个字符后面，插入3次之后对得到的字符串进行验证

```java
public class Solution {
    ArrayList<String> res = new ArrayList<>();
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        if(s.length() == 0)
            return res;
        //表示当前字符串s，可以从第0个位置开始插入'.' ，还有3个'.'可以插入
        backTrack(s, 0, 3);
        return res;
    }

    public void backTrack(String s, int start, int cnt){
        if(cnt == 0){
            String[] splits = s.split("\\.");
            //没有插入4个合法的小数点
            if(splits.length < 4)
                return;
            //判断每一位是否合法
            for(String str:splits){
                if(str.length() > 1 && str.charAt(0) == '0') return;  //最前面的数字不能为0
                if(Integer.valueOf(str) > 255) return;  //每一位都不能大于255
            }
            res.add(s);
            return;
        }

        if(start >= s.length()) return;  //没有插完全部的点 就已经超出字符串的范围了
        int len = s.length();
        //每次将一个字符作为一位
        backTrack(s.substring(0,start+1)+'.'
            +s.substring(start+1,len), start+2, cnt-1);
        //每次将两位字符作为一位
        if(start < len-2)
            backTrack(s.substring(0,start+2)+'.'
                +s.substring(start+2,len), start+3, cnt-1);
        //每次将三位字符作为一位
        if(start < len-3)
            backTrack(s.substring(0,start+3)+'.'
                +s.substring(start+3,len), start+4, cnt-1);
    }
}
```

### 加起来和为目标值的组合

```java
import java.util.* ;
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num) ;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>() ;
        help(target , num , 0 , res , new ArrayList<Integer>()) ;
        return res ;
    }
    public void help(int target , int[] num , int idx , 
        ArrayList<ArrayList<Integer>> res , ArrayList<Integer> tmp)  {        
        if(target == 0) {
            res.add(new ArrayList<Integer>(tmp)) ;
            return ;
        }
        for(int i = idx ; i < num.length ; i ++) {
            if(num[i] > target) return ;//剪枝
            if((i > idx && num[i] == num[i-1])) continue ;//去重
            tmp.add(num[i]) ;
            help(target-num[i] , num , i + 1 , res , tmp) ;//递归
            tmp.remove(tmp.size() - 1) ;//回溯
        } 
    }  
}
```

## 其他

### 螺旋矩阵

给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素

```java
import java.util.*;
public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();

        if(matrix.length == 0) {
            return list;
        }

        int left = 0; 
        int right = matrix[0].length - 1;
        int top = 0;
        int bottom = matrix.length - 1; 
        int x = 0;


        while(true) {
            for(int i = left; i <= right; i++) {  //从左到右
               list.add(matrix[top][i]) ; 
            }

            if(++top > bottom){
                break;
            } 
            for(int i = top; i <= bottom; i++){
                 list.add( matrix[i][right]);    //从上到下
            } 

            if(left > --right){
                break;
            } 
            for(int i = right; i >= left; i--){
                  list.add(matrix[bottom][i]); //从右到左
            } 

            if(top > --bottom){
                break;
            }
            for(int i = bottom; i >= top; i--){
                 list.add(matrix[i][left]);   //从下到上
            } 

            if(++left > right){
               break;
            } 
        }
        return list;
    }
}
```

### 顺时针旋转矩阵

原矩阵元素的列数变成新矩阵元素的行数: 原矩阵元素的行数是第2行，旋转后元素的列数是从右往左倒数第2列。
因此对于原矩阵mat[i][j]，旋转后该值应该在新矩阵ans[j][n-i-1]的位置。

```java
class Solution {
public:
  vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
      // write code here
      vector<vector<int>> ans(n,vector<int>(n));
      for(int i=0;i<n;i++){
          for(int j=0;j<n;j++){
              ans[j][n-i-1]=mat[i][j];
          }
      }
      return ans;
  }
};
```

### 进制转换

- 首先建立一个字符映射数组arr，用于表示大于10的情况。
- 再用一个boolean型变量f标识M是否为负数，如果为负数，要多加一个负号。
- 只要M不为0，不断地取余，加入到sb。并且每次将M除N。
- 最后将得到的sb反转之后正好是所求N进制的数对应的字符串。

```java
public class Solution {
    public String solve (int M, int N) {
        //记录转换后的字符串
        StringBuilder sb=new StringBuilder();
        //用于表示大于10的情况
        char[] arr={'A','B','C','D','E','F'};
        //判断是否为负数
        boolean f=false;
        if(M<0){
            //测试用例里不包含Integer.MIN_VALUE，所以可以这么写
            M=-M;
            f=true;
        }
        while(M!=0){
            //记录每一次除N的余数
            int temp=M%N;
            //大于等于10，加对应的字母
            if(temp>=10){
                sb.append(arr[temp-10]); 
            }
            //小于10，直接加到sb
            else{
                sb.append(temp); 
            }            
            M/=N;
        }
        //负数要多加一个负号
        if(f){
            sb.append('-');
        }
        //反转后转为字符串返回
        return sb.reverse().toString();
    }
}
```

### 反转数字

```java
public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int reverse (int x) {
        // write code here
        int res = 0;
        while(x != 0){
            // 获取最后一位
            int tail = x % 10;
            int newRes = res * 10 + tail;
            // 如果不等于，说明溢出
            if((newRes - tail) / 10 != res){
                return 0;
            }
            res = newRes;
            x /= 10;
        }
        
        return res;
    }
}
```

### 大数加法

```java
public class Solution {
    public String solve (String s, String t){
        int i = s.length() - 1, j = t.length() - 1;
        int temp = 0;
        StringBuilder out = new Stringbuilder();
        while (i >= 0 || j >= 0 || temp != 0) {
            temp += i >= 0 ? s.charAt(i--) - '0' : 0;
            temp += j >= 0 ? t.charAt(j--) - '0' : 0;
            out.append(temp % 10);
            temp = temp / 10;
        }
        return out.reverse().toString();
    }
}

public class Solution {
    public String solveByJava(String s, String t){
        BigInteger num1 = new BigInteger(s);
        BigInteger num2 = new BigInteger(t);
        return num1.add(num2).toString();
    }
}
```

### 把字符串转换成整数(atoi)

1、首位空格：通过trim()函数即可处理
2、正负：通过判断第一位，使用变量储存符号即可
3、非数字字符：对每一位进行判断，非数字则结束
4、越界：通过提前预判，判断拼接后是否大于阈值，进行处理

```java
public class Solution {
    public int StrToInt (String s) {
        // write code here
        char[] array = s.trim().toCharArray();
        if(array.length==0){
            return 0;
        }
        int sign = 1;
        int res = 0;
        int i = 0;
        
        if(array[i] == '+' || array[i] == '-'){
            sign = array[i++] == '+' ? 1 : -1;
        }
        while(i < array.length){
            char cur = array[i];
            if(cur < '0' || cur>'9'){
                break;
            }
            if (res >= Integer.MAX_VALUE / 10) {
                if(res > Integer.MAX_VALUE / 10){
                    return sign==1 
                            ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                }
                if(res == Integer.MAX_VALUE / 10){
                    if(sign == 1 && (cur - '0') > 7){
                        return Integer.MAX_VALUE;
                    }else if(sign == -1 && (cur - '0') > 8){
                        return Integer.MIN_VALUE;
                    }
                }
            }
            res = res * 10 + (cur - '0');
            i++;
        }
        return sign * res;
    }
}
```

### 最长公共前缀

```java
// 方法一：先取第一个字符串当做他们的公共前缀
// 然后找出他和第2个字符串的公共前缀，然后再用这个找出的公共前缀分别和第3个，第4个……判断
public String longestCommonPrefix(String[] strs) {
    //边界条件判断
    if (strs == null || strs.length == 0)
        return "";
    //默认第一个字符串是他们的公共前缀
    String pre = strs[0];
    int i = 1;
    while (i < strs.length) {
        //不断的截取
        while (strs[i].indexOf(pre) != 0)
            pre = pre.substring(0, pre.length() - 1);
        i++;
    }
    return pre;
}

// 方法二：按照字典序排序之后比较字典序最小的子串和字典序最大的子串的相同部分，
// 得到的最长公共前缀就是所有字符串的最长公共前缀
public class Solution {
    public String longestCommonPrefix (String[] strs) {
        int len = strs.length;
        if(len==0) return "";
        Arrays.sort(strs);
        //枚举第一个最小的子串和最后一个最大的子串
        int i = 0;
        String a = strs[0];
        String b = strs[len-1];
        for(i = 0;i < a.length()&&a.charAt(i)==b.charAt(i);i++);
        return a.substring(0,i);
    }
}
```

### 回文数字

```java
// 方法一：双指针
import java.util.*;
public class Solution {
    /**
     * 
     * @param x int整型 
     * @return bool布尔型
     */
    public boolean isPalindrome (int x) {
        if(x<0) return false;
        // 转换成字符串
        String xs = String.valueOf(x);
        // 利用双指针
        int left = 0;
        int right = xs.length()-1;
        // 比较字符串的头部和尾部是否相同
        while(left < right){
            // 不相同直接返回
            if(xs.charAt(left) != xs.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}

// 方法二：翻转数字
public class Solution {
    /**
     * 
     * @param x int整型 
     * @return bool布尔型
     */
    public boolean isPalindrome (int x) {
        // write code here
        if(x<0) return false;
        int reverse = 0;
        int tmp = x;
        while(tmp>0){
            int div = tmp%10;
            // 判断是否会溢出
            if(reverse >= Integer.MAX_VALUE/10 && div > 7) return false;
            // 获得反向数字
            reverse = reverse*10 + div;
            tmp = tmp/10;
        }
        return x == reverse;
    }
}
```

### 字符串变形（反序，大写）

利用split切割为String数组
String数组从后往前遍历，拿到具体的String从0到str.length()遍历，并判断大小写然后转换
需要注意的地方就是s.split(" ",-1)，limit需要设置为-1来不舍弃最后的空串

```java
import java.util.*;

public class Solution {
    public String trans(String s, int n) {
        // write code here
        String[] strArr = s.split(" ",-1); // 注意这里limit为-1,不舍弃最后的空串
        StringBuilder sb = new StringBuilder();
        for(int i = strArr.length - 1; i >= 0; i--) {
            for(int j = 0; j < strArr[i].length(); j++) {
                if(Character.isUpperCase(strArr[i].charAt(j))) {
                    sb.append(Character.toLowerCase(strArr[i].charAt(j)));
                } else {
                    sb.append(Character.toUpperCase(strArr[i].charAt(j)));
                }
            }
            if(i != 0) {
                sb.append(" ");
            }
        }
        return sb.toString();
    }
}
```

### 最大值（数组拼接最大数）

```java
import java.util.*;
public class Solution {
    /**
     * 最大数
     * @param nums int整型一维数组
     * @return string字符串
     */
    public String solve (int[] nums) {
        String[] strArr = new String[nums.length];
        for (int i = 0 ; i < nums.length ; i++) {
            strArr[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strArr, 
        (o1, o2) -> Integer.parseInt(o2 + o1) - Integer.parseInt(o1 + o2));
        StringBuilder maxString = new StringBuilder();
        if (strArr[0].equals( "0")) {
            return "0";
        }
        for (int i = 0 ; i < strArr.length; i++) {
            maxString.append(strArr[i]);
        }
        return maxString.toString();
    }
}
```

### 验证ip地址

```java
public String validIPAddress(String IP) {
    return validIPv4(IP) 
        ? "IPv4" : (validIPv6(IP) ? "IPv6" : "Neither");
}

private boolean validIPv4(String IP) {
    String[] strs = IP.split("\\.", -1);
    if (strs.length != 4) {
        return false;
    }

    for (String str : strs) {
        if (str.length() > 1 && str.startsWith("0")) {
            return false;
        }
        try {
            int val = Integer.parseInt(str);
            if (!(val >= 0 && val <= 255)) {
                return false;
            }
        } catch (NumberFormatException numberFormatException) {
            return false;
        }
    }
    return true;
}

private boolean validIPv6(String IP) {
    String[] strs = IP.split(":", -1);
    if (strs.length != 8) {
        return false;
    }

    for (String str : strs) {
        if (str.length() > 4 || str.length() == 0) {
            return false;
        }
        try {
            int val = Integer.parseInt(str, 16);
        } catch (NumberFormatException numberFormatException) {
            return false;
        }
    }
    return true;
}
```

### 二进制中1的个数

将数字与1进行与运算，返回结果为1则表明数字二进制最后一位是1，通过对不断数字右移运算判断有多少个1。

```java
public class Solution {
    // replace替换
    public int NumberOf1(int n) {
        return Integer.toBinaryString(n).replace("0","").length();
    }

    // 遍历字符串记录
    public int NumberOf1(int n) {
        String str = Integer.toBinaryString(n);
        int length = str.length();
        int count = 0;
        for (int i=0; i<length; i++) {
            if (str.charAt(i) == '1') {
                count++;
            }
        }
        return count;
    }
}

public class Solution {
    public int NumberOf1(int n) {
        int res = 0;
        while (n != 0) {
            res += n & 1;
            n >>>= 1;
        }
        return res;
    }
}
```

### 第一个只出现一次的字符

```java
import java.util.*;
public class Solution {
    public static int FirstNotRepeatingChar(String str) {
        int[] map = new int[58];
        char[] chs = str.toCharArray();
        for(int i = 0; i < chs.length; i++){
            map[chs[i] - 'A'] ++;
        }
        int res = -1;
        for(int i = 0; i < chs.length; i++){
            if(map[chs[i] - 'A'] == 1){
                res = i;
                break;
            }
        }
        return res;
    }
}
```

## 其他编程题（golang、java）

### 单例模式

双重否定单例模式：即可以保证线程的安全性
（避免两个线程同时进入到 synchronized (Singleton.class)时，
线程1先获取到了锁，释放后，线程2执行，如果没有第二次空的判断，会导致多次创建对象），
也可以实现只有第一次创建new的时候才会执行到同步代码块中的代码，提高了效率。

- java

```java
// 方法一
//优点：线程安全，volatile关键词主要是保证多线程之间的可见性，
// 保证线程在每次取值volatile变量都是最新值
//volatile关键字主要是禁止命令重排序的，但是volatile不是原子性的
public class Singleton {
 private static volatile Singleton instance = null;
    private Singleton() {}
    public static Singleton getInstance() {
        if (null == instance) {
            synchronized (Singleton.class) {
                if (null == instance) {
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

// 方法二
public class Singleton {
    private Singleton() {}
    private static Singleton getInstance() {
        return SingletonHolder.instance;
    }
    private static class SingletonHolder {
        //静态变量值会初始化一次
        private static Singleton instance = new Singleton();
    }
}
```

- go

```go
package main

import (
    "fmt"
    "sync"
)

var lock = &sync.Mutex{} // 创建互锁
type Singleton struct {}    // 创建结构体

var singletonInstance *Singleton // 创建指针

func getInstance() *single {
    if singletonInstance == nil { //!!!注意这里check nil了两次
        lock.Lock()
        defer lock.Unlock()
        if singletonInstance == nil {
            fmt.Println("创建单例")
            singletonInstance = &Singleton{}
        } else {
            fmt.Println("单例对象已创建")
        }
    } else {
        fmt.Println("单例对象已创建")
    }
    return singletonInstance
}
```

### 实现线程安全的生产者消费者

- java

https://blog.csdn.net/u010983881/article/details/78554671

- golang

https://blog.csdn.net/weixin_50005436/article/details/123065703

### 一个10G的文件，里面全部是自然数，一行一个，乱序排列，对其排序。在32位机器上面完成，内存限制为 2G（bitmap原理知道吗？）

首先，10G文件是不可能一次性放到内存里的。这类问题一般有两种解决方案：

- 将10G文件分成多个小文件，分别排序，最后合并一个文件；
- 采用bitmap

如果面试大数据类岗位，可能面试官就想考察你对Mapreduce熟悉程度，要采用第一种merge and sort。

如果是算法类岗位，就要考虑bitmap，但需要注意的是bitmap**不能对重复数据进行排序**。这里我们详细介绍一下：

定量分析一下，32位机器自然数有2^32个，用一个bit来存放一个整数，那么所需的内存是，
`2^32/(8<<20) = 512MB` ，这些数存放在文件中，一行一个，需要20G容量，
所以题目问10G文件，只需要256MB内存就可以完成。

bitmap实现具体分为两步：插入一个数，和排序。

```go
type BitMap struct {
	vec  []byte
	size int
}

func New(size int) *BitMap {
	return &BitMap{
		size: size,
		vec:  make([]byte, size),
	}
}

func (bm *BitMap) Set(num int) (ok bool, err error) {
	if num/8 >= bm.size {
		return false, errors.New("the num overflows the size of bitmap")
	}
	bm.vec[num/8] |= 1 << (num % 8)
	return true, nil
}

func (bm *BitMap) Exist(num int) bool {
	if num/8 >= bm.size {
		return false
	}
	return bm.vec[num/8]&(1<<(num%8)) > 0
}

func (bm *BitMap) Sort() (ret []int) {
	ret = make([]int, 0)
	for i := 0; i < (8 * bm.size); i++ {
		if bm.Exist(i) {
			ret = append(ret, i)
		}
	}
	return
}
```

### 实现使用字符串函数名，调用函数

思路：采用反射的Call方法实现。

```go 
package main
import (
	"fmt"
    "reflect"
)

type Animal struct{

}

func (a *Animal) Eat(){
    fmt.Println("Eat")
}

func main(){
    a := Animal{}
    reflect.ValueOf(&a).MethodByName("Eat").Call([]reflect.Value{})

}
``` 

### 负载均衡算法。（一致性哈希）

```go
package main

import (
	"fmt"
	"sort"
	"strconv"
)

type HashFunc func(key []byte) uint32

type ConsistentHash struct {
	hash       HashFunc
	hashvals   []int
	hashToKey  map[int]string
	virtualNum int
}

func NewConsistentHash(virtualNum int, fn HashFunc) *ConsistentHash {
	return &ConsistentHash{
		hash:       fn,
		virtualNum: virtualNum,
		hashToKey:  make(map[int]string),
	}
}

func (ch *ConsistentHash) AddNode(keys ...string) {
	for _, k := range keys {
		for i := 0; i < ch.virtualNum; i++ {
			conv := strconv.Itoa(i)
			hashval := int(ch.hash([]byte(conv + k)))
			ch.hashvals = append(ch.hashvals, hashval)
			ch.hashToKey[hashval] = k
		}
	}
	sort.Ints(ch.hashvals)
}

func (ch *ConsistentHash) GetNode(key string) string {
	if len(ch.hashToKey) == 0 {
		return ""
	}
	keyhash := int(ch.hash([]byte(key)))
	id := sort.Search(len(ch.hashToKey), func(i int) bool {
		return ch.hashvals[i] >= keyhash
	})
	return ch.hashToKey[ch.hashvals[id%len(ch.hashvals)]]
}

func main() {
	ch := NewConsistentHash(3, func(key []byte) uint32 {
		ret, _ := strconv.Atoi(string(key))
		return uint32(ret)
	})
	ch.AddNode("1", "3", "5", "7")
	testkeys := []string{"12", "4", "7", "8"}
	for _, k := range testkeys {
		fmt.Printf("k:%s,node:%s\n", k, ch.GetNode(k))
	}
}
```

### （Goroutine）有三个函数，分别打印"cat", "fish","dog"要求每一个函数都用一个goroutine，按照顺序打印100次

此题目考察channel，用三个无缓冲channel，如果一个channel收到信号则通知下一个。

```go
package main

import (
	"fmt"
	"time"
)

var dog = make(chan struct{})
var cat = make(chan struct{})
var fish = make(chan struct{})

func Dog() {
	<-fish
	fmt.Println("dog")
	dog <- struct{}{}
}

func Cat() {
	<-dog
	fmt.Println("cat")
	cat <- struct{}{}
}

func Fish() {
	<-cat
	fmt.Println("fish")
	fish <- struct{}{}
}

func main() {
	for i := 0; i < 100; i++ {
		go Dog()
		go Cat()
		go Fish()
	}
	fish <- struct{}{}

	time.Sleep(10 * time.Second)
}
```

- Java 实现

https://www.cnblogs.com/jyx140521/p/6747750.html

### 两个协程交替打印10个字母和数字

思路：采用channel来协调goroutine之间顺序。

主线程一般要waitGroup等待协程退出，这里简化了一下直接sleep。

```go
package main

import (
	"fmt"
	"time"
)

var word = make(chan struct{}, 1)
var num = make(chan struct{}, 1)

func printNums() {
	for i := 0; i < 10; i++ {
		<-word
		fmt.Println(1)
		num <- struct{}{}
	}
}
func printWords() {
	for i := 0; i < 10; i++ {
		<-num
		fmt.Println("a")
		word <- struct{}{}
	}
}

func main() {
	num <- struct{}{}
	go printNums()
	go printWords()
	time.Sleep(time.Second * 1)
}
```

- Java 实现

```java
package com.lutongnet.util;
 
import org.junit.Test;
 
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedTransferQueue;
import java.util.concurrent.TransferQueue;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.LockSupport;
import java.util.concurrent.locks.ReentrantLock;
 
/**
 * @author mifei
 * @version 1.0.0
 * @description 多线程测试
 * @date 2020-11-28 15:18
 */
public class CommonThreadTest {
 
    Thread t1 = null;
    Thread t2 = null;
 
    /**
     * 测试Synchronized的wait和notify写法
     */
    @Test
    public void testSynchronized() {
        Object o = new Object();
        char [] letterArray = "ABCDEFGHIJ".toCharArray();
        char [] numbberArray = "1234567890".toCharArray();
 
        t1 = new Thread(()->{
            synchronized (o) {
                for (char c: letterArray) {
                    System.out.println("字母：" + c);
                    try {
                        o.notify();
                        o.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                o.notify();
            }
        });
 
        t2 = new Thread(()->{
            synchronized (o) {
                for (char c: numbberArray) {
                    System.out.println("数字：" + c);
                    try {
                        o.notify();
                        o.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                o.notify();
            }
        });
 
        t1.start();
        t2.start();
    }
 
    /**
     * 测试ReenTrantLock写法
     */
    @Test
    public void testReenTrantlock() {
        char [] letterArray = "ABCDEFGHIJ".toCharArray();
        char [] numberArray = "1234567890".toCharArray();
 
        Lock lock = new ReentrantLock();
        Condition letterCondition = lock.newCondition();
        Condition numberCondition = lock.newCondition();
 
        new Thread(()->{
            try {
                lock.lock();
                for (char c: letterArray) {
                    System.out.println("字母：" + c);
                    numberCondition.signal();
                    letterCondition.await();
                }
                numberCondition.signal();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }, "t1").start();
 
        new Thread(()->{
            try {
                lock.lock();
                for (char c: numberArray) {
                    System.out.println("数字：" + c);
                    letterCondition.signal();
                    numberCondition.await();
                }
                letterCondition.signal();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                lock.unlock();
            }
        }, "t2").start();
    }
 
    /**
     * 测试LockSupport写法
     */
    @Test
    public void testLockSupport() {
        char [] letterArray = "ABCDEFGHIJ".toCharArray();
        char [] numberArray = "1234567890".toCharArray();
 
        t1 = new Thread(()->{
            for (char c: letterArray) {
                System.out.println("字母：" + c);
                LockSupport.unpark(t2);
                LockSupport.park();
            }
        });
 
        t2 = new Thread(()->{
            for (char c: numberArray) {
                LockSupport.park();
                System.out.println("数字：" + c);
                LockSupport.unpark(t1);
            }
        });
 
        t1.start();
        t2.start();
    }
 
    /**
     * 测试BlockingQueue写法
     */
    @Test
    public void testBlockingQueue() {
        char [] letterArray = "ABCDEFGHIJ".toCharArray();
        char [] numberArray = "1234567890".toCharArray();
 
        BlockingQueue<String> q1 = new ArrayBlockingQueue(1);
        BlockingQueue<String> q2 = new ArrayBlockingQueue(1);
 
        new Thread(()->{
            for (char c: letterArray) {
                System.out.println("字母：" + c);
                try {
                    q1.put("ok");
                    q2.take();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
 
            }
        }, "t1").start();
 
        new Thread(()->{
            for (char c: numberArray) {
                try {
                    q1.take();
                    System.out.println("数字：" + c);
                    q2.put("ok");
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }, "t2").start();
    }
 
    /**
     * 测试AtomicInteger写法
     */
    @Test
    public void testAtomicInteger() {
        AtomicInteger threadNo = new AtomicInteger(1);
 
        char [] letterArray = "ABCDEFGHIJ".toCharArray();
        char [] numberArray = "1234567890".toCharArray();
 
        new Thread(()->{
            for (char c: letterArray) {
                while (threadNo.get() != 1) {}
                System.out.println("字母：" + c);
                threadNo.set(2);
            }
        }, "t1").start();
 
        new Thread(()->{
            for (char c: numberArray) {
                while (threadNo.get() != 2) {}
                System.out.println("数字：" + c);
                threadNo.set(1);
            }
        }, "t2").start();
    }
 
    /**
     * 测试TransferQueue写法
     */
    @Test
    public void testTransferQueue() {
        char [] letterArray = "ABCDEFGHIJ".toCharArray();
        char [] numberArray = "1234567890".toCharArray();
 
        TransferQueue<Character> queue = new LinkedTransferQueue<>();
        new Thread(()->{
            try {
                for (char c : letterArray) {
                    System.out.println("数字：" + queue.take());
                    queue.transfer(c);
                }
 
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, "t1").start();
 
        new Thread(()->{
            try {
                for (char c : numberArray) {
                    queue.transfer(c);
                    System.out.println("字母：" + queue.take());
                }
 
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, "t2").start();
 
    }
}
```

### 启动 2个groutine 2秒后取消， 第一个协程1秒执行完，第二个协程3秒执行完。

思路：采用`ctx, _ := context.WithTimeout(context.Background(), time.Second*2)`实现2s取消。
协程执行完后通过channel通知，是否超时。

```go
package main

import (
	"context"
	"fmt"
	"time"
)

func f1(in chan struct{}) {

	time.Sleep(1 * time.Second)
	in <- struct{}{}

}

func f2(in chan struct{}) {
	time.Sleep(3 * time.Second)
	in <- struct{}{}
}

func main() {
	ch1 := make(chan struct{})
	ch2 := make(chan struct{})
	ctx, _ := context.WithTimeout(context.Background(), 2*time.Second)

	go func() {
		go f1(ch1)
		select {
		case <-ctx.Done():
			fmt.Println("f1 timeout")
			break
		case <-ch1:
			fmt.Println("f1 done")
		}
	}()

	go func() {
		go f2(ch2)
		select {
		case <-ctx.Done():
			fmt.Println("f2 timeout")
			break
		case <-ch2:
			fmt.Println("f2 done")
		}
	}()
	time.Sleep(time.Second * 5)
}
```


### 当select监控多个chan同时到达就绪态时，如何先执行某个任务？

可以在子case再加一个for select语句。

```go
func priority_select(ch1, ch2 <-chan string) {
	for {
		select {
		case val := <-ch1:
			fmt.Println(val)
		case val2 := <-ch2:
		priority:
			for {
				select {
				case val1 := <-ch1:
					fmt.Println(val1)

				default:
					break priority
				}
			}
			fmt.Println(val2)
		}
	}

}
```