小锵的博客

题目信息 题目：剑指 Offer 32 - III. 从上到下打印二叉树 III 时间： 2020-09-08 题目链接：Leetcode tag：双端队列 队列 难易程度：中等 题目描述： 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。 示例1: 给定二叉树: [3,9,20,null,null,15,7], 12345 3 / \9 20 / \ 15 7 返回其层次遍历结果： 12345[ [3], [20,9], [15,7]] 提示 11.节点总数 <= 1000 解题思路 本题难点 二叉树层序遍历，每层遍历顺序都发生变化，奇数层逆序 具体思路 层序遍历 + 双端队列 操作：利用双端队列的两端皆可添加元素的特性，设打印列表（双端队列） level ，并规定 奇数层 则添加至 level 尾部 偶数层 则添加至 level 头部 代码 1234567891011121314151617181920 ...

题目信息 题目：剑指 Offer 33. 二叉搜索树的后序遍历序列 时间： 2020-09-08 题目链接：Leetcode tag：分治算法 递归 难易程度：中等 题目描述： 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考如下: 12345 5 / \ 2 6 / \1 3 示例1: 12输入: [1,6,3,2,5]输出: false 示例2: 12输入: [1,3,2,6,5]输出: true 提示 11.数组长度<=1000 解题思路 本题难点 后序遍历定义： [ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。 二叉搜索树定义： 左子树中所有节点的值< 根节点的值；右子树中所有节点的值 <根节点的值；其左、右子树也分别为二叉搜索树。 具体思路 根据二叉搜索树的定义，可以通过递归，判断所有子树的 正确性 （即其后序遍历是否满足二叉搜索树的定义） ，若所有子树都正确， ...

题目信息 题目：剑指 Offer 34. 二叉树中和为某一值的路径 时间： 2020-09-07 题目链接：Leetcode tag：深度优先搜索 回溯法 难易程度：中等 题目描述： 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例: 给定如下二叉树，以及目标和 sum = 22， 1234567 5 / \ 4 8 / / \ 11 13 4 / \ / \7 2 5 1 返回： 1234[ [5,4,11,2], [5,8,4,5]] 提示 11.节点总数<=10000 解题思路 本题难点 本问题是典型的二叉树方案搜索问题，使用回溯法解决，其包含 先序遍历 + 路径记录 两部分。 具体思路 先序遍历：按照 “根、左、右” 的顺序，遍历树的所有节点。 路径记录： 在先序遍历中，记录从根节点到当前节点的路径。当路径为 ① 根节点到叶节点形成的路径 且 ② 各节点值的和等于目标值 ...

题目信息 题目：剑指 Offer 35. 复杂链表的复制 时间： 2020-09-06 题目链接：Leetcode tag： 链表 难易程度：中等 题目描述： 请实现 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]] 提示 1231.-10000 <= Node.val <= 100002.Node.random为null或指向链表中的节点3.节点数目不超过1000 解题思路 本题难点 本题的意思是复制一个链表并返回，这个链表与一般链表不同的是多了一个 random 指针。 具体思路 这个复制过程可以分成两步：第一步是复 ...

题目信息 题目：剑指 Offer 36. 二叉搜索树与双向链表 时间： 2020-09-05 题目链接：Leetcode tag： 二叉搜索树 中序遍历 递归 深度优先搜索 难易程度：中等 题目描述： 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 示例: 12345 4 / \ 2 5 / \ 1 3 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。 提示 1特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。 解题思路 本题难点 二叉搜索树 转换成一个 “排序的循环双向链表” ，其中包含三个要素： 排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点； 双向链表： 在构建相邻节点（设前驱节点 pre ， ...

题目信息 题目： 剑指 Offer 37. 序列化二叉树 时间： 2020-09-04 题目链接：Leetcode tag：序列化 二叉树 队列 难易程度：中等 题目描述： 请实现两个函数，分别用来序列化和反序列化二叉树。 示例: 12345 1 / \2 3 / \ 4 5 序列化为 “[1,2,3,null,null,4,5]” 解题思路 本题难点 题目要求的 “序列化” 和 “反序列化” 是 可逆 操作。因此，序列化的字符串应携带 “完整的” 二叉树信息，即拥有单独表示二叉树的能力。 具体思路 序列化的字符串实际上是二叉树的 “层序遍历”（BFS）结果。为使反序列化可行，考虑将越过叶节点后的 null 也看作是节点。 **序列化 serialize **：借助队列，对二叉树做层序遍历，并将越过叶节点的 null 也打印出来。 **反序列化 deserialize **：利用队列按层构建二叉树，借助一个指针 i 指向节点 node 的左、右子节点，每构建一个 node 的左、右子节点，指针 i 就向右移动 1 位。 ...

题目信息 题目：剑指 Offer 38. 字符串的排列 时间： 2020-09-03 题目链接：Leetcode tag：深度优先搜索 回溯法 难易程度：中等 题目描述： 输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 示例: 12输入：s = "abc"输出：["abc","acb","bac","bca","cab","cba"] 提示 11 <= s.length() <= 8 解题思路 本题难点 对于一个长度为 n 的字符串（假设字符互不重复），其排列共有 n×(n−1)×(n−2)…×2×1 种方案。要求返回的结果又不能有重复元素。 回溯法 ：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解的话（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。 具体思路 这个问题可以看作有 n 个排列成一行的空格，我们需要从左往右依此填入题目给定的 n 个字符，每个字符只能使用一次。 定义chars[]为 ...

题目信息 题目；剑指 Offer 39. 数组中出现次数超过一半的数字 时间： 2020-09-02 题目链接：Leetcode tag： 数组 哈希表 难易程度：简单 题目描述： 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 假设数组是非空的，并且给定的数组总是存在多数元素。 示例: 12输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2 提示 11 <= 数组长度 <= 50000 解题思路 本题难点 如何实现查找数组中的众数的最优解，时间复杂度和空间复杂度最小。 具体思路 摩尔投票法： 票数和：由于众数出现的次数超过数组长度的一半；若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的票数和 > 0。 票数正负抵消： 设数组 nums 中的众数为 x ，数组长度为 n 。若 nums 的前 a 个数字的 票数和 =0 ，则 数组后 (n−a) 个数字的 票数和一定仍 > 0 （即后 (n−a) 个数字的 众数仍为 x ）。 为构建正负抵消，假设数 ...

题目信息 题目：剑指 Offer 40. 最小的k个数 时间： 2020-09-01 题目链接：Leetcode tag： 快速排序 难易程度：中等 题目描述： 输入整数数组 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] 提示 121.0 <= k <= arr.length <= 100002.0 <= arr[i] <= 10000 解题思路 本题难点 多种解题方案，快排，大根堆，二叉搜索树，计数排序 具体思路 快速排序的思想。快排的划分函数每次执行完后都能将数组分成两个部分，小于等于分界值 pivot 的元素的都会被放到数组的左边，大于的都会被放到数组的右边，然后返回分界值的下标。 我们的目的是寻找最小的 k 个数。假设经过一次 partition 操作，分界 ...

题目信息 题目：剑指 Offer 41. 数据流中的中位数 时间： 2020-08-31 题目链接：Leetcode tag： 大根堆 小根堆 难易程度：中等 题目描述： 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。 设计一个支持以下两种操作的数据结构： void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。 示例1: 1234输入：["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"][[],[1],[2],[],[3],[]]输出：[null,null,null,1.50000,null,2.00000] 示例2: 1234输入：["MedianFinder","addNum","findMedian","addNum","f ...