剑指 Offer（第 2 版）

拼搏现实的明天。 2022-09-16 00:25 363阅读 0赞

### 目录 ###

*  剑指 Offer 03. 数组中重复的数字
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 04. 二维数组中的查找
 *   *  题目介绍
     *   *   *  \[240. 搜索二维矩阵 II\](https://leetcode-cn.com/problems/search-a-2d-matrix-ii/)
     *  题目实现
 *  剑指 Offer 05. 替换空格
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 06. 从尾到头打印链表
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 07. 重建二叉树
 *   *  题目介绍
     *   *   *  \[105. 从前序与中序遍历序列构造二叉树\](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
     *  题目实现
 *  剑指 Offer 09. 用两个栈实现队列
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 10- I. 斐波那契数列
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 10- II. 青蛙跳台阶问题
 *   *  题目介绍
     *   *   *  \[70. 爬楼梯\](https://leetcode-cn.com/problems/climbing-stairs/)
     *  题目实现
 *  剑指 Offer 11. 旋转数组的最小数字
 *   *  题目介绍
     *   *   *  \[154. 寻找旋转排序数组中的最小值 II\](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/)
     *  题目实现
 *  剑指 Offer 12. 矩阵中的路径
 *   *  题目介绍
     *   *   *  \[79. 单词搜索\](https://leetcode-cn.com/problems/word-search/)
     *  题目实现
 *  剑指 Offer 13. 机器人的运动范围
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 14- I. 剪绳子
 *   *  题目介绍
     *   *   *  \[343. 整数拆分\](https://leetcode-cn.com/problems/integer-break/)
     *  题目实现
 *  剑指 Offer 14- II. 剪绳子 II
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 15. 二进制中1的个数
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 16. 数值的整数次方
 *   *  题目介绍
     *   *   *  \[50. Pow(x, n)\](https://leetcode-cn.com/problems/powx-n/)
     *  题目实现
 *  剑指 Offer 17. 打印从1到最大的n位数
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 18. 删除链表的节点
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 19. 正则表达式匹配
 *   *  题目介绍
     *   *   *  \[10. 正则表达式匹配\](https://leetcode-cn.com/problems/regular-expression-matching/)
     *  题目实现
 *  剑指 Offer 20. 表示数值的字符串
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 22. 链表中倒数第k个节点
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 24. 反转链表
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 25. 合并两个排序的链表
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 26. 树的子结构
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 27. 二叉树的镜像
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 28. 对称的二叉树
 *   *  题目介绍
     *   *   *  \[101. 对称二叉树\](https://leetcode-cn.com/problems/symmetric-tree/)
     *  题目实现
 *  剑指 Offer 29. 顺时针打印矩阵
 *   *  题目介绍
     *   *   *  \[54. 螺旋矩阵\](https://leetcode-cn.com/problems/spiral-matrix/)
     *  题目实现
 *  剑指 Offer 30. 包含min函数的栈
 *   *  题目介绍
     *   *   *  \[155. 最小栈\](https://leetcode-cn.com/problems/min-stack/)
     *  题目实现
 *  剑指 Offer 31. 栈的压入、弹出序列
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 32 - I. 从上到下打印二叉树
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 32 - II. 从上到下打印二叉树 II
 *   *  题目介绍
     *   *   *  \[102. 二叉树的层序遍历\](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
     *  题目实现
 *  剑指 Offer 32 - III. 从上到下打印二叉树 III
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 33. 二叉搜索树的后序遍历序列
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 34. 二叉树中和为某一值的路径
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 35. 复杂链表的复制
 *   *  题目介绍
     *   *   *  \[138. 复制带随机指针的链表\](https://leetcode-cn.com/problems/copy-list-with-random-pointer/)
     *  题目实现
 *  剑指 Offer 36. 二叉搜索树与双向链表
 *   *  题目介绍
     *   *   *  \[426. 将二叉搜索树转化为排序的双向链表\](https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/)
     *  题目实现
 *  剑指 Offer 37. 序列化二叉树
 *   *  题目介绍
     *   *   *  \[297. 二叉树的序列化与反序列化\](https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/)
     *  题目实现
 *  剑指 Offer 38. 字符串的排列
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 39. 数组中出现次数超过一半的数字
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 40. 最小的k个数
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 41. 数据流中的中位数
 *   *  题目介绍
     *   *   *  \[295. 数据流的中位数\](https://leetcode-cn.com/problems/find-median-from-data-stream/)
     *  题目实现
 *  剑指 Offer 42. 连续子数组的最大和
 *   *  题目介绍
     *   *   *  \[53. 最大子序和\](https://leetcode-cn.com/problems/maximum-subarray/)
     *  题目实现
 *  剑指 Offer 43. 1～n 整数中 1 出现的次数
 *   *  题目介绍
     *   *   *  \[233. 数字 1 的个数\](https://leetcode-cn.com/problems/number-of-digit-one/)
     *  题目实现
 *  剑指 Offer 44. 数字序列中某一位的数字
 *   *  题目介绍
     *   *   *  \[400. 第 N 位数字\](https://leetcode-cn.com/problems/nth-digit/)
     *  题目实现
 *  剑指 Offer 45. 把数组排成最小的数
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 46. 把数字翻译成字符串
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 47. 礼物的最大价值
 *   *  题目介绍
     *   *   *  \[64. 最小路径和\](https://leetcode-cn.com/problems/minimum-path-sum/)
             *  \[62. 不同路径\](https://leetcode-cn.com/problems/unique-paths/)
     *  题目实现
 *  剑指 Offer 48. 最长不含重复字符的子字符串
 *   *  题目介绍
     *   *   *  \[3. 无重复字符的最长子串\](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)
     *  题目实现
 *  剑指 Offer 49. 丑数
 *   *  题目介绍
     *   *   *  \[264. 丑数 II\](https://leetcode-cn.com/problems/ugly-number-ii/)
     *  题目实现
 *  剑指 Offer 50. 第一个只出现一次的字符
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 51. 数组中的逆序对
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 52. 两个链表的第一个公共节点
 *   *  题目介绍
     *   *   *  \[160. 相交链表\](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/)
     *  题目实现
 *  剑指 Offer 53 - I. 在排序数组中查找数字 I
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 53 - II. 0～n-1中缺失的数字
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 54. 二叉搜索树的第k大节点
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 55 - I. 二叉树的深度
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 55 - II. 平衡二叉树
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 56 - I. 数组中数字出现的次数
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 56 - II. 数组中数字出现的次数 II
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 57 - I. 和为s的两个数字
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 57 - II. 和为s的连续正数序列
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 58 - I. 翻转单词顺序
 *   *  题目介绍
     *   *   *  \[151. 翻转字符串里的单词\](https://leetcode-cn.com/problems/reverse-words-in-a-string/)
     *  题目实现
 *  剑指 Offer 58 - II. 左旋转字符串
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 59 - I. 滑动窗口的最大值
 *   *  题目介绍
     *   *   *  \[239. 滑动窗口最大值\](https://leetcode-cn.com/problems/sliding-window-maximum/)
     *  题目实现
 *  剑指 Offer 59 - II. 队列的最大值
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 60. n个骰子的点数
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 61. 扑克牌中的顺子
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 62. 圆圈中最后剩下的数字
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 63. 股票的最大利润
 *   *  题目介绍
     *   *   *  \[121. 买卖股票的最佳时机\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/)
             *  \[122. 买卖股票的最佳时机 II\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/)
             *  \[123. 买卖股票的最佳时机 III\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/)
             *  \[188. 买卖股票的最佳时机 IV\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/)
             *  \[714. 买卖股票的最佳时机含手续费\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)
             *  \[309. 最佳买卖股票时机含冷冻期\](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)
     *  题目实现
 *  剑指 Offer 64. 求1+2+…+n
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 65. 不用加减乘除做加法
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 66. 构建乘积数组
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 67. 把字符串转换成整数
 *   *  题目介绍
     *   *   *  \[8. 字符串转换整数 (atoi)\](https://leetcode-cn.com/problems/string-to-integer-atoi/)
     *  题目实现
 *  剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
 *   *  题目介绍
     *   *   *  \[剑指 Offer 68 - II. 二叉树的最近公共祖先\](https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/)
             *  \[236. 二叉树的最近公共祖先\](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
     *  题目实现
 *  剑指 Offer 68 - II. 二叉树的最近公共祖先
 *   *  题目介绍
     *   *   *  \[剑指 Offer 68 - I. 二叉搜索树的最近公共祖先\](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/)
             *  \[236. 二叉树的最近公共祖先\](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
     *  题目实现

--------------------

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

## 题目介绍 ##

找出数组中重复的数字。

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

**示例 1：**

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

**限制：**

*  2 <= n <= 100000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

我们可以利用 set 集合元素不能重复这一特点，循环遍历数组元素，依次加入到 set 集合中，如果加入失败，就代表该数字重复。

class Solution { 
        public int findRepeatNumber(int[] nums) { 
            HashSet<Integer> hashSet = new HashSet<>();
            for (int num : nums) { 
                if (!hashSet.add(num)) { 
                    return num;
                }
            }
            return -1;
        }
    }

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

## 题目介绍 ##

在一个 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]
    ]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

**限制：**

*  0 <= n <= 1000
 *  0 <= m <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

**相同题目：**

*  #### [240. 搜索二维矩阵 II][240. _ II] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

如果 `target = 5`，我们来看看在不使用暴力搜索的情况下，如何快速查找。

从右上角开始查找，`15>5`，因此，我们需要向左移动。为什么不向下移动，因为，向下的数都比15大。

![bd93575c0908efc3548a1d757720b38c.png][]

向左移动完毕之后，`11>5`，因此，我们需要向左移动。为什么不向下移动，因为，向下的数都比11大。

![14a4a2ec2b990591c8f725460e04c3ed.png][]

向左移动完毕之后，`7>5`，因此，我们需要向左移动。为什么不向下移动，因为，向下的数都比7大。

![3e4d4154be5fe8d9868259ef6c57dc5e.png][]

向左移动完毕之后，`4<5`，因此，我们需要向下移动。为什么不向左移动，因为，向左的数都比4小。

![c8710acc1515262c469ecd56f241c541.png][]

向下移动完毕之后，`5=5`，因此，我们需要返回true。

![2fac973f6367147085e1d776a1453d02.png][]

可能上面的步骤不是很难理解，但有人可能会想，为啥不从左上角的 1 开始搜索呢？原因很简单，左上角的 1 下边都是比 1 大的，左上角的 1 右边都是比 1 大的，两个都是大的，你咋知道该下还是垓右，同理，右下角的 30 也类似，向左看都比 30 小，向上看都比 30 小。两个都是小的，你咋知道该左还是垓上，因此，只有从左下角的18处或者右上角的15处开始搜索才是正解。因为当target大于、小于、等于当前数组元素值时，都有方向可以走，没有歧义。

class Solution { 
        public boolean searchMatrix(int[][] matrix, int target) { 
            // 临界检查
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
            // 获取行数
            int rows = matrix.length;
            // 获取列数
            int cols = matrix[0].length;
            // 定义行指针
            int row = 0;
            // 定义列指针（从右上角开始搜索）
            int col = cols - 1;
            // 循环搜索
            while ((row >= 0 && row < rows) && (col >= 0 && col < cols)) { 
                if (target > matrix[row][col]) { 
                    row++;
                } else if (target < matrix[row][col]) { 
                    col--;
                } else { 
                    return true;
                }
            }
            // 没有找到
            return false;
        }
    }

# 剑指 Offer 05. 替换空格 #

## 题目介绍 ##

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

**示例 1：**

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

**限制：**

*  0 <= s 的长度 <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public String replaceSpace(String s) { 
            return s.replace(" ", "%20");
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**限制：**

*  0 <= 链表长度 <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

栈的特点是后进先出，即最后压入栈的元素最先弹出。考虑到栈的这一特点，使用栈将链表元素顺序倒置。从链表的头节点开始，依次将每个节点压入栈内，然后依次弹出栈内的元素并存储到数组中。

class Solution { 
        public int[] reversePrint(ListNode head) { 
            Stack<ListNode> stack = new Stack<>();
            while (head != null) { 
                stack.push(head);
                head = head.next;
            }
            int size = stack.size();
            int[] arr = new int[size];
            for (int i = 0; i < size; i++) { 
                arr[i] = stack.pop().val;
            }
            return arr;
        }
    }

# 剑指 Offer 07. 重建二叉树 #

## 题目介绍 ##

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

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

**示例 1：**

![ff3a53d9fd4cda56349a97000cc0d833.png][]

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
    Output: [3,9,20,null,null,15,7]

**示例 2：**

Input: preorder = [-1], inorder = [-1]
    Output: [-1]

**提示：**

*  0 <= 节点个数 <= 5000

**相同题目：**

*  #### [105. 从前序与中序遍历序列构造二叉树][105.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        private Map<Integer, Integer> indexMap = new HashMap<>();
    
        public TreeNode buildTree(int[] preorder, int[] inorder) { 
            int n = inorder.length;
            for (int i = 0; i < n; i++) { 
                indexMap.put(inorder[i], i);
            }
            return buildSubTree(preorder, inorder, 0, n - 1, 0, n - 1);
        }
    
        private TreeNode buildSubTree(int[] preorder, int[] inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) { 
            //递归的终止
            if (preorderLeft > preorderRight) return null;
            //获取根元素
            int rootValue = preorder[preorderLeft];
            //定位根节点
            Integer inorderRoot = indexMap.get(rootValue);
            //构造根节点
            TreeNode root = new TreeNode(rootValue);
            //左元素个数
            int size = inorderRoot - inorderLeft;
            //构造左子树
            root.left = buildSubTree(preorder, inorder, preorderLeft + 1, preorderLeft + size, inorderLeft, inorderRoot - 1);
            //构造右子树
            root.right = buildSubTree(preorder, inorder, preorderLeft + size + 1, preorderRight, inorderRoot + 1, inorderRight);
            //返回根节点
            return root;
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

输入：
    ["CQueue","appendTail","deleteHead","deleteHead"]
    [[],[3],[],[]]
    输出：[null,null,3,-1]

**示例 2：**

输入：
    ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
    [[],[],[5],[2],[],[]]
    输出：[null,-1,null,null,5,2]

**提示：**

*  1 <= values <= 10000
 *  最多会对 appendTail、deleteHead 进行 10000 次调用

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

队列的特性是 `FIFO`（先入先出），而栈的特性是 `FILO`（先入后出）。

知道两者特性之后，我们需要用两个栈来模拟队列的特性，一个栈为入队栈，一个栈为出对栈。

当出队栈存在内容时，出队栈的栈顶，即为第一个出队的元素。

若出队栈无元素，我们的需求又是出队的话，我们就需要将入队栈的内容反序导入出队栈，然后弹出栈顶即可。

注意：根据栈的的特性，我们仅能使用 `push` 和 `pop` 操作。

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

# 剑指 Offer 10- I. 斐波那契数列 #

## 题目介绍 ##

写一个函数，输入 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。

**示例 1：**

输入：n = 2
    输出：1

**示例 2：**

输入：n = 5
    输出：5

**提示：**

*  0 <= n <= 100

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

解法一：数组版

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

解法二：变量版

class Solution { 
        public int fib(int n) { 
            if (n <= 1) return n;
            int n1 = 0, n2 = 0, r = 1;
            for (int i = 2; i < n + 1; i++) { 
                n1 = n2;
                n2 = r;
                r = (n1 + n2) % 1000000007;
            }
            return r;
        }
    }

# 剑指 Offer 10- II. 青蛙跳台阶问题 #

## 题目介绍 ##

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

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

**示例 1：**

输入：n = 2
    输出：2

**示例 2：**

输入：n = 7
    输出：21

**示例 3：**

输入：n = 0
    输出：1

**提示：**

*  0 <= n <= 100

**相同题目：**

*  #### [70. 爬楼梯][70.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

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

# 剑指 Offer 11. 旋转数组的最小数字 #

## 题目介绍 ##

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 \[3,4,5,1,2\] 为 \[1,2,3,4,5\] 的一个旋转，该数组的最小值为1。

**示例 1：**

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

**示例 2：**

输入：[2,2,2,0,1]
    输出：0

**相同题目：**

*  #### [154. 寻找旋转排序数组中的最小值 II][154. _ II] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

解法一：排序

class Solution { 
        public int minArray(int[] numbers) { 
            Arrays.sort(numbers);
            return numbers[0];
        }
    }

解法二：遍历

class Solution { 
        public int minArray(int[] numbers) { 
            int min = numbers[0];
            for (int i = 0; i < numbers.length; i++) { 
                if (min > numbers[i]) { 
                    min = numbers[i];
                }
            }
            return min;
        }
    }

# 剑指 Offer 12. 矩阵中的路径 #

## 题目介绍 ##

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

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

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

![830137c28efb4b66b0e3d17a14eb2d50.png][]

**示例 1：**

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

**示例 2：**

输入：board = [["a","b"],["c","d"]], word = "abcd"
    输出：false

**提示：**

*  1 <= board.length <= 200
 *  1 <= board\[i\].length <= 200
 *  board 和 word 仅由大小写英文字母组成

**相同题目：**

*  #### [79. 单词搜索][79.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public boolean exist(char[][] board, String word) { 
            for (int i = 0; i < board.length; i++) { 
                for (int j = 0; j < board[0].length; j++) { 
                    if (dfs(board, word, i, j, 0)) { 
                        return true;
                    }
                }
            }
            return false;
        }
    
        private boolean dfs(char[][] board, String word, int i, int j, int k) { 
            //临界条件
            if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k)) { 
                return false;
            }
            //搜索结束
            if (k == word.length() - 1) { 
                return true;
            }
            //搜索完成
            board[i][j] = 0;
            //上下左右
            boolean res = dfs(board, word, i - 1, j, k + 1) ||
                    dfs(board, word, i + 1, j, k + 1) ||
                    dfs(board, word, i, j - 1, k + 1) ||
                    dfs(board, word, i, j + 1, k + 1);
            //还原现场
            board[i][j] = word.charAt(k);
            //返回结果
            return res;
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**示例 2：**

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

**提示：**

*  1 <= n,m <= 100
 *  0 <= k <= 20

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        private int count = 0;
        private boolean[][] visited;
    
        public int movingCount(int m, int n, int k) { 
            visited = new boolean[m][n];
            dfs(m, n, 0, 0, k);
            return count;
        }
    
        private void dfs(int m, int n, int i, int j, int k) { 
            //临界条件
            if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || calc(i, j) > k) { 
                return;
            }
            //已经走过
            visited[i][j] = true;
            //更新最值
            count++;
            //上下左右
            dfs(m, n, i - 1, j, k);
            dfs(m, n, i + 1, j, k);
            dfs(m, n, i, j - 1, k);
            dfs(m, n, i, j + 1, k);
        }
    
        private int calc(int i, int j) { 
            String si = String.valueOf(i);
            String sj = String.valueOf(j);
            char[] c1 = si.toCharArray();
            char[] c2 = sj.toCharArray();
            int s = 0;
            for (char c : c1) { 
                s += c - 48;
            }
            for (char c : c2) { 
                s += c - 48;
            }
            return s;
        }
    }

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

**示例 1：**

输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1

**示例 2：**

输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

**提示：**

*  2 <= n <= 58

**相同题目：**

*  #### [343. 整数拆分][343.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![ad2718fb6b96ee51b4fd10deb112e87b.png][]

class Solution { 
        public int cuttingRope(int n) { 
            int[] dp = new int[n + 1];
            dp[2] = 1;
            for (int i = 3; i < n + 1; i++) { 
                for (int j = 2; j < i; j++) { 
                    dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
                }
            }
            return dp[n];
        }
    }

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

**示例 1：**

输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1

**示例 2：**

输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

**提示：**

*  2 <= n <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

import java.math.BigInteger;
    import java.util.Arrays;
    
    class Solution { 
        public int cuttingRope(int n) { 
            BigInteger[] dp = new BigInteger[n + 1];
            Arrays.fill(dp, BigInteger.valueOf(0));
            dp[2] = BigInteger.valueOf(1);
            for (int i = 3; i < n + 1; i++) { 
                for (int j = 2; j < i; j++) { 
                    dp[i] = dp[i].max(BigInteger.valueOf(j * (i - j))).max(dp[i - j].multiply(BigInteger.valueOf(j)));
                }
            }
            return dp[n].mod(BigInteger.valueOf(1000000007)).intValue();
        }
    }

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

## 题目介绍 ##

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 `1` 的个数。例如，把 `9` 表示成二进制是 `1001`，有 `2` 位是 `1`。因此，如果输入 `9`，则该函数输出 `2`。

**示例 1：**

输入：00000000000000000000000000001011
    输出：3
    解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

**示例 2：**

输入：00000000000000000000000010000000
    输出：1
    解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

**示例 3：**

输入：11111111111111111111111111111101
    输出：31
    解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

**提示：**

*  输入必须是长度为 32 的 二进制串 。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

*  根据 **与运算** 定义，设二进制数字 n ，则有：
    
     *  若 n & 1 = 0 ，则 n 二进制 **最右一位** 为 0 ；
     *  若 n & 1 = 1 ，则 n 二进制 **最右一位** 为 1 。
 *  根据以上特点，考虑以下 **循环判断** ：
    
     *  判断 n 最右一位是否为 1 ，根据结果计数。
     *  将 n 右移一位（本题要求把数字 n 看作无符号数，因此使用 **无符号右移** 操作）。

public class Solution { 
        public int hammingWeight(int n) { 
            int count = 0;
            while (n != 0) { 
                count += n & 1;
                n >>>= 1;
            }
            return count;
        }
    }

另外一种解法就更简单了。

public class Solution { 
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) { 
            return Integer.bitCount(n);
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**示例 2：**

输入：x = 2.10000, n = 3
    输出：9.26100

**示例 3：**

输入：x = 2.00000, n = -2
    输出：0.25000
    解释：2-2 = 1/22 = 1/4 = 0.25

**提示：**

*  \-100.0 < x < 100.0
 *  \-231 <= n <= 231\-1
 *  \-104 <= xn <= 104

**相同题目：**

*  #### [50. Pow(x, n)][50. Pow_x_ n] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![37c7fecb1af4ac86a40cc94f02fe04a5.png][]

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

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

## 题目介绍 ##

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

**示例 1：**

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

**说明：**

*  用返回一个整数列表来代替打印
 *  n 为正整数

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

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

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

## 题目介绍 ##

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

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

注意：此题对比原题有改动

**示例 1：**

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

**示例 2：**

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

**说明：**

*  题目保证链表中节点的值互不相同
 *  若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public ListNode deleteNode(ListNode head, int val) { 
            ListNode dummyHead = new ListNode();
            dummyHead.next = head;
            ListNode q = dummyHead;
            ListNode p = dummyHead.next;
            while (p != null) { 
                if (p.val == val) { 
                    q.next = q.next.next;
                    break;
                }
                q = q.next;
                p = p.next;
            }
            return dummyHead.next;
        }
    }

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

## 题目介绍 ##

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘\*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符  
‘\*’ 匹配零个或多个前面的那一个元素  
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

**示例 1：**

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

**示例 2：**

输入：s = "aa" p = "a*"
    输出：true
    解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

**示例 3：**

输入：s = "ab" p = ".*"
    输出：true
    解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

**示例 4：**

输入：s = "aab" p = "c*a*b"
    输出：true
    解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

**示例 5：**

输入：s = "mississippi" p = "mis*is*p*."
    输出：false

**提示：**

*  0 <= s.length <= 20
 *  0 <= p.length <= 30
 *  s 可能为空，且只包含从 a-z 的小写字母。
 *  p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 \*。
 *  保证每次出现字符 \* 时，前面都匹配到有效的字符

**相同题目：**

*  #### [10. 正则表达式匹配][10.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![05db8bf07ac0abf2e64490b0fe46c5bc.png][]

![897464d6e839ab0e3530d0da1ee85873.png][]

class Solution { 
        public boolean isMatch(String ss, String pp) { 
            int m = ss.length(), n = pp.length();
            char[] s = ss.toCharArray(), p = pp.toCharArray();
            boolean[][] dp = new boolean[m + 1][n + 1];
            //初始化值
            dp[0][0] = true;
            for (int j = 0; j < n; j++) { 
                if (p[j] == '*') { 
                    dp[0][j + 1] = dp[0][j - 1];
                }
            }
            //动态规划
            for (int i = 0; i < m; i++) { 
                for (int j = 0; j < n; j++) { 
                    if (p[j] == '*') { 
                        if (p[j - 1] == '.') { 
                            if (dp[i + 1][j - 1] || dp[i + 1][j] || dp[i][j + 1]) { 
                                dp[i + 1][j + 1] = true;
                            }
                        } else { 
                            if (dp[i + 1][j - 1] || dp[i + 1][j] || (s[i] == p[j - 1] && dp[i][j + 1])) { 
                                dp[i + 1][j + 1] = true;
                            }
                        }
                    } else if (p[j] == '.' || s[i] == p[j]) { 
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                }
            }
            return dp[m][n];
        }
    }

# 剑指 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"]

**示例 1：**

输入：s = "0"
    输出：true

**示例 2：**

输入：s = "e"
    输出：false

**示例 3：**

输入：s = "."
    输出：false

**示例 4：**

输入：s = "    .1  "
    输出：true

**提示：**

*  1 <= s.length <= 20
 *  s 仅含英文字母（大写和小写），数字（0-9），加号 ‘+’ ，减号 ‘-’ ，空格 ’ ’ 或者点 ‘.’ 。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

/** * 1、对字符串为空判断 * 2、对字符串去除空格 * 3、小数点 . 之前不能出现小数点 . 也不能出现 e/E * 4、指数 e/E 之前不能出现指数 e/E ，并且之前出现的是数字 * 5、+、-号出现在第一个字符或者e/E之后 */
    class Solution { 
        public boolean isNumber(String s) { 
            if (s == null || s.length() == 0) return false;
            s = s.trim();
            char[] c = s.toCharArray();
            boolean isNum = false;
            boolean isDot = false;
            boolean isE = false;
            for (int i = 0; i < c.length; i++) { 
                if (c[i] >= '0' && c[i] <= '9') { 
                    isNum = true;
                } else if (c[i] == '.') { 
                    if (isDot || isE) { //isE解决6e6.5
                        return false;
                    }
                    isDot = true;
                } else if (c[i] == 'e' || c[i] == 'E') { 
                    if (isE || !isNum) { 
                        return false;
                    }
                    isE = true;
                    isNum = false;//isNum解决8e
                } else if (c[i] == '+' || c[i] == '-') { 
                    if (i != 0 && (c[i - 1] != 'e' && c[i - 1] != 'E')) { 
                        return false;
                    }
                } else { 
                    return false;
                }
            }
            return isNum;
        }
    }

另外一种使用异常可以判断：

class Solution { 
        public boolean isNumber(String s) { 
            if (s == null || s.endsWith("f") || s.endsWith("F") || s.endsWith("d") || s.endsWith("D")) { 
                return false;
            }
            try { 
                Double.parseDouble(s);
                return true;
            } catch (Exception e) { 
                return false;
            }
        }
    }

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

## 题目介绍 ##

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

**示例：**

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

**提示：**

*  0 <= nums.length <= 50000
 *  1 <= nums\[i\] <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

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

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

## 题目介绍 ##

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

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

**示例：**

给定一个链表: 1->2->3->4->5, 和 k = 2.
    
    返回链表 4->5.

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public ListNode getKthFromEnd(ListNode head, int k) { 
            ListNode q = head;
            ListNode p = head;
            for (int i = 0; i < k; i++) { 
                p = p.next;
            }
            while (p != null) { 
                q = q.next;
                p = p.next;
            }
            return q;
        }
    }

# 剑指 Offer 24. 反转链表 #

## 题目介绍 ##

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

**示例：**

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

**限制：**

*  0 <= 节点个数 <= 5000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public ListNode reverseList(ListNode head) { 
            ListNode dummyHead = new ListNode();
            while (head != null) { 
                ListNode temp = head.next;
                head.next = dummyHead.next;
                dummyHead.next = head;
                head = temp;
            }
            return dummyHead.next;
        }
    }

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

## 题目介绍 ##

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

**示例1：**

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

**限制：**

*  0 <= 链表长度 <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

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

# 剑指 Offer 26. 树的子结构 #

## 题目介绍 ##

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

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

**例如：**

给定的树 A：

3
        / \
       4   5
      / \
     1   2

给定的树 B：

4 
      /
     1

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

**示例 1：**

输入：A = [1,2,3], B = [3,1]
    输出：false

**示例 2：**

输入：A = [3,4,5,1,2], B = [4,1]
    输出：true

**限制：**

*  0 <= 节点个数 <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public boolean isSubStructure(TreeNode A, TreeNode B) { 
            if (A == null || B == null) return false;
            return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
        }
    
        private boolean isSub(TreeNode A, TreeNode B) { 
            if (B == null) return true;
            if (A == null) return false;
            return (A.val == B.val) && isSub(A.left, B.left) && isSub(A.right, B.right);
        }
    }

# 剑指 Offer 27. 二叉树的镜像 #

## 题目介绍 ##

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

**例如输入：**

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

**镜像输出：**

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

**示例 1：**

输入：root = [4,2,7,1,3,6,9]
    输出：[4,7,2,9,6,3,1]

**限制：**

*  0 <= 节点个数 <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

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;
        }
    }

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

**示例 1：**

输入：root = [1,2,2,3,4,4,3]
    输出：true

**示例 2：**

输入：root = [1,2,2,null,3,null,3]
    输出：false

**限制：**

*  0 <= 节点个数 <= 1000

**相同题目：**

*  #### [101. 对称二叉树][101.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![9c67aacf604acf4fd7900ac9cdab5ddc.png][]

class Solution { 
        public boolean isSymmetric(TreeNode root) { 
            return root == null ? true : symmetric(root.left, root.right);
        }
    
        private boolean symmetric(TreeNode L, TreeNode R) { 
            if (L == null && R == null) return true;
            if (L == null || R == null) return false;
            return (L.val == R.val) && symmetric(L.left, R.right) && symmetric(L.right, R.left);
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**示例 2：**

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
    输出：[1,2,3,4,8,12,11,10,9,5,6,7]

**限制：**

*  0 <= matrix.length <= 100
 *  0 <= matrix\[i\].length <= 100

**相同题目：**

*  #### [54. 螺旋矩阵][54.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public int[] spiralOrder(int[][] matrix) { 
            ArrayList<Integer> list = new ArrayList<>();
            if (matrix == null || matrix.length == 0) return new int[0];
            int top = 0, bottom = matrix.length - 1;
            int left = 0, right = matrix[0].length - 1;
            while (top < bottom && left < right) { 
                //开始旋转
                for (int i = left; i < right; i++) list.add(matrix[top][i]);//上层
                for (int i = top; i < bottom; i++) list.add(matrix[i][right]);//右层
                for (int i = right; i > left; i--) list.add(matrix[bottom][i]);//下层
                for (int i = bottom; i > top; i--) list.add(matrix[i][left]);//左层
                //同时收缩
                top++;
                bottom--;
                left++;
                right--;
            }
            if (top == bottom) { 
                //剩下一行
                for (int i = left; i <= right; i++) list.add(matrix[top][i]);//上层
            } else if (left == right) { 
                //剩下一列
                for (int i = top; i <= bottom; i++) list.add(matrix[i][left]);//左层
            }
            int[] res = new int[list.size()];
            for (int i = 0; i < list.size(); i++) { 
                res[i] = list.get(i);
            }
            return res;
        }
    }

# 剑指 Offer 30. 包含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.

**提示：**

*  各函数的调用总次数不超过 20000 次

**相同题目：**

*  #### [155. 最小栈][155.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class MinStack { 
        // 定义最小栈节点
        private class StackNode { 
            int val;
            int min;
            StackNode next;
    
            public StackNode(int val, int min, StackNode next) { 
                this.val = val;
                this.min = min;
                this.next = next;
            }
        }
    
        // 定义最小栈头部
        private StackNode head;
    
        public MinStack() { 
            head = new StackNode(0, Integer.MAX_VALUE, null);
        }
    
        public void push(int val) { 
            int min = Math.min(val, head.min);
            head = new StackNode(val, min, head);
        }
    
        public void pop() { 
            head = head.next;
        }
    
        public int top() { 
            return head.val;
        }
    
        public int min() { 
            return head.min;
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
    输出：true
    解释：我们可以按以下顺序执行：
    push(1), push(2), push(3), push(4), pop() -> 4,
    push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

**示例 2：**

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
    输出：false
    解释：1 不能在 2 之前弹出。

**提示：**

*  0 <= pushed.length == popped.length <= 1000
 *  0 <= pushed\[i\], popped\[i\] < 1000
 *  pushed 是 popped 的排列。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

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

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

## 题目介绍 ##

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

**例如：**

给定二叉树: \[3,9,20,null,null,15,7\],

3
       / \
      9  20
        /  \
       15   7

**返回：**

[3,9,20,15,7]

**提示：**

*  节点总数 <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

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

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

## 题目介绍 ##

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

**例如：**

给定二叉树: \[3,9,20,null,null,15,7\],

3
       / \
      9  20
        /  \
       15   7

返回其层次遍历结果：

[
      [3],
      [9,20],
      [15,7]
    ]

**提示：**

*  节点总数 <= 1000

**相同题目：**

*  #### [102. 二叉树的层序遍历][102.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

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

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

## 题目介绍 ##

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

**例如：**

给定二叉树: \[3,9,20,null,null,15,7\],

3
       / \
      9  20
        /  \
       15   7

返回其层次遍历结果：

[
      [3],
      [20,9],
      [15,7]
    ]

**提示：**

*  节点总数 <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public List<List<Integer>> levelOrder(TreeNode root) { 
            List<List<Integer>> levels = new ArrayList<>();
            if (root == null) return levels;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) { 
                int size = queue.size();
                List<Integer> level = new ArrayList<>();
                for (int i = 0; i < size; i++) { 
                    TreeNode node = queue.poll();
                    level.add(node.val);
                    if (node.left != null) queue.offer(node.left);
                    if (node.right != null) queue.offer(node.right);
                }
                if (levels.size() % 2 == 1) { 
                    Collections.reverse(level);
                }
                levels.add(level);
            }
            return levels;
        }
    }

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

## 题目介绍 ##

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

参考以下这颗二叉搜索树：

5
        / \
       2   6
      / \
     1   3

**示例 1：**

输入: [1,6,3,2,5]
    输出: false

**示例 2：**

输入: [1,3,2,6,5]
    输出: true

**提示：**

*  数组长度 <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public boolean verifyPostorder(int[] postorder) { 
            return helper(postorder, 0, postorder.length - 1);
        }
    
        private boolean helper(int[] postorder, int left, int right) { 
            //终止的条件
            if (left >= right) return true;
            //找到根节点
            int root = postorder[right];
            //判断左子树
            int i = left;
            while (postorder[i] < root) { 
                i++;
            }
            //判断右子树
            for (int j = i; j < right; j++) { 
                if (postorder[j] < root) { 
                    return false;
                }
            }
            //递归判断
            return helper(postorder, left, i - 1) && helper(postorder, i, right - 1);
        }
    }

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

## 题目介绍 ##

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

**示例：**

给定如下二叉树，以及目标和 target = 22，

5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

**返回：**

[
       [5,4,11,2],
       [5,8,4,5]
    ]

**提示：**

*  节点总数 <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

import java.util.ArrayList;
    import java.util.List;
    
    class Solution { 
        private List<List<Integer>> result = new ArrayList<>();
        private List<Integer> list = new ArrayList<>();
    
        public List<List<Integer>> pathSum(TreeNode root, int target) { 
            dfs(root, target);
            return result;
        }
    
        private void dfs(TreeNode node, int target) { 
            //无效节点
            if (node == null) return;
            //添加节点
            list.add(node.val);
            target -= node.val;
            //叶子节点
            if (node.left == null && node.right == null && target == 0) { 
                result.add(new ArrayList<>(list));
            }
            //深度优先
            dfs(node.left, target);
            dfs(node.right, target);
            //移除节点
            list.remove(list.size() - 1);
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

![cdd80367654dc138d5323cea09461f30.png][]

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
    输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

**示例 2：**

![4ce3e916a187d9a7af8c645c102a3c9d.png][]

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

**示例 3：**

![b6114cfb00d7e9c96d13d601e3c55a90.png][]

输入：head = [[3,null],[3,0],[3,null]]
    输出：[[3,null],[3,0],[3,null]]

**示例 4：**

输入：head = []
    输出：[]
    解释：给定的链表为空（空指针），因此返回 null。

**提示：**

*  \-10000 <= Node.val <= 10000
 *  Node.random 为空（null）或指向链表中的节点。
 *  节点数目不超过 1000 。

**相同题目：**

*  #### [138. 复制带随机指针的链表][138.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

我们遍历整个链表，在遍历的过程中，以 **旧节点** 为 **键** ，**新节点** 为 **值** 储存在哈希表中。

然后再次遍历整个链表，通过 **旧节点** 拿到 **新节点** ，然后为 **新节点** 进行 `next` 和 `random` 赋值即可。

class Solution { 
        public Node copyRandomList(Node head) { 
            if (head == null) return null;
            HashMap<Node, Node> hashMap = new HashMap<>();
            Node temp = head;
            while (temp != null) { 
                hashMap.put(temp, new Node(temp.val));
                temp = temp.next;
            }
            temp = head;
            while (temp != null) { 
                hashMap.get(temp).next = hashMap.get(temp.next);
                hashMap.get(temp).random = hashMap.get(temp.random);
                temp = temp.next;
            }
            return hashMap.get(head);
        }
    }

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

## 题目介绍 ##

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

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

![40f9b898cd35d5e536105609421e32c4.png][]

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

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

![83c1ad6713fd0f156a13cc0a5558c0d8.png][]

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

**相同题目：**

*  #### [426. 将二叉搜索树转化为排序的双向链表][426.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![3cefa60c59c5f6f14232b90efb4b0a4a.png][]

![68c83a78d2e7ab00fa9bba1a4f52f607.png][]

![21e658a4c3542f92708708874a6f2fbb.png][]

![175eb3c650feac9e6a94d30dfc0cba39.png][]

![02517f7ec34ec62f71a94cc401e4e269.png][]

class Solution { 
        private Node head, pre;
    
        public Node treeToDoublyList(Node root) { 
            if (root == null) return null;
            dfs(root);
            head.left = pre;
            pre.right = head;
            return head;
        }
    
        private void dfs(Node cur) { 
            if (cur == null) return;
            dfs(cur.left);
            if (pre == null) { 
                head = cur;
                pre = cur;
            } else { 
                pre.right = cur;
                cur.left = pre;
                pre = cur;
            }
            dfs(cur.right);
        }
    }

# 剑指 Offer 37. 序列化二叉树 #

## 题目介绍 ##

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

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

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

**示例：**

![7ed5c6427508f35d5430f85c48d2045a.png][]

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

相同题目：

*  #### [297. 二叉树的序列化与反序列化][297.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Codec { 
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) { 
            StringBuilder sb = new StringBuilder();
            preorderTraversal(root, sb);
            return sb.toString();
        }
    
        private void preorderTraversal(TreeNode node, StringBuilder sb) { 
            if (node == null) { 
                sb.append("null").append(",");
            } else { 
                sb.append(node.val).append(",");
                preorderTraversal(node.left, sb);
                preorderTraversal(node.right, sb);
            }
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) { 
            if (data == null || data.length() == 0) return null;
            Queue<String> queue = new LinkedList<>();
            Collections.addAll(queue, data.split(","));
            return preorderBuilder(queue);
        }
    
        private TreeNode preorderBuilder(Queue<String> queue) { 
            if (queue.isEmpty()) return null;
            String current = queue.poll();
            if (current.equals("null")) return null;
            TreeNode node = new TreeNode(Integer.parseInt(current));
            node.left = preorderBuilder(queue);
            node.right = preorderBuilder(queue);
            return node;
        }
    }

# 剑指 Offer 38. 字符串的排列 #

## 题目介绍 ##

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

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

**示例：**

输入：s = "abc"
    输出：["abc","acb","bac","bca","cab","cba"]

**限制：**

*  1 <= s 的长度 <= 8

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        private List<String> list = new ArrayList<>();
    
        public String[] permutation(String s) { 
            if (s == null || s.length() == 0) return new String[0];
            char[] c = s.toCharArray();
            dfs(c, 0);
            String[] result = new String[list.size()];
            for (int i = 0; i < list.size(); i++) { 
                result[i] = list.get(i);
            }
            return result;
        }
    
        private void dfs(char[] c, int idx) { 
            //终止条件
            if (idx == c.length) { 
                list.add(new String(c));
                return;
            }
            //深度优先
            for (int i = idx; i < c.length; i++) { 
                //去重核心
                if (isRepeat(c, idx, i)) continue;
                swap(c, idx, i);
                dfs(c, idx + 1);
                swap(c, idx, i);
            }
        }
    
        private boolean isRepeat(char[] c, int idx, int i) { 
            for (int j = idx; j < i; j++) { 
                if (c[j] == c[i]) { 
                    return true;
                }
            }
            return false;
        }
    
        private void swap(char[] c, int idx, int i) { 
            char temp = c[idx];
            c[idx] = c[i];
            c[i] = temp;
        }
    }

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

## 题目介绍 ##

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

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

**示例 1：**

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

**限制：**

*  1 <= 数组长度 <= 50000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![be9101c30793f516115cdbf74252ef9d.png][]

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

# 剑指 Offer 40. 最小的k个数 #

## 题目介绍 ##

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

**示例 1：**

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

**示例 2：**

输入：arr = [0,1,2,1], k = 1
    输出：[0]

**限制：**

*  0 <= k <= arr.length <= 10000
 *  0 <= arr\[i\] <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public int[] getLeastNumbers(int[] arr, int k) { 
            int[] res = new int[k];
            if (arr == null || arr.length == 0) return res;
            Arrays.sort(arr);
            for (int i = 0; i < k; i++) { 
                res[i] = arr[i];
            }
            return res;
        }
    }

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

## 题目介绍 ##

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

**例如：**

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

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

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

**示例 1：**

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

**示例 2：**

输入：
    ["MedianFinder","addNum","findMedian","addNum","findMedian"]
    [[],[2],[],[3],[]]
    输出：[null,null,2.00000,null,2.50000]

**限制：**

*  最多会对 addNum、findMedian 进行 50000 次调用。

**相同题目：**

*  #### [295. 数据流的中位数][295.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class MedianFinder { 
        ArrayList<Integer> list;
    
        public MedianFinder() { 
            list = new ArrayList<>();
        }
    
        public void addNum(int num) { 
            list.add(num);
            Collections.sort(list);
        }
    
        public double findMedian() { 
            int mid = list.size() / 2;
            if (list.size() % 2 == 0) { 
                return 1.0 * (list.get(mid - 1) + list.get(mid)) / 2;
            } else { 
                return 1.0 * list.get(mid);
            }
        }
    }

![6c56ea72df2deda5c199d0f6eebf77ee.png][]

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

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

## 题目介绍 ##

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

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

**示例1：**

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

**提示：**

*  1 <= arr.length <= 105
 *  \-100 <= arr\[i\] <= 100

**相同题目：**

*  #### [53. 最大子序和][53.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public int maxSubArray(int[] nums) { 
            int max = Integer.MIN_VALUE;
            int sum = 0;
            for (int num : nums) { 
                if (sum + num > num) { 
                    sum += num;
                } else { 
                    sum = num;
                }
                max = Math.max(max, sum);
            }
            return max;
        }
    }

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

## 题目介绍 ##

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

**示例 1：**

输入：n = 12
    输出：5

**示例 2：**

输入：n = 13
    输出：6

**限制：**

*  1 <= n < 231

**相同题目：**

*  #### [233. 数字 1 的个数][233. _ 1] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![af6cea16531f3588136054b2f911ad48.png][]

class Solution { 
        public int countDigitOne(int n) { 
            int count = 0;
            long a, b, cur, base = 1;
            while (base <= n) { 
                b = n % base;
                a = n / base;
                cur = a % 10;
                a /= 10;
                if (cur > 1) count += (a + 1) * base;
                else if (cur == 1) count += a * base + b + 1;
                else count += a * base;
                base *= 10;
            }
            return count;
        }
    }

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

## 题目介绍 ##

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

**示例 1：**

输入：n = 3
    输出：3

**示例 2：**

输入：n = 11
    输出：0

**限制：**

*  0 <= n < 231

**相同题目：**

*  #### [400. 第 N 位数字][400. _ N] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![1917b79b67563bbdd14a4a0b0bc8d928.png][]

![5732df37d1d50bfd7f0c5d1d9066b136.png][]

![ce28b0c4d768e4b2add246ea53b806a6.png][]

![20644a92b56bdab925033f49e8012591.png][]

![3a528d0810edd88eba1d2233e6ebd5bb.png][]

![6f6736937d007d867e8599e83b7ce7a6.png][]

![efb7e896d73c7aa3275e111fe6bf85ca.png][]

![b6860383a957b7f2386830bf352aa24c.png][]

![cfac3a51bcaf531d739495469c6b5536.png][]

class Solution { 
        public int findNthDigit(int n) { 
            int digit = 1;
            long start = 1, count = 9;
            while (n > count) { 
                n -= count;
                digit += 1;
                start *= 10;
                count = 9 * start * digit;
            }
            long num = start + (n - 1) / digit;
            return Long.toString(num).charAt((n - 1) % digit) - '0';
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

输入: [10,2]
    输出: "102"

**示例 2：**

输入: [3,30,34,5,9]
    输出: "3033459"

**提示：**

*  0 < nums.length <= 100

**说明：**

*  输出结果可能非常大，所以你需要返回一个字符串而不是整数
 *  拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![31177609cc362ddf324a30679406861e.png][]

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 str : strs) { 
                sb.append(str);
            }
            return sb.toString();
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**提示：**

*  0 <= num < 231

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![15647cade71f16441cb0d43e25387ff1.png][]

class Solution { 
        public int translateNum(int num) { 
            String s = String.valueOf(num);
            char[] c = s.toCharArray();
            int[] dp = new int[c.length];
            dp[0] = 1;
            for (int i = 1; i < c.length; i++) { 
                if (c[i - 1] == '1' || (c[i - 1] == '2' && c[i] <= '5')) { 
                    if (i == 1) { 
                        dp[i] = 2;
                    } else { 
                        dp[i] = dp[i - 2] + dp[i - 1];
                    }
                } else { 
                    dp[i] = dp[i - 1];
                }
            }
            return dp[dp.length - 1];
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**提示：**

*  0 < grid.length <= 200
 *  0 < grid\[0\].length <= 200

**相似题目：**

*  #### [64. 最小路径和][64.] ####
 *  #### [62. 不同路径][62.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

从棋盘的左上角开始拿格子里的礼物，并每次 **向右** 或者 **向下** 移动一格、直到到达棋盘的右下角。

根据题目说明，易得某单元格只可能从上边单元格或左边单元格到达。

![c605992c817a45901e5e9383c3988dde.png][]

设 `f(i, j)` 为从棋盘左上角走至单元格 `(i ,j)` 的礼物最大累计价值，易得到以下递推关系：`f(i,j)` 等于 `f(i,j-1)` 和 `f(i-1,j)` 中的较大值加上当前单元格礼物价值 `grid(i,j)`。

![9f6d843a389b5a2bc0c48348e0c7b141.png][]

因此，可用动态规划解决此问题，以上公式便为转移方程。

![19c3e4e95a280e03605f60d883697d6c.png][]

由于 `dp[i][j]` 只与 `dp[i-1][j]` , `dp[i][j-1]`, `grid[i][j]` 有关系，因此可以将原矩阵 `grid` 用作 `dp` 矩阵，即直接在 `grid` 上修改即可。应用此方法可省去 `dp` 矩阵使用的额外空间，因此空间复杂度从 `O(MN)` 降至 `O(1)` 。

class Solution { 
        public int maxValue(int[][] grid) { 
            // 对临界值的判断
            int rows = grid.length;
            int cols = grid[0].length;
            if (grid == null || rows == 0 || cols == 0) return 0;
            // 初始化第一列
            for (int i = 1; i < rows; i++) { 
                grid[i][0] = grid[i - 1][0] + grid[i][0];
            }
            // 初始化第一行
            for (int i = 1; i < cols; i++) { 
                grid[0][i] = grid[0][i - 1] + grid[0][i];
            }
            // 动态规划核心
            for (int i = 1; i < rows; i++) { 
                for (int j = 1; j < cols; j++) { 
                    grid[i][j] = Math.max(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
                }
            }
            // 返回最后元素
            return grid[rows - 1][cols - 1];
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**示例 2：**

输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

**示例 3：**

输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
             请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

**提示：**

*  s.length <= 40000

**相同题目：**

*  #### [3. 无重复字符的最长子串][3.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

解法一：暴力枚举

class Solution { 
        public int lengthOfLongestSubstring(String s) { 
            if (s == null || s.length() == 0) return 0;
            HashSet<Character> hashSet = new HashSet<>();
            char[] c = s.toCharArray();
            int left = 0, right = 0, max = Integer.MIN_VALUE, n = c.length;
            while (left < n && right < n) { 
                right = left;
                while (right < n && !hashSet.contains(c[right])) { 
                    hashSet.add(c[right]);
                    right++;
                }
                max = Math.max(max, hashSet.size());
                hashSet.clear();
                left++;
            }
            return max;
        }
    }

解法二：滑动窗口

class Solution { 
        public int lengthOfLongestSubstring(String s) { 
            if (s == null || s.length() == 0) return 0;
            HashSet<Character> hashSet = new HashSet<>();
            char[] c = s.toCharArray();
            int left = 0, right = 0, max = Integer.MIN_VALUE, n = c.length;
            while (left < n && right < n) { 
                //窗口右移
                if (left != 0) { 
                    hashSet.remove(c[left - 1]);
                }
                //指针右移
                while (right < n && !hashSet.contains(c[right])) { 
                    hashSet.add(c[right]);
                    right++;
                }
                //判断大小
                max = Math.max(max, hashSet.size());
                left++;
            }
            return max;
        }
    }

# 剑指 Offer 49. 丑数 #

## 题目介绍 ##

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

**示例：**

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

**说明:**

*  1 是丑数。
 *  n 不超过1690。

**相同题目：**

*  #### [264. 丑数 II][264. _ II] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/chou-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public int nthUglyNumber(int n) { 
            int[] dp = new int[n];
            dp[0] = 1;
            int t2 = 0, t3 = 0, t5 = 0;
            for (int i = 1; i < n; i++) { 
                int next2 = dp[t2] * 2, next3 = dp[t3] * 3, next5 = dp[t5] * 5;
                dp[i] = Math.min(Math.min(next2, next3), next5);
                if (next2 == dp[i]) t2++;
                if (next3 == dp[i]) t3++;
                if (next5 == dp[i]) t5++;
            }
            return dp[n - 1];
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

输入：s = "abaccdeff"
    输出：'b'

**示例 2：**

输入：s = "" 
    输出：' '

**限制：**

*  0 <= s 的长度 <= 50000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

解法一：

class Solution { 
        public char firstUniqChar(String s) { 
            LinkedHashMap<Character, Integer> map = new LinkedHashMap<>(26);
            char[] chars = s.toCharArray();
            for (char c : chars) { 
                Integer count = map.get(c);
                if (count == null) { 
                    map.put(c, 1);
                } else { 
                    map.put(c, ++count);
                }
            }
            for (char c : chars) { 
                Integer count = map.get(c);
                if (count == 1) { 
                    return c;
                }
            }
            return ' ';
        }
    }

解法二：

class Solution { 
        public char firstUniqChar(String s) { 
            int[] count = new int[128];
            char[] chars = s.toCharArray();
            for (char c : chars) { 
                count[c]++;
            }
            ArrayList<Character> list = new ArrayList<>();
            for (int i = 0; i < count.length; i++) { 
                if (count[i] == 1) { 
                    list.add((char) i);
                }
            }
            for (char c : chars) { 
                if (list.contains(c)) { 
                    return c;
                }
            }
            return ' ';
        }
    }

解法三：

class Solution { 
        public char firstUniqChar(String s) { 
            int min = Integer.MAX_VALUE;
            for (char i = 'a'; i <= 'z'; i++) { 
                int index = s.indexOf(i);
                if (index != -1 && s.lastIndexOf(i) == index) { 
                    min = Math.min(min, index);
                }
            }
            return min == Integer.MAX_VALUE ? ' ' : s.charAt(min);
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**限制：**

*  0 <= 数组长度 <= 50000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

解法一：暴力枚举，简单明了，但是会超时

class Solution { 
        public int reversePairs(int[] nums) { 
            int count = 0;
            for (int i = 0; i < nums.length; i++) { 
                for (int j = i + 1; j < nums.length; j++) { 
                    if (nums[i] > nums[j]) { 
                        count++;
                    }
                }
            }
            return count;
        }
    }

解法二：归并排序，归并之时，我们会统计

![9148ff1afafcb8eb4c58fb720680e873.png][]

class Solution { 
        public int reversePairs(int[] nums) { 
            int[] temp = new int[nums.length];
            return mergeSort(nums, 0, nums.length - 1, temp);
        }
    
        private int mergeSort(int[] nums, int L, int R, int[] temp) { 
            //终止
            if (L >= R) return 0;
            //先分
            int left = L, middle = (L + R) / 2, right = middle + 1, idx = L;
            int count = mergeSort(nums, L, middle, temp) + mergeSort(nums, right, R, temp);
            //再合
            while (left <= middle && right <= R) { 
                if (nums[left] <= nums[right]) { 
                    temp[idx++] = nums[left++];
                } else { 
                    count += middle - left + 1;
                    temp[idx++] = nums[right++];
                }
            }
            while (left <= middle) temp[idx++] = nums[left++];
            while (right <= R) temp[idx++] = nums[right++];
            for (int i = L; i <= R; i++) { 
                nums[i] = temp[i];
            }
            return count;
        }
    }

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

## 题目介绍 ##

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

如下面的两个链表：

![608561a5aa13a89324655a3e10c2bb79.png][]

在节点 c1 开始相交。

**示例 1：**

![456a9294f3e35314a0b91b2de20d15dc.png][]

输入：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 个节点。

**示例 2：**

![54874887f68b3bdca93a555cf0610299.png][]

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

**示例 3：**

![944ba111c3b9680fd2add071fe14e165.png][]

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
    输出：null
    输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
    解释：这两个链表不相交，因此返回 null。

**注意：**

*  如果两个链表没有交点，返回 null。
 *  在返回结果后，两个链表仍须保持原有的结构。
 *  可假定整个链表结构中没有循环。
 *  程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

**相同题目：**

*  #### [160. 相交链表][160.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![42fab0317e87fd4e667d349639bbb1a0.png][]

我们拿到这道题，会感觉有点困难，有点无从下手，其实我们不妨换个角度来看，如下图：

![b7b50c17bcaab25584099091144b6813.png][]

我们只需要把A链表的长度和B链表的长度补齐，然后从左向右依次判断下图第一行中的节点和下图第二行中的节点地址是否相等即可。

![25e7341bd60f5204859959138df5e8d6.png][]

就拿上图补全后的第一行来说，一旦扫描完毕A链表发现没有相交的节点，当扫描到链表尾部，发现 `curA == null` ，他会立刻开始从B链表开始向后搜索，直到找到一个 **地址值** 相等的节点，那就意味着找到了一个相交的节点，即使B链表搜索了一遍也没找到，那也没关系，由于补全后上图上下两行链表的长度是一样的，到最后都会扫描到 null，由于 `null == null` 是相等的，循环自然会退出，并且此时返回 curA 也就是 null，也是正确的。

public class Solution { 
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
            if (headA == null || headB == null) return null;
            ListNode curA = headA;
            ListNode curB = headB;
            while (curA != curB) { // 注意：这里判断的是地址值
                curA = (curA == null) ? headB : curA.next;
                curB = (curB == null) ? headA : curB.next;
            }
            return curA;
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**示例 2：**

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

**提示：**

*  0 <= nums.length <= 105
 *  \-109 <= nums\[i\] <= 109
 *  nums 是一个非递减数组
 *  \-109 <= target <= 109

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

本题可转化为：使用二分法分别找到 左边界 left 和 右边界 right ，易得数字 target 的数量为 right - left - 1。

![c03e8404af4c915be42aad905364f8d5.png][]

class Solution { 
        public int search(int[] nums, int target) { 
            int i, j, k, left, right;
    
            // 搜索右边界 right
            i = 0; j = nums.length - 1;
            while (i <= j) { 
                k = (i + j) / 2;
                if (nums[k] <= target) i = k + 1;
                else j = k - 1;
            }
            right = i;
    
            // 搜索左边界 left
            i = 0; j = nums.length - 1;
            while (i <= j) { 
                k = (i + j) / 2;
                if (nums[k] < target) i = k + 1;
                else j = k - 1;
            }
            left = j;
    
            return right - left - 1;
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**示例 2：**

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

**限制：**

*  1 <= 数组长度 <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![617c3d5875d3a4cd8b4dabf5f19bdd5b.png][]

class Solution { 
        public int missingNumber(int[] nums) { 
            int l = 0, r = nums.length - 1;
            while (l <= r) { 
                int mid = (l + r) / 2;
                if (nums[mid] == mid) l = mid + 1;
                else r = mid - 1;
            }
            return l;
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

输入: root = [3,1,4,null,2], k = 1
       3
      / \
     1   4
      \
       2
    输出: 4

**示例 2：**

输入: root = [5,3,6,2,4,null,null,1], k = 3
           5
          / \
         3   6
        / \
       2   4
      /
     1
    输出: 4

**限制：**

*  1 ≤ k ≤ 二叉搜索树元素个数

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

解法一：最大堆+弹出

class Solution { 
        private PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
    
        public int kthLargest(TreeNode root, int k) { 
            preorder(root);
            int kth = 0;
            for (int i = 0; i < k; i++) { 
                kth = queue.poll();
            }
            return kth;
        }
    
        public void preorder(TreeNode root) { 
            if (root != null) { 
                queue.offer(root.val);
                preorder(root.left);
                preorder(root.right);
            }
        }
    }

解法二：倒着中序遍历

![3c263d62a5531feb60bd3ee1ba16265a.png][]

class Solution { 
        private int kth, ans;
    
        public int kthLargest(TreeNode root, int k) { 
            kth = k;
            preorder(root);
            return ans;
        }
    
        public void preorder(TreeNode root) { 
            if (root != null && kth != 0) { 
                preorder(root.right);
                if (--kth == 0) ans = root.val;
                preorder(root.left);
            }
        }
    }

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

## 题目介绍 ##

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

**例如：**

给定二叉树 \[3,9,20,null,null,15,7\]，

3
       / \
      9  20
        /  \
       15   7

返回它的最大深度 3 。

**提示：**

*  节点总数 <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public int maxDepth(TreeNode root) { 
                if (root == null) return 0;
                // 计算x节点左子树的最大深度
                int left = maxDepth(root.left);
                // 计算x节点右子树的最大深度
                int right = maxDepth(root.right);
                // 计算x节点右子树的最大深度
                return Math.max(left + 1, right + 1);
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

给定二叉树 \[3,9,20,null,null,15,7\]

3
       / \
      9  20
        /  \
       15   7

返回 true 。

**示例 2：**

给定二叉树 \[1,2,2,3,3,null,null,4,4\]

1
          / \
         2   2
        / \
       3   3
      / \
     4   4

返回 false 。

**限制：**

*  0 <= 树的结点个数 <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

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

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

## 题目介绍 ##

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

**示例 1：**

输入：nums = [4,1,4,6]
    输出：[1,6] 或 [6,1]

**示例 2：**

输入：nums = [1,2,10,4,1,4,3,3]
    输出：[2,10] 或 [10,2]

**限制：**

*  2 <= nums.length <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public int[] singleNumbers(int[] nums) { 
            int res = 0;
            for (int num : nums) { 
                res ^= num;
            }
            int div = 1;
            while ((div & res) == 0) { 
                div <<= 1;
            }
            int a = 0, b = 0;
            for (int num : nums) { 
                if ((div & num) != 0) { 
                    a ^= num;
                } else { 
                    b ^= num;
                }
            }
            return new int[]{ a, b};
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

输入：nums = [3,4,3,3]
    输出：4

**示例 2：**

输入：nums = [9,1,7,9,7,9,7]
    输出：1

**限制：**

*  1 <= nums.length <= 10000
 *  1 <= nums\[i\] < 231

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![997d2fa95795acbe74a28c6fb1dee147.png][]

**通俗版：**

class Solution { 
        public int singleNumber(int[] nums) { 
            int[] bitCounts = new int[32];
            //累计每一位
            for (int i = 0; i < nums.length; i++) { 
                for (int j = 0; j < 32; j++) { 
                    bitCounts[j] += nums[i] & 1;
                    nums[i] >>= 1;
                }
            }
            //取余每一位
            for (int i = 0; i < 32; i++) { 
                bitCounts[i] %= 3;
            }
            //转为十进制
            int res = 0;
            for (int i = 0; i < 32; i++) { 
                res = res * 2 + bitCounts[31 - i];
            }
            return res;
        }
    }

**精简版：**

class Solution { 
        public int singleNumber(int[] nums) { 
            int[] bitCounts = new int[32];
            //累计每一位
            for (int i = 0; i < nums.length; i++) { 
                for (int j = 0; j < 32; j++) { 
                    bitCounts[j] += nums[i] & 1;
                    nums[i] >>= 1;
                }
            }
            //取余每一位，转为十进制
            int res = 0;
            for (int i = 0; i < 32; i++) { 
                res <<= 1;
                res |= bitCounts[31 - i] % 3;
            }
            return res;
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**示例 2：**

输入：nums = \[10,26,30,31,47,60\], target = 40  
输出：\[10,30\] 或者 \[30,10\]

**限制：**

*  1 <= nums.length <= 105
 *  1 <= nums\[i\] <= 106

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

使用哈希表，可以将寻找 `target - x` 的时间复杂度降低到从 `O(N)` 降低到 `O(1)`。

我们创建一个哈希表，对于每一个 `x`，我们首先查询哈希表中是否存在 `target - x`，然后将 `x` 插入到哈希表中，即可保证不会让 `x` 和自己匹配。

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            HashMap<Integer, Integer> hashMap = new HashMap<>();
            for (int i = 0; i < nums.length; i++) { 
                if (hashMap.containsKey(target - nums[i])) { 
                    return new int[]{ hashMap.get(target - nums[i]), i};
                }
                hashMap.put(nums[i], i);
            }
            return new int[0];
        }
    }

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

## 题目介绍 ##

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

**示例 1：**

输入：target = 9
    输出：[[2,3,4],[4,5]]

**示例 2：**

输入：target = 15
    输出：[[1,2,3,4,5],[4,5,6],[7,8]]

**限制：**

*  1 <= target <= 105

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![6d8cbdfb1737f2209ab51e705f56a3f7.png][]

class Solution { 
        public int[][] findContinuousSequence(int target) { 
            ArrayList<int[]> result = new ArrayList<>();
            for (int L = 1, R = L + 1; L < R; ) { 
                int sum = (L + R) * (R - L + 1) / 2;
                if (sum == target) { 
                    int[] sub = new int[R - L + 1];
                    for (int i = L; i <= R; i++) { 
                        sub[i - L] = i;
                    }
                    result.add(sub);
                    L++;
                } else if (sum > target) { 
                    L++;
                } else if (sum < target) { 
                    R++;
                }
            }
            return result.toArray(new int[result.size()][]);
        }
    }

# 剑指 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"
    解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

**说明：**

*  无空格字符构成一个单词。
 *  输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 *  如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

**相同题目：**

*  #### [151. 翻转字符串里的单词][151.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public String reverseWords(String s) { 
            // 除去开头和末尾的空白字符
            s = s.trim();
            // 正则匹配连续的空白字符作为分隔符分割
            List<String> wordList = Arrays.asList(s.split("\\s+"));
            Collections.reverse(wordList);
            return String.join(" ", wordList);
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

输入: s = "abcdefg", k = 2
    输出: "cdefgab"

**示例 2：**

输入: s = "lrloseumgh", k = 6
    输出: "umghlrlose"

**限制：**

*  1 <= k < s.length <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public String reverseLeftWords(String s, int n) { 
            //abcdefgabcdefg
            String str = s + s;
            char[] ch = str.toCharArray();
            n = n % s.length();
            return new String(ch, n, s.length());
        }
    }

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

## 题目介绍 ##

给定一个数组 `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

**提示：**

*  你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

**相同题目：**

*  #### [239. 滑动窗口最大值][239.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

题目中提到了滑动窗口，我们先以示例为例看下什么是滑动窗口？

在示例中，我们从数组中第一个元素开始遍历，由于窗口的大小是3，因此当遍历到第三个元素时，窗口就形成了。

![0494429509d0efbd283d9e5be2cd5825.gif][]

之后，继续遍历元素时，为了保持窗口的大小为3，左侧元素就需要从窗口中剔除。这样使得窗口一直在向右移动，直到考察到最后一个元素结束，这就是所谓的滑动窗口。

![bf2869b6303efcaa58c7728cfa208d78.gif][]

在上述滑动窗口形成及移动的过程中，我们注意到元素是从窗口的右侧进入的，然后由于窗口大小是固定的，因此多余的元素是从窗口左侧移除的。 一端进入，另一端移除，这不就是队列的性质吗？所以，该题目可以借助队列来求解。

题目要求是返回每个窗口中的最大值。那么这个如何解决呢？

我们以数组\{5, 3, 4, 1\}，窗口大小k=3来进行说明。这里我们规定窗口右侧边界为right，左侧边界为left，其值为元素下标。

然后，开始遍历nums = \{5, 3, 4, 1\}。当right指向第一个元素5时，此时队列为空，将第一个元素5入队。

![4b005c9422b6484d7221bfae46e1d107.gif][]

继续考察第二个元素3，此时3小于队列末尾的元素5，因此元素3入队，以便看其是否是下一个窗口的最大值。这时队列中元素从队首到队尾是递减的。

![a20abba0c72a84ed31d7c8513a51f789.gif][]

接着考察\{5, 3, 4, 1\}中的第三个元素4，此时4大于队尾元素3，这表明元素3不可能是窗口「5 3 4」中的最大元素，因此需要将其从队列移除。但队首有元素5存在，因此不能将其从队首移除，那怎么办呢？我们可以将其从队尾移除。

**对于这种一端既可以有元素入队，又有元素出队的队列，称之为双向队列。**

队尾元素3出队之后，由于新的队尾元素5大于当前考察元素4，因此元素4入队，以便看其是否是下一个窗口的最大值。

![1882303c455c24ff434db17a3b0699c6.gif][]

当元素4入队之后，我们发现这时，队列中元素从队首到队尾依旧是递减的。

**我们把从队首到队尾单调递减或递增的队列称之为单调队列。**

接着，考察第四个元素1，此时元素1小于队尾元素4，因此元素1入队。

![ac5dfb26586064ea31a7c37debb6b1fc.gif][]

但这时，窗口内有4个元素，而我们这里规定窗口大小是3，因此，需要缩小窗口左边界left。在缩小窗口左边界left后，意味着元素5已经不再窗口内了，因此，队首元素5需要出队。也就是说，当队首元素在原数组中的下标小于窗口左边界时，队首元素就需要移除队列。

![0707cfc47c970f34d2a82f163cbb567e.gif][]

至此，该题目的求解思路就清晰了，具体如下：

*  遍历给定数组中的元素，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。直到，队列为空或当前考察元素小于新的队尾元素；
 *  当队首元素的下标小于滑动窗口左侧边界left时，表示队首元素已经不再滑动窗口内，因此将其从队首移除。
 *  由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时，意味着窗口形成。此时，队首元素就是该窗口内的最大值。

需要说明的一点是，在上述演示中，队列存储的是元素值。而在具体代码实现中，为了方便计算，队列中存储的是元素的下标。

class Solution { 
        public int[] maxSlidingWindow(int[] nums, int k) { 
            if (nums == null || nums.length == 0) return new int[0];
            // 定义双端队列，用于存储最大值的下标，注意：不是数组元素
            Deque<Integer> deque = new LinkedList<>();
            // 窗口个数，如何确定？nums.length - (k - 1) = nums.length - k + 1
            int[] ans = new int[nums.length - k + 1];
            // 遍历数组中元素，right表示滑动窗口右边界
            for (int right = 0; right < nums.length; right++) { 
                // 如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
                // 直到，队列为空或当前考察元素小于新的队尾元素
                while (!deque.isEmpty() && nums[right] >= nums[deque.getLast()]) { 
                    deque.removeLast();
                }
                // 存储元素下标
                deque.addLast(right);
                // 计算窗口左侧边界
                int left = right - k + 1;
                // 当队首元素的下标小于滑动窗口左侧边界left时
                // 表示队首元素已经不再滑动窗口内，因此将其从队首移除
                if (deque.getFirst() < left) { 
                    deque.removeFirst();
                }
                // 由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时
                // 意味着窗口形成。此时，队首元素就是该窗口内的最大值
                if (right + 1 >= k) { 
                    ans[left] = nums[deque.peekFirst()];
                }
            }
            return ans;
        }
    }

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

## 题目介绍 ##

请定义一个队列并实现函数 `max_value` 得到队列里的最大值，要求函数`max_value`、`push_back` 和 `pop_front` 的均摊时间复杂度都是O(1)。若队列为空，`pop_front` 和 `max_value` 需要返回 `-1` 。

**示例 1：**

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

**示例 2：**

输入: 
    ["MaxQueue","pop_front","max_value"]
    [[],[],[]]
    输出: [null,-1,-1]

**限制：**

*  1 <= push\_back,pop\_front,max\_value的总操作数 <= 10000
 *  1 <= value <= 105

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

直接实现一个普通的队列，查询最大值时遍历计算。

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

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

## 题目介绍 ##

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

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

**示例 1：**

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

**示例 2：**

输入: 2
    输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

**限制：**

*  1 <= n <= 11

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![d02f9bb1a643946ce462f8c27f8a67c7.png][]

![d5a4ee438f74e045589178bdc0ba229c.png][]

![cde6f27d6fae788f68f6ee24265fa219.png][]

![0e41ef8b6462a013e610f12717880121.png][]

![71c85f9500653c083fe6c5d4bb3c640c.png][]

![89337efcd910affc03209ad7e4398f9a.png][]

![1442f92e7527ef58c912354888e3bb42.png][]

![e79671a501fd994040023efdfdf76be1.png][]

![f06c5df0b8bade4e4d51135d0ca04b3b.png][]

![82435c873a617b21898344c580c86681.png][]

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;
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**示例 2：**

输入: [0,0,1,2,5]
    输出: True

**限制：**

*  数组长度为 5
 *  数组的数取值为 \[0, 13\] .

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![eb0cb04cb7d8ba6d765fe184095181af.png][]

![e1dea5668aa32506deee22e756e5cb06.png][]

class Solution { 
        public boolean isStraight(int[] nums) { 
            HashSet<Integer> repeat = new HashSet<>();
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for (int num : nums) { 
                if (num == 0) continue;//跳过大小王
                if (repeat.contains(num)) return false;//提前跳过
                max = Math.max(max, num);
                min = Math.min(min, num);
                repeat.add(num);
            }
            return max - min < 5;
        }
    }

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

## 题目介绍 ##

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

**示例 1：**

输入: n = 5, m = 3
    输出: 3

**示例 2：**

输入: n = 10, m = 17
    输出: 2

**限制：**

*  1 <= n <= 105
 *  1 <= m <= 106

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![4055081fcf4df8f09b814c366f54f97b.png][]

![c0e81c14238e04c48992473523486f7f.png][]

class Solution { 
        public int lastRemaining(int n, int m) { 
            int index = 0;
            // 最后一轮剩下2个人，所以从2开始反推
            for (int i = 2; i <= n; i++) { 
                index = (index + m) % i;
            }
            return index;
        }
    }

# 剑指 Offer 63. 股票的最大利润 #

## 题目介绍 ##

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

**示例 1：**

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

**示例 2：**

输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

**限制：**

*  0 <= 数组长度 <= 105

**相同题目：**

*  #### [121. 买卖股票的最佳时机][121.] ####

**相似题目：**

*  #### [122. 买卖股票的最佳时机 II][122. _ II] ####
 *  #### [123. 买卖股票的最佳时机 III][123. _ III] ####
 *  #### [188. 买卖股票的最佳时机 IV][188. _ IV] ####
 *  #### [714. 买卖股票的最佳时机含手续费][714.] ####
 *  #### [309. 最佳买卖股票时机含冷冻期][309.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

想通这一招，搞定所有股票买卖问题，包括买卖股票的最佳时机（1,2,3,4）、含冷冻期、含手续费。

**我们要跳出固有的思维模式，并不是要考虑买还是卖，而是要最大化手里持有的钱。**

**买股票手里的钱减少，卖股票手里的钱增加，无论什么时刻，我们要保证手里的钱最多。**

**我们这一次买还是卖只跟上一次我们卖还是买的状态有关。**

我们解题需要使用动态规划，既然用了动态规划，肯定是要用 **空间换时间** 。

我们先看下执行状态，这是一个买入和卖出的过程，而且能交易一次即只能买卖一次，所以 **买入** 之后，状态可以转换到 **卖出** ，但是 **卖出** 之后就不能再 **买入** 了，因为只能 **买卖一次** 。

![37fc5b6cb1bf38c261bfa2ac3c1579cc.png][]

我们需要用开辟额外的空间，来不断更新买入和卖出的最大收益。

![b293df625a68049f22e1955b0c34f18e.png][]

我们先看一个最简单的例子，假设只数组长度是 **1** ，即只有一天。

这时候不管股价是多少，我的收益都是0，为什么呢？

因为必须要先买后卖，只有一天的情况下无法卖出，所以卖出的收益是0。

股价是7美元，也就是花了7美元买进这个股票，那么对应到第一天买入的最大收益就是-7美元。两者一合计当然是坐地不动更划算。

![8c9b553b47ed930cf7c88240a84b3915.png][]

我们再来看一个复杂点的，假设有三天。这里卖出数组记录了每次卖出的最大收益，数组下标i即对应第i天的最大收益。

买入数组记录了每次买入的最大收益，数组下标i即对应第i天的最大收益，第一天的时候还是老样子，卖出是0，买入是-7。

第二天卖出的最大利润仍然是0。

卖出的收益是：第一天买入的值-7，加上第二天股票价格，也就是第一天我花7美元买入(买入对应收益就是-7)，第二天1美元卖出，所以第二天的卖出收益就是-6美元。这当时是亏本了，于是继续不动。

买入的收益是：记录当天买入的最大收益，因为买入都是负的，所以最大收益就是找一个价格最低的，即前一天买入的最大收益vs第二天的股价，第一天花了7美元买入的，第二天股票跌到1美元，当然是买第二天的。

![95aa344ad4e9aff6f0c3886c40e8cd03.png][]

第三天卖出的利润就变了。

卖出收益是：第二天买入的值-1，加上第三天的股票价格，也就是前一天买入的最大收益 -1加上第三天的股票价格5，于是第三天买入的收益就变成了4。

买入的收益是：第二天买入的值-1 vs 第三天买入的股价-5，选择不动。

![f2ba5d6dc9107d63f140dd45fe2fbdc6.png][]

我们先看当前问题的代码，其中buy和sell都代表操作之后手里的钱。如果只买一次，那么上一个状态一定是0。

class Solution { 
        public int maxProfit(int[] prices) { 
            int buy = Integer.MIN_VALUE;
            int sell = 0;
            for (int price : prices) { 
                buy = Math.max(buy, 0 - price);
                sell = Math.max(sell, buy + price);
            }
            return sell;
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

输入: n = 3
    输出: 6

**示例 2：**

输入: n = 9
    输出: 45

**限制：**

*  1 <= n <= 10000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/qiu-12n-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

这道题使用高斯求和公式，将乘除法用位运算替换掉即可。

文字表述：`和 = (首项 + 末项) x 项数 / 2`

数学表达：`1+2+……+ n = (n+1) n / 2`

class Solution { 
        public int sumNums(int n) { 
            return (1 + n) * n >> 1;
        }
    }

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

## 题目介绍 ##

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

**示例：**

输入: a = 1, b = 1
    输出: 2

**提示：**

*  a, b 均可能是负数或 0
 *  结果不会溢出 32 位整数

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![55004d87f5e2e218e085657a75fc7e8c.png][]

![f1649037ed837de1d7e47f79c135e306.png][]

> Q ： 若数字 a 和 b 中有负数，则变成了减法，如何处理？  
> A ： 在计算机系统中，数值一律用 补码 来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法 同时适用于正数和负数的加法 。

class Solution { 
        public int add(int a, int b) { 
            while(b != 0) {  // 当进位为 0 时跳出
                int c = (a & b) << 1;  // c = 进位
                a ^= b; // a = 非进位和
                b = c; // b = 进位
            }
            return a;
        }
    }

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

**示例：**

输入: [1,2,3,4,5]
    输出: [120,60,40,30,24]

**提示：**

*  所有元素乘积之和不会溢出 32 位整数
 *  a.length <= 100000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![618126a63191e252e18a1b4ef512b297.png][]

![5c8ee43f24df59f2629605e6f0308a7c.png][]

![e79fae05f32fe6867bcdef8a1a772d61.png][]

class Solution { 
        public int[] constructArr(int[] a) { 
            int n = a.length;
            int[] b = new int[n];
            if (n == 0) return b;
            //计算下三角
            b[0] = 1;
            for (int i = 1; i < n; i++) { 
                b[i] = b[i - 1] * a[i - 1];
            }
            //计算上三角
            int temp = 1;
            for (int i = n - 2; i >= 0; i--) { 
                temp *= a[i + 1];
                b[i] *= temp;
            }
            return b;
        }
    }

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

## 题目介绍 ##

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

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

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

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

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

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

**说明：**

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

**示例 1：**

输入: "42"
    输出: 42

**示例 2：**

输入: "   -42"
    输出: -42
    解释: 第一个非空白字符为 '-', 它是一个负号。
         我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

**示例 3：**

输入: "4193 with words"
    输出: 4193
    解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

**示例 4：**

输入: "words and 987"
    输出: 0
    解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
         因此无法执行有效的转换。

**示例 5：**

输入: "-91283472332"
    输出: -2147483648
    解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
         因此返回 INT_MIN (−231) 。

**相同题目：**

*  #### [8. 字符串转换整数 (atoi)][8. _ _atoi] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public int strToInt(String str) { 
            long res = 0;
            if (str == null) return 0;
            char[] ch = str.trim().toCharArray();
            if (ch.length == 0) return 0;
            boolean isPreNum = true;
            boolean isHasMinus = ch[0] == '-';
            boolean isHasPlus = ch[0] == '+';
            for (int i = (isHasMinus ? 1 : isHasPlus ? 1 : 0); i < ch.length; i++) { 
                if (isPreNum && ('0' <= ch[i] && ch[i] <= '9')) { 
                    res = res * 10 + ch[i] - '0';
                    if ((isHasMinus ? -res : res) >= Integer.MAX_VALUE) { 
                        res = Integer.MAX_VALUE;
                        break;
                    } else if ((isHasMinus ? -res : res) <= Integer.MIN_VALUE) { 
                        res = Integer.MIN_VALUE;
                        break;
                    }
                    isPreNum = true;
                } else { 
                    isPreNum = false;
                }
            }
            return (int) (isHasMinus ? -res : res);
        }
    }

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

## 题目介绍 ##

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

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

例如，给定如下二叉搜索树: root = \[6,2,8,0,4,7,9,null,null,3,5\]

![b4ffe37eab5fa2fc6efad385eacb1c2b.png][]

**示例 1：**

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6 
    解释: 节点 2 和节点 8 的最近公共祖先是 6。

**示例 2：**

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    输出: 2
    解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

**说明：**

*  所有节点的值都是唯一的。
 *  p、q 为不同节点且均存在于给定的二叉搜索树中。

**相同题目：**

*  #### [剑指 Offer 68 - II. 二叉树的最近公共祖先][Offer 68 - II.] ####
 *  #### [236. 二叉树的最近公共祖先][236.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

去以root为根节点的二叉树中查找p、q的最近公共祖先

*  如果p、q同时存在于这棵二叉树中，就能成功返回它们的最近公共祖先。
 *  如果p、q都不存在于这棵二叉树中，返回null，但是题目提示，p 和 q 均存在于给定的二叉树中，所以这种情况可以不用考虑。
 *  如果只有p存在于这棵二叉树中，返回p。
 *  如果只有q存在于这棵二叉树中，返回q。

完全版：

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == null || root == p || root == q) return root;
            // 去以root.left 为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            // 去以root.right为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) return root;
            if (left == null && right == null) return null;
            if (left != null && right == null) return left;
            if (left == null && right != null) return right;
            return null;
        }
    }

简化后：

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == null || root == p || root == q) return root;
            // 去以root.left 为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            // 去以root.right为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) return root;
            if (left != null && right == null) return left;
            if (left == null && right != null) return right;
            return null;
        }
    }

再简化：

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == null || root == p || root == q) return root;
            // 去以root.left 为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            // 去以root.right为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) return root;
            return (left != null) ? left : right;
        }
    }

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

## 题目介绍 ##

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

例如，给定如下二叉树: root = \[3,5,1,6,2,0,8,null,null,7,4\]

![6e72cd0a5e72c1da927606767215532f.png][]

**示例 1：**

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    输出: 3
    解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

**示例 2：**

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
    输出: 5
    解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

**说明：**

*  所有节点的值都是唯一的。
 *  p、q 为不同节点且均存在于给定的二叉搜索树中。

**相同题目：**

*  #### [剑指 Offer 68 - I. 二叉搜索树的最近公共祖先][Offer 68 - I.] ####
 *  #### [236. 二叉树的最近公共祖先][236.] ####

## 题目实现 ##

去以root为根节点的二叉树中查找p、q的最近公共祖先

完全版：

简化后：

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == null || root == p || root == q) return root;
            // 去以root.left 为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            // 去以root.right为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) return root;
            if (left != null && right == null) return left;
            if (left == null && right != null) return right;
            return null;
        }
    }

再简化：

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == null || root == p || root == q) return root;
            // 去以root.left 为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            // 去以root.right为根节点的二叉树中查找p、q的最近公共祖先
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) return root;
            return (left != null) ? left : right;
        }
    }

[240. _ II]: https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
[bd93575c0908efc3548a1d757720b38c.png]: /images/20220828/328e2401771e4c619c5ae67745af90e2.png
[14a4a2ec2b990591c8f725460e04c3ed.png]: /images/20220828/b3a3fea4635a4378b5b4cd95a47eed6d.png
[3e4d4154be5fe8d9868259ef6c57dc5e.png]: /images/20220828/1e223a1b2843415fb5636a05e9a4180f.png
[c8710acc1515262c469ecd56f241c541.png]: /images/20220828/4d1ef59b34bf44139165044534cd3a05.png
[2fac973f6367147085e1d776a1453d02.png]: /images/20220828/9a22aa34194b452d8bbc3fb31a48d931.png
[ff3a53d9fd4cda56349a97000cc0d833.png]: /images/20220828/8c28d3fbb0834ba5a60229aa92d6c854.png
[105.]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[70.]: https://leetcode-cn.com/problems/climbing-stairs/
[154. _ II]: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
[830137c28efb4b66b0e3d17a14eb2d50.png]: /images/20220828/a11a4eff8e174d51bb9d7ab2c6ca03fd.png
[79.]: https://leetcode-cn.com/problems/word-search/
[343.]: https://leetcode-cn.com/problems/integer-break/
[ad2718fb6b96ee51b4fd10deb112e87b.png]: /images/20220828/239313fd8098432ba482c79d6838525f.png
[50. Pow_x_ n]: https://leetcode-cn.com/problems/powx-n/
[37c7fecb1af4ac86a40cc94f02fe04a5.png]: /images/20220828/4578782542d641bfa5391bad36ed4ba1.png
[10.]: https://leetcode-cn.com/problems/regular-expression-matching/
[05db8bf07ac0abf2e64490b0fe46c5bc.png]: /images/20220828/96e289b0238f466bb9dfd75d4b728579.png
[897464d6e839ab0e3530d0da1ee85873.png]: /images/20220828/f29341887fbf4f21ad1fd8680932d451.png
[101.]: https://leetcode-cn.com/problems/symmetric-tree/
[9c67aacf604acf4fd7900ac9cdab5ddc.png]: /images/20220828/b6b15697e6c244bf9be01cfa2b6141e7.png
[54.]: https://leetcode-cn.com/problems/spiral-matrix/
[155.]: https://leetcode-cn.com/problems/min-stack/
[102.]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
[cdd80367654dc138d5323cea09461f30.png]: /images/20220828/ea539c5172aa49968517d81a8a191cfb.png
[4ce3e916a187d9a7af8c645c102a3c9d.png]: /images/20220828/9984a9a893314ef69a753eb09aee1814.png
[b6114cfb00d7e9c96d13d601e3c55a90.png]: /images/20220828/0461de46589a483f8d7e7c3017fa2c8b.png
[138.]: https://leetcode-cn.com/problems/copy-list-with-random-pointer/
[40f9b898cd35d5e536105609421e32c4.png]: /images/20220828/7da966a5483c4f4a83d981f421eee95e.png
[83c1ad6713fd0f156a13cc0a5558c0d8.png]: /images/20220828/5095736376d94fd7af93e276ddb434eb.png
[426.]: https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
[3cefa60c59c5f6f14232b90efb4b0a4a.png]: /images/20220828/0b2e657120454af1a58f22536924fe74.png
[68c83a78d2e7ab00fa9bba1a4f52f607.png]: /images/20220828/b645f6deebf84eceb099b4d7ab27c2bc.png
[21e658a4c3542f92708708874a6f2fbb.png]: /images/20220828/5fc81c5b28ed4d6fbacd45d1e67580e2.png
[175eb3c650feac9e6a94d30dfc0cba39.png]: /images/20220828/c3da313f40bf4ea2ad3377dcaf8d415e.png
[02517f7ec34ec62f71a94cc401e4e269.png]: /images/20220828/6c9161675b75468291ce4796f6c4ad64.png
[7ed5c6427508f35d5430f85c48d2045a.png]: /images/20220828/045da392d90f4d86b7e23ae342f2d0e2.png
[297.]: https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
[be9101c30793f516115cdbf74252ef9d.png]: /images/20220828/5121b2e6145747339706cb58ff673572.png
[295.]: https://leetcode-cn.com/problems/find-median-from-data-stream/
[6c56ea72df2deda5c199d0f6eebf77ee.png]: /images/20220828/bb8ddd933b324cc29a718d843ec493c5.png
[53.]: https://leetcode-cn.com/problems/maximum-subarray/
[233. _ 1]: https://leetcode-cn.com/problems/number-of-digit-one/
[af6cea16531f3588136054b2f911ad48.png]: /images/20220828/9c0f1237dcc1458cb90d54a5287d1c85.png
[400. _ N]: https://leetcode-cn.com/problems/nth-digit/
[1917b79b67563bbdd14a4a0b0bc8d928.png]: /images/20220828/6f291a0d8c0944f0ad48e56f72b53b83.png
[5732df37d1d50bfd7f0c5d1d9066b136.png]: /images/20220828/206ef9cde0144c1c86d6d808c68fd6ad.png
[ce28b0c4d768e4b2add246ea53b806a6.png]: /images/20220828/e989e05b37284ccd94058f51d4edd8db.png
[20644a92b56bdab925033f49e8012591.png]: /images/20220828/eb646bdedb814c34be19a50d02babfb9.png
[3a528d0810edd88eba1d2233e6ebd5bb.png]: /images/20220828/2c84995fb9ff48ddae002e5deab7a9a5.png
[6f6736937d007d867e8599e83b7ce7a6.png]: /images/20220828/582aa58b14604d9a840793ffae85a48f.png
[efb7e896d73c7aa3275e111fe6bf85ca.png]: /images/20220828/fca3e1823d054e5abfdff969088de0b8.png
[b6860383a957b7f2386830bf352aa24c.png]: /images/20220828/734de6f6cc934cab847e41cc6395ba93.png
[cfac3a51bcaf531d739495469c6b5536.png]: /images/20220828/53807e7c013a439e89f4669aaba8c20f.png
[31177609cc362ddf324a30679406861e.png]: /images/20220828/e5b3836df9a34df9ae7a396168bb18de.png
[15647cade71f16441cb0d43e25387ff1.png]: /images/20220828/b901a471c088424aa4c21a6673726cb9.png
[64.]: https://leetcode-cn.com/problems/minimum-path-sum/
[62.]: https://leetcode-cn.com/problems/unique-paths/
[c605992c817a45901e5e9383c3988dde.png]: /images/20220828/151c3fc65d054772a2e9e279001017e7.png
[9f6d843a389b5a2bc0c48348e0c7b141.png]: /images/20220828/09d27b90034e46a2acadea89910ab6eb.png
[19c3e4e95a280e03605f60d883697d6c.png]: /images/20220828/3f9b8ea80d964766bad88a461eff354b.png
[3.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[264. _ II]: https://leetcode-cn.com/problems/ugly-number-ii/
[9148ff1afafcb8eb4c58fb720680e873.png]: /images/20220828/bc98b893f2c646f497f24b9614489151.png
[608561a5aa13a89324655a3e10c2bb79.png]: /images/20220828/79144933d2e645af98bd324eea2f8ffa.png
[456a9294f3e35314a0b91b2de20d15dc.png]: /images/20220828/ae0191b22f7c434aa570d0860dac93d7.png
[54874887f68b3bdca93a555cf0610299.png]: /images/20220828/3fb513ece6da4f28bc9acebd4e084802.png
[944ba111c3b9680fd2add071fe14e165.png]: /images/20220828/20fc6b052dca4d4abefb21a022c1a3ee.png
[160.]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
[42fab0317e87fd4e667d349639bbb1a0.png]: /images/20220828/c516234053694a1a82b7497b5e2cfcc8.png
[b7b50c17bcaab25584099091144b6813.png]: /images/20220828/288599c78b9c4b5db3d49eec234641ec.png
[25e7341bd60f5204859959138df5e8d6.png]: /images/20220828/5f344d1231264c61aac38adc10009388.png
[c03e8404af4c915be42aad905364f8d5.png]: /images/20220828/159b253d62f545a4aac1392720862e9e.png
[617c3d5875d3a4cd8b4dabf5f19bdd5b.png]: /images/20220828/741352b8366a4ce4bfca133595ace365.png
[3c263d62a5531feb60bd3ee1ba16265a.png]: /images/20220828/4193ae9a228f4002b3710b36b9a826d7.png
[997d2fa95795acbe74a28c6fb1dee147.png]: /images/20220828/e1f003cac55a4e27aa98bbd21c5a3401.png
[6d8cbdfb1737f2209ab51e705f56a3f7.png]: /images/20220828/2c76646cbcb2404ea273da79160e71f6.png
[151.]: https://leetcode-cn.com/problems/reverse-words-in-a-string/
[239.]: https://leetcode-cn.com/problems/sliding-window-maximum/
[0494429509d0efbd283d9e5be2cd5825.gif]: /images/20220828/79d12025276445f7908755226a0a919d.png
[bf2869b6303efcaa58c7728cfa208d78.gif]: /images/20220828/ac5298c1ce4a4456a27628e3733658df.png
[4b005c9422b6484d7221bfae46e1d107.gif]: /images/20220828/73ddd277f9ff4632833726dc41910b90.png
[a20abba0c72a84ed31d7c8513a51f789.gif]: /images/20220828/ca8f017fdfe74c7d9c67ffb5d1d5eb60.png
[1882303c455c24ff434db17a3b0699c6.gif]: /images/20220828/d6cffbdf009c44ca94bce1911b637c8c.png
[ac5dfb26586064ea31a7c37debb6b1fc.gif]: /images/20220828/8a7ba6d5adf944a3bd44831260b78c10.png
[0707cfc47c970f34d2a82f163cbb567e.gif]: /images/20220828/3f5cee62ed134b22bf205234d4fe0ddf.png
[d02f9bb1a643946ce462f8c27f8a67c7.png]: /images/20220828/6bc75a3858354e74a5a7ab23d7738735.png
[d5a4ee438f74e045589178bdc0ba229c.png]: /images/20220828/1edef4fac2594ad7a7a9e72b0a0d4a49.png
[cde6f27d6fae788f68f6ee24265fa219.png]: /images/20220828/6d1ab9a96f5c41098d47a4591694e0d6.png
[0e41ef8b6462a013e610f12717880121.png]: /images/20220828/11a5637799f0477aaf62c86612303fcd.png
[71c85f9500653c083fe6c5d4bb3c640c.png]: /images/20220828/14738c427e65499cbd9db687e104049b.png
[89337efcd910affc03209ad7e4398f9a.png]: /images/20220828/ac68256372084f9c9b260f49a920a76f.png
[1442f92e7527ef58c912354888e3bb42.png]: /images/20220828/07c1a5c9c4ac4702a52bc3525594b93a.png
[e79671a501fd994040023efdfdf76be1.png]: /images/20220828/5fea4080ea244da3a4cf4725d00be586.png
[f06c5df0b8bade4e4d51135d0ca04b3b.png]: /images/20220828/2f75d036334548fe95e858d5ac7a8aaa.png
[82435c873a617b21898344c580c86681.png]: /images/20220828/c8d7990b028c45db8acf5655fb40a29c.png
[eb0cb04cb7d8ba6d765fe184095181af.png]: /images/20220828/497226cac28642a9b546a694ae9c9905.png
[e1dea5668aa32506deee22e756e5cb06.png]: /images/20220828/82f205f2f1744ddd8f970d65a69890f7.png
[4055081fcf4df8f09b814c366f54f97b.png]: /images/20220828/5e2bf1897a0c4072a125b2c2a1b65485.png
[c0e81c14238e04c48992473523486f7f.png]: /images/20220828/b22ac7c113ee448c9b3010b4797c0175.png
[121.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
[122. _ II]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
[123. _ III]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
[188. _ IV]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
[714.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
[309.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[37fc5b6cb1bf38c261bfa2ac3c1579cc.png]: /images/20220828/2ab1c7bede8a40368c95b348d2460663.png
[b293df625a68049f22e1955b0c34f18e.png]: /images/20220828/8fd3f9e90be24510bd8a25fbe2f07bb0.png
[8c9b553b47ed930cf7c88240a84b3915.png]: /images/20220828/45f66a0522b047dfa858c1be7f52128f.png
[95aa344ad4e9aff6f0c3886c40e8cd03.png]: /images/20220828/01929d36cb2e4710b898d5ae130143f7.png
[f2ba5d6dc9107d63f140dd45fe2fbdc6.png]: /images/20220828/a5cb262091f74ac0b99256f4cbec9264.png
[55004d87f5e2e218e085657a75fc7e8c.png]: /images/20220828/2c2b863943604b0ba282828b55e00145.png
[f1649037ed837de1d7e47f79c135e306.png]: /images/20220828/98cd705e050e4c92836dcb43aac27689.png
[618126a63191e252e18a1b4ef512b297.png]: /images/20220828/e2df8c8bada24eb99ec718621d5fff73.png
[5c8ee43f24df59f2629605e6f0308a7c.png]: /images/20220828/2b67b341f90a4306945a930ce5df4eb6.png
[e79fae05f32fe6867bcdef8a1a772d61.png]: /images/20220828/6b73eab935094fc1a90487c50fea3667.png
[8. _ _atoi]: https://leetcode-cn.com/problems/string-to-integer-atoi/
[b4ffe37eab5fa2fc6efad385eacb1c2b.png]: /images/20220828/2f817e66129e412aa40605eb54961890.png
[Offer 68 - II.]: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[236.]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
[6e72cd0a5e72c1da927606767215532f.png]: /images/20220828/93d0b157c62b4628ac42b3eb54ee1e1c.png
[Offer 68 - I.]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/