剑指Offer归类总结

LeetCode学习计划里的剑指offer为期一个月，刷完又会重置，后面的题点又点不进去，只能等到对应天数才解锁，还要我一个一个搜，故做了这篇博客用于复习。

栈与队列

用两个栈实现队列

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

示例：

输入: [“CQueue”,”appendTail”,”deleteHead”,”deleteHead”,”deleteHead”]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]

class CQueue {
    LinkedList<Integer> A;
    LinkedList<Integer> B;
    public CQueue() {
        A = new LinkedList();
        B = new LinkedList();
    }
    
    public void appendTail(int value) {
        A.push(value);
    }
    
    public int deleteHead() {
        if(B.isEmpty()){
            if(A.isEmpty()){
                return -1;
            }
            while(!A.isEmpty()){
                B.push(A.pop());
            }
            return B.pop();
        }else{
            return B.pop();
        }
    }
}

包含min函数的栈

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

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.min(); –> 返回 -2.

class MinStack {
    LinkedList<Integer> A;
    LinkedList<Integer> B;
    /** initialize your data structure here. */
    public MinStack() {
        A = new LinkedList();
        B = new LinkedList();
    }
    
    public void push(int x) {
        A.push(x);
        if(B.isEmpty() || B.peek() >= A.peek()){
            B.push(x);
        }
    }
    
    public void pop() {
        if(A.pop().equals(B.peek())){
            B.pop();
        }
    }
    
    public int top() {
        return A.peek();
    }
    
    public int min() {
        return B.peek();
    }
}

滑动窗口的最大值

题目链接
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0) {
            return new int[0];
        }
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> queue = new ArrayDeque<>();
        for(int i = 0, j = 0; i < nums.length; i++) {
            if(!queue.isEmpty() && i - queue.peek() >= k) {
                queue.poll();
            }
            while(!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offer(i);
            if(i >= k - 1) {
                res[j++] = nums[queue.peek()];
            }
        }
        return res;
    }
}

队列的最大值

题目链接
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例：

输入:
[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

class MaxQueue {
    Queue<Integer> queue;
    Deque<Integer> deque;
    public MaxQueue() {
        queue = new LinkedList<>();
        deque = new LinkedList<>();
    }
    
    public int max_value() {
        return deque.isEmpty() ? -1 : deque.peekFirst();
    }
    
    public void push_back(int value) {
        queue.offer(value);
        while(!deque.isEmpty() && deque.peekLast() < value){
            deque.pollLast();
        }
        deque.offerLast(value);
    }
    
    public int pop_front() {
        if(queue.isEmpty()) return -1;
        if(queue.peek().equals(deque.peekFirst())){
            deque.pollFirst();
        }
        return queue.poll();
    }
}

链表

从尾到头打印链表

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

示例：

输入：head = [1,3,2]
输出：[2,3,1]

class Solution {
    ArrayList<Integer> tmp = new ArrayList();
    public int[] reversePrint(ListNode head) {
        dfs(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++){
            res[i] = tmp.get(i);
        }
        return res;
    }
    void dfs(ListNode head){
        if(head == null){
            return;
        }
        dfs(head.next);
        tmp.add(head.val);
    }
}

反转链表

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

示例：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

复杂链表的复制

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

示例：

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        //复制链表
        Node cur = head;
        while(cur != null){
            Node curNode = new Node(cur.val);
            curNode.next = cur.next;
            cur.next = curNode;
            cur = cur.next.next;
        }
        //链接random
        cur = head;
        while(cur != null){
            if(cur.random != null){
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //分离
        cur = head;
        Node curHead = head.next;
        Node curCopy = head.next;
        while(cur != null){
            //分离原链表
            cur.next = cur.next.next;
            cur = cur.next;
            if(curCopy.next != null){
                curCopy.next = curCopy.next.next;
                curCopy = curCopy.next;
            }
        }
        return curHead;
    }   
}

字符串

替换空格

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

示例：

输入：s = “We are happy.”
输出：”We%20are%20happy.”

class Solution {
    public String replaceSpace(String s) {
        if(s == null || s.length() == 0){
            return s;
        }
        return s.replaceAll(" ", "%20");
    }
}

左旋转字符串

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

示例：

输入: s = “abcdefg”, k = 2
输出: “cdefgab”

class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n) + s.substring(0, n);
    }
}

表示数值的字符串

题目链接
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：
1.若干空格
2.一个 小数 或者 整数
3.（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
4.若干空格
小数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（’+’ 或 ‘-‘）
下述格式之一：
1.至少一位数字，后面跟着一个点 ‘.’
2.至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
3.一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（’+’ 或 ‘-‘）
至少一位数字
部分数值列举如下：

• ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
  部分非数值列举如下：
• ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

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++){
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                numFlag = true;
            }else if(s.charAt(i) == '.' && !dotFlag && !eFlag){
                dotFlag = true;
            }else if((s.charAt(i) == 'e' || s.charAt(i) == 'E') && !eFlag && numFlag){
                eFlag = true;
                numFlag = false;
            }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;
    }
}

把字符串转换成整数

题目链接
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

 

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

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

查找

数组中重复的数字

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

示例：

输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length){
            if(nums[i] == i){
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]){
                return nums[i];
            }
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;
    }
}

在排序数组中查找数字 I

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

示例：

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

class Solution {
    public int search(int[] nums, int target) {
        if(nums.length == 0){
            return 0;
        }
        return helper(nums, target) - helper(nums, target - 1);
    }

    int helper(int[] nums, int target){
        int i = 0, j = nums.length - 1;
        while(i <= j){
            int m = i + ((j - i) >> 1);
            if(nums[m] <= target){
                i = m + 1;
            }else{
                j = m - 1;
            }
        }
        return i;
    }
}

0～n-1中缺失的数字

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

示例：

输入: [0,1,3]
输出: 2

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while(i <= j){
            int m = i + ((j - i ) >> 1);
            if(nums[m] == m){
                i = m + 1;
            }else{
                j = m - 1;
            }
        }
        return i;
    }
}

二维数组中的查找

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

示例：
现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

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

旋转数组的最小数字

题目链接
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。  

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

示例：

输入：numbers = [3,4,5,1,2]
输出：1

class Solution {
    public int minArray(int[] numbers) {
        int l = 0, r = numbers.length - 1;
        while(l <= r){
            int m = l + ((r - l) >> 1);
            if(numbers[m] < numbers[r]){
                r = m;
            }else if(numbers[m] > numbers[r]){
                l = m + 1;
            }else{
                r--;
            }
        }
        return numbers[l];
    }
}

第一个只出现一次的字符

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

示例：

输入：s = “abaccdeff”
输出：’b’

class Solution {
    public char firstUniqChar(String s) {
        char[] ch = new char[26];
        char[] str = s.toCharArray();
        for(char c : str){
            ch[c - 'a']++;
        }
        for(int i = 0; i < str.length; i++){
            if(ch[str[i] - 'a'] == 1){
                return str[i];
            }
        }
        return ' ';
    }
}

搜索与回溯

从上到下打印二叉树

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

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

从上到下打印二叉树 II

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

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--){
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

从上到下打印二叉树 III

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

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        boolean flag = false;
        queue.add(root);
        while(!queue.isEmpty()){
            flag = !flag;
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--){
                TreeNode node = queue.poll();
                if(flag){
                    tmp.addLast(node.val);
                }else{
                    tmp.addFirst(node.val);
                }
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
}

树的子结构

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

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

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;
        return helper(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    private boolean helper(TreeNode A, TreeNode B){
        if(B == null) return true;
        if(A == null) return false;
        return A.val == B.val && helper(A.left, B.left) && helper(A.right, B.right);
    }
}

二叉树的镜像

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

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

对称的二叉树

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

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return helper(root.left, root.right);
    }
    private boolean helper(TreeNode p, TreeNode q){
        //先且再或
        if(p == null && q == null) return true;
        if(p == null || q == null || p.val != q.val) return false;
        return helper(p.left, q.right) && helper(p.right, q.left);
    }
}

矩阵中的路径

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

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

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例：

输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
输出：true

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(backtrack(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }

    boolean backtrack(char[][] board, char[] words, int i, int j, int start){
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[start]) return false;
        if(start == words.length - 1) return true;
        board[i][j] = '\0';
        boolean res = backtrack(board, words, i + 1, j, start + 1) || backtrack(board, words, i - 1, j, start + 1) || 
                      backtrack(board, words, i, j + 1, start + 1) || backtrack(board, words, i, j - 1, start + 1);
        board[i][j] = words[start];
        return res;
    }
}

机器人的运动范围

题目链接
地上有一个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。请问该机器人能够到达多少个格子？

示例：

输入：m = 2, n = 3, k = 1
输出：3

class Solution {
    boolean[][] visit;
    public int movingCount(int m, int n, int k) {
        visit = new boolean[m][n];
        return dfs(m, n, k, 0, 0);
    }
    int dfs(int m, int n, int k, int i, int j){
        if(i >= m || j >= n || visit[i][j] || tmpSum(i) + tmpSum(j) > k) return 0;
        visit[i][j] = true;
        return 1 + dfs(m, n, k, i + 1, j) + dfs(m, n, k, i, j + 1);
    }
    int tmpSum(int num){
        int sum = 0;
        while(num != 0){
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

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

题目链接
给你二叉树的根节点 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]]

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

二叉搜索树与双向链表

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

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

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

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

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

class Solution {
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        infixOrder(root, queue);
        Node head = queue.poll();
        Node pre = head;
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            pre.right = cur;
            cur.left = pre;
            pre = cur;
        }
        pre.right = head;
        head.left = pre;
        return head;
    }
    void infixOrder(Node root, Queue queue){
        if(root.left != null){
            infixOrder(root.left, queue);
        }
        queue.add(root);
        if(root.right != null){
            infixOrder(root.right, queue);
        }
    }
}

二叉搜索树的第k大节点

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

class Solution {
    int res = 0, count = 0;
    public int kthLargest(TreeNode root, int k) {
        dfs(root, k);
        return res;
    }
    void dfs(TreeNode root, int k){
        if(root == null) return;
        if(root.right != null){
            dfs(root.right, k);
        }
        if(++count == k){
            res = root.val;
        }
        if(root.left != null){
            dfs(root.left, k);
        }
    }
}

二叉树的深度

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

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return left > right ? left + 1: right + 1;
    }
}

平衡二叉树

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

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

序列化二叉树

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

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

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

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

动态规划

斐波那契数列

题目链接
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

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

示例：

输入：n = 2
输出：1

class Solution {
    public int fib(int n) {
        int f1 = 0;
        int f2 = 1;
        int fn = 0;
        if(n == 1) return f2;
        for(int i = 2; i <= n; i++){
            fn = (f1 + f2) % 1000000007;
            f1 = f2;
            f2 = fn;
        }
        return fn;
    }
}

青蛙跳台阶问题

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

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

示例：

输入：n = 2
输出：2

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

股票的最大利润

题目链接
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例:

输入: [7,1,5,3,6,4]
输出: 5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

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

连续子数组的最大和

题目链接
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例：

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

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

礼物的最大价值

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

示例:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

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

把数字翻译成字符串

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

示例:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi”

class Solution {
    public int translateNum(int num) {
        String str = String.valueOf(num);
        int[] dp = new int[str.length() + 1];
        dp[0] = dp[1] = 1;
        for(int i = 2; i <= str.length(); i++){
            String tmpStr = str.substring(i - 2, i);
            if(tmpStr.compareTo("10") >= 0 && tmpStr.compareTo("25") <= 0){
                dp[i] = dp[i - 1] + dp[i - 2];
            }else{
                dp[i] = dp[i - 1];
            }
        }
        return dp[str.length()];
    }
}

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

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

示例：

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() < 2) return s.length();
        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;
    }
}

正则表达式匹配

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

示例:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

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

丑数

题目链接
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例：

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

class Solution {
    public int nthUglyNumber(int n) {
        if(n == 0) return 0;
        int[] ugly = new int[n];
        ugly[0] = 1;
        int i = 0, j = 0, k = 0;
        for(int idx = 1; idx < n; idx++){
            int tmp = Math.min(ugly[i] * 2, Math.min(ugly[j] * 3, ugly[k] * 5));
            if(tmp == ugly[i] * 2) i++;
            if(tmp == ugly[j] * 3) j++;
            if(tmp == ugly[k] * 5) k++;
            ugly[idx] = tmp;
        }
        return ugly[n - 1];
    }
}

n个骰子的点数

题目链接
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例：

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

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[] tmp = new double[5 * i + 1];
            for (int j = 0; j < dp.length; j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
}

双指针

删除链表的节点

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

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

示例：

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head == null) return null;
        ListNode pre = new ListNode(-1);
        ListNode cur = pre;
        pre.next = head;
        while(cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
                break;
            }
            cur = cur.next;
        }
        return pre.next;
    }
}

链表中倒数第k个节点

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

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

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null || k == 0) return null;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && k > 0){
            fast = fast.next;
            k--;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

合并两个排序的链表

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

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

两个链表的第一个公共节点

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

如下面的两个链表：

在节点 c1 开始相交。

示例：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode n1 = headA;
        ListNode n2 = headB;
        while(n1 != n2){
            n1 = n1 == null ? headB : n1.next;
            n2 = n2 == null ? headA : n2.next;
        }
        return n1;
    }
}

调整数组顺序使奇数位于偶数前面

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

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。

class Solution {
    public int[] exchange(int[] nums) {
        if(nums.length == 0) return new int[0];
        int tmp = 0;
        int l = 0, r = nums.length - 1;
        while(l < r){
            while(l < r && nums[l] % 2 != 0){
                l++;
            }
            while(l < r && nums[r] % 2 == 0){
                r--;
            }
            tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
        }
        return nums;
    }
}

和为s的两个数字

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

示例：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

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

翻转单词顺序

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

示例：

输入: “the sky is blue”
输出: “blue is sky the”

class Solution {
    public String reverseWords(String s) {
        String[] str = s.trim().split(" ");
        StringBuilder sb = new StringBuilder();
        for(int i = str.length - 1; i >= 0; i--){
            if(str[i].equals("")) continue;
            if(i == 0){
                sb.append(str[i]);
            }else{
                sb.append(str[i]).append(" ");
            }
        }
        return sb.toString();
    }
}

排序

最小的k个数

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

示例：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k >= arr.length) return arr;
        return quickSort(arr, k, 0, arr.length - 1);
    }
    int[] quickSort(int[] arr, int k, int l, int r){
        int i = l, j = r;
        while(i < j){
            while(i < j && arr[j] >= arr[l]) j--;
            while(i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j); 
        }
        swap(arr, i, l);
        if(i > k) return quickSort(arr, k, l, i - 1);
        if(i < k) return quickSort(arr, k, i + 1, r);
        return Arrays.copyOf(arr, k);
    }
    void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

把数组排成最小的数

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

示例：

输入: [10,2]
输出: “102”

class Solution {
     public String minNumber(int[] nums){
        String[] str = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            str[i] = String.valueOf(nums[i]);
        }
        quickSort(str, 0, str.length - 1);
        StringBuilder res = new StringBuilder();
        for (String s : str) {
            res.append(s);
        }
        return res.toString();
    }
    public void quickSort(String[] str, int low, int high){
        if(low < high){
            int mid = getMid(str, low, high);
            quickSort(str, low, mid - 1);
            quickSort(str, mid + 1, high);
        }
    }
    int getMid(String[] str, int low, int high){
        String tmp = str[low];
        while (low < high){
            while (low < high && (str[high] + tmp).compareTo(tmp + str[high])>= 0) high--;
                str[low] = str[high];
            while (low < high && (str[low] + tmp).compareTo(tmp + str[low]) <= 0) low++;
                str[high] = str[low];
        }
        str[low] = tmp;
        return low;
    }
}

扑克牌中的顺子

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

示例：

输入: [1,2,3,4,5]
输出: True

class Solution {
    public boolean isStraight(int[] nums) {
        Set<Integer> repeat = new HashSet<>();
        int max = 0, min = 14;
        for(int num : nums){
            if(num == 0) continue;
            max = Math.max(max, num);
            min = Math.min(min, num);
            if(repeat.contains(num)) return false;
            repeat.add(num);
        }
        return max - min < 5;
    }
}

数据流中的中位数

题目链接
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

• void addNum(int num) - 从数据流中添加一个整数到数据结构中。
• double findMedian() - 返回目前所有元素的中位数。

示例：

输入：
[“MedianFinder”,”addNum”,”addNum”,”findMedian”,”addNum”,”findMedian”]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

class MedianFinder {
    PriorityQueue<Integer> left;
    PriorityQueue<Integer> right;
    public MedianFinder() {
        left = new PriorityQueue<>((n1, n2) -> (n2 - n1));
        right = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        left.add(num);
        right.add(left.poll());
        if(left.size() + 1 < right.size()){
            left.add(right.poll());
        }
    }
    
    public double findMedian() {
        if(right.size() > left.size()) return right.peek();
        return (double)(left.peek() + right.peek()) / 2;
    }
}

分治算法

重建二叉树

题目链接
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例：

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

class Solution {
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++){
            dic.put(inorder[i], i);
        }
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int root, int left, int right){
        if(left > right) return null;
        TreeNode node = new TreeNode(preorder[root]);
        int i = dic.get(preorder[root]);
        node.left = recur(root + 1, left, i - 1);
        node.right = recur(root + i - left + 1, i + 1, right);
        return node;
    }
}

数值的整数次方

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

示例：

输入：x = 2.00000, n = 10
输出：1024.00000

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

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

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

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null) return true;
        return func(postorder, 0, postorder.length - 1);
    }
    boolean func(int[] postorder, int i, int j){
        if(i > j) return true;
        int root = postorder[j];
        int p = i;
        while(postorder[p] < root) p++;
        for(int k = p; k < j; k++){
            if(postorder[k] < root) return false;
        }
        return func(postorder, i, p - 1) && func(postorder, p, j - 1);
    }
}

打印从1到最大的n位数

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

示例：

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

class Solution {
    int[] res;
    int nine = 0, count = 0, start, n;
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public int[] printNumbers(int n) {
        this.n = n;
        res = new int[(int)Math.pow(10, n) - 1];
        num = new char[n];
        start = n - 1;
        dfs(0);
        return res;
    }
    void dfs(int x) {
        if(x == n) {
            String s = String.valueOf(num).substring(start);
            if(!s.equals("0")) res[count++] = Integer.parseInt(s);
            if(n - start == nine) start--;
            return;
        }
        for(char i : loop) {
            if(i == '9') nine++;
            num[x] = i;
            dfs(x + 1);
        }
        nine--;
    }
}

数组中的逆序对

题目链接
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例：

输入: [7,5,6,4]
输出: 5

class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        if(nums.length == 0) return 0;
        process(nums, 0, nums.length - 1);
        return count;
    }
    void process(int[] nums, int l, int r){
        if(l >= r) return;
        int mid = l + ((r - l) >> 1);
        process(nums, l, mid);
        process(nums, mid + 1, r);
        merge(nums, l, mid, r);
    }
    void merge(int[] nums, int l, int mid, int r){
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l, p2 = mid + 1;
        while(p1 <= mid && p2 <= r){
            if(nums[p1] <= nums[p2]){
                help[i++] = nums[p1++];
            }
            else{
                help[i++] = nums[p2++];
                count += (mid - p1 + 1);
            }
        }
        while(p1 <= mid) help[i++] = nums[p1++];
        while(p2 <= r) help[i++] = nums[p2++];
        for(i = 0; i < help.length; i++){
            nums[l + i] = help[i];
        }
    }
}

位运算