剑指offer刷题报告(Java)

Myth丶恋晨 2021-12-21 15:53 335阅读 0赞

### 文章目录 ###

*   *  1. 二维数组中的查找
     *  2. 替换空格
     *  3. 从尾到头打印链表
     *  4. 重建二叉树
     *  5. 用两个栈实现队列
     *  6. 旋转数组的最小数字
     *  7.斐波那契数列
     *  8. 跳台阶
     *  9. 变态跳台阶
     *  10.矩形覆盖
     *  11.二进制中1的个数
     *  12.数值的整数次方
     *  13.调整数组顺序使奇数位于偶数前
     *  14.链表中倒数第k个节点
     *  15.反转链表
     *  16.合并两个排序的链表
     *  17.树的子结构
     *  18.二叉树的镜像
     *  19.顺时针打印矩阵
     *  20.包含min函数的栈
     *  21.栈的压入、弹出序列
     *  22.从上往下打印二叉树
     *  23.二叉搜索树的后序遍历序列
     *  24.二叉树中和胃某一值的路径
     *  25.复杂链表的复制
     *  26.二叉搜索树与双向链表
     *  27.字符串的排列
     *  28.数组中出现次数超过一半的数字
     *  29.最小的k个数
     *  30.连续子数组的最大和
     *  31.整数中1出现的次数（从1到n）
     *  32.把数组排成最小的数
     *  33.丑数
     *  34.第一个只出现一次的字符
     *  35. 数组中的逆序对
     *  36.两个链表的第一个公共节点
     *  37.数字在排序数组中出现的次数
     *  38.二叉树的深度
     *  39.平衡二叉树
     *  40.数组中只出现一次的数字
     *  41.和为S的连续正数序列
     *  42.和为S的两个数字
     *  43.左旋转字符串
     *  44.翻转单词顺序列
     *  45.扑克牌顺子
     *  46.孩子们的游戏(圆圈中最后剩下的数)
     *  47.求1+2+3+...+n
     *  48.不用加减乘除做加法
     *  49.把字符串转换成整数
     *  50.数组中重复的数字
     *  51.构建乘积数组
     *  52.正则表达式匹配
     *  53.表示数值的字符串
     *  54.字符流中第一个不重复的字符
     *  55.链表中环的入口结点
     *  56.删除链表中重复的节点
     *  57.二叉树的下一个结点
     *  58.对称的二叉树
     *  59.按之字形顺序打印二叉树
     *  60.把二叉树打印成多行
     *  61.序列化二叉树
     *  62.二叉搜索树的第k个结点
     *  63.数据流中的中位数
     *  64.滑动窗口的最大值
     *  65.矩阵中的路径
     *  66.机器人的运动范围

## 1. 二维数组中的查找 ##

**题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。**

// 解法一：220ms 暴力n^2
    
    public class Solution { 
        public boolean Find(int target, int [][] array) { 
            int x = array.length, y = array[0].length;
            boolean flag = false;
            
            for(int i = x - 1;i >= 0;i--) { 
                for(int j = y - 1;j >= 0;j--) { 
                    if(array[i][j] == target) { 
                        flag = true;
                        break;
                    }
                }
            }
            return flag;
        }
    }

// 解法二：182ms 把每一行看成有序递增的数组，利用二分查找，通过遍历每一行得到答案，时间复杂度是nlogn
    public class Solution { 
        public boolean Find(int target, int [][] array) { 
            if(array == null || array.length == 0 || array[0].length == 0) { 
                return false;
            }
            int row = array.length, col = array[0].length;
            for(int i = 0;i < row;i++) { 
                // 每一行进行二分
                int left = 0, right = col - 1;
                while(left <= right) { 
                    int mid = (left + right) / 2;
                    if(array[i][mid] > target) { 
                        right = mid - 1;
                    } else if(array[i][mid] < target) { 
                        left = mid + 1;
                    } else { 
                        return true;
                    }
                }
            }
            return false;
        }
    }

/*解法三：195ms 利用二维数组由上到下，由左到右递增的规律，那么选取右上角或者左下角的元素a[row][col]与target进行比较，当target小于元素 a[row][col]时，那么target必定在元素a所在行的左边,即col--；当target大于元素a[row][col]时， 那么target必定在元素a所在列的下边,即row++； */
    public class Solution { 
        public boolean Find(int target, int [][] array) { 
            if(array == null || array.length == 0 || array[0].length == 0) { 
                return false;
            }
            int row = array.length, col = array[0].length;
            int r = 0, c = col - 1;//从右上角开始
            while(r < row && c >= 0) { 
                if(array[r][c] > target) { 
                    c--;
                } else if(array[r][c] < target) { 
                    r++;
                } else { 
                    return true;
                }
            }
            return false;
        }
    }

## 2. 替换空格 ##

**题目：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。**

// 解法一：20ms 常规解法
    public class Solution { 
        public String replaceSpace(StringBuffer str) { 
        	StringBuilder tempStr = new StringBuilder();
            for(int i = 0;i < str.length();i++) { 
                if(str.charAt(i) == ' ') { 
                    tempStr.append("%20");
                } else { 
                    tempStr.append(str.charAt(i));
                }
            }
            return tempStr.toString();
        }
    }

## 3. 从尾到头打印链表 ##

**题目：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。**

// 解法一：运行时间：20ms 占用内存：9252k
    // 利用递归求解
    /** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */
    import java.util.ArrayList;
    public class Solution { 
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { 
            ArrayList<Integer> resList = new ArrayList<Integer>();
            if(listNode == null) { 
                return resList;
            } else { 
                return returnListFromTailToHead(listNode);
            }
            
        }
        public ArrayList<Integer> returnListFromTailToHead(ListNode listNode) { 
            ArrayList<Integer> tempList;
            if(listNode.next == null) { 
                tempList = new ArrayList<Integer>();
                tempList.add(listNode.val);
            } else { 
                tempList = returnListFromTailToHead(listNode.next);
                tempList.add(listNode.val);
            }
            return tempList;
        }
        
    }

// 解法二： 超简洁版，运行时间：30ms 占用内存：9340k
    // 相当于也是递归，然后输出
    /** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */
    import java.util.ArrayList;
    public class Solution { 
        ArrayList<Integer> resList = new ArrayList<Integer>();
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { 
            if(listNode != null) { 
                printListFromTailToHead(listNode.next);
                resList.add(listNode.val);
            }
            return resList;
        }
    }

//解法三：运行时间：27ms 占用内存：9248k
    //先获得正序的ArrayList，在借助Collections.reverse（）反转链表
    /** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */
    import java.util.ArrayList;
    import java.util.Collections;
    public class Solution { 
        ArrayList<Integer> resList = new ArrayList<Integer>();
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { 
            while(listNode != null) { 
                resList.add(listNode.val);
                listNode = listNode.next;
            }
            Collections.reverse(resList);
            return resList;
        }
    }

## 4. 重建二叉树 ##

**题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。**

// 解法一： 运行时间：190ms 占用内存：22148k
    /* 代码里有注释 基本思想是递归分治，利用了先序遍历和中序遍历的特性。 先序遍历的特性是：第一个访问的结点一定是根结点。（即数组第一个值是根结点的值） 中序遍历的特性是：数组中的一个值（现结点），其左边的全部是现结点的左子树中的值，右边的全部是现结点的右子树中的值。 */
    /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    public class Solution { 
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 
            return buildTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
        }
        // 根据pre[pre_l, pre_r], in[in_l, in_r] 构建二叉树
        public TreeNode buildTree(int [] pre, int pre_l, int pre_r, int [] in, int in_l, int in_r) { 
            // 边界处理
            if(pre_l > pre_r) { 
                return null;
            }
            if(pre_l == pre_r) return new TreeNode(pre[pre_l]);
            
            //找到前序遍历的根节点，在中序遍历中的位置
            int index = find(in, in_l, in_r, pre[pre_l]);
            //左子树长度
            int len_l = index - in_l;
            
            // 构建根节点
            TreeNode root = new TreeNode(pre[pre_l]);
            
            // 根据pre[pre_l + 1, pre_l + len_l], in[in_l, index - 1]构建左子树
            TreeNode leftNode = buildTree(pre, pre_l+1, pre_l+len_l, in, in_l, index - 1);
            // 根据pre[pre_l + len_l + 1, pre_r], in[index+1, in_r]构建右子树
            TreeNode rightNode = buildTree(pre, pre_l+len_l+1, pre_r, in, index+1, in_r);
            
            root.left = leftNode;
            root.right = rightNode;
            
            return root;
        }
        
        // 找到根节点在中序遍历中的位置
        public int find(int [] in, int in_l, int in_r, int target) { 
            int len = in.length;
            for(int i = 0;i < len;i++) { 
                if(target == in[i]) { 
                    return i;
                }
            }
            return -1;
        }
    }

//解法二： 运行时间：179ms 占用内存：22980k 超简洁版本
    /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    import java.util.*;
    public class Solution { 
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 
            if(pre.length == 0) { 
                return null;
            }
            TreeNode root = new TreeNode(pre[0]);
            if(pre.length == 1) { 
                return root;
            }
            for(int i = 0;i < in.length;i++) { 
                if(pre[0] == in[i]) {  //根节点在中序遍历中的位置
                    //Arrays.copyOfRange() 是左闭右开区间
                    root.left  = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                    root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                }
            }
            return root;
        }
    }

## 5. 用两个栈实现队列 ##

**题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。**

// 解法一： 运行时间：15ms 占用内存：9404k
    
    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.push(node);
        }
        
        public int pop() { 
            if(stack2.empty()) { 
                while(!stack1.empty()) { 
                    int x = stack1.peek();
                    stack1.pop();
                    stack2.push(x);
                }
            }
            int node = stack2.peek();
            stack2.pop();
            return node;
        }
    }

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

**题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。**

//解法一：运行时间：383ms 占用内存：30980k
    //排序
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.*;
    public class Solution { 
        public int minNumberInRotateArray(int [] array) { 
            if(array.length == 0) { 
                return 0;
            }
            Arrays.sort(array);
            return array[0];
        }
    }

//解法二：运行时间：324ms 占用内存：28728k
    //变向二分法，分析在注释里，也可以看这个https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba
    //~~~这种二分法，时间小了点，内存小了点
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.*;
    public class Solution { 
        public int minNumberInRotateArray(int [] array) { 
            if(array.length == 0) { 
                return 0;
            }
            int left = 0, right = array.length - 1;
            int mid = 0;
            
            // 确保left在左边递增序列，right在右边递增序列
            while(array[left] >= array[right]) { 
                //边界条件
                if(right - left == 1) { 
                    mid = right;
                    break;
                }
                mid = (left + right) / 2;
                //三者相等的情况下，无法判断，只能顺序查找
                if(array[mid] == array[left] && array[mid] == array[right]){ 
                    return minNumOfArray(array, left, right + 1);
                }
                // 中间元素位于前面的递增子数组
                // 此时最小元素位于中间元素的后面
                if(array[mid] >= array[left]) { 
                    left = mid;
                }
                // 中间元素位于后面的递增子数组
                // 此时最小元素位于中间元素的前面
                else { 
                    right = mid;
                }
            }
            return array[mid];
        }
        /** * 获得一段数组中的最小值 */
        public int minNumOfArray(int [] array, int left, int right) { 
            int minNum = array[left];
            for(int i = left;i < right;i++) { 
                if(array[i] < minNum) { 
                    minNum = array[i];
                }
            }
            return minNum;
        }
    }

// 解法三：运行时间：354ms 占用内存：28200k
    // 也是二分，上面那种方法的简洁版本，不需要定义一个辅助函数
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.*;
    public class Solution { 
        public int minNumberInRotateArray(int [] array) { 
            int low = 0 ; int high = array.length - 1;   
            while(low < high){ 
                int mid = (low + high) / 2;
                if(array[mid] > array[low]){ 
                    low = mid;
                } else if(array[mid] == array[low]){ 
                    low = low + 1;
                }else{ 
                    high = mid;
                }   
            }
            return array[low];
        }
    }

## 7.斐波那契数列 ##

**题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39**

// 解法一：运行时间：1348ms 占用内存：9408k
    // 暴力递归，最简单的
    public class Solution { 
        public int Fibonacci(int n) { 
            if(n == 0 || n == 1) { 
                return  n;
            } 
            return Fibonacci(n-1) + Fibonacci(n-2);
        }
    }

// 解法二： 运行时间：1408ms 占用内存：9300k
    // 存下中间值（按道理应该比上面那种方法快的）
    import java.util.*;
    public class Solution { 
        int [] fibo = new int[40];
        public int fibona(int n) { 
            if(n == 0 || n == 1) { 
                return n;
            }
            if(fibo[n] != 0) { 
                return fibo[n];
            } else { 
                return fibona(n - 1) + fibona(n - 2);
            }
        }
        
        public int Fibonacci(int n) { 
            
            Arrays.fill(fibo, 0);
            fibo[1] = 1;
            return fibona(n);
        }
    }

// 解法三： O(n) 运行时间：16ms 占用内存：9324k
    // 循环求，复杂度O（n），递归的好处是简单，但是做了很多无用的操作
    import java.util.*;
    
    public class Solution { 
        int [] fibo = new int[40];
        public int Fibonacci(int n) { 
            fibo[1] = 1;
            fibo[0] = 0;
            for(int i = 2;i <= n;i++) { 
                fibo[i] = fibo[i - 1] + fibo[i - 2];
            }
            return fibo[n];
        }
    }

// 解法四：O(logn) 运行时间：14ms 占用内存：9412k
    // 矩阵快速幂：https://blog.csdn.net/aaakkk_1996/article/details/87927108
    /* * O(logN)解法：由f(n) = f(n-1) + f(n-2)，可以知道 * [f(n),f(n-1)] = [f(n-1),f(n-2)] * {[1,1],[1,0]} * 所以最后化简为:[f(n),f(n-1)] = [1,1] * {[1,1],[1,0]}^(n-2) * 所以这里的核心是： * 1.矩阵的乘法 * 2.矩阵快速幂（因为如果不用快速幂的算法，时间复杂度也只能达到O(N)） */
    public class Solution { 
        public int Fibonacci(int n) { 
            if(n == 0) { 
                return 0;
            } else if(n == 2 || n == 1) { 
                return 1;
            }
            int [][]base = { { 1, 1}, { 1, 0}};
            
            int [][]res = matrixPower(base, n - 2);
            
            return res[0][0] + res[0][1];
        }
         
        //矩阵乘法
        public int [][] matrixMultiply(int [][] m1, int [][]m2) { 
            int [][] m = new int[m1.length][m2[0].length];
            for(int i = 0;i < m1.length;i++) { 
                for(int j = 0;j < m2[0].length;j++) { 
                    for(int k = 0;k < m2.length;k++) { 
                        m[i][j] += m1[i][k] * m2[k][j];
                    }
                }
            }
            return m;
        }
        /* * 矩阵的快速幂： * 1.假如不是矩阵，叫你求m^n,如何做到O(logn)？答案就是整数的快速幂： * 假如不会溢出，如10^75,把75用用二进制表示：1001011,那么对应的就是： * 10^75 = 10^64*10^8*10^2*10 * 2.把整数换成矩阵，是一样的 */
        public int [][] matrixPower(int [][] m, int p) { 
            int [][]res = new int [m.length][m[0].length];
            
            //初始化res微单位矩阵
            for(int i = 0;i < res.length;i++) { 
                res[i][i] = 1;
            }
            
            // tmp矩阵保存m^n, n是2的指数倍，初始化为m
            int [][] tmp = m;
            
            //快速幂
            for(;p != 0;p >>= 1) { 
                if((p&1) != 0) { 
                    res = matrixMultiply(res, tmp);
                }
                tmp = matrixMultiply(tmp, tmp);
            }
            return res;
        }
    }

## 8. 跳台阶 ##

**题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。**

//解法：多列几个，找找规律，依旧是斐波那契，直接按题目7来就行了

## 9. 变态跳台阶 ##

**题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。**

//解法一：运行时间：13ms 占用内存：9412k
    // record[i] = 2 * record[i - 1]
    public class Solution { 
        
        public static final int N = 100001;
        
        public int JumpFloorII(int target) { 
            if(target == 1) { 
                return 1;
            }
            
            int a = 1;
            for(int i = 2;i <= target;i++) { 
                a *= 2;
            }
            return a;
        }
    }

// 解法二： 运行时间：21ms 占用内存：9228k
    // 相当于求2^(n - 1)这就可以直接库函数
    public class Solution { 
        
        public static final int N = 100001;
        
        public int JumpFloorII(int target) { 
            if(target == 1) { 
                return 1;
            }
            
            return (int)Math.pow(2, target - 1);
        }
    }

// 解法三：运行时间：22ms 占用内存：11620k
    // 快速幂
    public class Solution { 
        
        public static final int N = 100001;
        
        public int JumpFloorII(int target) { 
            if(target == 1) { 
                return 1;
            }
            return ksm(2, target - 1);
        }
        
        //快速幂
        public static int ksm(int a, int p) { 
            int res = 1;
            int tmp = a;
            for(; p != 0;p >>= 1) { 
                if((p&1) != 0) { 
                    res *= tmp;
                }
                tmp *= tmp;
            }
            return res;
        }
    }

## 10.矩形覆盖 ##

**题目：我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？**

// 解法: 斐波那契数列，参考7、8题
    
    // 1.递归做 运行时间：311ms 占用内存：9276k
    // 2.存中间值，防止重复求值：运行时间：50ms 占用内存：25736k
    // 3.矩阵快速幂 运行时间：22ms 占用内存：9364k

## 11.二进制中1的个数 ##

\*\*题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。  
\*\*

//解法一：运行时间：15ms 占用内存：9344k
    //转二进制字符串，遍历字符串
    public class Solution { 
        public int NumberOf1(int n) { 
            int num = 0;
            String str = Integer.toBinaryString(n);
            for(int i = 0;i < str.length();i++) { 
                if(str.charAt(i) == '1') { 
                    num++;
                }
            }
            return num;
        }
    }

// 解法二：运行时间：20ms 占用内存：9340k
    // 最优解法
    /* 如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。 举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。 */
    public class Solution { 
        public int NumberOf1(int n) { 
            int num = 0;
            while(n != 0) { 
                num ++;
                n = n & (n - 1);
            }
            return num;
        }
    }

## 12.数值的整数次方 ##

**题目：**

//解法一：运行时间：60ms 占用内存：10336k
    //需要对exponent进行判断，如果是负的，就取正，然后结果输出倒数
    //同时使用快速幂求解
    public class Solution { 
        public double Power(double base, int exponent) { 
            double res = 1;
            double tmp = base;
            boolean isN = false;
            if(exponent < 0) { 
                isN = true;
                exponent = -exponent;
            }
            for(; exponent != 0;exponent >>= 1) { 
                if((exponent & 1) != 0) { 
                    res = res * tmp;
                }
                tmp = tmp * tmp;
            }
            return isN ? 1 / res : res;
        }
    }

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

**题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。**

//解法一： 运行时间：17ms 占用内存：9328k
    //定义两个数组，分别存奇数和偶数，最后再拷贝在一起
    import java.util.*;
    public class Solution { 
        public void reOrderArray(int [] array) { 
            int []even = new int[array.length];
            int []ood = new int[array.length];
            int idx_even = 0, idx_odd = 0;
            for(int i = 0;i < array.length;i++) { 
                if(array[i] % 2 == 0) { 
                    even[idx_even] = array[i];
                    idx_even++;
                } else { 
                    ood[idx_odd] = array[i];
                    idx_odd++;
                }
            }
            for(int i = idx_odd;i < array.length;i++) { 
                ood[i] = even[i - idx_odd];
            }
            for(int i = 0;i < array.length;i++) { 
                array[i] = ood[i];
            }
        }
    }

## 14.链表中倒数第k个节点 ##

**题目：**

//解法一：运行时间：31ms 占用内存：9552k
    //两个指针，一个先走k步，这样第一个到达链表尾部时，第二个就在倒数第k个位置
    /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution { 
        public ListNode FindKthToTail(ListNode head,int k) { 
            if(head == null || k <= 0) { 
                return null;
            }
            ListNode firstNode = head;
            ListNode secNode = head;
            while(firstNode != null) { 
                firstNode = firstNode.next;
                if(k < 1) { 
                    secNode = secNode.next;
                }
                k--;
            }
            //如果k > 0 表示链表长度不足k，返回null
            if(k > 0) { 
                return null;
            } else { 
                return secNode;
            }
        }
    }

## 15.反转链表 ##

**题目：**

//解法：运行时间：25ms 占用内存：9580k
    //递归（感觉链表的题都可以有一种非常简洁的方法做，通常是递归）
    /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution { 
        public ListNode ReverseList(ListNode head) { 
            if(head == null || head.next == null) { 
                return head;
            }
            ListNode node = ReverseList(head.next);
            head.next.next = head;
            head.next = null;
            return node;
        }
    }

## 16.合并两个排序的链表 ##

**题目：**

//解法：运行时间：27ms 占用内存：9672k
    //递归(还是那句话，感觉链表的题都可以有一种非常简洁的方法做，通常是递归)
    /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution { 
        public ListNode Merge(ListNode list1,ListNode list2) { 
            ListNode head = null;
            if(list1 == null) { 
                return list2;
            } 
            if(list2 == null) { 
                return list1;
            }
            if(list1.val <= list2.val) { 
                head = list1;
                head.next = Merge(list1.next, list2);
            }
            if(list1.val > list2.val) { 
                head = list2;
                head.next = Merge(list1, list2.next);
            }
            return head;
        }
    }

## 17.树的子结构 ##

**题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）**

//解法：运行时间：15ms 占用内存：9556k
    //递归，（感觉树的问题也都可以用一种非常简洁的方法解决，通常是递归）
    /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        public boolean HasSubtree(TreeNode root1,TreeNode root2) { 
            boolean result = false;
            if(root1 == null || root2 == null) { 
                return false;
            }
            if(root1.val == root2.val) { 
                result = doTree1hasTree2(root1, root2);
            }
            if(!result) { 
                result = doTree1hasTree2(root1.left, root2);
            }
            if(!result) { 
                result = doTree1hasTree2(root1.right, root2);
            }
            return result;
        }
        public static boolean doTree1hasTree2(TreeNode root1, TreeNode root2) { 
            if(root2 == null) { 
                return true;
            }
            if(root1 == null) { 
                return false;
            }
            if(root1.val != root2.val) { 
                return false;
            }
            return doTree1hasTree2(root1.left, root2.left) && doTree1hasTree2(root1.right, root2.right);
        }
    }

带代码解释版本：

//运行时间：25ms 占用内存：9276k
    public class Solution { 
        public static boolean HasSubtree(TreeNode root1, TreeNode root2) { 
            boolean result = false;
            //当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
            if (root2 != null && root1 != null) { 
                //如果找到了对应Tree2的根节点的点
                if(root1.val == root2.val){ 
                    //以这个根节点为为起点判断是否包含Tree2
                    result = doesTree1HaveTree2(root1,root2);
                }
                //如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2
                if (!result) { 
                    result = HasSubtree(root1.left,root2);
                }
                 
                //如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
                if (!result) { 
                    result = HasSubtree(root1.right,root2);
                }
            }
                //返回结果
            return result;
        }
     
        public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) { 
            //如果Tree2已经遍历完了都能对应的上，返回true
            if (node2 == null) { 
                return true;
            }
            //如果Tree2还没有遍历完，Tree1却遍历完了。返回false
            if (node1 == null) { 
                return false;
            }
            //如果其中有一个点没有对应上，返回false
            if (node1.val != node2.val) {   
                    return false;
            }
             
            //如果根节点对应的上，那么就分别去子节点里面匹配
            return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
        }
    }

## 18.二叉树的镜像 ##

**题目：操作给定的二叉树，将其变换为源二叉树的镜像。**

二叉树的镜像定义：源二叉树 
        	    8
        	   /  \
        	  6   10
        	 / \  / \
        	5  7 9 11
        	镜像二叉树
        	    8
        	   /  \
        	  10   6
        	 / \  / \
        	11 9 7  5

//解法：运行时间：38ms 占用内存：9616k
    /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        public void Mirror(TreeNode root) { 
            if(root == null) { 
                return;
            }
            TreeNode temp = null;
            temp = root.left;
            root.left = root.right;
            root.right = temp;
            if(root.left != null) { 
                Mirror(root.left);
            }
            if(root.right != null) { 
                Mirror(root.right);
            }
        }
    }

## 19.顺时针打印矩阵 ##

**题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.**

//解法一：运行时间：50ms 占用内存：9468k
    //模拟，根据圈数来，注意只有一行的那种圈，最好画个例子模拟下
    import java.util.ArrayList;
    public class Solution { 
        public ArrayList<Integer> printMatrix(int [][] matrix) { 
            ArrayList<Integer> arrayList = new ArrayList<Integer>();
            int row = matrix.length;
            if(row == 0) { 
                return arrayList;
            }
            int col = matrix[0].length;
            int circle = ((row < col ? row : col) + 1 ) / 2;
            for(int i = 0;i < circle;i++) { 
                
                for(int j = i;j < col - i;j++) { 
                    arrayList.add(matrix[i][j]);
                }
                
                for(int j = i+1;j < row - i;j++) { 
                    arrayList.add(matrix[j][col - i - 1]);
                }
                
                for(int j = col - i - 2;j >= i && row - 1 != 2*i;j--) { 
                    arrayList.add(matrix[row-i-1][j]);
                }
                
                for(int j = row - i - 2;j >= i + 1 && col - 1 != 2*i;j--) { 
                    arrayList.add(matrix[j][i]);
                }
            }
            return arrayList;
        }
    }

//解法二：运行时间：36ms 占用内存：9300k
    //魔方旋转：一次取一行，然后旋转
    import java.util.ArrayList;
    public class Solution { 
        public ArrayList<Integer> printMatrix(int [][] matrix) { 
            ArrayList<Integer> arrayList = new ArrayList<Integer>();
            int row = matrix.length;
            while(row != 0) { 
                for(int i = 0;i < matrix[0].length;i++) { 
                    arrayList.add(matrix[0][i]);
                }
                if(row == 1) break;
                matrix = turn(matrix);
                row = matrix.length;
            }
            return arrayList;
        }
        
        public static int [][] turn(int[][] matrix) { 
            int row = matrix.length;
            int col = matrix[0].length;
            int [][]temp = new int[col][row - 1];
            for(int i = col - 1;i >= 0;i--) { 
                for(int j = 1;j < row;j++) { 
                    temp[col - i - 1][j - 1] = matrix[j][i];
                }
            }
            return temp;
        }
    }

## 20.包含min函数的栈 ##

**题目：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。**

//解法一：运行时间：14ms 占用内存：9376k
    //关键在于，如果push的元素比min大，则minStack还是push的是min，
    //否则push的是node，这样可以保证，每次minStack的栈顶都是当前栈内元素的最小值！！！
    import java.util.Stack;
    import java.util.Arrays;
    public class Solution { 
        
        private int size;
        private Stack<Integer> minStack = new Stack<Integer>();
        private int [] elements = new int[10];
        private int min = Integer.MAX_VALUE;
        
        public void push(int node) { 
            ensureCapacity(size + 1);
            elements[size] = node;
            size++;
            if(node < min) { 
                minStack.push(node);
                min = node;
            } else { 
                minStack.push(min);
            }
        }
        
        private void ensureCapacity(int size) { 
            if(size > elements.length) { 
                int newLen = (elements.length*3) / 2 + 1;
                elements = Arrays.copyOf(elements, newLen);
            }
        }
        
        public void pop() { 
            Integer num = top();
            if(num != null) { 
                size--;
            }
            minStack.pop();
            min = minStack.peek();
        }
        
        
        public int top() { 
            if(size != 0) { 
                return elements[size - 1];
            } else { 
                return (Integer)null;
            }
        }
        
        public int min() { 
            return min;
        }
    }

## 21.栈的压入、弹出序列 ##

**题目：**

//解法一：运行时间：25ms 占用内存：9032k
    //比较简洁的一种解法
    import java.util.ArrayList;
    import java.util.Stack;
    public class Solution { 
        public boolean IsPopOrder(int [] pushA,int [] popA) { 
            Stack<Integer> s = new Stack<Integer>();
            for(int i = 0, j = 0;i < pushA.length;i++) { 
                s.push(pushA[i]);
                while(j < popA.length && s.peek() == popA[j]) { 
                    s.pop();
                    j++;
                }
            }
            return s.empty();
        }
    }

## 22.从上往下打印二叉树 ##

**题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。**

//解法：运行时间：25ms 占用内存：9504k
    //队列结构
    import java.util.ArrayList;
    /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    import java.util.ArrayList;
    public class Solution { 
        
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { 
            
            ArrayList<Integer> arrayList = new ArrayList<Integer>();
            ArrayList<TreeNode> treeList = new ArrayList<TreeNode>();
            
            if(root == null) { 
                return arrayList;
            }
            
            treeList.add(root);
            while(treeList.size() != 0) { 
                TreeNode node = treeList.remove(0);
                arrayList.add(node.val);
                if(node.left != null) { 
                    treeList.add(node.left);
                }
                if(node.right != null) { 
                    treeList.add(node.right);
                }
            }
            return arrayList;
        }
    }

//解法二：运行时间：18ms 占用内存：9360k
    //使用队列实现的，Java里的队列要实现Queue接口
    import java.util.ArrayList;
    /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    import java.util.ArrayList;
    import java.util.Queue;
    import java.util.LinkedList;
    public class Solution { 
        
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { 
            
            ArrayList<Integer> arrayList = new ArrayList<Integer>();
            Queue<TreeNode> treeQueue = new LinkedList<TreeNode>();
            
            if(root == null) { 
                return arrayList;
            }
            
            treeQueue.add(root);
            while(treeQueue.size() != 0) { 
                TreeNode node = treeQueue.remove();
                arrayList.add(node.val);
                if(node.left != null) { 
                    treeQueue.add(node.left);
                }
                if(node.right != null) { 
                    treeQueue.add(node.right);
                }
            }
            return arrayList;
        }
    }

## 23.二叉搜索树的后序遍历序列 ##

**题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。**

//解法：
    //递归：
    //BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。完美的递归定义 : ) 。 
    public class Solution { 
        public boolean VerifySquenceOfBST(int [] sequence) { 
            if(sequence.length == 0) { 
                return false;
            }
            return judge(sequence, 0, sequence.length - 1);
        }
        
        //判断一顿序列是否二叉搜索树
        public static boolean judge(int [] sequence, int l, int r) { 
            if(l >= r) return true;
            
            int i = l;
            while(i < r && sequence[i] < sequence[r]) i++;
            for(int j = i;j < r;j++) { 
                if(sequence[j] < sequence[r]) { 
                    return false;
                }
            }
            return judge(sequence, l, i - 1) && judge(sequence, i, r - 1);
        }
    }

## 24.二叉树中和胃某一值的路径 ##

**题目：**

//解法一：运行时间：22ms 占用内存：9660k
    //满足递归定义，第一种递归方法，在每一个分支节点，new一个新路径，分别处理左右路径
    import java.util.ArrayList;
    /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { 
            ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
            if(root == null) { 
                return paths;
            }
            findPath(paths, new ArrayList<Integer>(), root, target);
            return paths;
        }
        
        public void findPath(ArrayList<ArrayList<Integer>> paths, ArrayList<Integer> path, TreeNode root, int target) { 
            path.add(root.val);
            if(root.left == null && root.right == null) { 
                if(target == root.val) { 
                    paths.add(path);
                }
                return;
            }
            ArrayList<Integer> path2 = new ArrayList<Integer>();
            path2.addAll(path);
            if(root.left!=null) findPath(paths, path, root.left, target - root.val);
            if(root.right!=null) findPath(paths, path2, root.right, target - root.val);
        }
    }

//解法二：运行时间：23ms 占用内存：9536k
    //也是递归版本（加上排序），但是中途不重新申请new一个ArrayList，而是每一层删去最后一个树后回退，有点难理解，我也不太能接受其实
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { 
            ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
            if(root == null) { 
                return paths;
            }
            findPath(paths, new ArrayList<Integer>(), root, target);
            Collections.sort(paths, new Comparator<ArrayList<Integer>>(){ 
                public int compare(ArrayList<Integer> a1, ArrayList<Integer> a2) { 
                    if(a1.size() > a2.size()) { 
                        return -1;
                    } else { 
                        return 1;
                    }
                }
            });
            return paths;
        }
        
        public void findPath(ArrayList<ArrayList<Integer>> paths, ArrayList<Integer> path, TreeNode root, int target) { 
            if(root == null) return;
            path.add(root.val);
            if(target == root.val && root.left == null && root.right == null) { 
                paths.add(new ArrayList<Integer>(path));
            }
            if(root.left!=null) findPath(paths, path, root.left, target - root.val);
            if(root.right!=null) findPath(paths, path, root.right, target - root.val);
            
            path.remove(path.size() - 1);
        }
    }

## 25.复杂链表的复制 ##

**题目：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）**

//解法：运行时间：23ms 占用内存：9712k
    //浅显易懂，其实我不晓得这个题目究竟是个啥意思！！！
    //用HashMap映射，一个原来的节点对应一个新的复制过的节点
    /* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */
    import java.util.HashMap;
    public class Solution { 
        public RandomListNode Clone(RandomListNode pHead) { 
            HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
            RandomListNode cur = pHead;
            
            //复制label的值
            while(cur != null) { 
                map.put(cur, new RandomListNode(cur.label));
                cur = cur.next;
            }
            //复制next的值
            cur = pHead;
            while(cur != null) { 
                map.get(cur).next = map.get(cur.next);
                cur = cur.next;
            }
            //复制random的值
            cur = pHead;
            while(cur != null) { 
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            
            RandomListNode root = map.get(pHead);
            return root;
        }
    }

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

**题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。**

//解法：运行时间：19ms 占用内存：9308k
    //递归：二叉树的中序遍历，改进即可
    /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        private TreeNode leftNode = null;
        private TreeNode rightNode = null;
        public TreeNode Convert(TreeNode pRootOfTree) { 
            if(pRootOfTree == null) { 
                return null;
            }
            Convert(pRootOfTree.left);
            if(leftNode == null) { 
                leftNode = rightNode = pRootOfTree;
            } else { 
                rightNode.right = pRootOfTree;
                pRootOfTree.left = rightNode;
                rightNode = pRootOfTree;
            }
            Convert(pRootOfTree.right);
            return leftNode;
        }
    }

## 27.字符串的排列 ##

**题目：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。  
输入描述:**

> 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

//解法：运行时间：157ms 占用内存：11828k
    //递归全排列，需要注意的是，如果有重复的字符的话，需要在进入递归前判断条件j == i || ch[j] != ch[i]
    import java.util.ArrayList;
    import java.util.Collections;
    public class Solution { 
        public ArrayList<String> Permutation(String str) { 
            ArrayList<String> arrayList = new ArrayList<String>();
            if(str != null && str.length() > 0) { 
                PermutationHelper(str.toCharArray(), 0, arrayList);
            }
            Collections.sort(arrayList);
            return arrayList;
        }
        public void PermutationHelper(char [] ch, int i, ArrayList<String> res) { 
            if(i == ch.length - 1) { 
                res.add(String.valueOf(ch));
            } else { 
                for(int j = i;j < ch.length;j++) { 
                    if(j == i || ch[j] != ch[i]) { 
                        swap(ch, i, j);
                        PermutationHelper(ch, i + 1, res);
                        swap(ch, i, j);
                    }
                }
            }
        }
        public void swap(char [] ch, int i, int j) { 
            char temp = ch[i];
            ch[i] = ch[j];
            ch[j] = temp;
        }
    }

## 28.数组中出现次数超过一半的数字 ##

**题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。**

//解法：运行时间：22ms 占用内存：9352k
    //排序后找中间的那个数，就是次数超过一半的，再遍历一遍，看是不是，因为有sort，复杂度：O(nlogn)
    import java.util.Arrays;
    public class Solution { 
        public int MoreThanHalfNum_Solution(int [] array) { 
            Arrays.sort(array);
            int middle = array[array.length / 2];
            int num = 0;
            for(int i = 0;i < array.length;i++) { 
                if(array[i] == middle) { 
                    num++;
                }
            }
            if(num > array.length / 2) { 
                return middle;
            } else { 
                return 0;
            }
        }
    }

## 29.最小的k个数 ##

**题目：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。**

//解法一：运行时间：33ms 占用内存：9600k
    //排序，取前k个数
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.*;
    public class Solution { 
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { 
            ArrayList<Integer> arrayList = new ArrayList<Integer>();
            if(k > input.length || k < 0) { 
                return arrayList;
            }
            Arrays.sort(input);
            int [] temp = Arrays.copyOfRange(input, 0, k);
            
            for(int i = 0;i < temp.length;i++) { 
                arrayList.add(temp[i]);
            }
            return arrayList;
        }
    }

//解法二：运行时间：24ms 占用内存：9484k
    //最小堆：java的优先队列是用堆实现的
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.PriorityQueue;
    import java.util.Comparator;
    public class Solution { 
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { 
            ArrayList<Integer> arrayList = new ArrayList<Integer>();
            if(k > input.length || k <= 0) { 
                return arrayList;
            }
            PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>(){ 
                public int compare(Integer o1, Integer o2) { 
                    if(o1 > o2) { 
                        return -1;
                    } else { 
                        return 1;
                    }
                }
            });
            
            for(int i = 0;i < input.length;i++) { 
                if(maxHeap.size() != k) { 
                    maxHeap.offer(input[i]);
                } else if(maxHeap.peek() > input[i]) { 
                    maxHeap.poll();
                    maxHeap.offer(input[i]);
                }
            }
            for(Integer i : maxHeap) { 
                arrayList.add(i);
            }
            
            
            
            return arrayList;
        }
    }

## 30.连续子数组的最大和 ##

**题目：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:\{6,-3,-2,7,-15,1,2,2\},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)**

//解法一：运行时间：15ms 占用内存：9368k
    //
    public class Solution { 
        public int FindGreatestSumOfSubArray(int[] array) { 
            if(array.length == 0) { 
                return -1;
            }
            int res = 0;
            int max = 0;
            for(int i = 0;i < array.length;i++) { 
                res += array[i];
                if(res <= 0) { 
                    res = 0;
                } else { 
                    max = res > max? res : max;
                }
            }
            if(max == 0) { 
                return -1;
            } else { 
                return max;
            }
        }
    }

//解法二：运行时间：25ms 占用内存：9036k
    //动态规划
    public class Solution { 
        public int FindGreatestSumOfSubArray(int[] array) { 
            if(array.length == 0) { 
                return -1;
            }
            int res = 0;
            int[] dp = new int[array.length];
            dp[0] = array[0] < 0 ? 0 : array[0];
            for(int i = 1;i < array.length;i++) { 
                //以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变 
                dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
                res = Math.max(dp[i], res);
            }
            if(res <= 0) { 
                return -1;
            } else { 
                return res;
            }
        }
    }

## 31.整数中1出现的次数（从1到n） ##

**题目：求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。**

//解法一：运行时间：17ms 占用内存：9508k
    //暴力
    public class Solution { 
        public int NumberOf1Between1AndN_Solution(int n) { 
            int totalNum = 0;
            for(int i = 1;i <= n;i++) { 
                totalNum += get1OfNum(i);
            }
            return totalNum;
        }
        
        public int get1OfNum(int n) { 
            int num = 0;
            while(n != 0) { 
                if(n % 10 == 1) { 
                    num++;
                }
                n /= 10;
            }
            return num;
        }
    }

//解法二；运行时间：14ms 占用内存：9464k
    //找规律解法
    //https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6
    public class Solution { 
        public int NumberOf1Between1AndN_Solution(int n) { 
            int totalNum = 0;
            if(n <= 0) { 
                return 0;
            }
            for(long i = 1;i <= n;i *= 10) { 
                long div = i * 10;
                totalNum += (n / div) * i + Math.min(Math.max(n % div - i + 1, 0), i);
            }
            return totalNum;
        }
    }

## 32.把数组排成最小的数 ##

**题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组\{3，32，321\}，则打印出这三个数字能排成的最小数字为321323。**

//解法：运行时间：23ms 占用内存：9800k
    //重载sort
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Arrays;
    import java.util.Comparator;
    
    public class Solution { 
        public String PrintMinNumber(int [] numbers) { 
            
            ArrayList<Integer> arrayList = new ArrayList<Integer>();
            for(int num : numbers) { 
                arrayList.add(num);
            }
            Collections.sort(arrayList, new Comparator<Integer>(){ 
                public int compare(Integer a, Integer b) { 
                    String str1 = a + "" + b;
                    String str2 = b + "" + a;
                    return str1.compareTo(str2);
                }
            });
            
            String res = "";
            for(int num : arrayList) { 
                res += num;
            }
            
            return res;
        }
    }

## 33.丑数 ##

**题目：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。**

//解法一：运行时间：19ms 占用内存：9544k
    //暴力求解，注意p2， p3， p5队列里存的是res[]*(2, 3, 5), 而不是对应2，3，5的倍数，看懵了好久
    //解析：https://www.nowcoder.com/questionTerminal/6aa9e04fc3794f68acf8778237ba065b
    //例如：P1队列：2 4 6 8 10 12 18，这里每一个队列里存的是丑数队列里*2、*3、*5的值，而不是队列里前一个数加2，所以P1队列里12后面是18而不是14
    import java.util.ArrayList;
    
    public class Solution { 
        public int GetUglyNumber_Solution(int index) { 
            if(index < 7) { 
                return index;
            }
            ArrayList<Integer> arrayList = new ArrayList<Integer>();
            int p2 = 0, p3 = 0, p5 = 0;
            arrayList.add(1);
            
            for(int i = 1;i < index;i++) { 
                int Min = Math.min(arrayList.get(p2) * 2, Math.min(arrayList.get(p3) * 3, arrayList.get(p5) * 5));
                arrayList.add(Min);
                if(Min == arrayList.get(p2) * 2) p2++;
                if(Min == arrayList.get(p3) * 3) p3++;
                if(Min == arrayList.get(p5) * 5) p5++;
            }
            
            return arrayList.get(index - 1);
        }
    }

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

**题目：在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.**

//解法：运行时间：52ms 占用内存：9892k
    //HashMap查询
    import java.util.HashMap;
    
    public class Solution { 
        public int FirstNotRepeatingChar(String str) { 
            if(str.length() == 0 || str == null) { 
                return -1;
            }
            HashMap<Character, Integer> m = new HashMap<>();
            
            for(int i = 0;i < str.length();i++) { 
                if(m.containsKey(str.charAt(i))) { 
                    int t = m.get(str.charAt(i));
                    m.put(str.charAt(i), ++t);
                } else { 
                    m.put(str.charAt(i), 1);
                }
            }
            
            for(int i = 0;i < str.length();i++) { 
                if(m.get(str.charAt(i)) == 1) { 
                    return i;
                }
            }
            return -1;
        }
    }

## 35. 数组中的逆序对 ##

**题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007  
输入描述:**

题目保证输入的数组中没有的相同的数字
    
    数据范围：
    
    	对于%50的数据,size<=10^4
    
    	对于%75的数据,size<=10^5
    
    	对于%100的数据,size<=2*10^5

//解法一：暴力O（n^2），这种方法过不了，（—_-）
    public class Solution { 
        public int InversePairs(int [] array) { 
            int count = 0;
            for(int i = 0;i < array.length;i++) { 
                for(int j = i + 1;j < array.length;j++) { 
                    if(array[i] > array[j]) count++;
                }
            }
            return count;
        }
    }

//解法二：运行时间：683ms 占用内存：51552k
    //归并排序的变形，刚开始过不了，是因为没有对1000000000...7取模！！！
    //看了大部分题解，也都是归并来做的
    //看代码前，建议把归并排序的源代码看一看，就可以发现这个代码非常相似！
    public class Solution { 
        public int InversePairs(int [] array) { 
            if(array.length == 0) { 
                return 0;
            }
            return MergeSortFindInversePairs(array, 0, array.length - 1);
        }
    
        public static int MergeSortFindInversePairs(int [] array, int start, int end) { 
    
            if(start >= end) return 0;
            int mid = (start + end) / 2;
    
            int leftCount = MergeSortFindInversePairs(array, start, mid);
            int rightCount = MergeSortFindInversePairs(array, mid + 1, end);
    
            int foreIdx = start;
            int backIdx = mid + 1;
            int k = 0;
            int[] tmp = new int[end - start + 1];
    
            int count = 0;
    
            while(foreIdx <= mid && backIdx <= end) { 
                if(array[foreIdx] < array[backIdx]) { 
                    tmp[k++] = array[foreIdx++];
                } else { 
                    tmp[k++] = array[backIdx++];
                    count += mid - foreIdx + 1;
                    if(count>=1000000007) { //数值过大求余
                        count%=1000000007;
                    }
                }
            }
    
            while(foreIdx <= mid) { 
                tmp[k++] = array[foreIdx++];
            }
    
            while(backIdx <= end) { 
                tmp[k++] = array[backIdx++];
            }
    
            for(int i = 0;i < k;i++) { 
                array[start + i] = tmp[i];
            }
    
            return (leftCount + rightCount + count) % 1000000007;
        }
    }

## 36.两个链表的第一个公共节点 ##

**题目：输入两个链表，找出它们的第一个公共结点。**

//解法一：运行时间：30ms 占用内存：9396k
    //先让长的链表先走链表长度差，再比较，因为两个链表有公共尾部
    /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution { 
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { 
             
            int len1 = FindListLen(pHead1);
            int len2 = FindListLen(pHead2);
            if(len1 > len2) { 
                int k = len1 - len2;
                while(k != 0) { 
                    pHead1 = pHead1.next;
                    k--;
                }
            } else { 
                int k = len2 - len1;
                while(k != 0) { 
                    pHead2 = pHead2.next;
                    k--;
                }
            }
            
            while(pHead1 != null) { 
                if(pHead1 == pHead2) { 
                    return pHead1;
                }
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
            return null;
        }
        
        
        public int FindListLen(ListNode pHead) { 
            ListNode p = pHead;
            int len = 0;
            while(p != null) { 
                len++;
                p = p.next;
            }
            return len;
        }
        
    }

//解法二：运行时间：19ms 占用内存：9564k
    //利用HashMap
    /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    import java.util.HashMap;
    public class Solution { 
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { 
            HashMap<ListNode, Integer> m = new HashMap<ListNode, Integer>(); 
            
            while(pHead1 != null) { 
                m.put(pHead1, null);
                pHead1 = pHead1.next;
            }
            
            while(pHead2 != null) { 
                if(m.containsKey(pHead2)) { 
                    return pHead2;
                }
                pHead2 = pHead2.next;
            }
            return null;
        }
    }

## 37.数字在排序数组中出现的次数 ##

**题目：统计一个数字在排序数组中出现的次数。**

//解法一：运行时间：21ms 占用内存：9348k
    //二分后，向两边找
    public class Solution { 
        public int GetNumberOfK(int [] array , int k) { 
            int start = 0;
            int end = array.length - 1;
            int count = 0;
            while(start <= end) { 
                int mid = (start + end) / 2;
                if(array[mid] < k) { 
                    start = mid + 1;
                } else if(array[mid] > k) { 
                    end = mid - 1;
                } else { 
                    
                    int i = mid, j = mid + 1;
                    while(i >= 0 && array[i] == k) { 
                        count++;
                        i--;
                    }
                    while(j < array.length && array[j] == k) { 
                        count++;
                        j++;
                    }
                    return count;
                }
            }
            return 0;
        }
    }

//解法二：运行时间：13ms 占用内存：9264k
    //二分黑科技，学习了
    //经实验，如果二分法找的值k，不在数组中，那么最后返回的下标是小于k的那个值下标，这样我们找（k-0.5, k+0.5）就行了
    public class Solution { 
        public int GetNumberOfK(int [] array , int k) { 
            return binarySearch(array, k+0.5) - binarySearch(array, k-0.5);
        }
        
        public int binarySearch(int[] array, double k) { 
            int start = 0, end = array.length - 1;
            while(start <= end) { 
                int mid = (start + end) / 2;
                if(array[mid] < k) { 
                    start = mid + 1;
                } else if(array[mid] > k) { 
                    end = mid - 1;
                }
            }
            return start ;
        }
    }

## 38.二叉树的深度 ##

**题目：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。**

//解法一：运行时间：16ms 占用内存：9420k
    //递归版本
    /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        public int TreeDepth(TreeNode root) { 
            if(root == null) { 
                return 0;
            }
            int leftDepth = TreeDepth(root.left);
            int rightDepth = TreeDepth(root.right);
            return 1 +  Math.max(leftDepth, rightDepth);
        }
    }

//解法二：运行时间：35ms 占用内存：9356k
    //非递归版
    /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class Solution { 
        public int TreeDepth(TreeNode root) { 
            if(root == null) { 
                return 0;
            }
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.add(root);
            int depth = 0;
            while(q.size() != 0) { 
                int size = q.size();
                depth++;
                for(int i = 0;i < size;i++) { 
                    TreeNode temp = q.poll();
                    if(temp.left != null) q.add(temp.left);
                    if(temp.right != null) q.add(temp.right);
                }
            }
            return depth;
        }
    }

## 39.平衡二叉树 ##

**题目：输入一棵二叉树，判断该二叉树是否是平衡二叉树。**

//解法一：运行时间：20ms 占用内存：9328k
    //递归版，复杂度较大
    public class Solution { 
        public boolean IsBalanced_Solution(TreeNode root) { 
            if(root == null) { 
                return true;
            }
            return Math.abs(binaryDepth(root.left) - binaryDepth(root.right)) <= 1 &&
                IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
        }
        
        public int binaryDepth(TreeNode root) { 
            if(root == null) return 0;
            return 1 + Math.max(binaryDepth(root.left), binaryDepth(root.right));
        }
    }

//解法二：运行时间：16ms 占用内存：9204k
    //剪枝版
    public class Solution { 
        public boolean IsBalanced_Solution(TreeNode root) { 
            return binaryDepth(root) != -1;
        }
        
        public int binaryDepth(TreeNode root) { 
            if(root == null) return 0;
            int left = binaryDepth(root.left);
            if(left == -1) return -1;
            int right = binaryDepth(root.right);
            if(right == -1) return -1;
            return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
        }
    }

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

**题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。**

//解法一：运行时间：25ms 占用内存：9612k
    //利用HahMap，有点小题大作的感觉
    //num1,num2分别为长度为1的数组。传出参数
    //将num1[0],num2[0]设置为返回结果
    import java.util.HashMap;
    public class Solution { 
        public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { 
            HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
            for(int i = 0;i < array.length;i++) { 
                if(mp.containsKey(array[i])) { 
                    int count = mp.get(array[i]);
                    mp.put(array[i], ++count);
                } else { 
                    mp.put(array[i], 1);
                }
            }
            boolean flagNum1 = false;
            for(int i = 0;i < array.length;i++) { 
                if(mp.get(array[i]) == 1) { 
                    if(flagNum1) { 
                        num2[0] = array[i];
                    } else { 
                        num1[0] = array[i];
                        flagNum1 = true;
                    }
                }
            }
        }
    }

//解法二：运行时间：15ms 占用内存：9440k
    //通过异或，（技术流方法，解析请看https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811）
    //num1,num2分别为长度为1的数组。传出参数
    //将num1[0],num2[0]设置为返回结果
    import java.util.HashMap;
    public class Solution { 
        public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { 
            int len = array.length;
            if(len == 2) { 
                num1[0] = array[0];
                num2[0] = array[1];
            }
            int bitNum = 0;
            for(int i = 0;i < len;i++) { 
                bitNum ^= array[i];
            }
            int index = findFirst1(bitNum);
            for(int i = 0;i < len;i++) { 
                if(isBit1(array[i], index)) { 
                    num1[0] ^= array[i];
                } else { 
                    num2[0] ^= array[i];
                }
            }
        }
        
        public int findFirst1(int num) { 
            int index = 0;
            while((num & 1) == 0 && num < 32) { 
                num >>= 1;
                index++;
            }
            return index;
        }
        
        public boolean isBit1(int num, int index) { 
            return ((num >> index) & 1) == 1;
        }
    }

## 41.和为S的连续正数序列 ##

**题目：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!  
输出描述:**

> 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

//解法：运行时间：32ms 占用内存：9620k
    //穷举
    import java.util.ArrayList;
    public class Solution { 
        public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { 
            if(sum <= 0) { 
                return null;
            }
            ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
            int[] Plus = new int[sum + 5];
            Plus[0] = 0;
            Plus[1] = 1;
            for(int i = 2;i <= sum;i++) { 
                Plus[i] = Plus[i - 1] + i;
            }
            
            for(int i = 0;i < sum;i++) { 
                for(int j = 0;j < sum;j++) { 
                    if(Plus[j] - Plus[i] == sum) { 
                        ArrayList<Integer> arrayList = new ArrayList<Integer>();
                        for(int k = i + 1;k <= j;k++) { 
                            arrayList.add(k);
                        }
                        res.add(arrayList);
                        break;
                    } else if(Plus[j] - Plus[i] > sum) { 
                        break;
                    }
                }
            }
            return res;
        }
    }

//解法二：运行时间：20ms 占用内存：9556k
    //滑动窗口法
    import java.util.ArrayList;
    
    public class Solution { 
        public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { 
    
            ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
            
            int pLow = 1;
            int pHigh = 2;
            
            while(pHigh > pLow) { 
                int cur = (pHigh + pLow) * (pHigh - pLow + 1) / 2;
                if(cur == sum) { 
                    ArrayList<Integer> arrayList = new ArrayList<Integer>();
                    for(int i = pLow;i <= pHigh;i++) { 
                        arrayList.add(i);
                    }
                    res.add(arrayList);
                    pLow++;
                } else if(cur < sum) { 
                    pHigh++;
                } else { 
                    pLow++;
                }
                
            }
            return res;
            
        }
    }

## 42.和为S的两个数字 ##

**题目：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。  
输出描述:**

> 对应每个测试案例，输出两个数，小的先输出。

//解法一：运行时间：16ms 占用内存：9304k
    //二分查找
    import java.util.ArrayList;
    public class Solution { 
        public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { 
            
            ArrayList<Integer> res = new ArrayList<>();
            
            for(int i = 0;i < array.length;i++) { 
                if(binarySearch(array, sum - array[i])) { 
                    res.add(array[i]);
                    res.add(sum - array[i]);
                    return res;
                }
            }
            return res;
        }
        
        public boolean binarySearch(int [] array,int num) { 
            int s = 0;
            int e = array.length - 1;
            while(s <= e) { 
                int mid = (s + e) / 2;
                if(array[mid] < num) { 
                    s = mid + 1;
                } else if(array[mid] > num) { 
                    e = mid - 1;
                } else { 
                    return true;
                }
            }
            return false;
        }
    }

//解法二：运行时间：13ms 占用内存：9268k
    //前后指针法
    import java.util.ArrayList;
    public class Solution { 
        public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { 
            ArrayList<Integer> res = new ArrayList<>();
            int s = 0, e = array.length - 1;
            while(s < e) { 
                if(array[s] + array[e] == sum) { 
                    res.add(array[s]);
                    res.add(array[e]);
                    return res;
                } else if(array[s] + array[e] < sum) { 
                    s++;
                } else { 
                    e--;
                }
            }
            return res;
        }
    }

## 43.左旋转字符串 ##

**题目：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！**

//解法一：运行时间：25ms 占用内存：11224k
    //substring即可
    public class Solution { 
        public String LeftRotateString(String str,int n) { 
            String resStr = "";
            if(n > str.length()) { 
                return resStr;
            }
            resStr += str.substring(n, str.length());
            resStr += str.substring(0, n);
            
            return resStr;
        }
    }

## 44.翻转单词顺序列 ##

**题目：牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？**

//解法：运行时间：31ms 占用内存：9384k
    //注意str.trim().equals()的使用，比较字符串内容时，应该用equals，而不是==
    public class Solution { 
        public String ReverseSentence(String str) { 
            if(str.trim().equals("")) { 
                return str;
            }
            String[] arrayStr = str.split(" ");
            StringBuilder sb = new StringBuilder();
            
            for(int i = arrayStr.length - 1;i >= 0;i--) { 
                sb.append(arrayStr[i]);
                if(i >= 1) { 
                    sb.append(" ");
                }
            }
            
            return sb.toString();
        }
    }

## 45.扑克牌顺子 ##

**题目：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张\_)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…LL不高兴了,他想了想,决定大\\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。**

//解法：运行时间：14ms 占用内存：9248k
    /* 1、排序 2、计算所有相邻数字间隔总数 3、计算0的个数 4、如果2、3相等，就是顺子 5、如果出现对子，则不是顺子 */
    import java.util.Arrays;
    public class Solution { 
        public boolean isContinuous(int [] numbers) { 
            if(numbers.length == 0) { 
                return false;
            }
            int numOfZero = 0; //0的数目
            int numOfInterval = 0;//间隔数目
            
            Arrays.sort(numbers);
            for(int i = 0;i < numbers.length - 1;i++) { 
                if(numbers[i] == 0) { 
                    numOfZero++;
                    continue;
                }
                if(numbers[i] == numbers[i+1]) { 
                    return false;
                }
                numOfInterval += numbers[i+1] - numbers[i] - 1;
            }
            if(numOfZero >= numOfInterval) { 
                return true;
            } 
            return false;
        }
    }

## 46.孩子们的游戏(圆圈中最后剩下的数) ##

**每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!\_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)**

//解法：运行时间：14ms 占用内存：9176k
    //约瑟夫环，递归解法
    import java.util.LinkedList;
    import java.util.List;
    public class Solution { 
        public int LastRemaining_Solution(int n, int m) { 
            if(m == 0 || n==0) { 
                return -1;
            } 
            int res = 0;
            for(int i = 2;i <= n;i++) { 
                res = (res + m) % i;
            }
            return res;
        }
    }

## 47.求1+2+3+…+n ##

**题目：求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。**

//解法：运行时间：12ms 占用内存：9184k
    //等差数列求和公式....
    public class Solution { 
        public int Sum_Solution(int n) { 
            return n * (1 + n) / 2;
        }
    }

//解法二：运行时间：17ms 占用内存：9252k
    //大神的做法，&& 逻辑与的短路操作
    public class Solution { 
        public int Sum_Solution(int n) { 
            int ans = n;
            boolean flag = (ans > 0) && ((ans += Sum_Solution(n - 1)) > 0);
            return ans;
        }
    }

## 48.不用加减乘除做加法 ##

**题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、\*、/四则运算符号。**

//解法：运行时间：13ms 占用内存：9416k
    public class Solution { 
        public int Add(int num1,int num2) { 
            while (num2!=0) { 
                int temp = num1^num2;
                num2 = (num1&num2)<<1;
                num1 = temp;
            }
            return num1;
        }
    }

## 49.把字符串转换成整数 ##

**题目：将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。**

//解法： 运行时间：13ms 占用内存：9276k
    public class Solution { 
        public int StrToInt(String str) { 
            if(str == null || str.length() == 0) { 
                return 0;
            }
            int res = 0;
            boolean flag = false;//判断是否负数，false ----> 正数
            int i = 0;//循环变量
            if(!Character.isDigit(str.charAt(0))) { 
                if(str.charAt(0) == '-') { 
                    flag = true;
                } else if(str.charAt(0) == '+') { 
                    flag = false;
                } else {  //如果是其他字符，就不是字符串
                    return 0;
                }
                i++;
            }
            for(;i < str.length();i++) { 
                if(!Character.isDigit(str.charAt(i))) { 
                    return 0;
                }
                res = res*10 + (int)(str.charAt(i) - '0');
            }
            if(flag) { 
                res = 0 - res;
            }
            return res;
        }
    }

## 50.数组中重复的数字 ##

**题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是第一个重复的数字2。**

//解法：运行时间：18ms 占用内存：9660k
    //HashMap做法
    import java.util.HashMap;
    public class Solution { 
        // Parameters:
        // numbers: an array of integers
        // length: the length of array numbers
        // duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
        // Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
        // 这里要特别注意~返回任意重复的一个，赋值duplication[0]
        // Return value: true if the input is valid, and there are some duplications in the array number
        // otherwise false
        public boolean duplicate(int numbers[],int length,int [] duplication) { 
            HashMap<Integer, Integer> mp = new HashMap<>();
            for(int i = 0;i < length;i++) { 
                if(!mp.containsKey(numbers[i])) { 
                    mp.put(numbers[i], 1);
                } else { 
                    duplication[0] = numbers[i];
                    return true;
                }
            }
            return false;
        }
    }

//解法二：运行时间：23ms 占用内存：9656k
    //相当于哈希数组法
    import java.util.Arrays;
    public class Solution { 
        // Parameters:
        // numbers: an array of integers
        // length: the length of array numbers
        // duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
        // Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
        // 这里要特别注意~返回任意重复的一个，赋值duplication[0]
        // Return value: true if the input is valid, and there are some duplications in the array number
        // otherwise false
        public boolean duplicate(int numbers[],int length,int [] duplication) { 
            boolean[] isDup = new boolean[length];
            Arrays.fill(isDup, false);
            for(int i = 0;i < length;i++) { 
                if(!isDup[numbers[i]]) { 
                    isDup[numbers[i]] = true;
                } else { 
                    duplication[0] = numbers[i];
                    return true;
                }
            }
            return false;
        }
    }

## 51.构建乘积数组 ##

**题目：给定一个数组A\[0,1,…,n-1\],请构建一个数组B\[0,1,…,n-1\],其中B中的元素B\[i\]=A\[0\]·A\[1\]·…·A\[i-1\]·A\[i+1\]·…·\[n-1\]。不能使用除法**

//解法：运行时间：25ms 占用内存：9244k
    import java.util.ArrayList;
    //倒三角解法
    public class Solution { 
        public int[] multiply(int[] A) { 
            int[] b = new int[A.length];
            b[0] = 1;
            if(A.length == 0) { 
                return b;
            }
            for(int i = 1;i < A.length;i++) { 
                b[i] = b[i - 1] * A[i - 1];
            }
            int temp = 1;
            for(int i = A.length - 2;i >= 0;i--) { 
                temp *= A[i + 1];
                b[i] *= temp;
            }
            return b;
        }
    }

## 52.正则表达式匹配 ##

**题目：请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab\*a"均不匹配**

//解法：运行时间：14ms 占用内存：9272k
    //https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c
    //注意每一次访问数组的时候都要进行下表判断
    public class Solution { 
        public boolean match(char[] str, char[] pattern) { 
            if(str == null || pattern == null) { 
                return false;
            }
            return matchHelper(str, 0, pattern, 0);
        }
        
        public boolean matchHelper(char[] str, int strIdx, char[]  pattern, int patternIdx) { 
            //字符串走到尾，模式走到尾，返回true
            if(strIdx == str.length && patternIdx == pattern.length) { 
                return true;
            }
            //字符串没有走到尾，模式走到尾，返回false
            if(strIdx != str.length && patternIdx == pattern.length) { 
                return false;
            }
            
            //如果模式串第二个是*
            /* if(patternIdx + 1 < pattern.length && pattern[patternIdx + 1] == '*') { //如果模式串第一个与字符串第一个匹配,三匹配方式 if((str[strIdx] == pattern[patternIdx] && strIdx < str.length)|| (pattern[patternIdx] == '.' && strIdx < str.length)) { return matchHelper(str, strIdx, pattern, patternIdx + 2) || matchHelper(str, strIdx + 1, pattern, patternIdx) || matchHelper(str, strIdx + 1, pattern, patternIdx + 2); } else { return matchHelper(str, strIdx, pattern, patternIdx + 2); } } */
            if (patternIdx + 1 < pattern.length && pattern[patternIdx + 1] == '*') { 
                if ((strIdx != str.length && pattern[patternIdx] == str[strIdx]) || (pattern[patternIdx] == '.' && strIdx != str.length)) { 
                    return matchHelper(str, strIdx, pattern, patternIdx + 2)//模式后移2，视为x*匹配0个字符
                            || matchHelper(str, strIdx + 1, pattern, patternIdx + 2)//视为模式匹配1个字符
                            || matchHelper(str, strIdx + 1, pattern, patternIdx);//*匹配1个，再匹配str中的下一个
                } else { 
                    return matchHelper(str, strIdx, pattern, patternIdx + 2);
                }
            }
            if((strIdx != str.length && pattern[patternIdx] == str[strIdx]) || (pattern[patternIdx] == '.' && strIdx != str.length)) { //如果不是*
                return matchHelper(str, strIdx + 1, pattern, patternIdx + 1);
            }
            return false;
        }
        
    }

## 53.表示数值的字符串 ##

**题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。**

//解法：运行时间：22ms 占用内存：9336k
    //这题完全按题意写就行，一个一个查
    public class Solution { 
        public boolean isNumeric(char[] str) { 
            
            int len = str.length;
            int decNum = 0;//小数点数目
            int eNum = 0;//是否是指数，指数后面不能有小数点
            //如果第一位是数字或者正负号
            if(Character.isDigit(str[0]) || str[0] == '+' || str[0] == '-') { 
                for(int i = 1;i < len;i++) { 
                    if(str[i] == 'e' || str[i] == 'E') { 
                        eNum++;
                        if(i + 1 == len) return false; //如果e后面没有数字，返回false
                        if(str[i+1] == '+' || str[i+1] == '-') { //指数可以是正负号
                            i++;
                        }
                    } else if(str[i] == '.') { 
                        if(eNum != 0 || decNum != 0) { //说明是指数,不能有小数点
                            return false;
                        } 
                        decNum++;
                    } else if(!Character.isDigit(str[i])) { 
                        return false;
                    }
                }
            } else { 
                return false;
            }
            
            return true;
        }
    }

## 54.字符流中第一个不重复的字符 ##

\*\*题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。  
\*\*

//解法一：运行时间：18ms 占用内存：9668k
    //哈希
    public class Solution { 
        
        int[] hash = new int[256];
        StringBuilder sb = new StringBuilder();
        
        //Insert one char from stringstream
        public void Insert(char ch)
        { 
            sb.append(ch);
            if(hash[ch] == 0) { 
                hash[ch] = 1;
            } else { 
                hash[ch] += 1;
            }
        }
      //return the first appearence once char in current stringstream
        public char FirstAppearingOnce()
        { 
            char [] ch = sb.toString().toCharArray();
            for(char c : ch) { 
                if(hash[c] == 1) { 
                    return c;
                }
            }
                return '#';
        }
    }

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

**题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。**

//解法：运行时间：17ms 占用内存：9544k
    //解析：https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4?f=discussion
    /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
    public class Solution { 
    
        public ListNode EntryNodeOfLoop(ListNode pHead)
        { 
            ListNode fast = pHead;
            ListNode low = pHead;
            //找相遇点
            while(fast != null && fast.next != null) { 
                fast = fast.next.next;
                low = low.next;
                if(fast == low) { 
                    break;
                }
            }
            if(fast == null || fast.next == null) return null;
            low = pHead;
            while(fast != low) { 
                fast = fast.next;
                low = low.next;
            }
            return low;
        }
    }

## 56.删除链表中重复的节点 ##

**题目：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5**

//解法一：运行时间：19ms 占用内存：9712k
    //递归法
    /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
    import java.util.HashMap;
    public class Solution { 
        public ListNode deleteDuplication(ListNode pHead) { 
            if(pHead == null || pHead.next == null) { 
                return pHead;
            }
            if(pHead.val == pHead.next.val) { 
                ListNode pNode = pHead.next;
                while(pNode != null && pNode.val == pHead.val) { 
                    pNode = pNode.next;
                }
                return deleteDuplication(pNode);
            } else { 
                pHead.next = deleteDuplication(pHead.next);
                return pHead;
            }
        }
    }

//解法二：运行时间：19ms 占用内存：9660k
    //非递归，有点难度，没看懂
    /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
    import java.util.HashMap;
    public class Solution { 
        public ListNode deleteDuplication(ListNode pHead) { 
            if(pHead == null || pHead.next == null) { 
                return pHead;
            }
            ListNode root = new ListNode(0);
            root.next = pHead;
            ListNode pre = root;
            ListNode last = root.next;
            
            while(last != null) { 
                if(last.next != null && last.val == last.next.val) { 
                    while(last.next != null && last.val == last.next.val) { 
                        last = last.next;
                    }
                    pre.next = last.next;
                    last = last.next;
                } else { 
                    
                    pre = pre.next;
                    last = last.next;
                }
            }
            return root.next;
        }
    }

## 57.二叉树的下一个结点 ##

**给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。**

//解法：运行时间：30ms 占用内存：9604k
    /* 1、有右子树的，那么下个结点就是右子树最左边的点 2、没有右子树的，也可以分成两类，a)是父节点左孩子，那么父节点就是下一个节点b)是父节点的右孩子，找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有，那么他就是尾节点。 */
    /* public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; } } */
    public class Solution { 
        public TreeLinkNode GetNext(TreeLinkNode pNode) { 
            if(pNode == null) { 
                return null;
            }
            //如果当前节点有右子树
            if(pNode.right != null) { 
                TreeLinkNode node = pNode.right;
                while(node.left != null) { 
                    node = node.left;
                }
                return node;
            }
            //如果没有右子树，找父节点为左子树的父节点
            while(pNode.next != null) { 
                if(pNode.next.left == pNode) { 
                    return pNode.next;
                }
                pNode = pNode.next;
            }
            //如果没有找到，那么这个节点就是尾节点，下一个节点是null
            return null;
        }
    }

## 58.对称的二叉树 ##

**题目：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。**

//解法；运行时间：22ms 占用内存：9404k
    //依旧是递归（二叉树和链表类的题目基本上都递归的简便解法）
    /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        boolean isSymmetrical(TreeNode pRoot) { 
            if(pRoot == null) return true;
            
            return isSymmetricalHelper(pRoot.left, pRoot.right);
        }
        
        boolean isSymmetricalHelper(TreeNode left, TreeNode right) { 
            if(left == null) return right == null;
            if(right == null) return false;
            if(left.val != right.val) return false;
            return isSymmetricalHelper(left.right, right.left) && isSymmetricalHelper(left.left, right.right);
        }
    }

## 59.按之字形顺序打印二叉树 ##

**题目：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。**

//解法：运行时间：23ms 占用内存：9692k
    //层序遍历，偶数层进行reverse
    import java.util.ArrayList;
    
    /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    import java.util.Queue;
    import java.util.LinkedList;
    import java.util.Collections;
    public class Solution { 
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { 
            ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
            if(pRoot == null) { 
                return res;
            }
            Queue<TreeNode> q = new LinkedList<>();
            q.add(pRoot);
            int k = 0;//当前在第几层，需不需要取反
            while(q.size() != 0) { 
                int size = q.size();
                ArrayList<Integer> arrayList = new ArrayList<>();
                for(int i = 0;i < size;i++) { 
                    TreeNode t = q.remove();
                    arrayList.add(t.val);
                    if(t.left != null) { 
                        q.add(t.left);
                    }
                    if(t.right != null) { 
                        q.add(t.right);
                    }
                }
                if(k % 2 != 0) { 
                    Collections.reverse(arrayList);
                }
                k++;
                res.add(arrayList);
            }
            return res;
        }
    
    }

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

**题目：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。**

//解法；运行时间：33ms 占用内存：9428k
    //二叉树的层序遍历
    import java.util.ArrayList;
    import java.util.Queue;
    import java.util.LinkedList;
    import java.util.Collections;
    /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { 
            ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
            if(pRoot == null) { 
                return res;
            }
            Queue<TreeNode> q = new LinkedList<>();
            q.add(pRoot);
            
            while(q.size() != 0) { 
                int size = q.size();
                ArrayList<Integer> arrayList = new ArrayList<>();
                for(int i = 0;i < size;i++) { 
                    TreeNode t = q.remove();
                    arrayList.add(t.val);
                    if(t.left != null) { 
                        q.add(t.left);
                    }
                    if(t.right != null) { 
                        q.add(t.right);
                    }
                }
                res.add(arrayList);
            }
            return res;
        }
    }

//解法二：运行时间：23ms 占用内存：9664k
    //递归做法：
    import java.util.ArrayList;
    import java.util.Queue;
    import java.util.LinkedList;
    import java.util.Collections;
    /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { 
            ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
            if(pRoot == null) { 
                return res;
            }
            PrintHelper(pRoot, 1, res);
            return res;
        }
        
        private void PrintHelper(TreeNode root, int depth, ArrayList<ArrayList<Integer>> list) { 
            if(root == null) { 
                return;
            }
            if(depth > list.size()) { 
                list.add(new ArrayList<Integer>());
            }
            list.get(depth - 1).add(root.val);
            
            PrintHelper(root.left, depth+1, list);
            PrintHelper(root.right, depth+1, list);
        }
    }

## 61.序列化二叉树 ##

**题目：请实现两个函数，分别用来序列化和反序列化二叉树**

//解法：运行时间：38ms 占用内存：9728k
    /* 1. 对于序列化：使用前序遍历，递归的将二叉树的值转化为字符，并且在每次二叉树的结点 不为空时，在转化val所得的字符之后添加一个' ， '作为分割。对于空节点则以 '#' 代替。 2. 对于反序列化：按照前序顺序，递归的使用字符串中的字符创建一个二叉树(特别注意： 在递归时，递归函数的参数一定要是char ** ，这样才能保证每次递归后指向字符串的指针会 随着递归的进行而移动！！！) */
    /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        public int index = -1;//节点序号
        String Serialize(TreeNode root) { 
            StringBuilder sb = new StringBuilder();
            if(root == null) { 
                sb.append("#,");
                return sb.toString();
            }
            sb.append(root.val + ",");
            sb.append(Serialize(root.left));
            sb.append(Serialize(root.right));
            return sb.toString();
        }
        
        TreeNode Deserialize(String str) { 
            index ++;
            int len = str.length();
            if(index > len) return null;
            
            String[] strs = str.split(",");
            TreeNode node = null;
            if(!strs[index].equals("#")) { 
                node = new TreeNode(Integer.valueOf(strs[index]));
                node.left = Deserialize(str);
                node.right = Deserialize(str);
            }
            return node;
        }
    }

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

**题目：给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。**

//解法一：运行时间：26ms 占用内存：9560k
    //中序遍历，k时返回
    /* 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 = 0;
        TreeNode KthNode(TreeNode pRoot, int k) { 
            if(pRoot == null) { 
                return null;
            }
            TreeNode node = KthNode(pRoot.left, k);
            if(node != null) { 
                return node;
            }
            index++;
            if(index == k) { 
                return pRoot;
            }
            node = KthNode(pRoot.right, k);
            if(node != null) { 
                return node;
            }
            return null;
        }
    
    
    }

//解法二：运行时间：26ms 占用内存：9564k
    //容易理解的递归版
    /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    import java.util.ArrayList;
    public class Solution { 
        private ArrayList<TreeNode> res = new ArrayList<>();
        TreeNode KthNode(TreeNode pRoot, int k) { 
            if(pRoot == null) { 
                return null;
            }
            KthNodeHelper(pRoot);
            if(res.size() < 1 || k < 1 || res.size() < k) { 
                return null;
            }
            return res.get(k-1);
        }
        
        private void KthNodeHelper(TreeNode root) { 
            if(root != null) { 
                KthNodeHelper(root.left);
                res.add(root);
                KthNodeHelper(root.right);
            }
        }
    }

## 63.数据流中的中位数 ##

**题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。**

//解法：运行时间：21ms 占用内存：9680k
    //最大堆，最小堆法
    import java.util.PriorityQueue;
    import java.util.Comparator;
    public class Solution { 
    
        private int count = 0;
        private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() { 
            @Override
            public int compare(Integer o1, Integer o2) { 
                return o2 - o1;
            }
        });
        
        public void Insert(Integer num) { 
            if(count % 2 == 0) { 
                maxHeap.offer(num);
                int temp = maxHeap.poll();
                minHeap.offer(temp);
            } else { 
                minHeap.offer(num);
                int temp = minHeap.poll();
                maxHeap.offer(temp);
            }
            count++;
        }
    
        public Double GetMedian() { 
            if((count & 1) == 0) { 
                return new Double(maxHeap.peek() + minHeap.peek()) / 2;
            } else { 
                return new Double(minHeap.peek());
            }
        }
    }

## 64.滑动窗口的最大值 ##

**题目：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为\{4,4,6,6,6,5\}； 针对数组\{2,3,4,2,6,2,5,1\}的滑动窗口有以下6个： \{\[2,3,4\],2,6,2,5,1\}， \{2,\[3,4,2\],6,2,5,1\}， \{2,3,\[4,2,6\],2,5,1\}， \{2,3,4,\[2,6,2\],5,1\}， \{2,3,4,2,\[6,2,5\],1\}， \{2,3,4,2,6,\[2,5,1\]\}。**

//解法：运行时间：21ms 占用内存：9184k
    //暴力 O(n^2)
    import java.util.Comparator;
    import java.util.PriorityQueue;
    import java.util.ArrayList;
    public class Solution { 
        public ArrayList<Integer> maxInWindows(int [] num, int size) { 
            ArrayList<Integer> res = new ArrayList<Integer>();
            if(size <= 0) { 
                return res;
            }
            int len = num.length;
            for(int i = 0;i <= len - size; i++) { 
                int max = num[i];
                for(int j = i + 1;j < i + size;j++) { 
                    if(num[j] > max) { 
                        max = num[j];
                    }
                }
                res.add(max);
            }
            
            return res;
            
        }
    }

//解法二：运行时间：18ms 占用内存：9212k
    //左神，双端队列法
    import java.util.LinkedList;
    import java.util.ArrayList;
    public class Solution { 
        
        public ArrayList<Integer> maxInWindows(int [] num, int size) { 
            if (num == null || num.length == 0 || size <= 0 || num.length < size) { 
                return new ArrayList<Integer>();
            }
            ArrayList<Integer> res = new ArrayList<Integer>();
            LinkedList<Integer> qmax = new LinkedList<>();
            
            for(int i = 0;i < num.length;i++) { 
                //将队列前面比num[i]小的全部删掉
                while(!qmax.isEmpty() && num[qmax.peekLast()] < num[i]) { 
                    qmax.pollLast();
                }
                qmax.addLast(i);
                //判断队首元素是否过期(因为每一层循环都会判断，所以最多只有一个过期的元素)
                if(qmax.peekFirst() < i - size + 1) { 
                    qmax.pollFirst();
                }
                //加入滑动窗口最大值
                if(i >= size - 1) { 
                    res.add(num[qmax.peekFirst()]);
                }
            }
            return res;
        }
    }

## 65.矩阵中的路径 ##

**题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。**

//解法：运行时间：15ms 占用内存：9044k
    //回溯法 - 搜索
    public class Solution { 
        public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { 
            boolean[] flag = new boolean[matrix.length];
            for(int i = 0;i < rows;i++) { 
                for(int j = 0;j < cols;j++) { 
                    if(hasPathHelper(matrix, i, j, rows, cols, str, flag, 0)) { 
                        return true;
                    }
                }
            }
            return false;
        }
        
        //访问标志flag， k：正在查找第个字符
        public boolean hasPathHelper(char[] matrix, int i, int j, int rows, int cols, char[] str, boolean[] flag, int k) { 
            //计算二维字符在一维中的下标
            int index = i * cols + j;
            if(i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == true) { 
                return false;
            }
            
            //匹配到了最后一个字符
            if(k == str.length - 1) { 
                return true;
            }
            
            flag[index] = true;
            
            if(hasPathHelper(matrix, i - 1, j, rows, cols, str, flag, k+1)||
              hasPathHelper(matrix, i + 1, j, rows, cols, str, flag, k+1)||
              hasPathHelper(matrix, i, j + 1, rows, cols, str, flag, k+1)||
              hasPathHelper(matrix, i, j - 1, rows, cols, str, flag, k+1)) { 
                return true;
            }
            //回溯
            flag[index] = false;
            return false;
        }   
    }

## 66.机器人的运动范围 ##

**题目：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？**

//解法一：运行时间：24ms 占用内存：9420k
    //回溯
    public class Solution { 
     
        public int movingCount(int threshold, int rows, int cols) { 
            int flag[][] = new int[rows][cols]; //记录是否已经走过
            return helper(0, 0, rows, cols, flag, threshold);
        }
     
        private int helper(int i, int j, int rows, int cols, int[][] flag, int threshold) { 
            if (i < 0 || i >= rows || j < 0 || j >= cols || numSum(i) + numSum(j)  > threshold || flag[i][j] == 1) return 0;    
            flag[i][j] = 1;
            return helper(i - 1, j, rows, cols, flag, threshold)
                + helper(i + 1, j, rows, cols, flag, threshold)
                + helper(i, j - 1, rows, cols, flag, threshold)
                + helper(i, j + 1, rows, cols, flag, threshold)
                + 1;
        }
     
        private int numSum(int i) { 
            int sum = 0;
            do{ 
                sum += i%10;
            }while((i = i/10) > 0);
            return sum;
        }
    }