2021年4月刷题日志
4.30
刷完题复习一下软件项目管理就去考试了,考完起飞!
题目
137. 只出现一次的数字 II
难度中等580
给你一个整数数组
nums
,除某个元素仅出现 一次 外,其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。示例 1:
1
2 输入:nums = [2,2,3,2]
输出:3示例 2:
1
2 输入:nums = [0,1,0,1,0,1,99]
输出:99
思路
不会位运算,直接哈希表计数,一次遍历数组,一次遍历哈希表。
代码
1 | function singleNumber(nums: number[]): number { |
4.29
单杀困难题,芜湖🛫!
题目
403. 青蛙过河
难度困难
一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。
给你石子的位置列表
stones
(用单元格序号 升序 表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一块石子上)。开始时, 青蛙默认已站在第一块石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格 1 跳至单元格 2 )。
如果青蛙上一步跳跃了
k
个单位,那么它接下来的跳跃距离只能选择为k - 1
、k
或k + 1
个单位。 另请注意,青蛙只能向前方(终点的方向)跳跃。示例 1:
1
2
3 输入:stones = [0,1,3,5,6,8,12,17]
输出:true
解释:青蛙可以成功过河,按照如下方案跳跃:跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后,跳 5 个单位到第 8 个石子(即最后一块石子)。示例 2:
1
2
3 输入:stones = [0,1,2,3,4,8,9,11]
输出:false
解释:这是因为第 5 和第 6 个石子之间的间距太大,没有可选的方案供青蛙跳跃过去。
思路
很朴素的深搜,虽然题目中的数据规模是 2000,没想到记忆化一下就过了。
深搜过程:
- 记录上一次的步长和位置,尝试找到可以跳到的所有位置
- 然后记录跳的步长,从下一个位置继续搜索
记忆化:
- 记录下从第
i
格出发且步长为j
的可能 - 避免多次尝试无用解
代码
最近在试着用 TS 写项目,所以就用算法顺手练一下语法(不过似乎在这种函数里和 JS 区分不大)
1 | function canCross(stones: number[]): boolean { |
4.28
633. 平方数之和
难度中等
给定一个非负整数
c
,你要判断是否存在两个整数a
和b
,使得a2 + b2 = c
。示例 1:
1
2
3 输入:c = 5
输出:true
解释:1 * 1 + 2 * 2 = 5示例 2:
1
2 输入:c = 3
输出:false示例 3:
1
2 输入:c = 4
输出:true示例 4:
1
2 输入:c = 2
输出:true示例 5:
1
2 输入:c = 1
输出:true
思路
两年前做过的第一到老题目了。
双指针,左指针初始值为 0
,右指针为 根号c
。
偏大右指针左移,偏小左指针右移,直到两个指针重合求出来的和还不满足,说明不存在。
代码
1 | var judgeSquareSum = function(c) { |
4.27
题目
938. 二叉搜索树的范围和
难度简单
给定二叉搜索树的根结点
root
,返回值位于范围[low, high]
之间的所有结点的值的和。示例 1:
1
2 输入:root = [10,5,15,3,7,null,18], low = 7, high = 15
输出:32示例 2:
1
2 输入:root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出:23
思路
利用二叉搜索树的性质:左 < 根 < 右
,在求和的时候进行剪枝。
如果根结点的值比题目给出的最小值
low
还要小,那么就只能往右子树里继续找。如果根结点的值比题目给出的最大值
high
还要大,那么就只能往左子树里继续找。否则,就需要向两边找。
简单是简单,但是自己写完才发现官方题解代码真优雅。
代码
1 | var rangeSumBST = function(root, low, high) { |
4.26
题目
1011. 在 D 天内送达包裹的能力
难度中等236
传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第
i
个包裹的重量为weights[i]
。每一天,我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。返回能在
D
天内将传送带上的所有包裹送达的船的最低运载能力。示例 1:
1
2
3
4
5
6
7
8
9
10
11 输入:weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出:15
解释:
船舶最低载重 15 就能够在 5 天内送达所有包裹,如下所示:
第 1 天:1, 2, 3, 4, 5
第 2 天:6, 7
第 3 天:8
第 4 天:9
第 5 天:10
请注意,货物必须按照给定的顺序装运,因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。示例 2:
1
2
3
4
5
6
7 输入:weights = [3,2,2,4,1,4], D = 3
输出:6
解释:
船舶最低载重 6 就能够在 3 天内送达所有包裹,如下所示:
第 1 天:3, 2
第 2 天:2, 4
第 3 天:1, 4示例 3:
1
2
3
4
5
6
7 输入:weights = [1,2,3,1,1], D = 4
输出:3
解释:
第 1 天:1
第 2 天:2
第 3 天:3
第 4 天:1, 1
思路
下意识看到 在 * 天内 ** 的能力
还以为是动态规划,看了一遍题目之后发现遍历就行。
遍历完发现超时了,超时完看题解发现要用二分 🤒
题目要返回的是最低运载能力,左边界设为最大包裹的重量,右边界设为所有包裹的总重量。
二分的依据是判断是按照当前的运载能力是否能在 D 天内完成:
- 如果不能,说明运力偏小,左边界右移
- 如果能,说明运力偏大,右边界左移
直到左边界超过右边界时,左边界就是所需的最小运力。
代码
1 | var shipWithinDays = function(weights, D) { |
4.25
题目
897. 递增顺序搜索树
难度简单166
给你一棵二叉搜索树,请你 按中序遍历 将其重新排列为一棵递增顺序搜索树,使树中最左边的节点成为树的根节点,并且每个节点没有左子节点,只有一个右子节点。
示例 1:
1
2 输入:root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
输出:[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]示例 2:
1
2 输入:root = [5,1,7]
输出:[1,null,5,null,7]
思路
整体思路就是中序遍历,不过有两种建树方式。
- 先中序遍历一遍原树,然后把遍历到的结点值逐个存入数组,最终遍历完一棵树的数组就是一个递增数列。根据该数组,逐个新建结点,生成新树。
- 在中序遍历的同时改变原树上结点的指向,原地修改。
代码
两种思路都比较简单,这里就贴个第二种。
1 | var increasingBST = function(root) { |
4.24
题目
377. 组合总和 Ⅳ
难度中等
给你一个由 不同 整数组成的数组
nums
,和一个目标整数target
。请你从nums
中找出并返回总和为target
的元素组合的个数。题目数据保证答案符合 32 位整数范围。
示例 1:
1
2
3
4
5
6
7
8
9
10
11
12 输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。示例 2:
1
2 输入:nums = [9], target = 3
输出:0提示:
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums
中的所有元素 互不相同1 <= target <= 1000
思路1
第一想法 DFS,写出来就超时了。
因为像是 nums = [2, 1, 3], target = 35
的情况,递归实在太久了。
代码1
1 | var combinationSum4 = function(nums, target) { |
思路2
又又又是动态规划,本质上是一个完全背包问题。
这篇题解针不戳。
- DP table:开辟一个长度是
target + 1
的数组,dp[i]
表示的是和为i
的组合数。 - Base case:
dp[0] = 1
,表示和为 0 的组合只有一种,就是空数组。 - 动态转移方程
- 从
dp[1]
求到dp[target]
- 每次算
dp[i]
的时候,遍历一遍我们手头的数组nums
- 若
nums[j] <= i
,说明当前的这个数可以与之前某个的组合相结合,因此令dp[i] += dp[nums[j] - i]
- 从
代码2
1 | var combinationSum4 = function(nums, target) { |
4.23
题目
368. 最大整除子集
难度中等
给你一个由 无重复 正整数组成的集合
nums
,请你找出并返回其中最大的整除子集answer
,子集中每一元素对(answer[i], answer[j])
都应当满足:
answer[i] % answer[j] == 0
,或answer[j] % answer[i] == 0
如果存在多个有效解子集,返回其中任何一个均可。
示例 1:
1
2
3 输入:nums = [1,2,3]
输出:[1,2]
解释:[1,3] 也会被视为正确答案。示例 2:
1
2 输入:nums = [1,2,4,8]
输出:[1,2,4,8]
思路
初看题目要求子集,下意识是想去用 DFS 的,但是发现数组规模是 1000,而且 DFS 似乎也不太好写,求助于官方题解后得知是用 DP。
之所以是 DP,是因为整除的性质:
- 对于一个给定的整除子集而言,如果另外有一个数是该子集中最大数的整数倍,那么把这个数加入子集也是合法的。
由于有这条性质,所以数字的大小和我们的遍历应该是关系的,先对数组排序可以简化后续步骤。
同时基于这条性质,也可以联想到 DP table 的定义和状态转移方程。
假设
dp[i]
表示在nums[0:i]
子数组中包含nums[i]
在内的最大整除子集数。我们需要遍历比当前数字小的所有数字,根据上面的整除性质,可以很容易得到
dp[i]
Base case:由于数字自身整除于自身,所以 dp[i]
应该初始化为 1。
在进行动规后,我们就获得了一个 dp
数组,例如题目中的 nums = [1, 2, 3], dp = [1, 2, 2]
。
但是题目要求的并不是最大整除子集的规模,而是子集本身,所以我们现在可以根据子集数求子集。
首先确定最大子集的规模 maxSize
,通过倒序遍历 dp[i]
,找到 dp[i] = maxSize
的 nums[i]
,加入到结果自己。令 maxSize--
,继续往前找,找到能整除上一个数且 dp[i] = maxSize
的数。
代码
1 | var largestDivisibleSubset = function(nums) { |
4.22
今日没追求,暴力解困难
题目
363. 矩形区域不超过 K 的最大数值和
难度困难
给你一个
m x n
的矩阵matrix
和一个整数k
,找出并返回矩阵内部矩形区域的不超过k
的最大数值和。题目数据保证总会存在一个数值和不超过
k
的矩形区域。示例 1:
1
2
3 输入:matrix = [[1,0,1],[0,-2,3]], k = 2
输出:2
解释:蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2,且 2 是不超过 k 的最大数字(k = 2)。示例 2:
1
2 输入:matrix = [[2,2,-1]], k = 3
输出:3
思路
首先需要将一维前缀和数组扩展到二维,然后遍历整个二维数组的所有子数组,找出小于 k
的最大和。
代码
1 | var maxSumSubmatrix = function(matrix, k) { |
4.21
题目
91. 解码方法
难度中等
一条包含字母
A-Z
的消息通过以下映射进行了 编码 :
1
2
3
4 'A' -> 1
'B' -> 2
...
'Z' -> 26要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,
"11106"
可以映射为:
"AAJF"
,将消息分组为(1 1 10 6)
"KJF"
,将消息分组为(11 10 6)
注意,消息不能分组为
(1 11 06)
,因为"06"
不能映射为"F"
,这是由于"6"
和"06"
在映射中并不等价。给你一个只含数字的 非空 字符串
s
,请计算并返回 解码 方法的 总数 。题目数据保证答案肯定是一个 32 位 的整数。
示例 1:
1
2
3 输入:s = "12"
输出:2
解释:它可以解码为 "AB"(1 2)或者 "L"(12)。
思路1
利用 BFS,尝试遍历进行所有可能性的。
每个位置可以有两种向下延申的情况:
- 往后扩展一位
- 往后扩展两位
会进行大量的重复计算,导致这个解法超时
代码1
1 | var numDecodings = function(s) { |
思路2
动态规划,利用当前数和前一个数的大小,迭代计算。
- DP table:
dp = new Array(n+1).fill(0)
,数组长度为字符串长度+1
,dp[i]
表示s[0:i]
的解码方法数。 - Base case:
dp[0] = 1
,表示我们假设空字符串有一种解码方式。 - 动态转移方程:从
i = 1 to n
,当前的字符为s[i-1]
,前一个字符为s[i-2]
- 如果当前的字符本身不为0,说明他自己就可以进行解码,因此
s[0:i]
的解码方式和s[0:i-1]
的解码方式数相同。 - 如果当前的字符可以和前一个字符组成一个
10-26
的数,那么此时s[0:i]
的解码方式和s[0:i-2]
的解码方式数相同。
- 如果当前的字符本身不为0,说明他自己就可以进行解码,因此
代码2
1 | var numDecodings = function(s) { |
4.20
KMP???告辞
题目
28. 实现 strStr()
难度简单
实现 strStr() 函数。
给你两个字符串
haystack
和needle
,请你在haystack
字符串中找出needle
字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回-1
。说明:
当
needle
是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。对于本题而言,当
needle
是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。示例 1:
1
2 输入:haystack = "hello", needle = "ll"
输出:2示例 2:
1
2 输入:haystack = "aaaaa", needle = "bba"
输出:-1示例 3:
1
2 输入:haystack = "", needle = ""
输出:0
思路
不搞竞赛,暴力就完事儿了。
代码
1 | var strStr = function(haystack, needle) { |
4.19
题目
27. 移除元素
难度简单
给你一个数组
nums
和一个值val
,你需要 原地 移除所有数值等于val
的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用
O(1)
额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
1
2
3 输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。示例 2:
1
2
3 输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
思路
和昨天类似,也是双指针,直接上代码。
代码
1 | var removeElement = function(nums, val) { |
4.18
蓝桥杯考完了,10 道做出来 7 道 🤒 也不知道对不对。
题目
26. 删除有序数组中的重复项
难度简单
给你一个有序数组
nums
,请你** 原地** 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以**「引用」**方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
1
2
3
4
5
6
7
8 // nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}示例 1:
1
2
3 输入:nums = [1,1,2]
输出:2, nums = [1,2]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
思路
经典老题了,双指针,把非重复的数字直接放到数组前部即可。
代码
1 | class Solution: |
4.17
题目
220. 存在重复元素 III
难度中等
给你一个整数数组
nums
和两个整数k
和t
。请你判断是否存在两个下标i
和j
,使得abs(nums[i] - nums[j]) <= t
,同时又满足abs(i - j) <= k
。如果存在则返回
true
,不存在返回false
。示例 1:
1
2 输入:nums = [1,2,3,1], k = 3, t = 0
输出:true示例 2:
1
2 输入:nums = [1,0,1,1], k = 1, t = 2
输出:true示例 3:
1
2 输入:nums = [1,5,9,1,5,9], k = 2, t = 3
输出:false
思路
因为题目中对两个数字的距离有规定,很容易想到的是双指针(滑动窗口)的思路。
- 开辟一个长度为
k + 1
的滑动窗口,从数组左边滑到右边 - 滑动的过程中,维护一个有序集合来存储当前窗口内的数
- 边滑动,边判断这个有序集合中是否存在满足条件要求的差值
<= t
的两个数
然而 Python 原生库不提供有序集合,于是放弃了这个方法
另一种思路是参考的官方题解,利用桶排序的思想。
设我们当前遍历的数为
x
,题目中允许的最大差值t
所以我们的思想是每隔
t+1
的范围划分一个桶,把每个数放到对应的桶中公式:
x = (t + 1) * a + b
,其中a
就是x
的桶序号边遍历数组,边判断当前数字的前一个桶和后一个桶以及自己桶里有没有满足的数字
同时,保证桶的个数小于等于
k
代码
1 | class Solution: |
4.16
动规周他来了!
因为周日要参加蓝桥杯,所以又换回 python 写代码了。
题目
87. 扰乱字符串
难度困难
使用下面描述的算法可以扰乱字符串
s
得到字符串t
:
- 如果字符串的长度为 1 ,算法停止
- 如果字符串的长度 > 1 ,执行下述步骤:
- 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串
s
,则可以将其分成两个子字符串x
和y
,且满足s = x + y
。- 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即,在执行这一步骤之后,
s
可能是s = x + y
或者s = y + x
。- 在
x
和y
这两个子字符串上继续从步骤 1 开始递归执行此算法。给你两个 长度相等 的字符串
s1
和s2
,判断s2
是否是s1
的扰乱字符串。如果是,返回true
;否则,返回false
。示例 1:
1
2
3
4
5
6
7
8
9
10
11 输入:s1 = "great", s2 = "rgeat"
输出:true
解释:s1 上可能发生的一种情形是:
"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" // 随机决定:「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" // 随机决定:第一组「交换两个子字符串」,第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法,将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定:「保持这两个子字符串的顺序不变」
算法终止,结果字符串和 s2 相同,都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形,可以认为 s2 是 s1 的扰乱字符串,返回 true示例 2:
1
2 输入:s1 = "abcde", s2 = "caebd"
输出:false示例 3:
1
2 输入:s1 = "a", s2 = "a"
输出:true提示:
s1.length == s2.length
1 <= s1.length <= 30
s1
和s2
由小写英文字母组成
思路
动规困难题,最终还是参考了题解。
先确定动规的几个关键要素:
DP table
- 动规的核心思想就是
大化小,小化了
,本题的最终目标是要知道s1
能否被扰乱成s2
,在什么子条件下我们会知道最终答案呢? - 如果我们把
s1
划分成s11 + s12
,s2
划分成s21 + s22
,若满足以下条件之一,我们可以确定s1
能被扰乱成s2
s11
可以被扰乱成s21
,s12
可以被扰乱成s22
s11
可以被扰乱成s22
,s12
可以被扰乱成s21
- 由于被扰乱的字符串必定是等长的,我们只需要确定起始位置和字符串长度来表示状态。
dp[i][j][l]
的含义:s1[i:i+l]
能否扰乱获得s2[j:j+l]
- 动规的核心思想就是
Base case
- 每个相同的字符必定是可扰乱的
状态转移方程
- 在之前定义 DP table 的时候,其实就已经写出了状态转移的思想
- 枚举
k in range(1, l)
,表示切割的位置,下面两者之一为真则dp[i][j][l]
为真dp[i][j][k] and dp[i + k][j + k][l - k]
dp[i][j + l - k][k] and dp[i + k][j][l - k]
代码
1 | class Solution: |
4.15
题目
213. 打家劫舍 II
难度中等
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,能够偷窃到的最高金额。
示例 1:
1
2
3 输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。示例 2:
1
2
3
4 输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。示例 3:
1
2 输入:nums = [0]
输出:0提示:
1 <= nums.length <= 100
0 <= nums[i] <= 1000
思路
经典动规,和传统的打家劫舍的差别在于不能同时偷头尾两家,所以将头尾拆开考虑。
第一次遍历[0, n-2]
,第二次遍历 [1, n-1]
,找出最大值。
先定义 dp table
: dp[i]
表示从第 0
家开始,打劫到第 i
家时,所获得的最大金额。
动态转移方程:dp[i] = max(dp[i-2] + nums[i], dp[i-1])
,偷 i-2 和 i
或者 偷 i-1
,两者选最大值。
代码
1 | var rob = function(nums) { |
4.14
题目
208. 实现 Trie (前缀树)
难度中等
Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
请你实现 Trie 类:
Trie()
初始化前缀树对象。void insert(String word)
向前缀树中插入字符串word
。boolean search(String word)
如果字符串word
在前缀树中,返回true
(即,在检索之前已经插入);否则,返回false
。boolean startsWith(String prefix)
如果之前已经插入的字符串word
的前缀之一为prefix
,返回true
;否则,返回false
。示例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14 输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True提示:
1 <= word.length, prefix.length <= 2000
word
和prefix
仅由小写英文字母组成insert
、search
和startsWith
调用次数 总计 不超过3 * 104
次
思路
数据结构题,能理解这棵树长什么样子就很容易画出来。
一般无非两种思路,一种是定义 TrieNode(字典树节点)
,另一种是直接用哈希表(数组)。
JS 的语法就有点微妙,所以参考官方题解写的这个代码一开始有些费解。
代码
1 | var Trie = function() { |
4.13
题目
783. 二叉搜索树节点最小距离
难度简单1
给你一个二叉搜索树的根节点
root
,返回 树中任意两不同节点值之间的最小差值 。示例 1:
1
2 输入:root = [4,2,6,1,3]
输出:1示例 2:
1
2 输入:root = [1,0,48,null,null,12,49]
输出:1提示:
- 树中节点数目在范围
[2, 100]
内0 <= Node.val <= 105
思路
利用二叉搜索树的特性,node.left.val < node.val < node.right.val
,通过中序遍历一棵二叉搜索树就可以得到一个递增的序列。
有了这个递增序列之后,就很容易寻找任意两个结点的最小差值了。
代码
1 | var minDiffInBST = function(root) { |
4.12
题目
179. 最大数
难度中等
给定一组非负整数
nums
,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。**注意:**输出结果可能非常大,所以你需要返回一个字符串而不是整数。
示例 1:
1
2 输入:nums = [10,2]
输出:"210"示例 2:
1
2 输入:nums = [3,30,34,5,9]
输出:"9534330"示例 3:
1
2 输入:nums = [1]
输出:"1"示例 4:
1
2 输入:nums = [10]
输出:"10"提示:
1 <= nums.length <= 100
0 <= nums[i] <= 109
思路
有脑筋急转弯内味了,参考了题解。
首先要知道肯定需要对 nums
排序,那么要确定 x
和 y
哪个应该放到更前面,我们可以直接通过以下两个字符串的值来确定
x + y
y + x
注意,这边做的都是字符串的拼接,不是单纯加减
如果前者大,那么 x
就放前面,否则放后面。
对排完序之后的数组进行拼接即可得到最终答案。
当然,也有可能出现数组全为 0 的情况,需要额外判断。
代码
1 | var largestNumber = function(nums) { |
4.11
题目
264. 丑数 II
难度中等
给你一个整数
n
,请你找出并返回第n
个 丑数 。丑数 就是只包含质因数
2
、3
和/或5
的正整数。示例 1:
1
2
3 输入:n = 10
输出:12
解释:[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。示例 2:
1
2
3 输入:n = 1
输出:1
解释:1 通常被视为丑数。提示:
1 <= n <= 1690
思路
最小堆:先存后排序
一开始最小堆里存放的是 1,然后迭代
n-1
次,每次从最小堆中取出最小数,放回最小数的 2,3,5 倍。迭代完之后,堆顶的数,就是第
n
小的数(因为前n-1
个数已经被用掉了)三指针:先排序后存
初始化一个 0 数组,长度为
n
,第一个元素初始化为0
用三个指针
idx1, idx2, idx3
分别表示当前应该被乘2,3,5
的基数的位置,一开始都初始为0迭代
n-1
次,每次迭代中找到当前能添加的最小数,然后放到对应位置。
代码
1 | # 最小堆 |
1 | // 三指针 |
4.10
语法题
题目
263. 丑数
难度简单
给你一个整数
n
,请你判断n
是否为 丑数 。如果是,返回true
;否则,返回false
。丑数 就是只包含质因数
2
、3
和/或5
的正整数。示例 1:
1
2
3 输入:n = 6
输出:true
解释:6 = 2 × 3
代码
1 | var isUgly = function(n) { |
4.8
继续二分
题目
153. 寻找旋转排序数组中的最小值
难度中等
已知一个长度为
n
的数组,预先按照升序排列,经由1
到n
次 旋转 后,得到输入数组。例如,原数组nums = [0,1,2,4,5,6,7]
在变化后可能得到:
- 若旋转
4
次,则可以得到[4,5,6,7,0,1,2]
- 若旋转
4
次,则可以得到[0,1,2,4,5,6,7]
注意,数组
[a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]
。给你一个元素值 互不相同 的数组
nums
,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。示例 1:
1
2
3 输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。示例 2:
1
2
3 输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。示例 3:
1
2
3 输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。提示:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums
中的所有整数 互不相同nums
原来是一个升序排序的数组,并进行了1
至n
次旋转
思路
通过二分来不断约束,找到最小数的位置。
之所以只需要判断 nums[mid]
和 nums[right]
的原因是:
如果中间比右边大,说明最小数必定在右边数组中
1
2
3中
左
右如果中间比右边小,那么最小数必定在左边数组中
1
2
3左
右
中
参考:leetcode 题解
代码
1 | var findMin = function(nums) { |
4.7
题目
81. 搜索旋转排序数组 II
难度中等
已知存在一个按非降序排列的整数数组
nums
,数组中的值不必互不相同。在传递给函数之前,
nums
在预先未知的某个下标k
(0 <= k < nums.length
)上进行了 旋转 ,使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标 从 0 开始 计数)。例如,[0,1,2,4,4,4,5,6,6,7]
在下标5
处经旋转后可能变为[4,5,6,6,7,0,1,2,4,4]
。给你 旋转后 的数组
nums
和一个整数target
,请你编写一个函数来判断给定的目标值是否存在于数组中。如果nums
中存在这个目标值target
,则返回true
,否则返回false
。示例 1:
1
2 输入:nums = [2,5,6,0,0,1,2], target = 0
输出:true示例 2:
1
2 输入:nums = [2,5,6,0,0,1,2], target = 3
输出:false提示:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
- 题目数据保证
nums
在预先未知的某个下标上进行了旋转-104 <= target <= 104
思路
菜鸡写不出二分,只能官方题解了。
先说基础的思路:
- 普通的二分可以直接搜索有序数组,但是题目中给的是翻转后的数组,所以只能保证数组部分有序
- 但是我们确实只需要部分有序就能够对二分的范围进行约束
- 假设当前的左指针为
left
,右指针为right
,中指针mid = (left + right) // 2
,且此时的nums[mid] != target
- 此时
nums[left:mid]
和nums[mid:right]
其中之一必定是有序的- 如果
nums[left] <= nums[mid]
,就是左边有序 - 如果
nums[mid] <= nums[right]
,就是右边有序
- 如果
- 如果此时左边有序
- 若
nums[left] <= target < nums[mid]
,则区间向左约束right = mid - 1
- 否则区间向右约束
left = mid + 1
- 若
- 如果此时右边有序
- 若
nums[mid] < target <= nums[right]
,则区间向右约束 - 否则向左约束
- 若
在这个基础上,由于题目中给出的数组会重现重复数组,可能出现 [1, 0, 1, 1, 1]
,无法正确约束区间
参考官方题解给出的思路是,在 nums[left] == nums[mid] == nums[right]
时,直接将左指针右移一格,右指针左移一格,向中心约束。
代码
1 | var search = function(nums, target) { |
4.6
收到 offer 啦 🤗
题目
80. 删除有序数组中的重复项 II
难度中等
给你一个有序数组
nums
,请你** 原地** 删除重复出现的元素,使每个元素 最多出现两次 ,返回删除后数组的新长度。不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以**「引用」**方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
1
2
3
4
5
6
7
8 // nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}示例 1:
1
2
3 输入:nums = [1,1,1,2,2,3]
输出:5, nums = [1,1,2,2,3]
解释:函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。示例 2:
1
2
3 输入:nums = [0,0,1,1,1,1,2,3,3]
输出:7, nums = [0,0,1,1,2,3,3]
解释:函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。提示:
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums
已按升序排列
思路
快慢指针,这个思路真的🐂。
用慢指针指向合法的数组尾部,用快指针指向已经遍历过的数组尾部。
代码
1 | var removeDuplicates = function(nums) { |
4.5
简单题 😴
题目
88. 合并两个有序数组
难度简单
给你两个有序整数数组
nums1
和nums2
,请你将nums2
合并到nums1
中*,*使nums1
成为一个有序数组。初始化
nums1
和nums2
的元素数量分别为m
和n
。你可以假设nums1
的空间大小等于m + n
,这样它就有足够的空间保存来自nums2
的元素。示例 1:
1
2 输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]示例 2:
1
2 输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]提示:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[i] <= 109
思路
从 nums1
的尾部开始放数字,反向遍历数组,无需额外开辟数组。
代码
1 | var merge = function(nums1, m, nums2, n) { |
4.4
题目
781. 森林中的兔子
难度中等
森林中,每个兔子都有颜色。其中一些兔子(可能是全部)告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在
answers
数组里。返回森林中兔子的最少数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 示例:
输入: answers = [1, 1, 2]
输出: 5
解释:
两只回答了 "1" 的兔子可能有相同的颜色,设为红色。
之后回答了 "2" 的兔子不会是红色,否则他们的回答会相互矛盾。
设回答了 "2" 的兔子为蓝色。
此外,森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
因此森林中兔子的最少数量是 5: 3 只回答的和 2 只没有回答的。
输入: answers = [10, 10, 10]
输出: 11
输入: answers = []
输出: 0说明:
answers
的长度最大为1000
。answers[i]
是在[0, 999]
范围内的整数。
思路
哈希表 + 贪心,先按兔子回答的数字对兔子进行分组,再尽可能地把回答相同的数字分成一个颜色。
代码
1 | var numRabbits = function(answers) { |
4.3
字节不出所料,秒挂。
腾讯似乎有点希望?
题目
1143. 最长公共子序列
难度中等472
给定两个字符串
text1
和text2
,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回0
。一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
- 例如,
"ace"
是"abcde"
的子序列,但"aec"
不是"abcde"
的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1:
1
2
3 输入:text1 = "abcde", text2 = "ace"
输出:3
解释:最长公共子序列是 "ace" ,它的长度为 3 。示例 2:
1
2
3 输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc" ,它的长度为 3 。示例 3:
1
2
3 输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0 。提示:
1 <= text1.length, text2.length <= 1000
text1
和text2
仅由小写英文字符组成。
思路
动态规划:由于有两个变量,考虑使用二维的动态规划。
开辟一个二维数组 dp
记录 dp[i][j]
代表 text1[0:i]
和 text[0:j]
的最大公共子序列长度。
Base case:第一行和第一列全部初始化为 0
状态转移方程:如果 text1[i] == text2[j]
,则 dp[i][j] = dp[i-1][j-1] + 1
,否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
代码
1 | var longestCommonSubsequence = function(text1, text2) { |
4.2
题目
面试题 17.21. 直方图的水量
难度困难
给定一个直方图(也称柱状图),假设有人从上面源源不断地倒水,最后直方图能存多少水量?直方图的宽度为 1。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图,在这种情况下,可以接 6 个单位的水(蓝色部分表示水)。 感谢 Marcos 贡献此图。
示例:
1
2 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
思路
每个位置能储存的水的量,由它左侧的最高柱和右侧最高柱以及它本身的高度的决定。
例如,左侧最高 2,右侧最高 3,本身高度为 1,那么它能存的水就是 min(2, 3) - 1 = 1
有两种方式来统计每根柱子的左右最高情况
- 开辟一个数组进行统计,时间复杂度
O(N)
,空间复杂度O(N)
- 双指针,一边遍历统计,时间复杂度
O(N)
,空间复杂度O(1)
代码
1 | class Solution: |
1 | var trap = function(height) { |
4.1
🐟人节快乐嗷
题目
1006. 笨阶乘
难度中等50
通常,正整数
n
的阶乘是所有小于或等于n
的正整数的乘积。例如,factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
。相反,我们设计了一个笨阶乘
clumsy
:在整数的递减序列中,我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符:乘法(*),除法(/),加法(+)和减法(-)。例如,
clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1
。然而,这些运算仍然使用通常的算术运算顺序:我们在任何加、减步骤之前执行所有的乘法和除法步骤,并且按从左到右处理乘法和除法步骤。另外,我们使用的除法是地板除法(floor division),所以
10 * 9 / 8
等于11
。这保证结果是一个整数。实现上面定义的笨函数:给定一个整数
N
,它返回N
的笨阶乘。示例 1:
1
2
3 输入:4
输出:7
解释:7 = 4 * 3 / 2 + 1示例 2:
1
2
3 输入:10
输出:12
解释:12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1提示:
1 <= N <= 10000
-2^31 <= answer <= 2^31 - 1
(答案保证符合 32 位整数。)
代码
标准栈解法
1 | /** |
if else
大法
1 | class Solution: |