[数据结构与算法]一段话总结一道题：剑指offer75道题

03：数组中重复的数字

前提：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内
遍历数组中每一个数字num，并且将这个数字作为索引，将取到的数字nums[num]进行标记进行标记，当一个待标记的nums[num]已经是一个负数，说明这个num就是重复的数字

    public int findRepeatNumber(int[] nums) {
        for(int i=0;i<nums.length;i++){
            int cur=(nums[i]<0)?-nums[i]:nums[i];
            if(nums[cur]<0)return cur;
            else{
                nums[cur]*=-1;
            }
        }
        return 0;
    }

04：二维数组中的查找

前提：二维数组的每一行都是从左到右递增的，每一列都是从上到下递增的。
将初始坐标定位左下角，那么上方就是依次递减的，下方就是依次递增的，这样一来就可以按照双指针去缩减范围，逼近目标值

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int m,n;
        if((n=matrix.length)==0||(m=matrix[0].length)==0)return false;
        int n0=n-1;
        int m0=0;
        while(m0<m&&n0>=0){
            if(matrix[n0][m0]==target)return true;
            else if(matrix[n0][m0]>target){
                n0--;
            }else{
                m0++;
            }
        }
        return false;
    }

05:替换空格

不推荐直接使用库函数。
先统计空格的数量，然后扩大相应的倍数，并创建相应大小的输出数组，然后从后往前遍历字符串并填充数组。

    public String replaceSpace(String s) {
        int count=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)==' ')count++;
        }
        char[] res =new char[s.length()+count*2];
        int index = res.length-1;
        for(int i=s.length()-1;i>=0;i--,index--){
            if(s.charAt(i)==' '){
                res[index--]='0';
                res[index--]='2';
                res[index]='%';
            }else{
                res[index]=s.charAt(i);
            }
        }
        return new String(res);
    }

06：从头到尾打印链表

前提：链表长度的范围在0到1万。
创建一个大小为10000的桶，遍历一遍链表，将链表的值装入桶中，然后再逆序遍历一遍桶填充结果数组即可。（代码直接根据index的偏移量进行拷贝了）
另一种方式是使用栈结构。

    public int[] reversePrint(ListNode head) {
        int[] res =new int[10000];
        int index=res.length-1;
        while(head!=null){
            res[index--]=head.val;
            head=head.next;
        }
        int[] ans =new int[10000-index-1];
        System.arraycopy(res,index+1,ans,0,ans.length);
        return ans;
    }

07：重建二叉树（中序+前序）

中序对应 左子树节点-根-右子树节点，而前序对应 根-左子树节点-右子树节点。将中序数组中的值-索引的关系保存起来（map），然后进行递归调用。每次从前序数组拿到一个节点（每次拿到的节点都可以看作一个局部的、子树级别的根），然后从map中可以取出该值在中序数组中对应的位置，根据这个位置可以确定左子树和右子树的范围。
假如当前根结点在前序数组的位置是index，而在中序数组的位置是inorder_index，那么inorder_index - left就是左子树的范围（左子树的节点数量），index加上左子树的范围就是右子树的“根结点”的位置，而左子树的根结点位置就是index+1。
而中序数组中，左子树的范围其实就是[left , inorder_index-1]，右子树的范围是[inorder_index+1 , right]

总结就是：记录中序数组的值-索引映射关系，深度遍历前序数组，取出当前的根结点，以及在中序数组中对应的索引 inorder_index。通过这个索引不但可以划分出左子树和右子树的范围，而且可以计算出下一轮左子树和右子树的根结点。后面的流程就是不断划分中序数组，并从前序数组取值，递归建立树结构，每一层的任务仅仅是负责建立当前的根结点，并初始化左右子树结构。

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        if(len==0)return null;
        Map<Integer,Integer> map = new HashMap<>();//值-inorder索引
        //根据前序找根，根据中序划定范围
        for(int i=0;i<len;i++){
            map.put(inorder[i],i);
        }
        TreeNode root=build(preorder,map,0,len-1,0);
        return root;
    }
    private TreeNode build(int[] preorder,Map<Integer,Integer> map,int left,int right,int index){
        if(left>right)return null;
        int curValue=preorder[index];//当前节点值 map.get(curValue)得到的是索引
        TreeNode root =new TreeNode(curValue);
        int inorderIndex = map.get(curValue);
            int nextLeftIndex=index+1;  //下一个preOrder坐标（左子树根）
            int nextRightIndex=nextLeftIndex+(inorderIndex-left);//下一个preOrder坐标（右子树根）
            root.left=build(preorder,map,left,inorderIndex-1,nextLeftIndex);
            root.right=build(preorder,map,inorderIndex+1,right,nextRightIndex);
        return root;
    }

09:双栈实现队列

使用两个栈A和B，一个栈实现队头，一个实现队尾。添加元素时往A中添加，如[1,2,3]，如果队列要删除元素，删除的应该是1，但是栈的特点只能删除3，于是使用另外一个栈B接收删除的元素[3,2,1]，如果栈B不空，每次从栈B删除，否则就将栈A的元素全部导入栈B中,再执行删除

    public int deleteHead() {
        if(!stack2.isEmpty()){
            return stack2.pop();    //stack2的栈顶就是队列的头
        }
        if(stack1.isEmpty()){
            return -1;
        }
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }

10:斐波那契、青蛙跳台阶

最简单的动态规划，不做任何解释。注意特殊情况判断，记住状态转移方程dp[i]=dp[i-1]+dp[i-2]

    public int fib(int n) {
        if(n<2)return n;
        int[] dp =new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=(dp[i-1]+dp[i-2])%1000000007;
        }
        return dp[n];
    }

11：旋转数组的最小数字

以右边元素作为判断的基点。
以0123456为例。
如果numbers[mid]<numbers[right]如5601234，说明[mid…right]局部有序，向左半边（不排除mid）继续搜寻，因为右半边是升序，无法找到最小数字。
如果numbers[mid]>numbers[right]如3456012，说明[left…mid]是局部有序的，那么我们应该继续向右半部（mid一定不是最小的，排除）分搜索。
如果numbers[mid]==numbers[right]，[mid…right]这一步存在重复，right–。
选择数组题型基本都是二分法，通过mid位置元素与right位置元素（我一般选right）比较后，确定一个局部有序的范围和剩下的范围，然后不断执行二分

    public int minArray(int[] numbers) {
        if(numbers.length==1)return numbers[0];
        int left=0;
        int right=numbers.length-1;
        while(left<right){
            int mid =(right-left)/2+left;
            //右边比中间大，则【中...右】有序
            if(numbers[mid]<numbers[right]){
                right=mid;
            }else if(numbers[mid]>numbers[right]){
                left=mid+1;
            }else{
                right--;
            }
        }
    return numbers[left];
    }

12：矩阵中的路径

经典的矩阵搜索题型，其实就是矩阵的搜索，写法很固定。
对每个点调用check函数，如果能够找到符合要求的路径就返回true

    public boolean exist(char[][] board, String word) {
        int m =board.length;
        int n =board[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(check(board,i,j,word,0)){
                    return true;
                }
            }
        }
        return false;
    }

check函数无法就是【1】判断当前坐标是否合法（非法分支的出口）一个是坐标是否越界、一个是当前坐标是否已经被访问、另一部分则是和本题相关的判断逻辑【2】复用矩阵或者建立布尔矩阵，记录某个点是否被搜索，同时在进入下一次搜索前进行标记，搜索完成后取消标记，防止对其他同层搜索造成干扰【3】四个方向搜索，有任意一个方向能满足结果就返回true，全不能满足结果那么当前层的搜索最终结果就是false

 private boolean check(char[][] board,int i,int j,String word,int index){
        if(index>=word.length())return true; // 路径结算点
        if(i>=board.length||i<0||j>=board[0].length||j<0)return false;
        char cur = board[i][j];
        if(cur=='.')return false;
        if(cur==word.charAt(index)){
            board[i][j]='.';
            if(
                check(board,i+1,j,word,index+1)||
                check(board,i-1,j,word,index+1)||
                check(board,i,j-1,word,index+1)||
                check(board,i,j+1,word,index+1)
            ){
                return true;
            }
            board[i][j]=cur;
        }
        return false;
    }

这类题一般就是DFS或BFS，不过一般DFS写的比较顺手。

13：机器人运动范围

题意：从[0,0]开始走，能走多少个格子。
先明确机器人的运动范围[0,0]到[99,99]，运动范围是上下左右，而且坐标数位相加如果>=k就是不合法的。那么仍然可以套用矩阵搜索的模型。
没走一个格仍然是对坐标的校验，本题中的坐标最多是2位数，所以直接就可以把坐标位数和计算出来，与K进行比较。然后后面的依旧是矩阵搜索的套路。

    //坐标范围【0,0】~【99,99】
    public int movingCount(int m, int n, int k) {
        boolean[][] isVisited =new boolean[m][n];
        return dfs(m,n,0,0,k,0,isVisited);
    }
    //以某一个方向进行行走，之后同一维度子问题不再计算已经走过的块数
    private int dfs(int m,int n,int i,int j,int k,int num,boolean[][] isVisited){
        if(i>=m||i<0||j>=n||j<0||isVisited[i][j])return 0;
        if(i%10+i/10+j%10+j/10>k)return 0;
        //当前坐标成立，计数加一
            isVisited[i][j]=true;
            int a=dfs(m,n,i+1,j,k,num+1,isVisited);
            int b=dfs(m,n,i-1,j,k,num+1,isVisited);
            int c=dfs(m,n,i,j+1,k,num+1,isVisited);
            int d=dfs(m,n,i,j-1,k,num+1,isVisited);
        return a+b+c+d+1;	//当前格子对应+1
    }

14：剪绳子1

dp这东西最难的就是确定dp[i]的意义和推导出转移方程，本文能做到就是总结它的动态规划数组和状态转移方程

dp[i] 长度为i的绳子，能够剪出的最大乘积。其中dp[0]和dp[1]没有意义。
一个长度为i的绳子，剪一刀得到一个j长度的绳子和一个i-j长度的绳子。其中可以选择是否继续对i-j的绳子剪或不剪（其中j是枚举1…i-1的长度），而不剪的乘积为j*(i-j)，剪的最大乘积为j*dp[i-j]。
状态转移方程即为:dp[i]=max{dp[i] , j*dp[i-j] , j*(i-j)}

    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];//剪i长绳子的最大乘积
        for (int i = 2; i <= n; i++) {
            //优化：少走一半路（1*2=2*1）
            for(int j=1;j<=i/2;j++){
                dp[i]=Math.max(dp[i],j*(i-j));//就剪一刀
                dp[i]=Math.max(dp[i],j*dp[i-j]);//接着剪
            }
        }
        return dp[n];
    }

14：剪绳子2

该题相对于上一题扩大了数据规模，不能使用n^2了，使用贪心的解法。
如果绳子长度大于4，将绳子尽可能分成长度为3的小段。
一旦剩余的绳子长度小于等于4，就不再剪了，将剩余的绳子看作尾段。

    //10 =3*3*4
    //19 = 3*3*3*3*3*4
    public int cuttingRope(int n) {
        int temp=1000000007;
        if(n<4)return n-1;
        if(n==4)return n;
        long res=1;
        while(n>4){//大于4时，依次切出长度为3的小段
            res*=3;
            res%=temp;
            n-=3;
        }
        return (int)(res*n%temp);
    }

15：二进制中1的数

JDK中有bitCount的函数可以得出结果，但是不推荐使用，也不推荐对二进制字符串进行遍历。本题考察位运算。
其实就是一个非常有用的公式，可以消除二进制末尾的1—— n&=(n-1)。例如4（0100）而3（0011）二者相与得到0000

    public int hammingWeight(int n) {
        int res=0;
        while(n!=0){//当1全被消除，那么统计工作也就完毕了
            res++;
            n&=(n-1);
        }
        return res;
    }

16：实现pow（x,n）

以pow(2,4)为例，暴力递归的话，是4个2而相乘，总共调用4次，属于一头减少。
而快速幂属于两头变化，调用log2(4)=2次

public double myPow(double x, int n) {
        //这里将参数转换为long类型
        long n_=n;
        if(n_<0){
            x=1/x;
            n_*=-1;
        }
        return myPow2(x,n_);
    }
    public double myPow2(double x, long n) {
        if(n==0)return 1;
        if(n==1)return x;       
        if(n%2==1){
        //奇数情况，单独乘上一个x
            return myPow2(x,n-1)*x;
        }else{
        //乘数加倍，开方减半
            return myPow2(x*x,n/2);
        }
    }

另一种写法：不改变乘数的入参，仅将开方折半，并且在返回结果处加倍

    public double myPow2(double x, long n) {
        if(n==0)return 1;
        if(n==1)return x;   
        double temp = myPow2(x,n/2);    
        if(n%2==1){
            return temp*temp*x;
        }else{
            return temp*temp;
        }
    }

17:打印1到n的N位数

假如要打印3，那么打印的上限就(3^10-1)

    public int[] printNumbers(int n) {
        int size =(int)(Math.pow(10,n)-1);
        int[] res =new int[size];
        for(int i=size-1;i>=0;i--){
            res[i]=i+1;
        }
        return res;
    }

18:删除链表

链表的题目，80%都是送分的，单链表、给一个头指针和一个需要删除的值，那把要删除的那个值的前一个节点找不出不就行了。

    public ListNode deleteNode(ListNode head, int val) {
        if(head.next==null)return null;
        if(head.val==val)return head.next;
        ListNode temp =head;
        while(temp.next!=null){
            if(temp.next.val==val){
                temp.next=temp.next.next;
                break;
            }
            temp=temp.next;
        }
        return head;
    }

19：正则表达式匹配

本题是一个比较难的困难题，需要考虑很多边界情况。
c、空字符串都可以与c*匹配上，c.可以与c或cc匹配上。
dp[i][j]就是源字符串s[0…i-1]这长度为i的字符串能否与p[0…j-1]这长度为j的模式串进行正则表达式匹配。

int m =s.length();
        int n =p.length();
        boolean[][] dp =new boolean[m+1][n+1];

这个题画个表会更好理解一些，其中空串能够匹配，因此初始值dp[0][0]就是true。如果拿一个空串与源串进行进行匹配一定是false，因此dp[i][0]这一列全是false。

双循环，外层遍历源字符串，内层遍历匹配字符串。其中点字符可以看作任意字符，如果**p.charAt(j-1)等于s.charAt(i-1)或p.charAt(j-1)==’.’**都算作s字符串的当前位置匹配成功。
而星号比较特殊，因为C*（占用两个字符）既可以看作一个若干长度字符，也可以看作占用一个位置的空字符。
因此，当遍历到一个*时，可以有两种选择：将C*看作一个字符空串，或者看作一个长串。如果我们遇到一个星号：
【1】看作空串即将p[j-2…j-1]位置看作空，而和p[j-3]继续比较，而s[0…i-1]和p[0…j-3]的匹配结果就是dp[i][j-2]，在计算dp[i][j]之前就已经被计算出来了。
【2】如果看作非空串，则将字符s[i-1]去和p[j-2]比较，如果匹配成功说明s[i-1]和p[j-2…j-1]能够匹配，而s[0…i-2]的部分也需要和p[0…j-1]能够匹配才能保证s[0…i-1]和p[0…j-1]能够匹配

    public boolean isMatch(String s, String p) {
        int m =s.length();
        int n =p.length();
        boolean[][] dp =new boolean[m+1][n+1];

        //双空
        dp[0][0]=true;
        //匹配串可以变成空的情况
        for(int i=2;i<=n;i++){
            if(dp[0][i-2]&&p.charAt(i-1)=='*')
                dp[0][i]=true;
        }

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(p.charAt(j-1)=='*'){
                    //将p[j-2...j-1]视作空字符串，直接和p[0...j-3]进行匹配
                    // 这部分结果保存在dp[i][j-2]
                    if(dp[i][j-2]){
                        dp[i][j]=true;
                    }
                    //将*看作重复，只需将当前s[i-1]和*前面的字符p[j-2]进行比较
                    else if(p.charAt(j-2)==s.charAt(i-1)||p.charAt(j-2)=='.'){
                        //s[i-1]可以匹配p[j-2...j-1]，而s[0...i-1]是否匹配p[0...j-1]
                        //还需要继续将s[0...i-2]和p[0...j-1]匹配，这部分保存在dp[i-1][j]
                        dp[i][j]=dp[i-1][j];
                    }
                }else{
                    //没有*号，那么就是一个常规的子串判断问题
                    //s[i-1]匹配p[j-1]，如果需要推广到s[0...i]匹配p[0...j]
                    //还需要判断s[0...i-2]和p[0...j-2]，这部分结果保存在dp[i-1][j-1]
                    if(s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='.'){
                        dp[i][j]=dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[m][n];
    }

20：表示数值的字符串

这种模拟题基本都是面向测试编程，提交率都比较低。因此这里只强调细节。
设置三个布尔值，标记数字、点、自然对数的出现状态，在遍历字符串的过程中更新这些状态变量。
【1】去除前导空格
【2】自然对数标志E只能出现一次，而且不能出现于数字出现之前。
【3】点只能出现一次，不能出现在自然对数E之后
【4】加号和减号只能出现在第一位或者在E的左边紧邻
【5】扫描完毕，应该以数字结尾

    public boolean isNumber(String s) {
        if(s==null||s.length()==0)return false;

        boolean numFlag = false;//数字结尾
        boolean dotFlag = false;//点
        boolean eFlag = false;

        s=s.trim();//去掉前空格

        for(int i=0;i<s.length();i++){
            if(s.charAt(i)>='0'&&s.charAt(i)<='9'){
                numFlag=true;
            }else if(s.charAt(i)=='E'||s.charAt(i)=='e'){
                //e只能出现一次
                if(!eFlag&&numFlag){
                    eFlag=true;
                    numFlag=false;
                }else return false;
            }else if(s.charAt(i)=='.'){
                //点只能出现一次,不能在e后面，允许3.  .1
                if(!dotFlag&&!eFlag){
                    dotFlag=true;
                }else return false;
            }else if(s.charAt(i)=='+'||s.charAt(i)=='-'){
                if(!(i==0||s.charAt(i-1)=='E'||s.charAt(i-1)=='e'))//符号要么在第一位，要么和e紧邻
                    return false;
                numFlag=false;
            }else return false;

        }
        return numFlag;
    }

21 ： 奇偶位置调整

双指针，每轮从左边找到一个奇数，右边找到一个偶数，然后交换。

    public int[] exchange(int[] nums) {
        if(nums.length<2)return nums;
        int left=0;
        int right=nums.length-1;
        while(left<right){

            while(left<right&&(nums[left]&1)==1)left++;
            if(left>=right)break;
            while(left<right&&(nums[right]&1)==0)right--;
            if(left>=right)break;

            int temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
            
            left++;
            right--;
        }
        return nums;
    }

22：链表倒数第K个节点

首先对找到链表第K个位置，这个节点设为temp节点，然后目标节点从头节点出发，目标节点和temp节点同时移动，当temp节点到达空节点时，目标节点指向的就是倒数第K个节点（画画图就懂了）

    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode temp=head;
        while(temp!=null&&k>0){
            temp=temp.next;
            k--;
        }
        //这里不考虑k越界的问题
        if(temp==null)return head;
        while(temp!=null){
            temp=temp.next;
            head=head.next;
        }
        return head;
    }

24：反转链表

本题的非递归解法十分简单（画个图就知道怎么做了），这里介绍递归解法。
把reverseList看作一个已经实现的函数，返回的是一个反转链表的头结点。当调用完reverseList（head.next）后，head.next就已经反转完毕了，而且它是返回后链表的尾结点，而返回值是反转链表的头结点（最终要被返回的）。
此时head和head.next的关系不再是一个单指向的关系，而是一个双指向的关系head-> <-next<-other<-cur
因此这里做一个操作head.next.next=head，同时将head的next指针置为空（此时head就是反转完毕的链表尾结点）

强烈推荐画个图，然后从一个节点开始画，体会调用的返回时机和返回值。

    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        /*
        head=4  4->5->null 
        head.next.next=head    4-><-5
        head.next=null  null<-4<-5
        */
        ListNode cur = reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return cur;
    }

25：合并排序链表

十分基础，挑选一个辅助头结点，然后双指针选择两个链表的节点（谁小就把谁的节点往结果链表上放，并移动指针）

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)return l2;
        if(l2==null)return l1;
        ListNode head =new ListNode(-1);
        ListNode temp =head;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                temp.next=l1;
                l1=l1.next;
            }else{
                temp.next=l2;
                l2=l2.next;
            }
            temp=temp.next;
        }
        if(l1!=null){
            temp.next=l1;
        }else{
            temp.next=l2;
        }
        return head.next;   
    }

26：树的子结构

两个递归函数：
【1】B是否是A的同根子结构
【2】判断B是否是A的子结构——如果不是同根的，就切换A的“根结点”，继续进行同根子结构的判断。

    //B是否是A的子结构（同根或异根）
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null)return false;
        if(dfs(A,B))return true;
        else{
            return isSubStructure(A.left,B)||isSubStructure(A.right,B);
        }
    }
    //B是否是A的一部分（同根）
    private boolean dfs(TreeNode A,TreeNode B){
        if(B==null)return true;
        if(A==null)return false;
        return A.val==B.val&&dfs(A.left,B.left)&&dfs(A.right,B.right);
    }

27：二叉树镜像

如果是空节点或者叶子节点直接返回，否则执行子任务：交换当前子树的左子树和右子树，mirrorTree看作是一个已经实现的调用，返回一棵树的镜像树结构。

    public TreeNode mirrorTree(TreeNode root) {
        if(root==null)return null;
        if(root.left==null&&root.right==null)return root;
        TreeNode l =root.left;
        root.left=mirrorTree(root.right);
        root.right=mirrorTree(l);
        return root;
    }

28:对称二叉树

根节点的任务就是确定比较左子树和右子树是否对称，而对于对称的子任务——先判断两颗子树的根结点值是否相同，然后保证两颗子树A和B中，A的左子树和B的右子树是对称，A的右子树和B的左子树是对称的。

处理子问题在递归中的体现就是：大问题和子问题共有同一套代码（本质上是同一个函数被多次调用），但是两个问题的入参和返回值不同（数据不同），而且往往具有一定关联（如把大问题的参数分解为若干子问题的参数，子问题解决最终汇集结果影响大问题的返回值）

    public boolean isSymmetric(TreeNode root) {
        if(root==null)return true;
        return dfs(root.left,root.right);
    }
    private boolean dfs(TreeNode l,TreeNode r){
        if(l==null&&r==null)return true;
        if(l==null||r==null)return false;
        if(l.val!=r.val)return false;
        return dfs(l.left,r.right)&&dfs(l.right,r.left);
    }

29：顺时针打印矩阵

四个变量卡住矩阵的四个角，每当遍历一条边，两个点组成的“墙面”就会收缩，看作很麻烦其实很简单，尤其是在纸上把四个点标出来，去模拟遍历过程变量的“收缩”。
这四个变量是一个“动态变化”的参考量即哨兵点。每一层外循环过后，上下左右的外围圈被遍历一遍，同时变量向内缩。

       public List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> res = new ArrayList<>();
        int a=0;
        int b=0;
        int c=matrix.length-1;
        int d=matrix[0].length-1;
        while (true){//一次迭代控制一次顺时针打印
            //上：左》右
            for(int i=a;i<=d;i++)res.add(matrix[a][i]);
            a++;
            if(res.size()>=(matrix[0].length)*(matrix.length))break;
            //右：上》下
            for(int i=a;i<=c;i++)res.add(matrix[i][d]);
            d--;
            if(res.size()>=(matrix[0].length)*(matrix.length))break;
            //下：右》左
            for(int i=d;i>=b;i--)res.add(matrix[c][i]);
            c--;
            if(res.size()>=(matrix[0].length)*(matrix.length))break;
            //左：上》下
            for(int i=c;i>=a;i--)res.add(matrix[i][b]);
            b++;
            if(res.size()>=(matrix[0].length)*(matrix.length))break;
        }
    return res;
    }

30最小栈

维护一个存放元素的常规栈，再额外维护一个单调栈，但是这个单调栈并不装入所有元素，而是只保证栈顶元素的最小的。这个单调栈在push或pop时根据需要更新

    public void push(int x) {
            stack.push(x);
            if(temp.isEmpty()||temp.peek()>=x){
                temp.push(x);
            }
    }
    
    public void pop() {
        int cur = stack.pop();
        if(cur==temp.peek()){
            temp.pop();
        }
    }

31 栈的压入和弹出序列

使用一个linkedList或者数组模拟栈（数组模拟栈一般使用index指向下一个待插入的位置，其中arr[0…index-1]就是栈结构），每轮从pushed数组入栈一个元素，然后从popped数组中看看有没有可以出栈的元素。如果最终序列成立，那么index应该指向0，意味着栈空

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int len = pushed.length;
        int indexPush =0,indexPop=0;
        int[] mockStack =new int[len];
        int index=0;//指向栈顶的下一个位置
        while(indexPush<len&&indexPop<len){
            //入栈
            mockStack[index]=pushed[indexPush++];
            //出栈
            while(indexPop<len&&index>=0&&popped[indexPop]==mockStack[index]){
                index--;
                indexPop++;
            }
            index++;
        }
        return index==0;
    }

32:从上到下打印二叉树3

前提：之字形打印，偶数从右到左，奇数层从左到右
BFS做这题太过简单和模板化，这里提供DFS解法。
DFS做层序遍历的思路就是使用类似list的数据结构记录每一层的元素。如果BFS每次都能拿到一整层的数据，那么DFS就是一次深度遍历为0…N层的每一层list追加一个元素，下一次DFS再为每一层list追加元素。
本题相对于普通的层序遍历，无非多了一个逻辑：判断当前层是奇数层还是偶数层，前者头插，后者尾插

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> temp = new LinkedList<>();
        dfs(temp,root,0);
        return temp;
    }
    private void dfs(List<List<Integer>> temp,TreeNode root,int level){
        if(root==null)return;
        if(level==temp.size())temp.add(new LinkedList<>());//当前层容器的初始化
        if(level%2==0){//奇数层级（从0开始）
            temp.get(level).add(root.val);
        }else{
            temp.get(level).add(0,root.val);
        }
        dfs(temp,root.left,level+1);
        dfs(temp,root.right,level+1);
    }

33：二叉搜索树的后序遍历序列

首先要知道后序遍历序列可以划分为：左子树节点-右子树节点-根，那么数组的len-1对应的就是根节点，而BST的左子树小于根，根小于右子树，因此通过遍历序列可以快速划分左子树和右子树。而子树又可以划分为：左子树节点-右子树节点-根，那么就可以通过递归进行验证。

private boolean dfs(int[] arr,int left,int right){
        if(left>=right)return true;	//验证结束的出口
        int rootIndex = right; //right就是根节点的位置
        int root = arr[rootIndex];
        int start=left;
        while(arr[start]<root){
            start++;
        }
        //start指向右子树的节点（右子树的left）或者rootIndex
        int r = start;
        //验证右子树是否全部大于root
        while(arr[r]>root){
            r++;
        }
        if(r!=rootIndex)
            return false;
        return dfs(arr,left,start-1)&&dfs(arr,start,rootIndex-1);

    }

34：二叉树中和为某一值的路径

前提：求的是从根结点走到叶子节点的路径（本题算简单的，已经明确说走到叶子节点了，因此结算的动作必然发送在叶子节点）。
没到一个节点后，下一步选择向左走或向右走，选择一条路对应add（），而从一条路返回（回溯）必然是选择同一级的另一个节点，因此remove（），防止对其他路径选择进行干扰

    public void dfs(List<List<Integer>> res,List<Integer> list,int target,TreeNode root){
        if(root==null)return;
        if(root.left==null&&root.right==null){//根结点
            if(target==root.val){
                ArrayList<Integer> temp = new ArrayList<>(list);
                temp.add(root.val);
                res.add(temp);
            }
            return;
        }
        list.add(root.val);
        dfs(res,list,target-root.val,root.left);
        dfs(res,list,target-root.val,root.right);
        list.remove(list.size()-1);
    }

35 ：复杂链表拷贝

本题的核心就是对随机指针进行拷贝。本题最容易实现的一种思路：先对链表进行一次遍历，并且每次拿到一个节点，都进行一次拷贝并添加到这个节点的后面如1>2>3，第一步结束后1>1>2>2>3>3，但是其中随机指针并没有初始化，第二步就是对随机指针的初始化：假如3指向1，那么初始化我们直接new出来的节点3，只需要让指针指向node3.random.next即可。最后一步任务就是把两个链表分离出来（这个把图画出来在写也很简单）

    public Node copyRandomList(Node head) {
        if(head==null)return null;
        //首先复制节点
        Node temp =head;
        while(temp!=null){
            Node node = new Node(temp.val);
            node.next=temp.next;
            temp.next=node;
            temp=node.next;
        }
        //随机节点
        temp=head;
        while(temp!=null){
            if(temp.random!=null){
                temp.next.random = temp.random.next;
            }
            temp=temp.next.next;
        }
        //分离
        temp = head;
        Node res = head.next;
        while(temp!=null){
            Node cur = temp.next;
            temp.next=cur.next;
            //此时temp指向第一个，cur指向第二个
            temp=temp.next;
            if(temp!=null){
                cur.next=temp.next;
            }

        }
        return res;
    }

36 二叉树与双向链表

很经典的一道中序遍历的题。
我们需要两个全局变量pre和head，这两个变量会在递归中被更新。当递归完全结束后pre指向最后一个节点，而head我们需要将它初始化为第一个节点。当根递归返回时，对着两个指针进行一个相连的处理，返回head即可

        Node head;
        Node pre;
        public Node treeToDoublyList(Node root) {
            dfs(root);
            if(head!=null&&pre!=null){
                head.left=pre;
                pre.right=head;
            }
            return head;
        }

我们以第一层递归为例，其中head的赋值时机就是递归到最左边的阶段（即dfs(root,left)走到了左节点的最深处，而这在BST中就是最小的节点，我们让head指向这个节点）。当dfs(root.left)返回后，pre指向的就是紧邻着root节点的前一个节点，既然pre和root这两个节点有了，那么当前调用的任务就是对pre和root进行适当的连接操作，同时将pre指向root，然后就开始进行向右递归，而此时pre也已经被指向之前的root了。
（最开始向左递归pre是没有值的，当左侧递归返回时pre才会被赋值，这时才能与root进行连接操作）。
个人经验：一般涉及中序遍历（尤其是BST）的题，都会借用全局变量存储“顺序”的关系。

        private void dfs(Node root){
            if(root==null){
                if(head==null)head=pre;
                return;
            }
            dfs(root.left);
            //此时pre已经指向“紧邻”root的最小元素
            if(pre!=null){
                pre.right=root;
                root.left=pre;
            }
            pre=root;
            //细品dfs(root.left)和root的关系 、root和dfs(root.right)的关系
            dfs(root.right);
        }

37:序列化二叉树

非常棒的一道题，要求将树序列化为字符串，然后还能从字符串还原成树。强烈建议去把这题搞明白（BFS和DFS都要搞懂），这里以DFS为例。
前提：题目没有规定格式，只要求能完成序列化和反序列化的任务就可以。

前序遍历，如果是空节点直接返回“null,”，否则继续从左右节点进行递归取值，返回拼串的内容

    public String serialize(TreeNode root) {
        if(root==null)return "null,";//递归出口
        String res=root.val+",";
        res+=serialize(root.left)+serialize(root.right);
        return res;//树（或子树）根调用出口
    }

一棵树经过序列化后会成为“1，2，null,null,3,4,null,null,5,null,null，”，看到这个输出就很有深度遍历的特点——一直往下打印直到遇到叶子节点，然后跟着两个null,null。
把这个字符串根据逗号切分，同样基于深度优先创建节点，维护一个index去扫描节点数组，为每一个节点创建对象，如果扫描一个叶子节点如2，最终2的左右指针都将指向null，同时，index也会移动到正确的位置（指向3），因为我们序列化的时候任何元素包括null是占位的，因此如果按照index去扫描便能够正确的恢复

    int index = 0;	//扫描每一个占位的节点
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(",");
        if(nodes.length==0||nodes[0].equals("null"))return null;
        return build(nodes);
    }
    private TreeNode build(String[] nodes){
        if(index==nodes.length)return null;
        String cur = nodes[index++];
        if(cur.equals("null"))return null;
        TreeNode root = new TreeNode(Integer.parseInt(cur));
        root.left=build(nodes);
        root.right=build(nodes);
        return root;
    }

38 字符串排列

经典的排列组合问题，使用回溯解法，假如abc，其中从哪个位置开始搜索？共有a、b、c三种选择，其中如果选择了b，那么下一轮可以选择a或c，第二个数从a还是从c开始…
因此根调用中，需要通过遍历，确定同一层（横向）从哪一个位置开始，然后对每一轮循环中，是dfs函数的调用，代表更深一层（纵向），这种横竖结合形成一颗大的递归调用树。
而为了不影响同一层的再次选择（i=1选择从a开始，i=2选择从b开始），必须将添加到候选元素集合list中的元素移除（这个元素就是当前集合的最后一个元素）。

（有一种交换代替集合增删的优化，有兴趣自行了解，这里不展开）

    ArrayList<String> res_ = new ArrayList<>();
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        dfs(chars,0,new StringBuilder());
        return res_.toArray(new String[0]);
    }

这里需要考虑重复字符的问题，如abbc，就以跟递归为例，从第1个位置选择一个字符b和从第2个位置选择一个字符b，两者返回的结果是重复的，因此我们在选取的时候就进行去重（例如本层是从aab中选，那么一个dfs基本的set保证只会执行i=0对应的分支和i=2的分支，i=1相当于被剪枝了）

    private void dfs(char[] chars,int cur,StringBuilder sb){
        if(cur==chars.length){
            res_.add(sb.toString());
            return;
        }
        HashSet<Character> set = new HashSet<Character>();
        for (int i = 0; i < chars.length; i++) {
            if(chars[i]==',')continue;
            if(!set.add(chars[i]))continue;
            char c = chars[i];
            chars[i]=',';	//标记已被访问
            sb.append(c);
            dfs(chars,cur+1,sb);
            sb.deleteCharAt(sb.length()-1);
            chars[i]=c;
        }
    }

39：数组中超过次数一半的数字

本题的最优解法：摩尔投票法
初始化最开始“得到票数最多”最多的值res，票数初始为1，遍历数组，如果遇到相同值，票数++，否则票数–，每轮过后进行一次判断，如果票数变为0，则重置res和票数，最终的res就是目标结果

    public int majorityElement(int[] nums) {
        int res =nums[0] ;
        int ticket=1;
        for(int i=1;i<nums.length;i++){
            //投票
            if(nums[i]!=res){
                ticket--;
            }else{
                ticket++;
            }
            //重新选举
            if(ticket==0){
                res=nums[i];
                ticket=1;
            }
        }
        return res;
    }

40： 最小K个数

做法很多，主要分为两种做法：排序或堆。其中排序推荐使用快速排序或堆排序。
这里主要说明堆的解法（使用优先队列）
维护大小为K的堆很适合实时计算（如数据流中最小的K数），因为仅仅维护K个堆节点即可，尤其是那种没办法将数据一次性放入内存的场景。
java的优先队列默认是小顶堆（每次从头部出队元素，升序），需要通过自定义排序器指定为大顶堆。
在大顶堆优先队列中，队头元素总是队列中最大的元素，（当size等于k时）我们一旦遇见比队头小的元素X头将队头出队，然后将当前元素X入队，最终扫描完毕整个数组，队列中只留下K个元素——这K个元素是最小的K个，因为我们维护队列的过程中，把数组中更大的arr.size() - K个元素全部排除出去了，剩下的K个元素自然都是最小的K个元素
因此大顶堆的目的，其实就是为了及时排除更大的元素。

    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for(int i:arr){
           if(pq.size()<k){
               pq.offer(i);
           }else {
               if(!pq.isEmpty()&&pq.peek()>i){
                   pq.poll();
                   pq.offer(i);
               }
           }
        }
        int[] res = new int[k];
        int index=0;
        while(k-->0){
            res[index++]=pq.poll();
        }
        return res;
    }

41：数据流中的中位数

使用一个大顶堆和一个小顶堆，数据流中的数字要么在大顶堆要么在小顶堆。拿到一个数字的时候，先放入大顶堆，然后从大顶堆拿出一个数（堆顶）放入小顶堆，以保持平衡。如果小顶堆的数量多于大顶堆，就将小顶堆堆顶放入大顶堆。
注意：大顶堆和小顶堆都是用于移除堆顶元素的，其中大顶堆中总是移除较大元素，而存放较小元素，小顶堆同理。
假如依次放入[1,2,3,6,5]，最终大顶堆中存放的元素为[3,2,1]堆顶是3，小顶堆中存放的元素是[5,6]最终直接返回大顶堆的栈顶。
如果是[2,0,8,4]则大顶堆[2,0]、小顶堆[4,8]中位数取两个堆的栈顶之和除二

    /**
     *  将元素割裂为两部分，一部分存在大顶堆，另一部分存在小顶堆
     * */
    PriorityQueue<Integer> small;
    PriorityQueue<Integer> big;

    public MedianFinder() {
        small=new PriorityQueue<>();
        big=new PriorityQueue<>((a,b)->b-a);
    }

    public void addNum(int num) {
        big.offer(num);
        small.offer(big.poll());
        if(small.size()>big.size())big.offer(small.poll());
    }

    public double findMedian() {
        if(small.size()<big.size()){
            return big.peek();
        }
        return ((double)small.peek()+big.peek())/2;
    }

42：连续子数组最大和

不使用额外变量，动态规划思想，拿到一个数nums[i]，不要管本身的值，nums[i-1]此时代表的是0…i-1的连续子数组最大和，如果这是一个整数就累加，否则抛弃（以nums[i]作为新的连续子数组的起始位置）

    public int maxSubArray(int[] nums) {
    int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(nums[i-1]>0){
                nums[i]+=nums[i-1];
            }
            res=Math.max(res,nums[i]);
        }
    return res;
    }

43 :数字1的个数

有人说考察数位DP，但是我真的不太会，这里只说数学思路。
拿到一个数字的某一位，都可以划分为高位、当前位和低位。例如1014中，如果当前位是1（此时base=10），那么高位就10，低位是4.
根据当前位大于1、等于1、小于1能够对应不同的组合数量。
我们依次举例所有位：
【1】left=101 ； cur=4 ； right =0；cur是大于1的，此时base=10。[000]1…[101]1共有(left+1)*1共102个还有1的数字
【2】left=10; cur=1 ; right=4; cur等于1，此时base=10,而由于cur=1,因此left和right完全可以看作一个数的范围，如104，这个范围就是000…104即105个数——left*base + right + 1
【3】left=1 ； cur=0 ； right =14; 此时高位只能计算从0…left-1。例如20只能有01和11。因此left*base

    public int countDigitOne(int n) {
        if(n==0)return 0;
        long base = 1;  //位数
        int sum = 0;
        while (base<=n){
            //高位
            int left = (int)(n/base/10);
            //当前位
            int cur = (int)(n/base%10);
            //低位
            int right=(int)(n%base);
            if(cur>1){
                //出现1的次数由高位决定
                sum+=(left+1)*base;
            }else if(cur<1){
                //出现1的次数由高位决定
                sum+=left*base;
            }else {
                //left和right看出一个合成数
                sum+=left*base + right + 1;
            }
            base*=10;
        }
        return sum;
    }

44: 第N个数字

前提：数字从1开始。其中1到9占用9个位置，10到99占用180个位置，依次类推，现在给你一个n问你对应位置的数字。
先从大方向找，确定n 的数字范围，再确定位置。
count、start和digit可以看作一个表格，当数字范围在1-9时，count-start-digit对应 9-1-1.我们不断更新这个表格如10-99：90-10-2 、 100-999 ：900-100-3
并且不断更新n，如果n小于当前count，说明n就在当前范围。例如n=11大于9，被更新为2,小于90则被确定为10-99 的数字范围，此时n对应的就是一个范围内的偏移量，而start此时也被更为10，位数为2，然后我们就找到了第n位落在了哪一个数字中。最后一步就是判断在数字内部定义是第几位数。

    public int findNthDigit(int n) {
        long count=9;
        long start=1;
        int digit=1;
        while(count<n){
            n-=count;
            start*=10;
            digit++;
            count=start*9*digit;//占位
        }
        //找到n落在哪一个数字
        long num = start +(n-1)/digit;//start初始值为1
        //确定n对应在数字中的位数
        return Long.toString(num).charAt((n-1)%digit)-'0';
    }

45：最小数

还有一个最大数问题与之相反，把每个数转换为字符串，使用拼接字符串字典序排序。，因为题目要求的就是拼接数，而排序后的字符串数组就是按照拼接后的升序去排列的，因此遍历拼接就能得到最终结果

    public String minNumber(int[] nums) {
        String[] strings = new String[nums.length];
        for (int i = 0; i < strings.length; i++) {
            strings[i]=String.valueOf(nums[i]);
        }
        Arrays.sort(strings,(s1,s2)->(s1+s2).compareTo(s2+s1));
        StringBuffer sb = new StringBuffer();
        for(String s:strings)sb.append(s);
        return sb.toString();
    }

46 :数字翻译为字符串

dp[i]以i结尾的数字字符串有多少种翻译方式。例如abc，dp[2]对应ab的翻译方式，其中将dp[0]和dp[1]是保证dp[2]的正确性
每次截取两个长度的子串，如果如果字符串不能够被“多种”翻译，那么dp[i]=dp[i-1]，s[i-1]作为单独字符翻译，因此翻译的种类等同于以i-2结尾的翻译种类dp[i-1]。
还可以选择将s[i-1]和s[i-2]组合成一个字符翻译，此时的翻译种类等于以i-3结尾的翻译种类，将两种选择方式加起来就是此时i-2结尾的字符串的翻译方式dp[i]=dp[i-1]+dp[i-2]。

    public int translateNum(int num) {
        String s = String.valueOf(num);
        if(s.length()==0)return 1;
        int[] dp = new int[s.length()+1];
        dp[0]=dp[1]=1;
        for (int i = 2; i <= s.length(); i++) {
            String temp=s.substring(i-2,i);
            if(temp.compareTo("25")>0
            ||temp.compareTo("10")<0){//例如506
                dp[i]=dp[i-1];
            }else dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[s.length()];
    }

47：礼物的最大价值

机器人行走问题的换皮题。
dp[i][j]是当前格子的最大价值。只能从上面或者左边走到这个格子，因此**当前这个格子的最大礼物数量=当前格子的价值 + max{ 从上面格子走来的最大礼物数 ，从左面格子走过来的最大礼物数 }**即 dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j]，需要对第一列和第一行进行初始化。（只能从一边走过来）

    public int maxValue(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0]=grid[0][0];
        for (int i = 1; i < grid.length; i++) {
            dp[i][0]=grid[i][0]+dp[i-1][0];
        }
        for (int i = 1; i < grid[0].length; i++) {
            dp[0][i]=grid[0][i]+dp[0][i-1];
        }
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[dp.length-1][dp[0].length-1];
    }

48:最长不含重复字符的子字符串

滑动窗口做法，维护一个set用于保存窗口中的字符。每轮迭代都取出一个字符放入集合中，如果集合中已经存在这个元素，那么左边界需要向右滑动，直到窗口中不存在当前右边界指向的字符。总结：滑动窗口题型要找好“稳定期”（左窗口不需要调整），本题的稳定期就是left和right圈出的窗口不含有重复字符。

    public int lengthOfLongestSubstring(String s) {
        int left=0;
        int right=0;
        int len = s.length();
        int max=0;
        HashSet<Character> set = new HashSet<>();
        while (right<len){
            char r = s.charAt(right);
            while (set.contains(r)){
                set.remove(s.charAt(left));
                left++;
            }
            max=Math.max(right-left+1,max);
            right++;
            set.add(r);
        }
        return max;
    }

49:丑数

本题的质因子只有2 3 5，因此维护三个指针p2 p3 p5（还有一题叫超级丑数，是给定一组数，我们需要维护一组指针）。
另外维护一个结果数组和指针index，数组的第一个元素是1，然后向后迭代，每轮结果数组中要放入一个丑数。三个指针最初同时执行第一个元素，分别与对应的质因子相乘得到a b c，比较得到三个数中最小的值min，放入本轮index指向的位置，这个min是ints[p2]*2、ints[p3]*3还是ints[p5]*5，是谁，谁的指针就向后移动。

    public int nthUglyNumber(int n) {
        if(n<2)return n;
    int p2=0,p3=0,p5=0;
        int[] ints = new int[n];
        ints[0]=1;
        for (int i = 1; i < n; i++) {
            int a =ints[p2]*2;
            int b =ints[p3]*3;
            int c =ints[p5]*5;
            int min=Math.min(a,Math.min(b,c));
            ints[i]=min;
            //如果两个丑数的值相同了，同时移动，防止出现重复的解
            if(min==a)p2++;
            if(min==b)p3++;
            if(min==c)p5++;
        }
        return ints[n-1];
    }

50 第一个只出现过一次的字符

对字符进行计数，返回第一个只出现过一次的字符

    public char firstUniqChar2(String s) {
  int[] letters=new int[26];
        for(char c:s.toCharArray()){
            letters[c-'a']+=1;
        }
        for(char c:s.toCharArray()){//对照统计表再次遍历字符串
          if(letters[c-'a']<2)return c;
        }
        return ' ';
    }

51：逆序对

使用归并排序，在排序的过程中进行统计，相似题有493翻转对，315
主要的不同就是merge()合并有序数组的过程中，需要一个统计的操作

public int reversePairs(int[] nums) {
        if(nums.length<2)return 0;
    return mergeSort(nums,0,nums.length-1);
}
    private int mergeSort(int[] nums,int left,int right){
         if(left>=right)return 0;
         int mid=(right-left)/2+left;
         //分
        int a=mergeSort(nums,left,mid);
        int b=mergeSort(nums,mid+1,right);
        //左边数组逆序对数+右边数组逆序对数+跨越数组的逆序对数
        return a+b+merge(nums,left,mid,right);
    }

以[7,5,6,4]为例，被查分为最小的粒度[7] 、[5] 、[6] 、[4] 后开始执行合并任务，7和5直接存在逆序对关系因此记为1，计数完毕，开始执行正常的有序数组合并任务，最终向上返回时，返回值为0，数组结构为[5,7]，另一边同理，返回1，数组结构为[4，6]。
第一层递归中，左边数组就是[5,7]，右边数组[4，6]。其中5和4都是所在数组的最小值，因为5大于4，因此5后面一直左边数组结尾，一定都是大于4的，因此直接累加mid-start1+1。否则继续向后计算。
最终，第二轮递归计算出两个逆序对7-5和6-4.第一轮递归计算出[5,7]-4和7-6 总共五对

    //相当于一边统计，一边进行归并排序
    private int merge(int[] nums,int left,int mid,int right){
        int start1=left;
        int start2=mid+1;
        int[] temp =new int[right-left+1];
        int res=0;
        int index=0;
        //此时【start1,mid】和【start2,right】都是升序的
        while (start1<=mid&&start2<=right){
            //start1是左边数组最小的数
            //如果nums[start1]>nums[start2]
            //则左边数组的mid-left+1个数都可以和nums[start2]构成逆序对
            //反之继续寻找下一个start1使得nums[start1]>nums[start2]
            if(nums[start1]>nums[start2]){
                //【start1,mid】都可以和start2组成逆序对
                temp[index]=nums[start2];
                res+=mid-start1+1;
                start2++;
            }else{
                //试图构建【start1,mid】
                temp[index]=nums[start1];
                start1++;
            }
            index++;
        }
        while (start1<=mid){
            temp[index++]=nums[start1++];
        }
        while (start2<=right){
            temp[index++]=nums[start2++];
        }
        System.arraycopy(temp,0,nums,left,temp.length);
        return res;
    }

52：链表公共节点

两个链表同速前进，如果其中一个跑到终点（空节点），从另一个节点的起点接着跑。
最终出现两个结果：
【1】最终全部到达空节点（不相交）
【2】相加点相遇
原理就是两个节点的总路程一样，从不同的节点同速前进，最终一定会相遇

     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode tempA =headA;
    ListNode tempB =headB;
    while (tempA!=tempB)//相遇就停止
    {
        //如果某个节点走到了头，就从另一个节点的头结点重新开始走（循环跑，直到遇上）
        if(tempA==null){
            tempA=headB;    //3 + 2 = 2 + 3 一定会相遇
        }else tempA=tempA.next;
        if(tempB == null){
            tempB=headA;
        }else tempB=tempB.next;
    }
    return tempA;
    }

53:0到n-1的缺失数字

二分查找。注意left+(right-left)/2值往左偏，因此使用左排除写法防止2节点时死循环。如果一个数字都不缺少（缺少n），那么最终left会与right重合，需要特殊判断

            public int missingNumber(int[] nums) {
        int left=0;int right=nums.length-1;
        while (left<right){
            int mid =left+(right-left)/2;
            if(nums[mid]==mid){
                left=mid+1;
            }else{
                right=mid;
            }
     }
        // 如果从0 ~ n - 1都不缺值, 则缺少的是n
        return left == nums.length-1&& nums[left] == left ? left + 1 : left;
    }

54：BST第K大节点

中序遍历，使用一个count计数节点的个数，反着搜索，先搜索右子树再搜索左子树。当count=k时返回

    int ans;
    int count;
    int level;
    public int kthLargest(TreeNode root, int k) {
        level = k;
        dfs(root);
        return ans;
    }
    private void dfs(TreeNode root){
        if(root==null)return;
        dfs(root.right);

        count++;    //有序元素统计
        if(count==level){
            ans = root.val;
            return;
        }
        
        dfs(root.left);
    }

55：平衡二叉树

平衡二叉树左右子树的高度的差值不能超过1。
把求子树高度的函数写出来，每一层的子任务就是判断以当前节点做根时是否满足平衡二叉树定义，然后向下递归。

 public boolean isBalanced(TreeNode root) {
    if(root==null)return true;
        int a = H(root.left);
        int b =H(root.right);
        if (Math.abs(a - b) > 1)
            return false;
        return isBalanced(root.left) && isBalanced(root.right);//左右子树也必须是平衡二叉树
    }
    private int H(TreeNode root) {
        if(root==null)return 0;
        return Math.max(H(root.left),H(root.right))+1;
    }

56-1：其他数字出现两次，找到出现一次的两个数

先对数组求出异或累加值，最后得到的就是只出现一次的两个数的亦或值。例如6（110）^1（001）得到111。
二者是不同的数字，因此至少有一位的异或结果是1，我们找到那位不为0的数位，例如111的第一位，我们使用一个掩码001标记出这一位。
我们创建两个数组，nums中所有第一位为0的放入一个数组（mask&num为0），另一部分放入剩下的数组。
两个数组内部也进行异或运算，最终剩下的只有只出现一次的两个数组数字

    public int[] singleNumbers(int[] nums) {
        int flag=0;
        for(int num:nums){
            flag^=num;
        }
        int mask=1;
        //标记异或值为1的位置
        while((mask&flag)==0){
            mask<<=1;
        }
        //最终nums的数字一部分放入res[0]，一部分放入res[1]。
        //但是只出现一次的两个数字一定位于不同的数组
        int[] res =new int[2];
        for(int num:nums){
            if((mask & num) ==0)
            res[0]^=num;
            else res[1]^=num;
        }
        return res;
    }

56-2:其他数字出现三次，找到仅出现一次的数

解法：枚举数位并统计
遍历数组中的每一个数，对一个数的每一位在数位数组中进行统计。最后再统计一遍数位数组，拼接不能被三整除的位，得到最终结果

    public int singleNumber(int[] nums) {
        //统计“位”对应的count
        int[] bits = new int[32];
        for (int i = 0; i < nums.length; i++) {
            int temp=nums[i];
            //32不随着规模改变而变化，因此看作常量级别的复杂度
            for (int j = 0; j < 32; j++) {
                bits[j]+=temp&1;
                temp>>=1;
            }
        }
        int res=0;
        int mask=1;
        for (int i = 0; i < 32; i++) {
            if(bits[i]%3==1){
                res|=mask;
            }
            mask<<=1;
        }
        return res;
    }

57：两数之和（递增）

双指针圈定范围，力扣最经典的题，写过人数最多的题，不再赘述。

    public int[] twoSum(int[] nums, int target) {
       int left =0;
       int right=nums.length-1;
       while (nums[right]>target)right--;
       while (nums[left]+nums[right]!=target){
           if(nums[left]+nums[right]>target)right--;
           else if(nums[left]+nums[right]<target) left++;
       }
       return new int[]{nums[left],nums[right]};
    }

57-2：和为s的连续正数序列

滑动窗口，稳定期就是没有形成序列的时候（sum<target），否则结算窗口[left…right]中的序列，左边界移动（左右边界不能重合），sumj减去相应的值，再次进入稳定期。

    public int[][] findContinuousSequence(int target) {
        int left=1,right=1;
        int sum=0;
        ArrayList<int[]> res = new ArrayList<>();
        while (left<=target){
            if(sum<target){
                sum+=right;
                right++;
            }else { //结算，左边界滑动
                if(sum==target&&right!=left+1){
                    int[] t = new int[right - left];
                    for (int i = left; i <right; i++) {
                        t[i-left]=i;
                    }
                    res.add(t);
                }
                sum-=left;
                left++;
            }
        }
    return res.toArray(new int[res.size()][]);
    }

59：滑动窗口最大值

维护一个递减的队列，队头总是最大值。队列中存储数值索引，这样可以判断队头的最大值是否已经“过期”，如果队头的最大值过期了就出队。当遍历的元素达成形成窗口的条件时，才进行结果数组的填充（即i-k+1>=0）

    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if(len==0||k==0)return new int[0];
        int[] res = new int[len-k+1];
        int index=0;
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            while (!queue.isEmpty()&&nums[i]>nums[queue.peekLast()]){
                queue.pollLast();
            }
            queue.offerLast(i);
            while (i-queue.peekFirst()+1>k){
                queue.pollFirst();
            }
            if(i>=k-1){
                res[index++]=nums[queue.peekFirst()];
            }
        }
        return res;
    }

60:N个骰子的点数

一个骰子6个面，投掷一个骰子的概率是1/6，如果投两个骰子，投不出1，投三个骰子投不出1和2，因此投n个骰子，投不出n-1 、n-2…1，因此n个骰子数组的长度是6*n-(n-1) = 5* n+1
将求解n个骰子的点数分解为n-1个骰子加上 上一个骰子的点数。
代码中的dp是第i个筛子的点数概率数组，one数组是i-1个骰子的点数概率数组。并且i-1的每个数都会对i个骰子投出时产生影响。例如一个筛子时，one[0]代表投出1的概率，它会对两个骰子投出2、3,7时产生影响，{dp[0]、dp[1]、dp[2] … dp[5] } +=one[0]/6.0.
转移方程即为： dp[i][s+num]+=dp[i-1][s]/6.0; num就是对0到6的枚举，s是对dp[i-1]有效范围的枚举。

    public double[] dicesProbability(int n) {
        double[] one = new double[6];
        Arrays.fill(one,1.0/6);
        for (int i = 2; i <= n; i++) {
        //第i个筛子的范围
            int range = 6*i - i +1;
            double[] dp = new double[range];
            for (int s = 0; s < one.length; s++) {
            //这里num从0开始是一个偏移量，是有效的最小点数，如三个骰子对应3
                for (int num = 0; num < 6; num++) {//每个选择对应1/6概率，需要乘上
                    dp[s+num]+=one[s]/6.0;
                }
            }
            one=dp;
        }
        return one;
    }

61 ：扑克牌中的顺子

前提：五张连续的牌是一张顺子（1和2不看做比J K Q大），鬼牌可以充当任何牌。给出的数组长度就是5。
排序，统计鬼牌对应的0，如果存在重复直接返回false。
最后判断最大值-最小值是否小于5。如果存在顺子如1 2 3 4 5 ，最大值减去最小值一定是小于5的，最大为4，如果存在鬼牌，那么差值只会更小。

    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int count=0;
        for(int i=0;i<4;i++){
            if(nums[i]==0)count++;
            else if(nums[i]==nums[i+1])return false;
        }
        //最大值-最小值
        return nums[4]-nums[count]<5;
    }

62:约瑟夫环

能通过的是反推解法，不过我想把模拟的写法（正推）写一下（超时）。
反推就是只关心剩下来的人的编号变化。
最终返回结果只剩下一个人，因此反推的初始编号为0，将每轮移除的人补充回来，并将编号重新计算。例如倒数第二轮重新加入一个人（加入后变为两个人），0+3溢出，重新计算为1，依次类推。最终的递推公式：
f(n , m) = [ f(n-1 , m) + m ]%n n>1（当n=1时，f(n , m) = 0）

 public int lastRemaining(int n, int m) {
        int ans = 0;
        // 最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }

超时但是主观（正向模拟）：

public int lastRemaining(int n, int m) {
    LinkedList<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        queue.add(i);
    }
    int num=1;//当前是第几个元素
    while (queue.size()>1){
        Integer cur = queue.poll();
        
        if(num%m==0){	//找到待删除的元素，不放入
            num=1;
            continue;
        }
        queue.offer(cur);// 重新放回去
        num++;
    }
    //唯一一个
    return queue.poll();
}

63：股票问题（一次交易）

一次交易，求最大利润。
min代表最小股票买入价格。每一轮和当前股票价格比较，并更新min=Math.min(min,prices[i])
max代表最大利润。max=Math.max(max,prices[i]-min)

    public int maxProfit(int[] prices) {
        if(prices.length<2)return 0;
        int min=prices[0];
        int max = 0;
        for(int i=1;i<prices.length;i++){
            max=Math.max(max,prices[i]-min);
            min=Math.min(min,prices[i]);
        }
        return max;
    }

65 :不使用加减乘除做加法

位运算，使用异或和移位模拟加法。其中异或就是不进位时的加和，而与运算得到要进位的值，左移一位与非进位和相加即可。

 public int add(int a, int b) {
        //计数a+b等价于（a^b）+((a&b)<<1)
        while (a != 0) {
            int temp = a ^ b;//非进位和_异或运算
            a = (a & b) << 1;//进位_与运算，左移一位
            b = temp;
        }
        return b;
    }

66：构建乘积数组

做本题最好画一个乘积式：
B【0】= 1 A【1】 A【2】 … A【n-1】 A【n】
B【1】= A【0】 1 A【2】 … A【n-1】 A【n】
B【2】= A【0】 A【1】 1 … A【n-1】 A【n】
… … … … … …
B【n-1]= A【0】 A【1】 A【2】 … 1 A【n】
B【n】= A【0】 A【1】 A【2】 … A【n-1】 1

我们第一次先把下三角 乘积，从上到下计算填充到B[i]数组，此时B【0】=1 ，B【1】=1 * A【0】* A【1】，B【1】=1 * A【0】 依次类推。
最好依次在将上三角从下往上填充进B[i]数组。

      public int[] constructArr(int[] a) {
        if(a.length == 0) return new int[0];
        int[] b = new int[a.length];
        //下三角行列式
        b[0] = 1;
        for(int i = 1; i < a.length; i++) {
            b[i] = b[i - 1] * a[i - 1];
        }
        //加上上三角
        int tmp = 1;
        for(int i = a.length - 2; i >= 0; i--) {
            //从倒数第一个开始加
            tmp *= a[i + 1];
            //倒数第一行不用加,直接从倒数第二行开始计算就可以
            b[i] *= tmp;
        }
        return b;
    }

67：字符串转整数

细节题，不再赘述

public int strToInt(String str) {
        boolean negative = false;
        int index=0;
    char[] target = str.toCharArray();
    while (index<target.length&&target[index]==' ')index++;
    //空字符串
    if(index==target.length)return 0;
    //确认符号
    if(target[index]=='-'||target[index]=='+'){
        negative= (target[index] == '-');
        index++;
    }else if(Character.isLetter(target[index])){
        return 0;
    }
    //前导0
    while (index<target.length&&Character.isDigit(target[index])&&target[index]=='0'){
        index++;
    }
    if(index==target.length||!Character.isDigit(target[index])){
        return 0;
    }
    //取连续数字
    LinkedList<Integer> queue = new LinkedList<>();
    while (index<target.length&&Character.isDigit(target[index])){
        queue.offer(target[index]-'0');
        index++;
    }
    //特别长的数，无法使用十进制整型表示
    if(queue.size()>10)return (negative)?Integer.MIN_VALUE:Integer.MAX_VALUE;
    long res=0;
    while (!queue.isEmpty()){
        res=res*10+queue.poll();
    }
    res=(negative)?-res:res;
    if(res>Integer.MAX_VALUE)return Integer.MAX_VALUE;
    else if(res<Integer.MIN_VALUE)return Integer.MIN_VALUE;
    else return (int)res;
}

68-1 BST最近的公共祖先

利用BST的特性，根据根结点的值与两颗子树的值进行比较，判断公共二叉树的位置，如果一个大一个小，那么root就是公共祖先。如果全部大于root的值说明在右子树，否则向左子树搜索

    TreeNode res_ = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        lca(root, p , q);
        return res_;
    }
    //利用二叉树搜索树的特定
    private void lca(TreeNode root, TreeNode p, TreeNode q){
        if((root.val - p.val)*(root.val - q.val) <= 0){//如果一个在左一个在右 则说明此时的root记为对应的最近公共祖先
            res_ = root;
        }else if(root.val < p.val && root.val < q.val){//如果p q都大于root，说明肯定在root的右子树中
            lca(root.right, p , q);
        }else{//如果p、q的值都小于root，说明p q 肯定在root的左子树中
            lca(root.left, p , q);
        }
    }

68-2 二叉树的最近公共祖先

后序遍历，递归返回的时机：搜索到空节点也没有搜索出来、或者说其中任意一个节点搜索到祖先节点。
根调用根据子树是否搜索到节点来圈定公共祖先的范围，如果都返回了值，那么root就是最近公共祖先（因为P和Q在两边都找了目标值）

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||q==root||p==root)return root;
        TreeNode a =lowestCommonAncestor(root.left,p,q);
        TreeNode b =lowestCommonAncestor(root.right,p,q);
        if(a==null&&b==null)return null;
        if(a==null)return b;
        if(b==null)return a;
        return root;     
    }