[数据结构与算法]Java算法做题笔记-剑指Offer做题记录

初始完整训练计划

第 1 天
栈与队列（简单）
剑指 Offer 09. 用两个栈实现队列 简单
剑指 Offer 30. 包含min函数的栈 简单

第 2 天
链表（简单）
剑指 Offer 06. 从尾到头打印链表 简单
剑指 Offer 24. 反转链表 简单
剑指 Offer 35. 复杂链表的复制 中等

第 3 天
字符串（简单）
剑指 Offer 05. 替换空格 简单
剑指 Offer 58 - II. 左旋转字符串 简单

第 4 天
查找算法（简单）
剑指 Offer 03. 数组中重复的数字 简单
剑指 Offer 53 - I. 在排序数组中查找数字 I 简单
剑指 Offer 53 - II. 0～n-1中缺失的数字 简单
第 5 天
查找算法（中等）
剑指 Offer 04. 二维数组中的查找 中等
剑指 Offer 11. 旋转数组的最小数字 简单
剑指 Offer 50. 第一个只出现一次的字符 简单

第 6 天
搜索与回溯算法（简单）
剑指 Offer 32 - I. 从上到下打印二叉树 中等
剑指 Offer 32 - II. 从上到下打印二叉树 II 简单
剑指 Offer 32 - III. 从上到下打印二叉树 III 中等

第 7 天
搜索与回溯算法（简单）
剑指 Offer 26. 树的子结构 中等
剑指 Offer 27. 二叉树的镜像 简单
剑指 Offer 28. 对称的二叉树 简单

第 8 天
动态规划（简单）
剑指 Offer 10- I. 斐波那契数列 简单
剑指 Offer 10- II. 青蛙跳台阶问题 简单
剑指 Offer 63. 股票的最大利润 中等

第 9 天
动态规划（中等）
剑指 Offer 42. 连续子数组的最大和 简单
剑指 Offer 47. 礼物的最大价值 中等

第 10 天
动态规划（中等）
剑指 Offer 46. 把数字翻译成字符串 中等
剑指 Offer 48. 最长不含重复字符的子字符串 中等

第 11 天
双指针（简单）
剑指 Offer 18. 删除链表的节点 简单
剑指 Offer 22. 链表中倒数第k个节点 简单

第 12 天
双指针（简单）
剑指 Offer 25. 合并两个排序的链表 简单
剑指 Offer 52. 两个链表的第一个公共节点 简单

第 13 天
双指针（简单）
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 简单
剑指 Offer 57. 和为s的两个数字 简单
剑指 Offer 58 - I. 翻转单词顺序 简单

第 14 天
搜索与回溯算法（中等）
剑指 Offer 12. 矩阵中的路径 中等
剑指 Offer 13. 机器人的运动范围 中等

第 15 天
搜索与回溯算法（中等）
剑指 Offer 34. 二叉树中和为某一值的路径 中等
剑指 Offer 36. 二叉搜索树与双向链表 中等
剑指 Offer 54. 二叉搜索树的第k大节点 简单

第 16 天
排序（简单）
剑指 Offer 45. 把数组排成最小的数 中等
剑指 Offer 61. 扑克牌中的顺子 简单

第 17 天
排序（中等）
剑指 Offer 40. 最小的k个数 简单
剑指 Offer 41. 数据流中的中位数 困难

第 18 天
搜索与回溯算法（中等）
剑指 Offer 55 - I. 二叉树的深度 简单
剑指 Offer 55 - II. 平衡二叉树 简单

第 19 天
搜索与回溯算法（中等）
剑指 Offer 64. 求1+2+…+n 中等
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 简单
剑指 Offer 68 - II. 二叉树的最近公共祖先 简单

第 20 天
分治算法（中等）
剑指 Offer 07. 重建二叉树 中等
剑指 Offer 16. 数值的整数次方 中等
剑指 Offer 33. 二叉搜索树的后序遍历序列 中等

第 21 天
位运算（简单）
剑指 Offer 15. 二进制中1的个数 简单
剑指 Offer 65. 不用加减乘除做加法 简单

第 22 天
位运算（中等）
剑指 Offer 56 - I. 数组中数字出现的次数 中等

剑指 Offer 56 - II. 数组中数字出现的次数 II 中等

第 23 天
数学（简单）
剑指 Offer 39. 数组中出现次数超过一半的数字 简单

剑指 Offer 66. 构建乘积数组 中等

第 24 天
数学（中等）
剑指 Offer 14- I. 剪绳子 中等

剑指 Offer 57 - II. 和为s的连续正数序列 简单

剑指 Offer 62. 圆圈中最后剩下的数字 简单

第 25 天
模拟（中等）
剑指 Offer 29. 顺时针打印矩阵 简单

剑指 Offer 31. 栈的压入、弹出序列 中等

第 26 天
字符串（中等）
剑指 Offer 20. 表示数值的字符串 中等

剑指 Offer 67. 把字符串转换成整数 中等

第 27 天
栈与队列（困难）
剑指 Offer 59 - I. 滑动窗口的最大值 困难

剑指 Offer 59 - II. 队列的最大值 中等

第 28 天
搜索与回溯算法（困难）
剑指 Offer 37. 序列化二叉树 困难

剑指 Offer 38. 字符串的排列 中等

第 29 天
动态规划（困难）
剑指 Offer 19. 正则表达式匹配 困难

剑指 Offer 49. 丑数 中等

剑指 Offer 60. n个骰子的点数 中等

第 30 天
分治算法（困难）
剑指 Offer 17. 打印从1到最大的n位数 简单

剑指 Offer 51. 数组中的逆序对 困难

第 31 天
数学（困难）
剑指 Offer 14- II. 剪绳子 II 中等

剑指 Offer 43. 1～n 整数中 1 出现的次数 困难

剑指 Offer 44. 数字序列中某一位的数字 中等

6.10 以前基本都是自己做过的，10号摆烂日，纯复制答案

2022.5

15

剑指 Offer 09. 用两个栈实现队列

题目内容：

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

如果你使用Stack的方式来做这道题，会造成速度较慢；
原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。

可以使用LinkedList来做Stack的容器
因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做
其本身结构是个双向链表，扩容消耗少。
有addFirst removeFirst
addLast removeLast

思路：
栈：先进后出
队列：先进先出

LinkedList只操作尾部，看作栈
stack1表为s1 stack2表为s2

1. s1用来存放数，s2用来颠倒顺序，所以只往s1后面加
2. s2用于颠倒顺序，所以s2不为空时，说明之前有取操作，已经颠倒过了，所以直接从s2的尾部取就是最先的顺序

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class CQueue {
    
    LinkedList<Integer> stack1;
    LinkedList<Integer> stack2;
    
    public CQueue() {
        // 初始化 stack1 与 stack2
        stack1 = new LinkedList<Integer>();
        stack2 = new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        // 直接将元素存放到 stack1 中
        stack1.addLast(value);
    }
    
    public int deleteHead() {
        // stack2 栈不为空，直接操作，返回 stack2 的栈顶元素
        if(!stack2.isEmpty()) {
           return stack2.removeLast(); 
        }
        // 走到这一步的时候，stack2 是为空的状态
        // 根据题意，当 stack1 为空时，直接返回 -1
        if(stack1.isEmpty()){
            return -1;   
        }
        // 将 stack1 中的元素依次倒序放入 stack2 中
        while(!stack1.isEmpty()){
            stack2.addLast(stack1.removeLast()); 
        }
        // 返回 stack2 的栈顶元素  
        return stack2.removeLast();
    }
}

剑指 Offer 30. 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
思路：

1. 一开始想着以第一个为分界，大的往后，小的往前，但是大小夹在中间会混乱
2. 用第二个栈来记录当前最小值

class MinStack {

    /** initialize your data structure here. */
    LinkedList<Integer> stack;
    LinkedList<Integer> min;
    public MinStack() {
        stack = new LinkedList();
        min = new LinkedList();
        min.addLast(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        min.addLast(Math.min(min.getLast(),x));
        stack.addLast(x);
    }
    
    public void pop() {
        min.removeLast();
        stack.removeLast();
    }
    
    public int top() {
        return stack.getLast();
    }
    
    public int min() {
        return min.getLast();
    }
}

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

class Solution {
    public int[] reversePrint(ListNode head) {
        int[] list=new int[10000];
        int i=0;
        ListNode hea = head;
        while(hea!=null){
            list[i]=hea.val;
            hea=hea.next;
            i++;
        }
        i--;
        int[] record=new int[i+1];
        for(;i>=0;i--){
            record[record.length-1-i] = list[i];
        }
        return record;
    }
}

16

24 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

思路：新建两个头节点，一直用头插入即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode r1= new ListNode();//原链表的头节点
        r1.next=head;
        ListNode r2= new ListNode();//做反转链表的头节点
        while(r1.next!=null){
            ListNode r= new ListNode();
            r.next=r2.next;
            r2.next=r1.next;
            r1.next=r1.next.next;
            r2.next.next=r.next;
        }
        r2=r2.next;
        return r2;
    }
}

18

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

思路：利用hashMap去记录已经创建的节点，递归地进行复制

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    Map<Node,Node> nodeMap = new HashMap<Node, Node>();
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        if(!nodeMap.containsKey(head)){
            Node node=new Node(head.val);
            nodeMap.put(head,node); 
            node.next= copyRandomList(head.next);
            node.random= copyRandomList(head.random);
        }
        return nodeMap.get(head);
    }
}

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

没什么思路，就是方法的使用

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<s.length();i++){
           char c = s.charAt(i);
            if(c == ' ') sb.append("%20");
            else sb.append(c);
        }
        return sb.toString();
    }
}

21

剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder sb = new StringBuilder();
        for(int i=n;i<s.length();i++){
            char c=s.charAt(i);
            sb.append(c);
        }
        for(int i=0;i<n;i++){
            char c=s.charAt(i);
            sb.append(c);
        }
        return sb.toString();
    }
}

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

class Solution {
    public int findRepeatNumber(int[] nums) {
        int[] list=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            list[nums[i]]++;
            if(list[nums[i]]>1){
                return nums[i];
            }
        }
        return -1;
    }
}

22

剑指 Offer 53 - I. 在排序数组中查找数字 I

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

思路：一般都是让写二分查找
注意：/2是向下取整

class Solution {
     public int search(int[] nums, int target) {
        int left =0,right = nums.length-1;
        int count = 0;
        while(left<right){
            int mid = (left+right)/2;
            if(nums[mid]>=target)
                right=mid;
            if(nums[mid]<target)
                left = mid+1;
        }
        while(left<nums.length&&nums[left++]==target)
            count++;
        return count;
    }
}

剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

思路：还是二分查找
后面多一个判断是因为可能存特殊情况：缺失的值为n-1

class Solution {
    public int missingNumber(int[] nums) {
        int left=0;
        int right=nums.length-1;
        while(left<right){
            int mid=(left+right)/2;
            if(mid<nums[mid]){
                right=mid;
            }
            if(mid>=nums[mid]){
                left=mid+1;
            }
        }
        if(left==nums.length-1&&left==nums[left]) {
            return nums.length;
        }
        return left;
    }
}

剑指 Offer 04. 二维数组中的查找 *

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路： 从右上角往下看，其实就是一个二叉搜索树

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int row = 0, column = columns - 1;
        while (row < rows && column >= 0) {
            int num = matrix[row][column];
            if (num == target) {
                return true;
            } else if (num > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }

剑指 Offer 50. 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

思路：采用map定位各个字符的次数，如果最后遍历查到1，则返回
因为这里的s只包含小写字母，也可以建立长度为26的字符数组进行计数

class Solution {
    public char firstUniqChar(String s) {
        char c=' ';
        if(s.length()==0||s==null) return c;
        Map<Character,Integer> map=new HashMap<Character,Integer>();
        for(int i=0;i<s.length();i++){
            char xc=s.charAt(i);
            if(map.get(xc)==null){
                map.put(xc,1);
            }else {
                map.replace(xc,2);
            }
        }
        for(int i=0;i<s.length();i++){
            if(map.get(s.charAt(i))==1){
                return s.charAt(i);
            }
        }
        return c;
    }
}

剑指 Offer 32 - I. 从上到下打印二叉树

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

思路：层序遍历即可，利用队列FIFO的特性即可

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root==null) return new int[0];
        LinkedList<TreeNode> list =new LinkedList<>();
        List<Integer> numb =new ArrayList<>();
        list.add(root);
        while(!list.isEmpty()){
            TreeNode node=list.pop();
            numb.add(node.val);
            if(node.left!=null) list.add(node.left);
            if(node.right!=null) list.add(node.right);
        }
        int[] ans = new int[numb.size()];
        for(int i=0;i<ans.length;i++){
            ans[i]=numb.get(i);
        }
        return ans;
    }
}

剑指 Offer 32 - II. 从上到下打印二叉树 II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

思路：同上一个，不过要在出队列的过程中进行加入

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> doublist = new ArrayList();
        if(root==null) return doublist;
        LinkedList<TreeNode> list =new LinkedList<>();
        list.add(root);
        while(!list.isEmpty()){
            List<Integer> numb =new ArrayList<>();
            int levellength=list.size();
            for(int i=0;i<levellength;i++){
                TreeNode node=list.pop();
                numb.add(node.val);
                if(node.left!=null) list.add(node.left);
            if(node.right!=null) list.add(node.right);
            }
            doublist.add(numb);
        }
        return doublist;
    }
}

剑指 Offer 32 - III. 从上到下打印二叉树 III

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

思路：基本思路同上一题，用flag标注这次该从右往左还是从左往右

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> doublist = new ArrayList();
        if(root==null) return doublist;
        LinkedList<TreeNode> list =new LinkedList<>();
        list.add(root);
        int flag=0;
        while(!list.isEmpty()){
            List<Integer> numb =new LinkedList<>();
            int levellength=list.size();
            for(int i=0;i<levellength;i++){
                TreeNode node =list.pop();
                numb.add(node.val);
                if(node.left!=null) list.add(node.left);
                if(node.right!=null) list.add(node.right);
            }
            if(flag==0) {doublist.add(numb);flag=1;}
            else {
                List<Integer> copynumb =new ArrayList<>();
                int longofnumb=numb.size();
                for(int i=0;i<longofnumb;i++){
                    copynumb.add(numb.get(longofnumb - 1 - i));
                }
                doublist.add(copynumb);
                flag=0;
            }
        }
        return doublist;
    }
}

23

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。

思路：这里还是用了队列，速度慢一点，但是占用空间小一些
判断只不同后还要把nodeB入队是为了防止最后一个点的值不同，但是listB为空，这样回会影响判断

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null) return false;
        LinkedList<TreeNode> listA=new LinkedList<>();
        listA.add(A);
        while(!listA.isEmpty()){
            TreeNode node=listA.removeFirst();
            if(node.val==B.val){
                LinkedList<TreeNode> listcA=new LinkedList<>();
                LinkedList<TreeNode> listB=new LinkedList<>();
                listcA.add(node);
                listB.add(B);
                while(!listcA.isEmpty()&&!listB.isEmpty()){
                    TreeNode nodeA=listcA.removeFirst();
                    TreeNode nodeB=listB.removeFirst();
                    if(nodeA.left!=null) listcA.add(nodeA.left);
                    if(nodeA.right!=null) listcA.add(nodeA.right);
                    if(nodeB.left!=null) listB.add(nodeB.left);
                    if(nodeB.right!=null) listB.add(nodeB.right);
                    if(nodeA.val!=nodeB.val){ listB.add(nodeB);break;}
                }
                if(listB.isEmpty()){return  true;}
            }
            if(node.left!=null) listA.add(node.left);
            if(node.right!=null) listA.add(node.right);
        }
        return false;
    }
}

剑指 Offer 27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

思路：用栈进行，跟着复制值即可

/**
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.6 MB, 在所有 Java 提交中击败了82.78%的用户
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null) return null;
        LinkedList<TreeNode> list =new LinkedList<>();
        list.add(root);
        LinkedList<TreeNode> listc =new LinkedList<>();
        TreeNode firstNode=new TreeNode(root.val);
        listc.add(firstNode);
        while(!list.isEmpty()){
            TreeNode node=list.removeLast();
            TreeNode nodec=listc.removeLast();
            if(node.left!=null) {
                list.add(node.left);
                nodec.right=new TreeNode(node.left.val); 
                listc.add(nodec.right);
            }
            if(node.right!=null) {
                list.add(node.right);
                nodec.left=new TreeNode(node.right.val);
                listc.add(nodec.left);
            }
        }
        return firstNode;
    }
}

剑指 Offer 28. 对称的二叉树*

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

剑指 Offer 42. 连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

思路：定义两个量，用于记录包含当前数与不包含当前数的最大值,然后根据是否加入新数来更新即可

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length==1) return nums[0];
        // int[][] dp=new int[nums.length][2];
        // dp[0][0]=Integer.MIN_VALUE;//存储不连的最大值
        // dp[0][1]=nums[0];//存储连上的最大值
        // for(int i=1;i<nums.length;i++){
        //     dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
        //     dp[i][1]=Math.max(dp[i-1][1]+nums[i],nums[i]);
        // }
        // return Math.max(dp[nums.length-1][0],dp[nums.length-1][1]);
        int x1=Integer.MIN_VALUE;
        int x2=nums[0];
        for(int i=1;i<nums.length;i++){
            x1=Math.max(x1,x2);
            x2=Math.max(x2+nums[i],nums[i]);
        }
        return x1=Math.max(x1,x2);
    }
}

剑指 Offer 47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

思路：只与上和右的最大值有关，记录即可

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

剑指 Offer 46. 把数字翻译成字符串*

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

思路：类似打家劫舍

public int translateNum(int num) {
        String src = String.valueOf(num);
        int p = 0, q = 0, r = 1;
        for (int i = 0; i < src.length(); ++i) {
            p = q; 
            q = r; 
            r = 0;
            r += q;
            if (i == 0) {
                continue;
            }
            String pre = src.substring(i - 1, i + 1);
            if (pre.compareTo("25") <= 0 && pre.compareTo("10") >= 0) {
                r += p;
            }
        }
        return r;
    }

剑指 Offer 48. 最长不含重复字符的子字符串*

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        Set<Character> set = new HashSet<>();
        for(int l = 0, r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            while(set.contains(c)) {
                set.remove(s.charAt(l++));
            }
            set.add(c);
            res = Math.max(res, r - l + 1);
        }

        return res;
    }
}

24

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode firstNode = new ListNode();
        firstNode.next=head;
        if(head.val==val){head=head.next; return head;}
        while(firstNode.next!=null){
            if(firstNode.next.val==val){
                ListNode node =firstNode.next;
                firstNode.next=node.next;
                return head;
            }
            firstNode=firstNode.next;
        }
        return head;
    }
}

剑指 Offer 22. 链表中倒数第k个节点*

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode first =new ListNode();
        first=head;
        ListNode second =new ListNode();second=first;
        while (second != null && k > 0) {
            second = second.next;
            k--;
        }
        while(second!=null){
            first=first.next;
            second=second.next;
        }
        return first;
        // int count=0;
        // if(first!=null){
        //     count++;
        //     first=first.next;
        // }
        // if(k>count) return null;
        // first=head;
        // for(int i=1;i<=count-k;i++){
        //     first=first.next;
        // }
        // return first;
    }
}

剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode head = new ListNode();
        ListNode node = new ListNode();
        while(l1!=null && l2!=null){
            if(l1.val<=l2.val){
                head.next=l1;
                l1=l1.next;
                head=head.next;
            }else{
                head.next=l2;
                l2=l2.next;
                head=head.next;
            }
            if(node.next==null) node.next=head;
        }
        if(l1!=null) head.next=l1;
        if(l2!=null) head.next=l2;
        return node.next;
    }
}

剑指 Offer 52. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 * 执行用时：1 ms, 在所有 Java 提交中击败了98.69%的用户
 * 内存消耗：44.1 MB, 在所有 Java 提交中击败了75.21%的用户
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null) return null;
        int countA=0;
        int countB=0;
        ListNode headAc=headA;//用于表大的
        ListNode headBc=headB;//用于表小的
        while(headAc!=null||headBc!=null){
            if(headAc!=null) {
                countA++;
                headAc=headAc.next;
            }
            if(headBc!=null){
                countB++;
                headBc=headBc.next;
            }
        }
        if(countA>=countB){
            headAc=headA;
            headBc=headB;
        }else{
            headAc=headB;
            headBc=headA;
        }
        int k = countA>=countB ? countA-countB: countB-countA;
        for(int i=0;i<k;i++){
            headAc=headAc.next;
        }
        while(headAc!=null||headBc!=null){
            if(headAc==headBc) return headBc;
            headAc=headAc.next;
            headBc=headBc.next;
        }
        return null;
    }
}

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

class Solution {
    public int[] exchange(int[] nums) {
        if(nums==null) return null;
        if(nums.length==1) return nums;
        int[] list =new int[nums.length];
        int c1=0;
        int c2=nums.length-1;
        for(int i=0;i<nums.length;i++){
            if(nums[i]%2==1){
                list[c1++]=nums[i];
            }else {
                list[c2--]=nums[i];
            }
        }
        return list;
    }
}

剑指 Offer 57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

思路：两个指针往中间夹即可

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if(nums==null||nums.length==1) return new int[]{};
        if(nums[nums.length-1]+nums[nums.length-2]<target||nums[0]+nums[1]>target) return new int[]{};
        int i=0;
        int j=nums.length-1;
        while(i<j){
            if(nums[i]+nums[j]==target){return new int[]{nums[i],nums[j]};}
            else if(nums[i]+nums[j]>target){
                j--;
            }else {
                i++;
            }
        }
        return new int[]{};
    }
}

25

剑指 Offer 58 - I. 翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。

class Solution {
    public String reverseWords(String s) {
        // 除去开头和末尾的空白字符
        s = s.trim();
        // 正则匹配连续的空白字符作为分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
        /*if(s==null|| s.length()==0 || s.length==1&&s==" ") return new String() ;
        StringBuffer ans=new StringBuffer();
        for(int i=s.length()-1;i>=0;i--){//i用于记录当前词的尾部 含入
            if(s.charAt(i)!=' '){
            int x=i;//x用于记录当前词的前部，不含
            while(x>=0&&s.charAt(x)!=' '){
                x--;
            }
            StringBuffer copy =new StringBuffer();
            for(int j=x+1;j<=i;j++){
                copy.append(s.charAt(j));
            }
            ans.append(copy);
            //while(x>0&&s.charAt(x)==' '){x--;}
            if(x!=0) ans.append(" ");
            i=x;
            }
        }
        ans.deleteCharAt(ans.length()-1);
        return ans.toString();
        */
    }
}

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

思路：本来想用迭代的方法，但是树形结构不好标记已访问节点，还是用递归方便点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int count=1;
    int r=0;
    int ans=0;
    public int kthLargest(TreeNode root, int k) {
        // LinkedList<TreeNode> list=new LinkedList<>();
        // int count=0;
        // list.addLast(root);
        // while(count!=k){
        //     root = list.removeLast();
        //     if(root.left!=null) list.addLast(root.left);
        //     if(root!=list.getLast())list.addLast(root);
        //     if(root.right!=null) list.addLast(root.right);
        //     count++;
        // }
        // return root.val;
        r=k;
        dfs(root);
        return ans;
    }
    public void dfs(TreeNode root){
        if(root ==null) return;
        dfs(root.right);
        if(count++==r) ans=root.val;
        dfs(root.left);
        
    }
}

剑指 Offer 61. 扑克牌中的顺子*

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

class Solution {
    public boolean isStraight(int[] nums) {
        int joker = 0;
        Arrays.sort(nums); // 数组排序
        for(int i = 0; i < 4; i++) {
            if(nums[i] == 0) joker++; // 统计大小王数量
            else if(nums[i] == nums[i + 1]) return false; // 若有重复，提前返回 false
        }
        return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
    }
}

剑指 Offer 55 - I. 二叉树的深度

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int deep=0;
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        deep=Math.max(maxDepth(root.left)+1,maxDepth(root.right)+1);
        return deep;
    }
}

剑指 Offer 55 - II. 平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        LinkedList<TreeNode> list=new LinkedList();
        list.add(root);
        while(!list.isEmpty()){
            TreeNode node=list.removeLast();
            if(Math.abs(getdeep(node.left)-getdeep(node.right))>1) return false;
            if(node.left!=null) list.add(node.left);
            if(node.right!=null) list.add(node.right);
        }
        return true;
    }
    public int getdeep(TreeNode root){
        if(root==null) return 0;
        return Math.max(getdeep(root.left)+1,getdeep(root.right)+1);
    }
}

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路：采取了迭代的层序遍历，对每一个节点判断是否是两节点的公共节点。
做完才发现是搜索树，没有利用搜索树的性质

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null|| p==null||q==null) return null;
        TreeNode node =root;
        LinkedList<TreeNode> list=new LinkedList<>();
        if(node.left!=null) list.add(node.left);
        if(node.right!=null) list.add(node.right);
        while(!list.isEmpty()){
            TreeNode rnode =list.pop();
            if(rnode.left!=null) list.add(rnode.left);
            if(rnode.right!=null) list.add(rnode.right);
            if(wetherIsGrand(rnode,p)&&wetherIsGrand(rnode,q)) node=rnode;
        }
        return node;
    }
    public boolean wetherIsGrand(TreeNode a,TreeNode b){
        if(a==null|| b==null) return false;
        if(a==b||a.right==b||a.left==b) return true;
        return wetherIsGrand(a.left,b)||wetherIsGrand(a.right,b);
    }

}

利用搜索树的性质的解法：
最近祖宗节点必然是夹在中间的。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null)
            return null;
        if (root.val > p.val && root.val > q.val)
            return lowestCommonAncestor(root.left, p, q);
        if (root.val < p.val && root.val < q.val)
            return lowestCommonAncestor(root.right, p, q);
        return root;
    }

}

剑指 Offer 68 - II. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路：这次不是搜索树了

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 二叉树的最近公共祖先
     * 思路：
     * 三种情况：
     * 1、p q 一个在左子树 一个在右子树 那么当前节点即是最近公共祖先
     * 2、p q 都在左子树 
     * 3、p q 都在右子树
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            // p q 一个在左，一个在右
            return root;
        }
        if (left != null) {
            // p q 都在左子树
            return left;
        }
        if (right != null) {
            // p q 都在右子树
            return right;
        }
        return null;
    }

}

剑指 Offer 64. 求1+2+…+n

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

思路：利用了逻辑运算符的机制，如果前面已经为flase，那么就不再执行后面的步骤

class Solution {
   public int sumNums(int n) {
       boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
       return n;
   }
}

剑指 Offer 15. 二进制中1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count=0;
        while(n!=0){
            n &= n - 1; //当前n与n-1进行与运算，每次运算会使得 n 的最低位的 1 被翻转，因此运算次数就等于 n 的二进制位中 1 的个数。
            count++;
        }
        return count;
    }
}

6

2

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

思路：迭代法
对于前序遍历中的任意两个连续节点 u 和 v，可能的关系如下

• v是u的左子树
• v是u的右子树/u的某祖宗的右子树
  • u有右子树 则v为u的右子树
  • u无右子树，则v为u的第一个有右子树的祖宗的右子树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null || preorder.length==0) return null;
        TreeNode  root=new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inindex =0;
        for(int i=1;i<preorder.length;i++){
            int preval=preorder[i];
            TreeNode node = stack.peek();
            if(inorder[inindex]!=node.val)//是为了判断当前顶端节点是否有左子树。如果有左子树，那当前中序的数必然不等于顶端数
                node.left=new TreeNode(preval);
                stack.push(node.left);
            }else{
                while(!stack.isEmpty() && stack.peek().val==inorder[inindex]){//为了出到当前顶端第一个有右子树的树 
                    node =stack.pop();
                    inindex++;
                }
                node.right=new TreeNode(preval);
                stack.push(node.right);
            }
        }
        return root;
    }
    
}

剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素

思路：https://mp.weixin.qq.com/s/nMUHqvwzG2LmWA9jMIHwQQ

class Solution {
    List<String> rec;
    boolean[] vis;
    public String[] permutation(String s) {
        int n = s.length();
        rec = new ArrayList<String>();
        vis = new boolean[n]; //默认为flase
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        StringBuffer perm = new StringBuffer();
        backtrack(arr, 0, n, perm);
        int size = rec.size();
        String[] recArr = new String[size];
        for (int i = 0; i < size; i++) {
            recArr[i] = rec.get(i);
        }
        return recArr;
    }
    public void backtrack(char[] arr, int i, int n, StringBuffer perm) {
        if (i == n) { //i用于记录当前到的路径步数
            rec.add(perm.toString());
            return;
        }
        for (int j = 0; j < n; j++) {
            if (vis[j] || (j > 0 && !vis[j - 1] && arr[j - 1] == arr[j])) {
                continue;
            }
            vis[j] = true;
            perm.append(arr[j]);
            backtrack(arr, i + 1, n, perm);
            perm.deleteCharAt(perm.length() - 1);
            vis[j] = false;
        }
    }
}

剑指 Offer 16. 数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

思路：每次对所得的内容进行平方，大大降低计算次数

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}

剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

思路：
排序后在中间
或用Hash表记录次数

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

剑指 Offer 66. 构建乘积数组

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

思路：用两个数组分别存储从头到i-1的乘积与从i+1到尾的乘积
然后再建立答案数组把这两个乘积乘起来

//执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
//内存消耗：51.3 MB, 在所有 Java 提交中击败了92.51%的用户
class Solution {
    public int[] constructArr(int[] a) {
        if(a==null || a.length==0) return new int[]{};
        if(a.length==1) return new int[]{a[0]};
        int[] left=new int[a.length];
        int[] right=new int[a.length];
        left[0] =1;
        right[a.length-1]=1;
        for(int i=1;i<a.length;i++){
            left[i]=left[i-1]*a[i-1];
        }
        for(int i=a.length-2;i>-1;i--){
            right[i]=right[i+1]*a[i+1];
        }
        int[] ans=new int[a.length];
        for(int i=0;i<a.length;i++){
            ans[i]=left[i]*right[i];
        }
        return ans;
    }
}

剑指 Offer 14- I. 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

思路：数论题， 需要尽可能多的3 和 2，乘积才最大
3的优先级大于2 因为 33 >22

证明：几何均值不等式证明相等的长度分多段才能最大乘积
也就是求 $y=x^{(\frac{1}{x})}$
两边做对数，然后求导，可得x=e(约2.7)时，取最大值，因为要取整，所以取3和2最多则乘积最大

class Solution {
    public int cuttingRope(int n) {
        if(n<=3) return n-1;
        int div=n/3;
        int rem=n%3;
        long result=1;
        for(int i=0;i<div;i++){
            result *= i<div-1 ? 3:(rem==2? 3*rem :(3+rem));
            if(result>=1000000007) result = result% 1000000007;
        }
        return (int)result;
    }
}

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

思路：双指针

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> vec = new ArrayList<int[]>();
        for (int l = 1, r = 2; l < r;) {
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum == target) {
                int[] res = new int[r - l + 1];
                for (int i = l; i <= r; ++i) {
                    res[i - l] = i;
                }
                vec.add(res);
                l++;
            } else if (sum < target) {
                r++;
            } else {
                l++;
            }
        }
        return vec.toArray(new int[vec.size()][]);
    }
}

剑指 Offer 62. 圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

思路：推导过程 m=3 最开始 n=5
第一次，【0, 1, 2, 3, 4】，本轮要踢出2 看3(下一轮开始从3计数，为了方便读者看出规律，将开始计数的那一位移到开头)
第二次，【3, 4, 0, 1】，本轮要踢出0 看1
第三次，【1, 3, 4】，本轮要踢出4 看1
第四次，【1, 3】 本轮要踢出1 看3
第五次，【3】
最后返回3

第一次 3 的位置为3 f(5)=(f(4)+3)%5=3
第二次 3 的位置为0 f(4)=(f(3)+3)%4=0
第三次 3 的位置为1 f(3)=(f(2)+3)%3=1 还剩3个数字，位置1
第四次 3 的位置为1 f(2)=(f(1)+3)%2 =1 还剩两个数字，位置在1
第五次 3 的位置为0 f(1)=0 还剩一个数字时3 的位置在0

也就是说f(n)=(f(n-1)+m)%n f(1)=0
利用这个公式求得

class Solution {
    public int lastRemaining(int n, int m) {
        int f = 0;
        for (int i = 2; i != n + 1; ++i) {
            f = (m + f) % i;
        }
        return f;
        
    }
}

剑指 Offer 29. 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

思路：设定边界，不停变换边界即可

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix==null || matrix.length==0||matrix[0].length==0) return new int[]{};
        int rows=matrix.length-1;//待打印矩阵边缘
        int cloumns=matrix[0].length-1;
        LinkedList<Integer> ans=new LinkedList<>();
        //boolean[][] matbol=new boolean[matrix.length][matrix[0].length];
        int row=0;
        int cloumn=0;
        int len=(rows+1) *(cloumns+1);
        while(true) {
            for (int i = cloumn; i <= cloumns; i++) ans.add(matrix[row][i]); //从左往右
            if (++row > rows) break; //因为要转换方向，所以做一个判断，越界跳出   列上+1
            for (int i = row; i <= rows; i++) ans.add(matrix[i][cloumns]);  //从上往下
            if (--cloumns < cloumn) break; //这一列的已经都访问了，边界往左缩
            for (int i = cloumns; i >= cloumn; i--) ans.add(matrix[rows][i]); //从右往左
            if (--rows < row) break;  // 这一行已经都访问了，边界网上缩
            for (int i = rows; i >= row; i--) ans.add(matrix[i][cloumn]);  //从下往上
            if (++cloumn > cloumns) break;
        }
        int[] anslist=new int[len];
        for(int i=0;i<len;i++){
            anslist[i]=ans.removeFirst();
        }
        return anslist;
    }
}

剑指 Offer 31. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

思路：用一个栈去模拟过程，如果栈头与第一个一样则出栈

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        LinkedList<Integer> stack =new LinkedList<>();
        //Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : pushed) {
            stack.push(num); // num 入栈
            while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

剑指 Offer 20. 表示数值的字符串

有一说一，题目有点恶心，选择不做

class Solution {
    public boolean isNumber(String s) {
        if (s == null || s.length() == 0) return false;
        //去掉首位空格
        s = s.trim();
        boolean numFlag = false;
        boolean dotFlag = false;
        boolean eFlag = false;
        for (int i = 0; i < s.length(); i++) {
            //判定为数字，则标记numFlag
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                numFlag = true;
                //判定为.  需要没出现过.并且没出现过e
            } else if (s.charAt(i) == '.' && !dotFlag && !eFlag) {
                dotFlag = true;
                //判定为e，需要没出现过e，并且出过数字了
            } else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && !eFlag && numFlag) {
                eFlag = true;
                numFlag = false;//为了避免123e这种请求，出现e之后就标志为false
                //判定为+-符号，只能出现在第一位或者紧接e后面
            } else if ((s.charAt(i) == '+' || s.charAt(i) == '-') && (i == 0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) {

                //其他情况，都是非法的
            } else {
                return false;
            }
        }
        return numFlag;
    }
    public int isnotNull(char[] chars,int start,int end){
        for(int i=start;i<=end;i++){
            if(chars[i]!=' ') return i;
        }
        return end;
    }
    
}

剑指 Offer 67. 把字符串转换成整数

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

class Solution {
    public int strToInt(String str) {
        //先去空格再判空，不然" "教您做人，血的教训
        str = str.trim();
        if(str.length() == 0){
            return 0;
        }
        //然后我想啊，下面要判断首位了
        //首位合格的无非就'+'或'-'或数字三种情况，其他的一概滚蛋
        //'+''-'肯定是要把它去掉的，这样三种情况就统一了
        //当然了，'-abc'这种有可能出现，不过只看首位它是没毛病的
        //让它进来，反正后面很容易解决
        //既然要去掉正负号，那肯定要出个boolean记一下是不是负数
        boolean isMinus = false;
        char[] ch = str.toCharArray();
        //首位是不是正负号或者数字啊
        if(ch[0] == '+' || ch[0] == '-' || Character.isDigit(ch[0])){
        	//是不是正负号啊
            if(ch[0] == '+' || ch[0] == '-'){
            	//是不是负号啊
                if(ch[0] == '-'){
                    isMinus = true;
                }
                //删除首位
                ch = Arrays.copyOfRange(ch,1,ch.length);
            }
            //首位搞定了就看后面是不是数字了，直到不是数字的地方或者倒底结束
            int index = 0;
            //结果可能超int范围，拿个long接一下
            //'-abc'这种情况返回的也是0，舒服，一箭双雕
            long res = 0;
            //短路与助您远离空指针喔，铁汁们，先后顺序关注一下
            while(index < ch.length && Character.isDigit(ch[index])){
                //一位一位往上算
                res *= 10;
                res += ch[index] - '0';
                //及时止损，一看到res超int范围立马return
                //你要是想着最后一起算，那肯定会有超long范围的测试用例等着你，你就哭去吧
                if(res > Integer.MAX_VALUE){
                    //正负号看是正数负数，返回最大值
                    return isMinus ? Integer.MIN_VALUE : Integer.MAX_VALUE;
                }
                //别忘了往后走一位
                index++;
            }
            //long转int就是这么朴实无华
            return isMinus ? -(int)res : (int)res;
        }
        //兄弟首位都不对想啥呢，回去吧您
        return 0;
    }

}

9

剑指 Offer 13. 机器人的运动范围

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

剑指 Offer 34. 二叉树中和为某一值的路径

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。

思路：标准的回溯法

 private List<List<Integer>> res;

    // 二叉树中和为某一值的路径
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        res = new ArrayList<>();
        backtrack(root, sum, new ArrayList<>());
        return res;
    }

    private void backtrack(TreeNode node, int target, List<Integer> collector) {
        if (node == null) {
            return;
        }
        collector.add(node.val);
        target -= node.val;
        if (target == 0 && node.left == null && node.right == null) {
            res.add(new ArrayList<>(collector));
        } else {
            backtrack(node.left, target, collector);
            backtrack(node.right, target, collector);
        }
        collector.remove(collector.size() - 1);
    }

剑指 Offer 36. 二叉搜索树与双向链表

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

我的思路：排序树中序遍历为递增序列，中序遍历中调整左右节点指向即可

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    public Node treeToDoublyList(Node root) {
        if(root==null|| (root.left==null&& root.right==null)) return root;
        LinkedList<Node> list =new LinkedList<>();//用于存储中序遍历链表
        LinkedList<Node> stack=new LinkedList<>();//用于中序遍历
        stack.push(root);
        while(!stack.isEmpty()){
            Node node=stack.peek();
            if(node.left!=null) {
                stack.push(node.left);
                continue;
            }
            node=stack.pop();
            list.add(node);
            if(node.right!=null) stack.push(node.right);
        }
        Node head=list.getFirst();
        Node node = head;
        Node nodenext=new Node();
        Node nodepre=head;
        while(!list.isEmpty()){
            nodepre=node;
            node= list.removeFirst();
            nodenext= list.getFirst();
            if(node==head){
                node.right=nodenext;
                continue;
            }
            if(nodenext==null) {
                node.left=nodepre;
                node.right=head;
                break;
            }
            node.left=nodepre;
            node.right=nodenext;
        }
        return head;
    }
    
}

迭代算法，但是效率不高

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    public Node treeToDoublyList(Node root) {
        if (root == null) return root;
        Stack<Node> stack = new Stack<>();
        Node curr = root;
        Node preNode = null;
        Node newHead = null;

        while (!stack.isEmpty() || curr != null){
            while (curr != null){
                stack.push(curr);
                curr = curr.left;
            }
            Node tempNode = stack.pop();
            if (preNode == null){
                newHead = tempNode;
            } else {
                preNode.right = tempNode;
            }
            tempNode.left = preNode;
            preNode = tempNode;
            if (tempNode.right != null){
                curr = tempNode.right;
            }
        }
        newHead.left = preNode;
        preNode.right = newHead;
        return newHead;
    }
    
}

剑指 Offer 45. 把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

思路：

工具类Arrays排序算法的使用
一般是以数字升序，如果要改变排序的参照规则，需要实现一个接口
Comparator 注意：不要和Comparable弄混

可以自行编写实现类，也可以使用内部类与lamdba表达式
编写实现类需要重写它的唯一方法 compare(o1,o2)

public int compare(Integer arg0, Integer arg1) {
			// TODO Auto-generated method stub
			return arg0-arg1;//升序   即返回负数
			//return arg1-arg0;//降序  即返回正数
		}

class Solution {
    public String minNumber(int[] nums) {
        //需要手写一个排序算法，分别对比最高位，一直比到最低位
        List<String> list = new ArrayList<>();
        for (int num : nums) {
            list.add(String.valueOf(num));
        }
        list.sort((o1, o2) -> (o1 + o2).compareTo(o2 + o1)); //升序，也就是说左边如果    即(o1 + o2)<(o2 + o1)   o1在前，o2 在后
        return String.join("", list);//拼接字符串
    }
}

剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

思路：用第一个大于根的节点作为左右子树分界线
然后依次扫过其左右，左边的必须都小于，右边的必须都大于

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        //排序，建成搜索二叉树，然后对比后序遍历 
        //二叉搜索树不一定平衡，所以生成的搜索二叉树不一定为原二叉树 
        //后续遍历的特点，先左右后跟
        int start=0;
        int end=postorder.length-1;
        return jugTree(postorder,start,end);

    }
    public boolean jugTree(int[] postorder,int start,int end){
        if(start==end ||start>end) return true;
        int flag=start;
        while(postorder[flag]<postorder[end]) flag++;
        int rightstart=flag;
       while(postorder[flag]>postorder[end]) flag++;
        return flag==end && jugTree(postorder,start,rightstart-1)&&jugTree(postorder,rightstart,end-1);
    }
}

10

剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

int ret = 0;
        for (int n : nums) {
            ret ^= n;
        }
        int div = 1;
        while ((div & ret) == 0) {
            div <<= 1;
        }
        int a = 0, b = 0;
        for (int n : nums) {
            if ((div & n) != 0) {
                a ^= n;
            } else {
                b ^= n;
            }
        }
        return new int[]{a, b};

剑指 Offer 56 - II. 数组中数字出现的次数 II

class Solution {
    public int singleNumber(int[] nums) {
        int[] counts = new int[32];
        for(int num : nums) {
            for(int j = 0; j < 32; j++) {
                counts[j] += num & 1;
                num >>>= 1;
            }
        }
        int res = 0, m = 3;
        for(int i = 0; i < 32; i++) {
            res <<= 1;
            res |= counts[31 - i] % m;
        }
        return res;
    }
}

剑指 Offer 59 - I. 滑动窗口的最大值

// 第三次提交，对第二种暴力遍历窗口的方法，小加速，成功（用时+内存：97%，72%）
        // 加速原理：每次滑动窗口向右移动时，判断
        // a. 新加入的值 是否比上一个窗口最大值大，若是，则直接返回 新加入的值
        // b. 待移除的值 是否比上一个窗口最大值小，若是，则返回 上一窗口最大值
        if(k==0)return new int[0];
        int ans[] = new int[nums.length-k+1];   // 记录每一窗口的最大值
        for(int i=0;i+k-1<nums.length;i++){
            if(i>0 && nums[i+k-1]>ans[i-1])ans[i] = nums[i+k-1];    // 新值比上一窗口最大值大，返回 新值
            else if(i>0 && nums[i-1]<ans[i-1])ans[i] = ans[i-1];    // 旧值比上一窗口最大值小，返回 上一窗口最大值
            else{   // 遍历滑动窗口，找到最大值
                int max = Integer.MAX_VALUE+1;
                for(int j=i;j<i+k;j++){
                    max = Math.max(max,nums[j]);
                    ans[i] = max;
                }
            }
        }
        return ans;

剑指 Offer 59 - II. 队列的最大值

class MaxQueue {
    int[] q = new int[20000];
    int begin = 0, end = 0;

    public MaxQueue() {

    }
    
    public int max_value() {
        int ans = -1;
        for (int i = begin; i != end; ++i) {
            ans = Math.max(ans, q[i]);
        }
        return ans;
    }
    
    public void push_back(int value) {
        q[end++] = value;
    }
    
    public int pop_front() {
        if (begin == end) {
            return -1;
        }
        return q[begin++];
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */

剑指 Offer 41. 数据流中的中位数

class MedianFinder {

    /** initialize your data structure here. */
    Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }
    public void addNum(int num) {
        if(A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

剑指 Offer 17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

无大数问题

class Solution {
    public int[] printNumbers(int n) {
        int max=0;
        while(n!=0){
            max=max*10+9;
            n--;
        }
        int[] ans=new int[max];
        for(int i=0;i<max;i++){
            ans[i]=i+1;
        }
        return ans;
    }
}

剑指 Offer 37. 序列化二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }
  
    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }

    public String rserialize(TreeNode root, String str) {
        if (root == null) {
            str += "None,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }
  
    public TreeNode rdeserialize(List<String> dataList) {
        if (dataList.get(0).equals("None")) {
            dataList.remove(0);
            return null;
        }
  
        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);
    
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

剑指 Offer 19. 正则表达式匹配

class Solution {
    public boolean isMatch(String s, String p) {
        if (p.equals(".*")) {
            return true;
        }

        // 用dp[i][j]表示p的前i个字符和s的前j个字符的匹配情况
        int sLen = s.length(), pLen = p.length();
        boolean[][] dp = new boolean[pLen + 1][sLen + 1];

        // 初始化
        // 空串可以和空串匹配
        dp[0][0] = true;
        // p为空，s非空时，p和s不匹配，所以dp[0][j]都等于false

        for (int i = 1; i <= pLen; ++i) {
            char pChar = p.charAt(i - 1);
            for (int j = 0; j <= sLen; ++j) {
                if (j == 0) {
                    if (pChar == '*' && i > 1) {
                        dp[i][j] = dp[i - 2][j];
                    }
                } else if (s.charAt(j - 1) == pChar || pChar == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pChar == '*' && i > 1) {
                    dp[i][j] = dp[i - 2][j];
                    if (s.charAt(j - 1) == p.charAt(i - 2) || p.charAt(i - 2) == '.') {
                        dp[i][j] = dp[i][j] || dp[i][j - 1];
                    }
                }
            }
        }
        return dp[pLen][sLen];
    }
}