剑指 Offer 40. 最小的k个数
剑指 Offer 40. 最小的k个数题目输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
12输入：arr = [3,2,1], k = 2输出：[1,2] 或者 [2,1]
示例 2：
12输入：arr = [0,1,2,1], k = 1输出：[0]
限制：
120 <= k <= arr.length <= 100000 <= arr[i] <= 10000
思路第一个就是排序，然后从0遍历k个数字
第二个，定义一个长度为k的数组，遍历一遍，如果这个值的大小小于数组最大（用一个值记录）的，则把数组加入，踢出最大的
实现
剑指 Offer 42. 连续子数组的最大和
剑指 Offer 42. 连续子数组的最大和题目输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
123输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
121 <= arr.length <= 10^5-100 <= arr[i] <= 100
思路第一种方法：遍历，找到所有可能的解
第二种方法就是动态规划：
实现暴力破解12345678910111213141516171819private static class Solution { public int maxSubArray(int[] nums) { int max = nums[0]; int curMax = 0; for (int i = 0; i < nums.length; i++) { curMax ...
剑指 Offer 38. 字符串的排列
剑指 Offer 38. 字符串的排列题目输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
12输入：s = "abc"输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
思路这个题有一个点：
不能有重复元素
这个不能有重复元素的意思是：数组中的一个字母只能有一次，但是可以给你重复的字母，所以我们不能用有一个hashset来判断这个元素是否已经加入（添加索引也不行，因为结果可能有重复）
12输入："aab"输出：["aba","aab","baa"]
所以我们可以通过递归的方法解决：
对于每一个元素，我们可以固定一个首部元素，然后对于后面的元素进行任意组合，然后后面的元素我们同样可以固定首部元素，对于后面的有元素进 ...
剑指 Offer 55 - I. 二叉树的深度
剑指 Offer 55 - I. 二叉树的深度题目输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
提示：
节点总数 <= 10000
思路递归，选出左右子节点的最大深度，如果为null怎跳出递归
实现12345678private static class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1); }}
剑指 Offer 39. 数组中出现次数超过一半的数字
剑指 Offer 39. 数组中出现次数超过一半的数字题目数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
12输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2
限制：
11 <= 数组长度 <= 50000
注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/
思路本题常见的三种解法：
哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N)O(N) 。数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N)O(N) 和 O(1)O(1) ，为本题的最佳解法。
实现哈希表123456789101112131415161718192021222324252627private static class Solution & ...
剑指 Offer 37. 序列化二叉树
剑指 Offer 37. 序列化二叉树题目请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例：
12输入：root = [1,2,3,null,null,4,5]输出：[1,2,3,null,null,4,5]
思路层序遍历，然后在依次构建
实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970private static class Codec { // Encodes a tree to a ...
剑指 Offer 33. 二叉搜索树的后序遍历序列
剑指 Offer 34. 二叉树中和为某一值的路径题目给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
12输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
12输入：root = [1,2,3], targetSum = 5输出：[]
示例 3：
12输入：root = [1,2], targetSum = 0输出：[]
思路深度遍历到根节点的时候判断最终值是否等于目标值，然后需要回溯
实现12345678910111213141516171819202122232425262728293031323334private static class Solution { LinkedList<List<Integer>> result = new LinkedList ...
剑指 Offer 33. 二叉搜索树的后序遍历序列
剑指 Offer 35. 复杂链表的复制题目请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
12输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
12输入：head = [[1,1],[2,1]]输出：[[1,1],[2,1]]
示例 3：
12输入：head = [[3,null],[3,0],[3,null]]输出：[[3,null],[3,0],[3,null]]
示例 4：
123输入：head = []输出：[]解释：给定的链表为空（空指针），因此返回 null。
提示：
-10000 <= Node.val <= 10000 Node.random 为空（null）或指向链表中的节点。 节点数目不超过 1000 。
思路本题的难点就 ...
剑指 Offer 33. 二叉搜索树的后序遍历序列
剑指 Offer 33. 二叉搜索树的后序遍历序列题目12345678910111213141516171819202122输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。参考以下这颗二叉搜索树： 5 / \ 2 6 / \ 1 3示例 1：输入: [1,6,3,2,5]输出: false示例 2：输入: [1,3,2,6,5]输出: true 提示：数组长度 <= 1000
思路因为为后续遍历，所以一定满足，最后的节点一定是根节点，所以我们找到了根节点，然后因为这个树为二叉搜索树，所以根节点的左边的值一定小于根节点，右边的值一定大于根节点，所以我们在前面的数组中一定能找到left和right，如果这个数组不满足这个条件那么就一定不能构建成搜索树。
这样我们找到了left和right后依次类推，我们逐个判断left和right是不是二叉搜索树。
和剑指offer第七题类似，也是通过指针和前序中序后序遍历确定根节点
实现123456789101112 ...
剑指 Offer 25. 合并两个排序的链表
剑指 Offer 25. 合并两个排序的链表题目12345678910输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。示例1：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4限制：0 <= 链表长度 <= 1000
思想双指针，声明一个变量记录新链表中的最大值，对每一个链表声明一个指针，先比较这两个指针中的值，小的值追加到新链表后指针++
实现1234567891011121314151617181920212223242526272829303132333435363738private static class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { ...
剑指 Offer 26. 树的子结构
剑指 Offer 26. 树的子结构题目123456789101112131415161718192021222324252627282930输入两棵二叉树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
思路深度遍历每一个节点，对每一个节点都对比一次TreeB，所以需要两个函数，第一个就是dfs，第二个就是对比TreeA和TreeB
实现123456789101112131415161718192021private static class Solution { public boolean is ...
剑指 Offer 27. 二叉树的镜像
剑指 Offer 27. 二叉树的镜像题目1234567891011121314151617181920212223242526请完成一个函数，输入一个二叉树，该函数输出它的镜像。例如输入： 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
思路我们可以在原来的数组上进行转换，寻找子问题，我们可以先转换叶子节点，然后逐层向根节点转换。这就是典型的递归的思维
实现1234567891011private static class Solution { public TreeNode mirrorTree(TreeNode root) { if (root == null){ return null; } ...
剑指 Offer 28. 对称的二叉树
剑指 Offer 28. 对称的二叉树题目123456789101112131415161718192021222324252627请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。例如，二叉树 [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
思路层序遍历，拿到每一层的数据，然后写一个函数判断这一层的数字是否为中心对称。
实现拿到每一层的数据然后判断，效率太低，击败了5%的用户
1234567891011121314151617181920212223242526272829303132333435363738394 ...
剑指 Offer 29. 顺时针打印矩阵
剑指 Offer 29. 顺时针打印矩阵题目1234567891011121314151617输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 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 <= 1000 <= matrix[i].length <= 100
思路定义四个指针，分别为top，right、bottom、left，能够确定四个角的位置，然后逐层遍历
每次打印完一层后都要判断数组是否发生越界（已经不用打印了）
实现通过定义的四个变量来判断是否越界
1234567891011121314151617181920212223242526272829303132333435363738394041424344private static class Sol ...
剑指 Offer 31. 栈的压入、弹出序列
剑指 Offer 31. 栈的压入、弹出序列题目123456789101112131415161718192021输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {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 ...
