小锵的博客

题目信息 题目：剑指 Offer 53 - I. 在排序数组中查找数字 I 时间： 2020-08-20 题目链接：Leetcode tag：二分查找 哈希表 难易程度：简单 题目描述： 统计一个数字在排序数组中出现的次数。 示例1: 12输入: nums = [5,7,7,8,8,10], target = 8输出: 2 示例2: 12输入: nums = [5,7,7,8,8,10], target = 6输出: 0 注意 11. 0 <= 数组长度 <= 50000 解题思路 本题难点 排序数组中查找数字，性能最优。 具体思路 排序数组中的搜索问题，首先想到 二分法 解决。 排序数组 nums 中的所有数字 target 形成一个窗口，记窗口的 左 / 右边界 索引分别为 left 和 right ，分别对应窗口左边 / 右边的首个元素。 统计数字 target 的出现次数，可转化为：使用二分法分别找到 左边界 left 和 右边界 right ，易得数字 target 的数量为 right−left−1 。 计算中点 m ...

题目信息 题目；剑指 Offer 53 - II. 0～n-1中缺失的数字 时间： 2020-08-19 题目链接：Leetcode tag： 二分查找 难易程度：简单 题目描述： 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。 示例1: 12输入: [0,1,3]输出: 2 示例2: 12输入: [0]输出: 1 注意 11 <= 数组长度 <= 10000 解题思路 本题难点 排序数组查找数组，性能最优。 具体思路 排序数组中的搜索问题，首先想到 二分法 解决。 题目中的数组可以按照以下规则划分为两部分。 左子数组： nums[i]=i 右子数组： nums[i]≠i 缺失的数字等于 “右子数组的首位元素” 对应的索引；因此考虑使用二分法查找 “右子数组的首位元素” 。 循环二分： 当 i≤j时循环 （即当闭区间 [i,j]为空时跳出） ； 计算中点 m=(i+j)/2，其中 “/” 为向下取整除法； ...

题目信息 题目：剑指 Offer 54. 二叉搜索树的第k大节点 时间： 2020-08-18 题目链接：Leetcode tag：二叉搜索树 中序遍历 递归 难易程度：中等 题目描述： 给定一棵二叉搜索树，请找出其中第k大的节点。 示例1: 1234567输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2输出: 4 示例2: 123456789输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1输出: 4 注意 11. 1 ≤ k ≤ 二叉搜索树元素个数 解题思路 本题难点 二叉排序树：根节点的值大于左子树的值，小于右子树的值。查找第K大节点。 具体思路 二叉搜索树的中序遍历为 递增序列 ，易得二叉搜索树的 中序遍历倒序 为 递减序列 。 求 “二叉搜索树第 k大的节点” 可转化为求 “此树的中序遍历倒序的第 k个节点”。 中序遍历 1234567// 打 ...

题目信息 题目：剑指 Offer 55 - I. 二叉树的深度 时间： 2020-08-17 题目链接：Leetcode tag： 二叉树 层序遍历 后序遍历 难易程度：简单 题目描述： 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。 示例: 给定二叉树 [3,9,20,null,null,15,7]， 12345 3 / \9 20 / \ 15 7 返回它的最大深度 3 。 注意 11. 节点总数 <= 10000 解题思路 本题难点 树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）； 常见的 DFS ： 先序遍历、中序遍历、后序遍历； 常见的 BFS ： 层序遍历（即按层遍历）。 求树的深度需要遍历树的所有节点。 具体思路 二叉树的层序遍历 / 广度优先搜索往往利用 队列 实现。 每遍历一层，则计数器 +1 ，直到遍历完成，则可得到树的深度。 注意 代码 12345678910111213141516 ...

题目信息 题目：剑指 Offer 55 - II. 平衡二叉树 时间： 2020-08-16 题目链接：Leetcode tag： 平衡二叉树 深度优先搜索 难易程度：简单 题目描述： 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 示例1: 给定二叉树 [3,9,20,null,null,15,7] 12345 3 / \9 20 / \ 15 7 返回 true 。 示例2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1234567 1 / \ 2 2 / \ 3 3 / \4 4 返回 false 。 注意 11. 1 <= 树的结点个数 <= 10000 解题思路 本题难点 树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1 。 具体思路 后序遍历 + 剪枝 （从底至顶），思路是对二叉树做后序遍历，从底至顶返回子树深度，若判定某子树不是平衡树则 “剪 ...

题目信息 题目：剑指 Offer 56 - I. 数组中数字出现的次数 时间： 2020-08-15 题目链接：Leetcode tag：位运算 难易程度：中等 题目描述： 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 示例1: 12输入：nums = [4,1,4,6]输出：[1,6] 或 [6,1] 示例2: 12输入：nums = [1,2,10,4,1,4,3,3]输出：[2,10] 或 [10,2] 注意 11. 2 <= nums.length <= 10000 解题思路 本题难点 查找数组中两个只出现一次的数字，性能最优。 具体思路 异或运算 交换律：p⊕q=q⊕p 结合律：p⊕(q⊕r)=(p⊕q)⊕r 恒等率：p⊕0=p 归零率：p⊕p=0 如果有若干个数字进行异或操作：根据 交换律、结合律 将相同的数字优先两两进行异或运算。此时就只剩下只出现一次的那个数了！ 由于数组中存在着两个数字不重复的情况，我们将所 ...

题目信息 题目：剑指 Offer 57 - I. 和为s的两个数字 时间： 2020-08-14 题目链接：Leetcode tag： 双指针 哈希表 难易程度：简单 题目描述： 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。 示例1: 12输入：nums = [2,7,11,15], target = 9输出：[2,7] 或者 [7,2] 示例2: 12输入：nums = [10,26,30,31,47,60], target = 40输出：[10,30] 或者 [30,10] 注意 121. 1 <= nums.length <= 10^52. 1 <= nums[i] <= 10^6 解题思路 本题难点 查找和为s的两个数字，性能最优。 具体思路 本题的 nums 是 排序数组 ，因此可使用 双指针法 将空间复杂度降低至 O(1)。 代码 123456789101112131415161718192021class Solution ...

题目信息 题目：剑指 Offer 57 - II. 和为s的连续正数序列 时间： 2020-08-13 题目链接：Leetcode tag：双指针 滑动窗口 难易程度：简单 题目描述： 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 示例1: 12输入：target = 9输出：[[2,3,4],[4,5]] 示例2: 12输入：target = 15输出：[[1,2,3,4,5],[4,5,6],[7,8]] 注意 11. 1 <= target <= 10^5 解题思路 本题难点 连续正整数序列的和为target，存在有多个正整数序列满足条件。 具体思路 滑动窗口：滑动窗口可以看成数组中框起来的一个部分。在一些数组类题目中，我们可以用滑动窗口来观察可能的候选结果。当滑动窗口从数组的左边滑到了右边，我们就可以从所有的候选结果中找到最优的结果。 窗口的左边界和右边界永远只能向右移动，而不能向左移动。这是为了保证滑动窗口的 ...

题目信息 题目：翻转单词顺序 时间： 2020-08-12 题目链接：Leetcode tag：字符串 排序 难易程度：简单 题目描述： 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。 示例1: 12输入: "the sky is blue"输出: "blue is sky the" 示例2: 123输入: "  hello world!  "输出: "world! hello"解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 注意 1231. 无空格字符构成一个单词。2. 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。3. 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。 解题思路 本题难点 处理空格情况，字符串倒序。 具体思路 倒序遍历字符串 s，记录单词左右索引边界 i, j； 每确定一个单词的 ...

题目信息 题目：剑指 Offer 58 - II. 左旋转字符串 时间： 2020-08-11 题目链接：Leetcode tag： 字符串 排序 难易程度：中等 题目描述： 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。 示例1: 12输入: s = "abcdefg", k = 2输出: "cdefgab" 示例2: 12输入: s = "lrloseumgh", k = 6输出: "umghlrlose" 注意 11. 1 <= k < s.length <= 10000 解题思路 本题难点 旋转k个字符串 具体思路 列表遍历拼接 新建一个StringBuilder(Java) ，记为 res； 先向 res 添加 “第 n+1 位至末位的字符” ； 再向 res 添加 “首位至第 n 位的字符” ； 将 res 转化为字 ...