剑指 Offer 14- II. 剪绳子 II

给你一根长度为 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。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

解题思路：

• 2 取 1*1
• 3 取 1*2
• 4 取 2*2
• 5 取 2*3
• 6 取 3*3
• 7 取 3*2*2
• 8 取 3*3*2
• 9 取 3*3*3
• 发现规律，能尽量多的取3
• 当取到不能取的时候，剩下有这几种情况
  • 留下0，则直接返回
  • 留下1，例如4-3=1，但是这种情况下2*2>3*1，所以回退一个3，乘一个4
  • 留下2，例如5-3=2，直接*2

class Solution {
    public int cuttingRope(int n) {
        // 动态规划max超出则没有意义
        // 尽量取3
            // 取3后 剩余0 则返回
            // 取3后 剩余2 则*2返回
            // 取3后 剩余1 则/3*4  2*2 > 1*3
        if (n <= 3)return n-1;
        long res = 1;
        while (n > 4){
            res = (res*3)%1000000007;
            n -= 3;
        }
        // n = 1，3，4
        return (int)((res*n)%1000000007);
    }
}

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

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

解题思路：

• 判断原有的1的个数
• n&1：检测最右边是否是1
• n>>>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 = n>>>1;
        }
        return res;
    }
}

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

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

解题思路：

• 二进制角度分析，一个 n 可以拆分，x^n 也可以继续拆分
• n 的拆分
  • n = 1, 0000 0001, x
  • n = 2, 0000 0010, x*x
  • n = 3, 0000 0011, x*x*x
  • n = 4, 0000 0100, x*x*x*x
  • 可以看出
    • 遇到 0，x = x*x 翻倍
    • 遇到 1，res = res * x
• Java中 int 在 [−2147483648,2147483647] ，所以当 n = -2147483648 , n = -n 会越界，所以计算的时候，要先用换个类型，用 long 来计算

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

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

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

解题思路：

• 根据 n 判断数组大小，10的n次方 - 1
• 给数组挨个赋值从1开始，正好对应 i -1 位

class Solution {
    public int[] printNumbers(int n) {
        int len = 1;
        while (n-- != 0){
            len *= 10;
        }
        int[] res = new int[len-1];
        for (int i=1;i
            res[i-1] = i;
        }
        return res;
    }
}

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

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

返回删除后的链表的头节点。

解题思路：

• 定义一个头节点pre，头节点的下一位就是head
• 判断当前位的下一位是否还有值，有值就判断是否等于value，如果等于就直接删除该节点，如果不等于，就接着判断下一位

/**
 * 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 pre = new ListNode(0);
        pre.next = head;
        ListNode node = pre;
        while (node.next != null){
            if (node.next.val == val){
                node.next = node.next.next;
                return pre.next;
            }else{
                node = node.next;
            }
        }
        return node;
    }
}

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

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

解题思路：

• 动态规划
• 随着s长度的增加，在不同长度下，p能否匹配
• 先判断当前位置p是不是‘*’，如果不是则表示无特殊情况，直接看最后两位是否能匹配起来，如果p的最后一位是‘.’，则表示可以，否则不相同不能匹配
  • 这里注意，首先需要判断当前 i 是否是0，0 表示当前s为空。当p的所在位置是‘*’，就是说如果是‘*'，还能删除前面的值和空匹配起来，已知不是’*‘也就不能和空匹配，所以在不是'*'的情况下，i = 0，都不能匹配
• 如果当前位置p是'*'，就有多种情况可以考虑
  • ’*‘前面的一位能否和当前s的最后一位对应上
    • 如果可以，'*'可以表示为删除前一位，'*'保留前一位，'*'表示前一位的多位
    • 分别代表 a* = ''，a* = a，a* = aaaaa
    • 所以当匹配起来的时候
    • 取 删除p的后两位和s当前位置再比较 的结果
    • 或者
    • 取 删除p的后两位和删除s的后一位再比较 的结果
    • 或者
    • 取 删除s的后一位和p当前保持不变 的结果（a*表示多个，所以不用动）

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n+1][m+1];
        // 两个空字符串也能匹配
        dp[0][0] = true;
        // i代表s长度的增加
        for (int i=0;i<=n;i++){
            //j代表p长度的增加
            for (int j=1;j<=m;j++){  
                // 分为有'*'和无'*'的情况 
                // 有*，可以匹配0，1，多次
                if (p.charAt(j-1) == '*'){
                    // 首先判断s最后一位和p中*前的一位相同不相同
                    if (isSame(s,p,i,j-1)){
                        // 如果*前面的字符和i最后的字符相等
                        // 可以把p的后两位删除，也就是*重复0次，之后看i和j-2是否一样
                        // 也可以把p的后两位删除，把s的后一位删除
                        // 也可以p不动，表示多次，把s的后一位删除
                        dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];  
                    }else{
                        // 如果不相等直接删除p的后两位，表示*重复0次，然后再看
                         dp[i][j] = dp[i][j-2];                   
                    }
                }else{
                    if (isSame(s,p,i,j)){
                        dp[i][j] = dp[i-1][j-1];
                    }
                }   
            }
        }
        return dp[n][m];
    }
 
    public boolean isSame(String s,String p,int i,int j){
        if (i == 0){
            return false;
        }
        if (p.charAt(j-1) == '.'){
            return true;
        }
        return s.charAt(i-1) == p.charAt(j-1);
    }
}

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

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

1. 若干空格
2. 一个 小数 或者 整数
3. （可选）一个 'e' 或 'E' ，后面跟着一个 整数
4. 若干空格

小数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（'+' 或 '-'）
2. 下述格式之一：
   1. 至少一位数字，后面跟着一个点 '.'
   2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
   3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（'+' 或 '-'）
2. 至少一位数字

部分数值列举如下：

• ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]

部分非数值列举如下：

• ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

解题思路:

• 分情况讨论
  • 首先判断'+','-'，应该处在第一位或者跟在e或者E后面
  • 其次判断数值，在 0 - 9 之间就是数值
  • 其次判读点，点只能出现一次，就是跟在数值后面，不能跟在e或E后面
  • 其次按段e或E，也只能出现一次，且跟在数值后面，e或E得后面还得跟数值

class Solution {
    public boolean isNumber(String s) {
        char[] c = s.trim().toCharArray();
        boolean hasE = false;
        boolean hasDot = false;
        boolean isNumber = false;
        for (int i=0;i
            // 0-9说明是数值
            if (c[i]>= '0' && c[i] <= '9'){
                isNumber = true;
            }
            // 正负号的时候，只能出现在第一位，或者跟在e或E的后面
            else if (c[i] == '+' || c[i] == '-'){    
                if (i != 0 && c[i-1] != 'e' && c[i-1] != 'E')return false;
            }
            // 当出现e或者E，得之前没出现过
            else if (c[i] == 'e' || c[i] == 'E'){
                // 如果已经出现过，或者e 前面没有数值
                if (hasE || !isNumber){
                    return false;
                }
                // e或E后面一定要跟数值
                hasE = true;
                isNumber = false;  
            }
            // 当出现.，允许出现一次，但是不能跟在e或E后面
            else if (c[i] == '.'){
                if (hasDot || hasE){
                    return false;
                }
                hasDot = true;
            }else {
               return false; 
            }
        }
        return isNumber;
    }
}

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

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

解题思路：

• 左右双指针，左指针移动到偶数，又指针移动到奇数
• 左指针先移动到偶数，然后移动右指针直到找到奇数，将两者交换，前提 left < right

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

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

难度简单385收藏分享切换为英文接收动态反馈

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

解题思路：

• 快慢指针，让快指针先走k步，然后快慢指针一起走，当快指针走到null的时候，slow就是答案。这里倒推一下，倒数k个节点，设置最后k个节点的左右边界，左边界往前移动到开始，左右边界正好差了k。

/**
 * 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 fast = head;
        ListNode slow = head;
        while (k-- > 0){
            fast = fast.next;
        }
        while (fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }   
}

剑指 Offer 24. 反转链表

难度简单473收藏分享切换为英文接收动态反馈

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

解题思路：

• 老生常谈，反转链表
• 设置一个虚拟节点prev，让当前节点的next指向prev，循环这个过程

/**
 * 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 prev = null;
        while (head != null){
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

剑指 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) {
        ListNode head = new ListNode(0);
        ListNode node = head;
        while (l1 != null && l2 != null){
            if (l1.val < l2.val){
                node.next = l1;
                l1 = l1.next;
            }else {
                node.next = l2;
                l2 = l2.next;
            }
            node = node.next;
        }
        node.next = l1 == null ? l2 : l1;
        return head.next;
    }
}

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

     3
    / \
   4   5
  / \
 1   2
给定的树 B：

   4 
  /
 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

解题思路：

• 当A和B都为null的时候直接返回false
• 只有当前节点相等，且左左相等，右右相等的时候才是子树
• 否则在当前节点找不到，只能去当前节点的左子树或者右子树查找
• 递归找的时候，如果当前B为null，说明已经找完了可以返回true。如果A为null，则表示在B不为null的时候，A已经为空，说明就不是了。其次如果A，B两个当前值就不一样，那就直接返回 false，当条件都满足的时候，递归的判断它们的左左和右右

/**
 * 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;
        }
        if (A.val == B.val && dfs(A.left,B.left) && dfs(A.right,B.right)){
            return true;
        }
        return isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }
 
    public boolean dfs(TreeNode A, TreeNode B){
        if (B == null){
            return true;
        }
        if (A == null){
            return false;
        }
        if (A.val != B.val){
            return false;
        }
        return dfs(A.left,B.left) && dfs(A.right,B.right);
    }
}

剑指 Offer 27. 二叉树的镜像

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

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解题思路：

• 递归的获取左，获取右，把左给右，把右给左，最后返回当前节点

/**
 * 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;
        TreeNode node1 = mirrorTree(root.right);
        TreeNode node2 = mirrorTree(root.left);
        root.left = node1;
        root.right = node2;
        return root;
    }
}

剑指 Offer 28. 对称的二叉树

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

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

解题思路:

• 递归条件：左左等于右右，左右等于右左
• 终止条件：都为null
• 其他都是不符合：
  • 一边为null，一边不为null
  • 两个节点的值不相同

/**
 * 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) {
        if (root == null)return true;
        return dfs(root.left,root.right);
    }
 
    public boolean dfs(TreeNode left,TreeNode right){
        if (left == null && right == null)return true;
        if (left == null && right != null)return false;
        if (left != null && right == null)return false;
        if (left.val != right.val)return false;
        return dfs(left.left,right.right) && dfs(left.right,right.left);
    }
}

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

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

解题思路：

• 按照顺序，从左至右遍历，当遇到超出边界，或访问过的情况则掉转方向，直至数组满

class Solution {
    int curr = 0;
    int[][] direction = {{0,1},{1,0},{0,-1},{-1,0}};
    public int[] spiralOrder(int[][] matrix) {
        int n = matrix.length;
        if (n == 0)return new int[0];
        int m = matrix[0].length;
        int[] res = new int[n*m];
        boolean[][] used = new boolean[n][m];
        dfs(res,used,matrix,n,m,0,0,0);
        return res;
    }
 
    public void dfs (int[] res,boolean[][] used,int[][] matrix,int n,int m,int i,int j,int size){
        if (size > n*m-1){
            return;
        }
        if (i < 0 || j < 0 || i > n-1 || j > m-1 || used[i][j]){
            if (curr == 0){
                curr = 1;
                dfs(res,used,matrix,n,m,i+direction[curr][0],j-1+direction[curr][1],size);
            }else if (curr == 1){
                curr = 2;
                dfs(res,used,matrix,n,m,i-1+direction[curr][0],j+direction[curr][1],size);
            }else if (curr == 2){
                curr = 3;
                dfs(res,used,matrix,n,m,i+direction[curr][0],j+1+direction[curr][1],size);
            }else if (curr == 3){
                curr = 0;
                dfs(res,used,matrix,n,m,i+1+direction[curr][0],j+direction[curr][1],size);
            }
        }else{
            res[size] = matrix[i][j];
            used[i][j] = true;
            dfs(res,used,matrix,n,m,i+direction[curr][0],j+direction[curr][1],size+1);
        }  
    }   
}

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

难度简单373收藏分享切换为英文接收动态反馈

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

解题思路：

• 辅助栈用来存放最小值，每次都会和栈顶比较，最小的值入栈，弹出则同时弹出

class MinStack {
    Stack stack1;
    Stack stack2;
    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new Stack();
        stack2 = new Stack();
    }
    
    public void push(int x) {
        if (stack1.isEmpty()){
            stack2.push(x);
        }else{
            if (stack2.peek() > x){
                stack2.push(x);
            }else{
                stack2.push(stack2.peek());
            }
        }   
        stack1.push(x);
    }
    
    public void pop() {
        stack1.pop();
        stack2.pop();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        return stack2.peek();
    }
}
 
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

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

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

解题思路：

• 循环一边pushed，当判断当前需要push的值和pop值相同时，就无需放入，双方都继续下一位的判断，直到不同为止。当产生不同后，有可能是需要把之前的值弹出，所以用一个栈去存放需要放入的值，当发现栈顶元素是当前需要弹出的值，则弹出栈，同时poped位置向后移动，while循环判断，直到发现不是弹出的元素。当什么都不是的时候，这就是一个新值，需要放入到栈中，最终遍历结束，可能会存在最后一位没有及时判断的情况，所以最终在把栈顶元素和当前弹出位比较，弹出需要弹出的元素，最终检查栈中元素是否都弹出了，都弹出则表示是正确的弹出顺序

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int n = pushed.length;
        Stack stack = new Stack();
        int i = 0;
        int j = 0;
        for (;i
            while (i < n && pushed[i] == popped[j]){
                j++;
                i++;
            }
            while (!stack.isEmpty() && stack.peek() == popped[j]){
                stack.pop();
                j++;
            }
            if (i < n){
                stack.push(pushed[i]);
            }
        }
        while (!stack.isEmpty() && stack.peek() == popped[j]){
            stack.pop();
            j++;
        }
        return stack.isEmpty();
    }
}

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

难度中等228收藏分享切换为英文接收动态反馈

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

解题思路：

• 层序遍历，挨个插入到list中，最终list转数组输出

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        List res = new ArrayList();
        if (root == null)return new int[0];
        Queue queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i=0;i
                root = queue.poll();
                res.add(root.val);
                if (root.left != null){
                    queue.add(root.left);
                }
                if (root.right != null){
                    queue.add(root.right);
                }
            }
        }
        int[] re = new int[res.size()];
        for (int i=0;i
            re[i] = res.get(i);
        }
        return re;
    }
}

剑指 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> levelOrder(TreeNode root) {
        List> res = new ArrayList();
        if (root == null)return res;
        Queue queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List list = new ArrayList();
            for (int i=0;i
                root = queue.poll();
                list.add(root.val);
                if (root.left != null){
                    queue.add(root.left);
                }
                if (root.right != null){
                    queue.add(root.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}

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

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

解题思路：

• 层序遍历的变形，一层从左到右，一层从右到左
• 根据层数判断奇偶确定左右顺序，由于每层的节点个数已知，就可以构建数组，插入的时候根据左右顺序决定是从前往后插入，还是从后往前插入

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List> levelOrder(TreeNode root) {
        List> res = new ArrayList();
        if (root == null)return res;
        Queue queue = new LinkedList();
        queue.add(root);
        int depth = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            depth++;
            Integer[] temp = new Integer[size];
            for (int i=0;i
                root = queue.poll();
                if (depth % 2 == 0){
                    temp[size-i-1] = root.val; 
                }else{
                    temp[i] = root.val; 
                }
                if (root.left != null){
                    queue.add(root.left);
                }
                if (root.right != null){
                    queue.add(root.right);
                }           
            }
            res.add(Arrays.asList(temp));
        }
        return res;
    }
}

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

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

解题思路：

• 二叉搜索树：左节点 < 根节点 < 右节点
• 数组中最后一位就是根节点，所以从头开始找，比根节点小的就是左子树，找到中间的界限mid，从left 到 mid-1 为左子树，从 mid 到 right 为右子树，之前只检验了左边小值的为左子树，右树也需要继续检验是否都大于根节点，如不满足则fan'hui
• 递归着左子树和右子树，判断是不是二叉搜索树

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        // 二叉搜索树，左节点 < 根节点 < 右节点
       int n = postorder.length;
       int left = 0;
       int right = n-1;
       return dfs(postorder,left,right);
    }
 
    public boolean dfs(int[] postorder,int left,int right){
        // 最后一位就是根节点，所以比根节点小的就是左子树，比根节点大的就是右子树
 
        if (left >= right)return true;
 
        // 先找左子树
        int i = left;
        while (postorder[i] < postorder[right]){
            i++;
        }
        // 从 left 到 mid-1 为左子树
        int mid = i;
 
        // 先判读剩下的右边的数是不是都大于根节点
        while (postorder[mid] > postorder[right]){
            mid++;
        }
        if (postorder[mid] != postorder[right])return false;
        
        // 递归遍历左和右
        return dfs(postorder,left,mid-1) && dfs(postorder,mid,right);
    }
}

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

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

叶子节点 是指没有子节点的节点。

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解题思路：

• 从根节点出发一直到叶子节点为止，找到对应和为target的路径
• 叶子节点，所以最终当target满足的时候，也要看下当前是否是叶子节点，也就是没有左子树和右子树，当满足时才是答案之一
• 总体递归从左至右，前序遍历树就行
• 用个栈存放遍历过的节点，在遍历到的时候插入，当遍历结束的时候弹出

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List> pathSum(TreeNode root, int target) {
        List> res = new ArrayList();
        Stack stack = new Stack();
        dfs(root,target,res,stack);
        return res;
    }
 
    public void dfs(TreeNode root,int target,List> list,Stack stack){
        if (root == null){
            return;
        }
        target -= root.val;
        stack.push(root.val);
        dfs(root.left,target,list,stack);
        dfs(root.right,target,list,stack);
        if (root.left == null && root.right == null){
            if (target == 0){
                list.add(new ArrayList(stack));
            }
        }
        target += root.val;
        stack.pop();
    }
}

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

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

解题思路：

• 因为存在下一个节点和随机节点，所以随机节点有可能会是之前的节点
• 所以要用个map储存下节点
• 创建第一个节点，是head的复制，接着递归着去查找它的next和random，如果之前没有过就创建新的，如果有直接返回

/*
// 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 {
    HashMap map = new HashMap();
    public Node copyRandomList(Node head) {
        if (head == null)return null;
        if (!map.containsKey(head)){
            Node node = new Node(head.val);
            map.put(head,node);
            node.next = copyRandomList(head.next);
            node.random = copyRandomList(head.random);
        }
 
        return map.get(head);
    }
}

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

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

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

解题思路：

• 链表的顺序就是中序遍历的顺序，所以大框架还是中序遍历
• 最后一个节点和第一个节点得相互连接，定义一个头节点，定义一个尾部节点，尾部节点只需要遍历得时候跟着移动就行
• 当头部节点为空得时候，赋值头部节点
• pre始终作为前一个节点，当前节点得左边即是pre，pre得右边即是当前节点，赋值完毕后，将当前节点赋值给pre，然后开始下一个节点，最终当下一个节点为null得时候，pre就恰好停留在最后一个节点，最后只需要head.left = pre; pre.right = 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 {
    Node head; // 定义第一个
    Node pre; // 遍历的时候到最后一个
    public Node treeToDoublyList(Node root) {
        // 中序遍历，获取节点顺序
        if (root == null)return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
 
    public void dfs(Node root){
        if (root == null)return;
        dfs(root.left);
        if (head == null){
            head = root;
        }else{
           pre.right = root; 
        }
        root.left = pre;
        pre = root;
        dfs(root.right);
    }
}

剑指 Offer 37. 序列化二叉树

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

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

解题思路：

• 应用题：按照前序遍历的方式，用字符串把它们连接起来，用 ’，‘ 分隔，注意None
• 反序列化的时候，就是先分割还原成数组，转为list，一个个取，分别按照前序的样子就构造

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
 
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return serializeToString(root,"");
    }
 
    public String serializeToString(TreeNode root,String s){
        if (root == null){
            s += "None,";
        }else{
            s += "" + root.val + ",";
            s = serializeToString(root.left,s);
            s = serializeToString(root.right,s);
        }
        return s;
    }
 
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] d = data.split(",");
        List list = new ArrayList(Arrays.asList(d));
        return redeserialize(list);
    }
 
    public TreeNode redeserialize(List list){
        if (list.get(0).equals("None")){
            list.remove(0);
            return null;
        }
 
        TreeNode node = new TreeNode(Integer.parseInt(list.get(0)));
        list.remove(0);
        node.left = redeserialize(list);
        node.right = redeserialize(list);
        return node;
    }
}

剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

解题思路：

• 回溯剪枝，相同得剪掉
• 为了使得相同得在一起，所以先要给char数组排个序
• 每个遍历都可以从头开始取，只不过每次用过得不能再用
• 注意剪枝得条件，当前仅当当前值和前一个值相同，且上一个值刚刚被撤回使用
  • 例如： aab
  • 一开始取第一个a，递归发现第一个a取过了，取第二个a，判断第二个a和第一个相同，但是第一个a是正在使用中得，说明符合选用条件，可以选择，最后选择b，结果为 aab
  • 当一开始取第二个，答案会和取一个 a 重复，所以这种情况就得剪枝，唯一不一样得点在于，第一个 a 这时候并没有选用状态，说明是外层的重复，不是里面选取的重复，所以判断条件得加一个有没有已经被使用

class Solution {
    public String[] permutation(String s) {
        char[] c = s.toCharArray();
        Arrays.sort(c);
        boolean[] used = new boolean[c.length];
        List  list = new ArrayList();
        dfs(c,used,list,"");
        String[] res = new String[list.size()];
        for (int i=0;i
            res[i] = list.get(i);
        }
        return res;
    }
 
    public void dfs(char[] c,boolean[] used,List list,String s){
        if (s.length() == c.length){
            list.add(s);
            return;
        }
        for (int i=0;i
            if (i > 0 && c[i] == c[i-1] && !used[i-1]){
                continue;
            }
            if (!used[i]){
                used[i] = true;
                dfs(c,used,list,s+c[i]);
                used[i] = false;
            }
        }
    }
}

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

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解题思路：

• 数组中随机查找一个数，因为是多数的数，所以大概率能取到
• 取到的数，遍历一遍看出现的次数，如果出现的次数超过长度一半，说明就是答案
• 否则再次随机选取

class Solution {
    public int majorityElement(int[] nums) {
        Random random = new Random();
        int max = nums.length/2;
        while (true){
            int curr = nums[randomNum(random,0,nums.length)];
            if (countNum(nums,curr) > max){
                return curr;
            }
        }
    }
 
    public int countNum(int[] nums,int curr){
        int count = 0;
        for (int i=0;i
            if (nums[i] == curr)count++;
        }
        return count;
    }
 
    public int randomNum (Random random,int left,int right){
        return random.nextInt(right-left)+left;
    }
}

剑指 Offer 40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

解题思路：

• 优先队列，使用保持k个最小数在队列中，最后返回队列
• 先随机插入k个数，k个数在队列中已经排序好了，最大的数在队列顶部
• 从k+1开始，每插入一个数都和顶部数比较，谁小谁进队列

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        if (k == 0) { // 排除 0 的情况
            return res;
        }
        PriorityQueue queue = new PriorityQueue(new Comparator() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        for (int i = 0; i < k; ++i) {
            queue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; ++i) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            res[i] = queue.poll();
        }
        return res;
    }
}