力扣剑指offer解题记录2

以下题目均来自力扣网

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

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

记忆知识点与分析：
对撞指针

剑指 Offer 12. 矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

class Solution {
    int[][] boardShadow;
    char[][] board;
    char[] wordChar;
    public boolean exist(char[][] board, String word) {
        this.board = board;
        wordChar = word.toCharArray();
        boardShadow = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                if (findNext(i, j, 0)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean findNext(int m, int n, int k){
        if (m < 0 || m >= board.length || n < 0 || n >= board[0].length || boardShadow[m][n] == 1 || board[m][n] != wordChar[k]){
            return false;
        }
        if (k == wordChar.length - 1){
            return true;
        }
        boardShadow[m][n] = 1;
        k++;
        if (findNext(m-1,n,k) || findNext(m+1,n,k) || findNext(m,n-1,k) || findNext(m,n+1,k)){
            return true;
        } 
        k--;
        boardShadow[m][n] = 0;
        return false;
    }
}

记忆知识点与分析：
构造影子矩阵用于记录已经走过的路程
涉及到回溯，函数进入和返回前要对称执行

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

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
含泪写完shit一样的代码

class Solution {
    public String reverseWords(String s) {
        String trimS = s.trim();
        StringBuffer sb = new StringBuffer();
        int end = trimS.length() - 1;
        int start = trimS.length() - 1;
        for (int i = trimS.length()-1; i >= 0; i--){
            if (i != trimS.length()-1 && !Character.isWhitespace(trimS.charAt(i)) && Character.isWhitespace(trimS.charAt(i+1))){
                end = i;
            }
            if ((i != 0 && Character.isWhitespace(trimS.charAt(i-1)) && !Character.isWhitespace(trimS.charAt(i))) || (i == 0)){
                start = i;
                sb.append(trimS.substring(start, end+1));
            } 
            if (Character.isWhitespace(trimS.charAt(i)) && !Character.isWhitespace(trimS.charAt(i+1))){
                sb.append(" ");
            } 
        }
        return  sb.toString();
    }
}

K神答案，感觉简洁优雅很多

class Solution {
    public String reverseWords(String s) {
        s = s.trim(); // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0) {
            while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
            j = i; // j 指向下个单词的尾字符
        }
        return res.toString().trim(); // 转化为字符串并返回
    }
}

记忆知识点与分析：
去除空格后可以服用原来的字符串变量名
多用StringBuilder,少用StringBuffer
注意边界保护，尤其是两个while里的i >= 0，这个判断非常关键
判定char是否为空格的方法Character.isWhitespace(c)

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

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    List> res = new LinkedList<>();
    LinkedList route = new LinkedList<>();
    public List> pathSum(TreeNode root, int target) {
        findRoute(root, target);
        return res;
    }
    public void findRoute(TreeNode node, int tar){
        if (node == null){
            return;
        }
        route.add(node.val);
        tar -= node.val;
        if (tar == 0 && node.right == null && node.left == null){
            res.add(new LinkedList(route));
        }
        findRoute(node.left, tar);
        findRoute(node.right, tar);
        route.removeLast();
    }
}

记忆知识点与分析：
无法确定列表长度且频繁插入，使用LinkedList
除了对路径重点的判断，其他的对节点的判断都放在迭代函数边界判断里，简化判断逻辑
通过减法来判断阈值，如果从0开始算加法，需要额外保存一个target值

剑指 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 {
    Node pre = null;
    Node head = null;
    public Node treeToDoublyList(Node root) {
        if (root == null){
            return null;
        }
        dfs(root);
        pre.right = head;
        head.left = pre;
        return head;
        
    }
    public void dfs(Node node){
        if (node == null){
            return;
        }
        dfs(node.left);
        if (pre == null){
            head = node;
        } else {
            pre.right = node;
        }
        node.left = pre;
        pre = node;
        dfs(node.right);
    }
}

记忆知识点与分析：
二叉搜索树特性，中根遍历为递增序列，深度优先，中根遍历即可
因为要返回头节点，所以注意保留一个头节点，另外用一个pre作为一个指针，指向上一个节点

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

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

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++){
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, (x,y) -> (x+y).compareTo(y+x));
        StringBuilder sb = new StringBuilder();
        for (String s : strs){
            sb.append(s);
        }
        return sb.toString();
    }
}

记忆知识点与分析：
若字符串x+y>y+x，则在排序上x大于y，应该将y排在前面
Arrays.sort(strs, (x,y) -> (x+y).compareTo(y+x)); 满足x+y>y+x,将x排在后面，y排在前面；

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

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

class MedianFinder {
    Queue A;
    Queue B;
    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>(Comparator.reverseOrder());
        B = new PriorityQueue<>();
    }
    public void addNum(int num) {
        if (A.size() == B.size()){
            B.add(num);
            A.add(B.poll());
        }
        if (A.size() != B.size()){
            A.add(num);
            B.add(A.poll());
        }
    }
    public double findMedian() {
        if (A.size() != B.size()){
            return A.peek();
        } else {
            return (A.peek() + B.peek())/2.0;
        }
    }
}

记忆知识点与分析：
使用两个堆来存储两个中间值
堆分为两种：最大堆和最小堆，两者的差别在于节点的排序方式。在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”，并且这个属性对堆中的每一个节点都成立。
java中优先队列底层是堆结构，java优先队列PriorityQueue()
倒序优先队列new PriorityQueue<>((x,y)->(y-x)) 或者 new PriorityQueue<>（Comparator.reverseOrder()）；

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

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。

class Solution {
    public int maxDepth(TreeNode root) {
        return depth(root);
    }
    public int depth(TreeNode node){
        if (node == null){
            return 0;
        } else {
            return Math.max(depth(node.right), depth(node.left)) + 1;
        }
    }
}

记忆知识点与分析：
初次做法为深度优先加回溯，速度较慢，看到K神的解决方法很简单，后续遍历比我的中序遍历简洁很多，效率也高很多，树结构要常从多种遍历方式分析；

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

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
给定二叉树 [3,9,20,null,null,15,7]

3

/
9 20
/
15 7
返回 true 。

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
        if (isBalanced(root.left) && isBalanced(root.right) && (findMaxDepth(root.left) - findMaxDepth(root.right) <= 1) && (findMaxDepth(root.left) - findMaxDepth(root.right) >= -1)){
            return true;
        } else {
            return false;
        }
    }
    public int findMaxDepth(TreeNode node){
        if(node == null){
            return 0;
        } else {
            return Math.max(findMaxDepth(node.left), findMaxDepth(node.right)) + 1;
        }
    }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (maxDepthOrInvalid(root) == -1){
            return false;
        } else {
            return true;
        }
    }
    public int maxDepthOrInvalid(TreeNode node){
        if (node == null){
            return 0;
        }
        int left = maxDepthOrInvalid(node.left);
        if (left == -1){
            return -1;
        }
        int right = maxDepthOrInvalid(node.right);
        if (right == -1){
            return -1;
        }
        if (Math.abs(right - left) < 2){
            return Math.max(right, left) + 1;
        } else {
            return -1;
        }
    }
}

记忆知识点与分析：
本题最开始考虑分别计算左右子树深度和是否为平衡树，但是没有考虑剪枝，方法二采用后序遍历加剪枝方法，可以提前返回结果；

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

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3
输出: 6

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

记忆知识点与分析：
迭代+短路

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null){
            return right;
        } else if (right == null){
            return left;
        } else {
            return root;
        }
    }
}

记忆知识点与分析：
本题的难点在于先序深度优先遍历的时候只返回第一个符合的子节点，终止条件和迭代比较巧妙

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

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

class Solution {
    public double myPow(double x, int n) {
        if (x == 0){
            return 0;
        }
        long b = n;
        double res = 1.0;
        if (b < 0){
            b = -b;
            x = 1 / x;
        }
        while (b > 0)(
            if ((b & 1) == 1){
                res *= x;
            }
            x *= x;
            b >>= 1;
        )
        return res;

记忆知识点与分析
向下整除 n//2 等价于右移一位 n>>1 ；
取余数n%2等价于判断二进制最右一位值 n&1 ；

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

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

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return isSearchTree(postorder, 0, postorder.length - 1);
    }
    public boolean isSearchTree(int[] postorder, int start, int end){
        if (start >= end){
            return true;
        }
        int point = start;
        while (postorder[point] < postorder[end]){
            point++;
        }
        int mid = point;
        while (postorder[point] > postorder[end]){
            point++;
        }
        return (point == end) && isSearchTree(postorder, start, mid - 1) && isSearchTree(postorder, mid, end - 1);
    }
}

记忆知识点与分析：
如果迭代的终止条件不确定，可以先估一个，先写常规模式，再拓展特殊模式，主要工作是对边界判断的改进
因为两个子树的相邻，故只需要一个start和end，mid在函数里求出即可
从边缘处向目标靠近遍历，更方便处理特殊情况

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

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

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0){
            res += (n & 1);
            n >>>= 1;
        }
        return res;
    }
}

记忆知识点与分析：
计算机中的整数分为两类：不带符号位的整数（unsigned integer，也称为无符号整数），此类整数一定是正整数；带符号位的整数（signed integer），此类整数可以表示正整数，又可以表示负整数。
">>>"无符号右移
操作规则：无论正负数，前面补零。
">>"右移
操作规则：正数前面补零，负数前面补1
"<<"左移
操作规则：无论正负数，后面补零。

剑指 Offer 65. 不用加减乘除做加法

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

class Solution {
    public int add(int a, int b) {
        int n = a ^ b;
        int s = (a & b) << 1;
        while (s != 0){
            int tn = n ^ s;
            int ts = (n & s) << 1;
            n = tn;
            s = ts;
        }
        return n;
    }
}

记忆知识点与分析：
非进位和与进位相加，反复迭代，直到进位为0，返回非进位和即可
Q ： 若数字 a 和 b 中有负数，则变成了减法，如何处理？
A ： 在计算机系统中，数值一律用 补码 来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法 同时适用于正数和负数的加法 。
不用考虑溢出情况

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

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

class Solution {
    public int[] singleNumbers(int[] nums) {
        int x = 0;
        int y = 0;
        int n = 0;
        int m = 1;
        for (int num : nums){
            n ^= num;
        }
        while ((m & n) == 0){
            m <<= 1;
        }
        for (int num : nums){
            if ((num & m) == 0){
                x ^= num;
            } else {
                y ^= num;
            }
        }
        return new int[]{x, y};
    }
}

记忆知识点与分析：
根据X异或Y的某一位是否为1进行分组；
若 a & 0010 != 0，则a的第二位为1,否则为0；

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

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

class Solution {
    public int singleNumber(int[] nums) {
        Map numMap = new HashMap<>();
        for(int num : nums){
          numMap.put(num, numMap.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry entry : numMap.entrySet()){
            if (entry.getValue() == 1){
                return entry.getKey();
            }
        }
        return -1;
    }
}

记忆知识点与分析：
通过numMap.entrySet()遍历比直接遍历KeySet效率高；
注意使用Map.getOrDefault方法，减少if else判断；
有限状态自动机后续再看吧；

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

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
摩尔投票法

class Solution {
    public int majorityElement(int[] nums) {
       int vort = 0;
       int x = nums[0];
       int count = 0;
       for (int num : nums){
           if (vort == 0){
               x = num;
           }
           if (num == x){
               vort++;
           } else {
               vort--;
           }
       }
       for (int num : nums){
           if (num == x){
               count++;
           }
       }
       if (count > nums.length / 2){
           return x;
       } else {
           return -1;
       }
    }
}

排序法

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

记忆知识点与分析：
没有要求就排序好了，Arrays.sort(nums);
对空间有要求的话就摩尔投票；
另外对list的排序，Collections.sort(list);
HashMap方法不介绍了

剑指 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]。不能使用除法。

class Solution {
    public int[] constructArr(int[] a) {
        if (a.length == 0){
            return a;
        }
        int[] b = new int[a.length];
        b[0] = 1;
        int temp = 1;
        for (int i = 1; i < b.length; i++){
            b[i] = b[i - 1] * a[i - 1];
        }
        for (int i = b.length - 2; i >= 0; i--){
            temp *= a[i + 1];
            b[i] *= temp;
        }
        return b;
    }
}

记忆知识点与分析：
动态规划，这种题目画图看看
https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/solution/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/

剑指 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。

class Solution {
    public int cuttingRope(int n) {
        if (n < 2){
            return n;
        }
        int numOf3 = n / 3;
        int rNum = n % 3;
        if (rNum == 0){
            return (int)Math.pow(3, numOf3);
        } else if(rNum == 2){
            return (int)Math.pow(3, numOf3) * 2;
        } else {
            return (int)Math.pow(3, numOf3 - 1) * 4;
        }
    }
}

记忆知识点与分析：
求极值

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

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

class Solution {
    public int[][] findContinuousSequence(int target) {
        List resList = new ArrayList<>();
        int i = 1;
        int j = 1;
        int numSum = 1;
      
        while (j < target){
            if (numSum > target){
                numSum -= i;
                i++;
            } else if (numSum < target){
                j++;
                numSum += j;
            } else {
                int[] tempArr = new int[j - i + 1];
                for (int k = i, m = 0; k <= j; k++, m++){
                    tempArr[m] = k;
                }
                resList.add(tempArr);
                j++;
                numSum += j;
            }
        }
        if (resList.size() == 0){
            return new int[0][0];
        }
        return resList.toArray(new int[0][0]);
    }
}

记忆知识点与分析
resList.toArray(new int[0][0])可以将list转成指定模板的Array;
for循环初始化可以申明多个变量，但是如果多个变量类型相同，需要写到一起例如int k = i, m = 0；
避免不必要的转换，本题采用List而不是List>，提高计算效率;

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

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

class Solution {
    public int lastRemaining(int n, int m) {
        if (n == 1){
            return 0;
        }
        return (lastRemaining(n - 1, m) + m) % n;
    }
}

记忆知识点与分析：
将0到n-1看成一个数组
设有n个数字，间隔为m，最后剩的数字索引y，有f(n, m)=y,即从0开始向后数y；
设有n-1个数字，间隔为m，最后剩的数字索引x，有f(n-1, m)=x,即从0开始向后数x；
对于f(n, m)，第一次去除的数字索引为（m-1）%n，去掉一个数字，这时的情况恰好变成f(n-1, m)的情况，从(m-1+1)%n开始，再向后数x即为最终的结果y
所以f(n, m) = (m%n+x)%n=(m%n%n+x%n)%n=(m%n+x%n)%n=(m+x)%n=(m+f(n-1,m))%n;
因为n>=1，当n为1时，返回索引为0，其实这里索引和数字相同。
迭代即可得到结果，知识点为动态规划

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

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
此题在美团面试碰到一次没做出来
个人解法

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0){
            return new int[0];
        }
        if (matrix[0].length == 0){
            return new int[0];
        }
        int[] res = new int[matrix.length * matrix[0].length];
        int[][] shawdow = new int[matrix.length][matrix[0].length];
        int countFlag = 0;
        int m = 0,n = 0;
        for (int i = 0; i < matrix.length * matrix[0].length; i++){
            res[i] = matrix[m][n];
            if (countFlag == 0){
                shawdow[m][n] = 1;
                n++;
                if (n >= matrix[0].length || shawdow[m][n] == 1){
                    countFlag = (countFlag + 1) % 4;
                    n--;
                    m++;
                }
            } else if (countFlag == 1){
                shawdow[m][n] = 1;
                m++;
                if (m >= matrix.length || shawdow[m][n] == 1){
                    countFlag = (countFlag + 1) % 4;
                    m--;
                    n--;
                }
            } else if (countFlag == 2){
                shawdow[m][n] = 1;
                n--;
                if (n < 0 || shawdow[m][n] == 1){
                    countFlag = (countFlag + 1) % 4;
                    n++;
                    m--;
                }
            } else {
                shawdow[m][n] = 1;
                m--;
                if (m < 0 || shawdow[m][n] == 1){
                    countFlag = (countFlag + 1) % 4;
                    m++;
                    n++;
                }
            }
        }
        return res;
    }
}

K神解法

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0){
            return new int[0];
        }
        int l = 0;
        int r = matrix[0].length - 1;
        int u = 0;
        int d = matrix.length - 1;
        int[] res = new int[(r + 1) * (d + 1)];
        int x = 0;
        while(true){
            for (int i = l; i <= r; i++){
                res[x++] = matrix[u][i];
            }
            if (++u > d){
                break;
            }
            for (int i = u; i <= d; i++){
                res[x++] = matrix[i][r];
            }
            if (--r < l){
                break;
            }
            for (int i = r; i >= l; i--){
                res[x++] = matrix[d][i];
            }
            if (--d < u){
                break;
            }
            for (int i = d; i >= u; i--){
                res[x++] = matrix[i][l];
            }
            if (++l > r){
                break;
            }
        }
        return res;
    }
}
``
**记忆知识点与分析：**
**巧用x++,++x计算，每次只判断两个边界，然后更新边界并判断退出条件。**

## 剑指 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) {
Stack stack = new Stack<>();
int i = 0;
for (int num : pushed){
stack.push(num);
while (!stack.isEmpty() && stack.peek() == popped[i]){
stack.pop();
i++;
}
}
if (stack.isEmpty()){
return true;
} else {
return false;
}
}
}

**记忆知识点与分析：**
**模拟法，用一个stack模拟实际的行为，如果完全契合popped的行为，最后的stack应该为空**

## 剑指 Offer 20. 表示数值的字符串
有些偏门的有限状态自动机，后续补充学习

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

class Solution {
public int strToInt(String str) {
char[] chars = str.trim().toCharArray();
if (chars.length == 0){
return 0;
}
int boundary = Integer.MAX_VALUE / 10;
int sign = 1;
int startIndex = 1;
int res = 0;
if (chars[0] == '-'){
sign = -1;
} else if (chars[0] != '+'){
startIndex = 0;
}
for (int i = startIndex; i < chars.length; i++){
if (chars[i] > '9' || chars[i] < '0'){
break;
}
if (res > boundary || (res == boundary && chars[i] > '7')){
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
res = res * 10 + (chars[i] - '0');
}
return res * sign;
}
}

记忆知识点与分析：
本题依次从头到尾考虑分析，注意要点为需要保留一个变量存符号，提前判断循环起始位置；
非数值的判断为if (chars[i] > '9' || chars[i] < '0')；
数值char的int值为 (chars[i] - '0')；
从高位到低位循环加和的逻辑为res = res * 10 + (chars[i] - '0');
另外需要判断越界问题，所以在循环加和前，可以看上一步的res乘以10是否已经超过边界，同时看res乘以10在加上本步的chars[i]是否会超过边界，如果越界，直接根据符号返回边界值；
另外边界是-2^32到2^32-1，选取的判断边界为2^32-1，当数值绝对值大于2^32-1时，直接返回边界值，这个同时满足了-2^32的情况

## 剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
暴力法

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0){
return new int[0];
}
PriorityQueue queue = new PriorityQueue<>((x,y)->y-x);
for (int i = 0; i < k; i++){
queue.add(nums[i]);
}
int[] res = new int[nums.length - k + 1];
res[0] = queue.peek();
for (int i = k, j = 1; i < nums.length; i++, j++){

            queue.remove(nums[i - k]);
            queue.add(nums[i]);
        
        res[j] = queue.peek();
    }
    return res;
}

k神题解

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0 || k == 0){
return new int[0];
}
int[] res = new int[nums.length - k + 1];
Deque deque = new LinkedList<>();
for (int i = 0; i < k; i++){
while (!deque.isEmpty() && deque.peekLast() < nums[i]){
deque.removeLast();
}
deque.addLast(nums[i]);
}
res[0] = deque.peekFirst();
for (int i = k, j = 1; i < nums.length; i++, j++){
if(deque.peekFirst() == nums[i - k]){
deque.removeFirst();
}
while (!deque.isEmpty() && deque.peekLast() < nums[i]){
deque.removeLast();
}
deque.addLast(nums[i]);
res[j] = deque.peekFirst();
}
return res;
}
}

**记忆知识点与分析：**
**双端队列和栈均用LinkedList实现 Deque deque = new LinkedList<>();**
**deque.isEmpty() 双端队列判空**
**构造递减队列，保证第一个始种为最大值，每次插入新值时，将前面无用的小值均删除，因为只要目前值在，前面的小值肯定不会被输出，另外每次滑出数字时需要判定是否将窗口中的最大值剔除，注意事项是窗口中允许最大值重复，即非严格递减队列。**

## 剑指 Offer 37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。

public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null){
return "[]";
}
StringBuilder sb = new StringBuilder("[");
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
if (node == null){
sb.append("null,");
} else {
sb.append(node.val);
sb.append(",");
queue.add(node.left);
queue.add(node.right);
}
}
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if (data.equals("[]")){
        return null;
    }
    String[] ss = data.substring(1, data.length() - 1).split(",");
    TreeNode root = new TreeNode(Integer.parseInt(ss[0]));
    Queue queue = new LinkedList<>();
    queue.add(root);
    int i = 1;
    while (!queue.isEmpty()){
        TreeNode node = queue.poll();
        if (!ss[i].equals("null")){
            node.left = new TreeNode(Integer.parseInt(ss[i]));
            queue.add(node.left);
        }
        i++;
        if (!ss[i].equals("null")){
            node.right = new TreeNode(Integer.parseInt(ss[i]));
            queue.add(node.right);
        }
        i++;
    }
    return root;
}

**记忆知识点与分析：**
**Queue queue = new LinkedList<>() queue的添加和弹出为add和poll；**
**sb.deleteCharAt(sb.length() - 1);StringBuilder删除某个位置deleteCharAt；**
**String[] ss = data.substring(1, data.length() - 1).split(","); substring方法前闭后开，String.split后为String[];**
**Integer.parseInt 将Sting转成Integer；**


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

class Solution {
List res = new LinkedList<>();
char[] chars;
public String[] permutation(String s) {
chars = s.toCharArray();
dfs(0);
return res.toArray(new String[0]);
}
public void dfs(int start){
if (start == chars.length - 1){
res.add(String.valueOf(chars));
return;
}
Set validChars = new HashSet<>();
for (int i = start; i < chars.length; i++){
if (!validChars.contains(chars[i])){
validChars.add(chars[i]);
swamp(start, i);
dfs(start+1);
swamp(start, i);
}
}
}
public void swamp(int i, int j){
char c = chars[i];
chars[i] = chars[j];
chars[j] = c;
}
}

**记忆知识点与分析：**
**此题我感觉挺难的，涉及到深度优先、回溯、剪枝。**
**chars = s.toCharArray(); String转array**
**res.toArray(new String[0]); List转array**
**String.valueOf(chars) array转String**

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

class Solution {
public boolean isMatch(String s, String p) {
int m = s.length() + 1;
int n = p.length() + 1;
boolean[][] matrix = new boolean[m][n];
matrix[0][0] = true;
for (int i = 2; i < n; i += 2){
matrix[0][i] = p.charAt(i - 1) == '' && matrix[0][i - 2];
}
for (int i = 1; i < m; i++){
for (int j = 1; j < n; j++){
if (p.charAt(j - 1) == ''){
if (matrix[i][j - 2] == true){
matrix[i][j] = true;
} else if (matrix[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2)){
matrix[i][j] = true;
} else if (matrix[i - 1][j] && p.charAt(j - 2) == '.'){
matrix[i][j] = true;
}
} else {
if (matrix[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)){
matrix[i][j] = true;
} else if (matrix[i - 1][j - 1] && p.charAt(j - 1) == '.'){
matrix[i][j] = true;
}
}
}
}
return matrix[m - 1][n - 1];
}
}

**记忆知识点与分析：**
**二维动态规划，这个题目的转移方程是真的离谱**

## 剑指 Offer 49. 丑数

class Solution {
public int nthUglyNumber(int n) {
int[] res = new int[n];
int a = 0;
int b = 0;
int c = 0;
res[0] = 1;
for (int i = 1; i < n; i++){
int n2 = res[a] * 2;
int n3 = res[b] * 3;
int n5 = res[c] * 5;
int minUgly = Math.min(Math.min(n2, n3), n5);
res[i] = minUgly;
if (n2 == minUgly) {
a++;
}
if (n3 == minUgly) {
b++;
}
if (n5 == minUgly) {
c++;
}
}
return res[n - 1];
}
}

记忆知识点与分析：
参照不是秒针大佬的分析，感觉比K神讲的清晰一点
我的一点理解： 在已有的丑数序列上每一个数都必须乘2， 乘3， 乘5， 这样才不会漏掉某些丑数。假设已有的丑数序列为[1, 2, 3, ..., n1, n2], 如果单纯的让每个丑数乘2， 乘3， 乘5顺序排列的话肯定会有问题，

比如如果按照这样的顺序排列下去肯定有问题[1*2, 1*3, 1*5, 2*2, 2*3, 2*5, 3*2, 3*3, 3*5, ... , n1 *2, n1 * 3, n1 * 5, n2 * 2, n3* 3, n2 * 5]，因为后面乘2的数据可能会比前面乘3乘5的数据要小，那这个乘2的数应该排在他们的前面， 后面乘3的数据也可能比前面乘5的数据要小，那这个乘3的数应该排在他们的前面。

那怎么办呢，每个数都必须乘2， 乘3， 乘5这样才能保证求出所有的丑数，而且还要保证丑数的顺序，这个改如何同时实现呢？

通过观察网上的各个题解，终于找到了办法，那就是记录每个丑数是否已经被乘2， 乘3， 乘5了， 具体的做法是

设置3个索引a, b, c，分别记录前几个数已经被乘2， 乘3， 乘5了，比如a表示前(a-1)个数都已经乘过一次2了，下次应该乘2的是第a个数；b表示前(b-1)个数都已经乘过一次3了，下次应该乘3的是第b个数；c表示前(c-1)个数都已经乘过一次5了，下次应该乘5的是第c个数；

对于某个状态下的丑数序列，我们知道此时第a个数还没有乘2(有没有乘3或者乘5不知道）， 第b个数还没有乘3(有没有乘2或者乘5不知道），第c个数还没有乘5(有没有乘2或者乘3不知道), 下一个丑数一定是从第a丑数乘2， 第b个数乘3， 第c个数乘5中获得，他们三者最小的那个就是下个丑数。

求得下个丑数后就得判断这个丑数是谁，是某个数通过乘2得到的，还是某个数乘3得到的，又或是说某个数通过乘5得到的。我们可以比较一下这个新的丑数等于究竟是等于第a个丑数乘2, 还是第b个数乘3， 还是第c个数乘5， 通过比较我们肯定可以知道这个新的丑数到底是哪个数通过乘哪个数得到的。假设这个新的丑数是通过第a个数乘2得到的，说明此时第a个数已经通过乘2得到了一个新的丑数，那下个通过乘2得到一个新的丑数的数应该是第(a+1)个数，此时我们可以说前 a 个数都已经乘过一次2了，下次应该乘2的是第 （a+1） 个数, 所以a++；如果新的丑数是通过第b个数乘3得到的, 说明此时第 b个数已经通过乘3得到了一个新的丑数，那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数，此时我们可以说前 b 个数都已经乘过一次3了，下次应该乘3的是第 （b+1） 个数, 所以 b++；同理，如果这个这个新的丑数是通过第c个数乘5得到的, 那么c++;

但是注意，如果第a个数乘2后等于第b个数乘3，或者等于第c个数乘5， 说明这个新的丑数是有两种或者三种方式可以得到，这时应该给得到这个新丑数的组合对应的索引都加一，比如新丑数是第a个数乘2后和第b个数乘3得到的，那么 a 和 b都应该加一， 因为此时第a个数已经通过乘2得到了一个新的丑数，第b个数已经通过乘3得到了一个新的丑数, 只不过这两个数相等而已。所以我们给计数器加一的时候不能使用 if else else if， 而应该使用if, if, if, 这样才不会把应该加一的计数器漏掉

经过n次循环，就能得到第n 个丑数了。

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

class Solution {
public double[] dicesProbability(int n) {
double[] dp = new double[6];
Arrays.fill(dp, 1.0/6.0);
for (int i = 2; i <= n; i++){
double[] temp = new double[5 * i + 1];
for (int j = 0; j < dp.length; j++){
for (int k = 0; k < 6; k++){
temp[j + k] += dp[j] / 6.0;
}
}
dp = temp;
}
return dp;
}
}

**记忆知识点与分析：**
**正向推导**

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

static class Solution {
StringBuilder res;
int n;
char[] num;
char[] numChars = {'0','1','2','3','4','5','6','7','8','9'};
int start;
int nine = 0;
public String printNumbers(int n) {
res = new StringBuilder();
this.n = n;
num = new char[n];
start = n - 1;
dfs(0);
return res.deleteCharAt(res.length() - 1).toString();
}
public void dfs(int i){
if (i == n){
String s = String.valueOf(num).substring(start);
if (!s.equals("0")){
res.append(s);
res.append(",");
if (nine + start == n){
start--;
}
}
return;
}
for (char numChar : numChars){
if (numChar == '9'){
nine++;
}
num[i] = numChar;
dfs(i + 1);
}
nine--;
}
}

**记忆知识点与分析：**
**难点在于去掉“0”和首位的“0”，需要考虑截取有效位，需要回溯。**
**res.deleteCharAt StringBuilder删除一位数字，**
**String.valueOf(num).substring(start);将char[]转成String，String截取**

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

class Solution {
int[] temp;
int[] nums;
public int reversePairs(int[] nums) {
temp = new int[nums.length];
this.nums = nums;
return sortMerge(0, nums.length-1);

}

public int sortMerge(int l, int r){
    if (l >= r){
        return 0;
    }
    int m = (r + l) / 2;
    int res = sortMerge(l, m) + sortMerge(m + 1, r);
    for (int k = l; k <= r; k++){
        temp[k] = nums[k];
    }
    int i = l;
    int j = m + 1;
    for (int k = l; k <= r; k++){
        if (i == m + 1){
            nums[k] = temp[j];
            j++;
        } else if (j == r + 1 || temp[j] >= temp[i]){
            nums[k] = temp[i];
            i++;
        } else {
            nums[k] = temp[j];
            j++;
            res += m - i + 1;
        }
    }
    return res;
}

**记忆知识点与分析：**
**归并排序，背就对了**

## 剑指 Offer 14- II. 剪绳子 II

class Solution {
public int cuttingRope(int n) {
if (n <= 3){
return n - 1;
}
int threeNum = n / 3;
int remaining = n % 3;
long res = 1;
if (remaining == 0){
for (int i = 0; i < threeNum; i++){
res = (res * 3) % 1000000007;
}
}
if (remaining == 1){
for (int i = 0; i < threeNum - 1; i++){
res = res * 3 % 1000000007;
}
res = res * 4 % 1000000007;
}
if (remaining == 2){
for (int i = 0; i < threeNum; i++){
res = res * 3 % 1000000007;
}
res = res * 2 % 1000000007;
}
return (int)res;
}
}

**记忆知识点与分析：**
**res 考虑上线 1000000007 * 3 大于 Integer.MAX_VALUE，所以使用long型；**

## 剑指 Offer 43. 1～n 整数中 1 出现的次数
K神题解

class Solution {
public int countDigitOne(int n) {
int res = 0;
int low = 0;
int cur = n % 10;
int high = n / 10;
int digit = 1;
while (cur != 0 || high != 0){
if (cur == 0){
res += high * digit;
} else if (cur == 1){
res += high * digit + low + 1;
} else {
res += (high + 1) * digit;
}
low = cur * digit + low;
cur = high % 10;
high = high / 10;
digit = digit * 10;
}
return res;
}
}

**记忆知识点与分析:**
**计算每一位的1的个数的和，就某一位为0，1和其他分别考虑，从低位向高位逐步求解即可**

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

class Solution {
public static int findNthDigit(int n) {
if (n <= 9){
return n;
}
long longn = (long)n;
long boundry = 1;
long i = 1;
while ((boundry + i * 9 * Math.pow(10, i - 1)) < (longn + 1)){
boundry += i * 9 * Math.pow(10, i - 1);
i++;
}
long a = (longn + 1 - boundry) / i;
long b = (longn + 1 - boundry) % i;
long before = (long) Math.pow(10, i - 1) - 1 + a;
if (b == 0){
String beforeString = String.valueOf(before);
return beforeString.charAt(beforeString.length() - 1) - '0';
} else {
String afterString = String.valueOf(before + 1);
return afterString.charAt((int)b - 1) - '0';
}
}
}

**记忆知识点与分析:**
**注意大数边界问题，需要将int转成long**
**将一个数值转成String,String.valueOf**
**将char转成int，'x'-'0'**


剑指offer第二遍结束啦！！！