2021年3月刷题日志
3.31
还没等到 MS 的正式 offer 🤦♂️
题目
90. 子集 II
难度中等
给你一个整数数组
nums
,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例 1:
1
2 输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2:
1
2 输入:nums = [0]
输出:[[],[0]]提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
思路
迭代法
- 新建一个空数组
res
,用于存放遍历到的所有子集,同时需要往数组中首先加一个空数组,代表空集 - 逐个遍历数组中的所有数,针对每个数字而言有两种情况
- 加入这个数
- 不加入这个数
- 对于上一次遍历所获得所有集合,都需要实行这两个操作
- 一般来说,假设原数组长度为
n
第一次res
会变成长度1 + 1
,第二次会变成1 + 4
… - 但是题目中的
nums
中可能出现重复整数,所以需要想办法规避掉重复的子集的添加
重复子集判断
首先需要对数组
nums
进行排序,保证是按顺序遍历的数字我们在每次遍历的时候维护一个数组
last
,用于记录当前res
中的每个子集在上一次遍历的时候加入的数字例如针对
[1, 2, 2]
而言- 第一遍:
res = [[], [1]], last = [1, -11]
- 第二遍:
res = [[], [1], [2], [1,2]], last = [2, 2, -11, -11]
- 第三遍:
res = [[], [1], [2], [1,2], [2,2], [1,2,2]], last = [2, 2, 2, 2, -11, -11]
- 第一遍:
由于数字的范围是
[-10, 10]
,所以这里我用-11
来表示该子集在上次遍历的时候没有新加入数字
代码
1 | /** |
3.30
昨日事多,刷题没写日志
题目
74. 搜索二维矩阵
难度中等352
编写一个高效的算法来判断
m x n
矩阵中,是否存在一个目标值。该矩阵具有如下特性:
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
1
2 输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true示例 2:
1
2 输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
思路
两周之前刷过的一道题,写两种思路
- 一维的二分
- 先根据第一列数字确定
target
可能出现的行 - 再到对应行,利用
index
(本质是二分),寻找target
- 先根据第一列数字确定
- 二维的二分
- 可以把二维数组的每行抽出来拼到一起,抽象出来之后对这个二维数组本身直接二分搜索即可
代码
1 | class Solution: |
3.28
题目
173. 二叉搜索树迭代器
难度中等
实现一个二叉搜索树迭代器类
BSTIterator
,表示一个按中序遍历二叉搜索树(BST)的迭代器:
BSTIterator(TreeNode root)
初始化BSTIterator
类的一个对象。BST 的根节点root
会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字,且该数字小于 BST 中的任何元素。boolean hasNext()
如果向指针右侧遍历存在数字,则返回true
;否则返回false
。int next()
将指针向右移动,然后返回指针处的数字。注意,指针初始化为一个不存在于 BST 中的数字,所以对
next()
的首次调用将返回 BST 中的最小元素。你可以假设
next()
调用总是有效的,也就是说,当调用next()
时,BST 的中序遍历中至少存在一个下一个数字。示例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]
解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False提示:
- 树中节点的数目在范围
[1, 105]
内0 <= Node.val <= 106
- 最多调用
105
次hasNext
和next
操作进阶:
- 你可以设计一个满足下述条件的解决方案吗?
next()
和hasNext()
操作均摊时间复杂度为O(1)
,并使用O(h)
内存。其中h
是树的高度。
思路
迭代,利用栈模拟递归
代码
1 | /** |
3.27
美好的周六,哦哈哟
题目
61. 旋转链表
难度中等
给你一个链表的头节点
head
,旋转链表,将链表每个节点向右移动k
个位置。示例 1:
1
2 输入:head = [1,2,3,4,5], k = 2
输出:[4,5,1,2,3]示例 2:
1
2 输入:head = [0,1,2], k = 4
输出:[2,0,1]提示:
- 链表中节点的数目在范围
[0, 500]
内-100 <= Node.val <= 100
0 <= k <= 2 * 10^9
思路
经典快慢指针,和之前一道好像叫翻转链表的题目差不多,思路也几乎一样。区别是之前那道题的 k
是比链表小的,所以快指针不会超过尾结点。
- 快慢指针指向头结点
- 先将快指针往后移动
k
个位置- 由于题目说明
k <= 2*10^9
,所以直接往后移动k
个位置是很浪费时间的 - 考虑到结点数目小于 500,于是在第一次向后移动的时候,我们会记录下链表的长度
- 当快指针指向尾结点的时候,通过链表长度和
k
,我们可以直接计算出还应该往后移动多少个单位
- 由于题目说明
- 当快指针在合适的位置之后,令快慢指针同时向后移,直到快指针指向尾结点
- 这个时候把慢指针后面的那段链表拼接到头节点前面即可
代码
1 | var rotateRight = function(head, k) { |
3.26
昨天每日一题的简化版。
题目
83. 删除排序链表中的重复元素
难度简单
存在一个按升序排列的链表,给你这个链表的头节点
head
,请你删除所有重复的元素,使每个元素 只出现一次 。返回同样按升序排列的结果链表。
示例 1:
1
2 输入:head = [1,1,2]
输出:[1,2]示例 2:
1
2 输入:head = [1,1,2,3,3]
输出:[1,2,3]提示:
- 链表中节点数目在范围
[0, 300]
内-100 <= Node.val <= 100
- 题目数据保证链表已经按升序排列
代码
1 | var deleteDuplicates = function(head) { |
3.25
题目
82. 删除排序链表中的重复元素 II
难度中等
存在一个按升序排列的链表,给你这个链表的头节点
head
,请你删除链表中所有存在数字重复情况的节点,只保留原始链表中 没有重复出现 的数字。返回同样按升序排列的结果链表。
示例 1:
1
2 输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]示例 2:
1
2 输入:head = [1,1,1,2,3]
输出:[2,3]提示:
- 链表中节点数目在范围
[0, 300]
内-100 <= Node.val <= 100
- 题目数据保证链表已经按升序排列
思路
一次遍历
设置一个哑节点 dummy
放到 head
的前面,从 dummy
开始向后遍历。
当遇到后一个结点的值和后一个的后一个的结点的值一样的时候,就记录下后一个结点的值 x
,然后把之后所有值为 x
的结点全部去掉。
代码
1 | var deleteDuplicates = function(head) { |
3.24
题目
456. 132模式
难度中等363
给你一个整数数组
nums
,数组中共有n
个整数。132 模式的子序列 由三个整数nums[i]
、nums[j]
和nums[k]
组成,并同时满足:i < j < k
和nums[i] < nums[k] < nums[j]
。如果
nums
中存在 132 模式的子序列 ,返回true
;否则,返回false
。**进阶:**很容易想到时间复杂度为
O(n^2)
的解决方案,你可以设计一个时间复杂度为O(n logn)
或O(n)
的解决方案吗?示例 1:
1
2
3 输入:nums = [1,2,3,4]
输出:false
解释:序列中不存在 132 模式的子序列。示例 2:
1
2
3 输入:nums = [3,1,4,2]
输出:true
解释:序列中有 1 个 132 模式的子序列: [1, 4, 2] 。示例 3:
1
2
3 输入:nums = [-1,3,2,0]
输出:true
解释:序列中有 3 个 132 模式的的子序列:[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。提示:
n == nums.length
1 <= n <= 104
-109 <= nums[i] <= 109
代码
1 | class Solution: |
3.22
题目
341. 扁平化嵌套列表迭代器
难度中等
给你一个嵌套的整型列表。请你设计一个迭代器,使其能够遍历这个整型列表中的所有整数。
列表中的每一项或者为一个整数,或者是另一个列表。其中列表的元素也可能是整数或是其他列表。
示例 1:
1
2
3 输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,1,2,1,1]。示例 2:
1
2
3 输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,4,6]。
思路
- 递归:在初始化函数中就利用深搜把数组处理成扁平的
- 迭代:在
hasNext
方法中用栈模拟递归,每次把栈顶元素转换成数字之后再返回True
代码
递归
1 | class NestedIterator: |
迭代
1 | class NestedIterator: |
3.21
题目
73. 矩阵置零
难度中等428
给定一个
*m* x *n*
的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法**。**进阶:
- 一个直观的解决方案是使用
O(*m**n*)
的额外空间,但这并不是一个好的解决方案。- 一个简单的改进方案是使用
O(*m* + *n*)
的额外空间,但这仍然不是最好的解决方案。- 你能想出一个仅使用常量空间的解决方案吗?
示例 1:
1
2 输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]示例 2:
1
2 输入:matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
思路
跟着题目中的进阶方案思路去思考
- 一个直观的解决方案是使用
O(m*n)
的额外空间,但这并不是一个好的解决方案。
直接克隆原矩阵,然后遍历原矩阵,如果遇到 0
就将新矩阵中的对应行和列置 0
。
- 一个简单的改进方案是使用
O(m + n)
的额外空间,但这仍然不是最好的解决方案。
新建两个数组 rows, cols
,遍历一遍原矩阵存储需要被置 0
的行和列,然后根据这两个数组对行和列进行置 0
。
- 你能想出一个仅使用常量空间的解决方案吗?
看了题解,真是鬼才。用第一行和第一列的来作为我们刚刚设置的两个数组,标记需要被置 0
的行和列。不过需要另外设置两个变量来记录第一行和第一列中有没有原生的0。
题解中给出了只需要一个变量的解法,思路是
3.20
昨天的题目太降智了,没记下来。
题目
150. 逆波兰表达式求值
难度中等
根据 逆波兰表示法,求表达式的值。
有效的算符包括
+
、-
、*
、/
。每个运算对象可以是整数,也可以是另一个逆波兰表达式。说明:
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1:
1
2
3 输入:tokens = ["2","1","+","3","*"]
输出:9
解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9示例 2:
1
2
3 输入:tokens = ["4","13","5","/","+"]
输出:6
解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6示例 3:
1
2
3
4
5
6
7
8
9
10
11 输入:tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出:22
解释:
该算式转化为常见的中缀算术表达式为:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22提示:
1 <= tokens.length <= 104
tokens[i]
要么是一个算符("+"
、"-"
、"*"
或"/"
),要么是一个在范围[-200, 200]
内的整数
思路
Leetcode 直接把解题方法写在了问题的后面。
逆波兰表达式:
逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式,如
( 1 + 2 ) * ( 3 + 4 )
。 - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )
。
逆波兰表达式主要有以下两个优点:
- 去掉括号后表达式无歧义,上式即便写成
1 2 + 3 4 + *
也可以依据次序计算出正确结果。 - 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中。
我们直接跟着他的指示,用栈这么做就行了。记得上次遇到这个逆波兰表达式还是在大二上学期的数据结构课上,当时老师会让我们手动转成逆波兰和波兰表达式。
代码
1 | /** |
3.18
题目
115. 不同的子序列
难度困难
给定一个字符串
s
和一个字符串t
,计算在s
的子序列中t
出现的个数。字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,
"ACE"
是"ABCDE"
的一个子序列,而"AEC"
不是)题目数据保证答案符合 32 位带符号整数范围。
示例 1:
1
2
3
4
5
6
7
8
9
10
11 输入:s = "rabbbit", t = "rabbit"
输出:3
解释:
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^示例 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 输入:s = "babgbag", t = "bag"
输出:5
解释:
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。
(上箭头符号 ^ 表示选取的字母)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^提示:
0 <= s.length, t.length <= 1000
s
和t
由英文字母组成
思路
动态规划,设字符串 s
长度为 m
,t
长度为 n
- DP table:
m+1
行,n+1
列,初始化为0
,dp[i][j]
代表的是s[i:]
中子序列t[j:]
的个数。 - Base case:最后一列,即
j = n
的时候,目标子序列为空串,则子串数应该为1
;最后一行,即当i = m
的时候,无论目标子序列为何,自身都是空串,所以子串数为0
。 - 状态转移方程:考虑
dp[i][j]
的大小的时候,应该分两种递推的情况s[i] == t[j]
,此时当前的子序列是可以直接从各字符串的后一个位置递推过来dp[i][j] += dp[i+1][j+1]
,当然也可以从当前字符串的后一个位置递推过来dp[i][j] += dp[i+1][j]
s[i] != t[j]
,这个时候就必不能匹配当前位置,则只能dp[i][j] += dp[i+1][j]
代码
1 | class Solution: |
3.17
题目
118. 杨辉三角
难度简单
给定一个非负整数
numRows
,生成杨辉三角的前numRows
行。
代码
1 | /** |
3.15
久违的原题
题目
54. 螺旋矩阵
难度中等
给你一个
m
行n
列的矩阵matrix
,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。示例 1:
1
2 输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]示例 2:
1
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]提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
思路
- 模拟螺旋:想象成有一个小人从左上角出发,他的方向顺序分别是:
[右,下,左,上]
,当即将撞到墙或者走上回头路的时候,小人都会非常机智地调整方向。 - 按圈迭代:将整个迷宫看成由若干个矩形边框组成,这个边框由最外层往最里层,逐渐缩小。每次只需要确定一个左上角,一个右下角,就可以很方便地遍历整个方框。我们依次迭代左上角和右下角的位置,直到两个点重合。
代码
模拟螺旋
1 | class Solution: |
按圈迭代
1 | /** |
3.14
题目
706. 设计哈希映射
难度简单
不使用任何内建的哈希表库设计一个哈希映射(HashMap)。
实现
MyHashMap
类:
MyHashMap()
用空映射初始化对象void put(int key, int value)
向 HashMap 插入一个键值对(key, value)
。如果key
已经存在于映射中,则更新其对应的值value
。int get(int key)
返回特定的key
所映射的value
;如果映射中不包含key
的映射,返回-1
。void remove(key)
如果映射中存在key
的映射,则移除key
和它所对应的value
。示例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 输入:
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出:
[null, null, null, 1, -1, null, 1, null, -1]
解释:
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1); // 返回 1 ,myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3); // 返回 -1(未找到),myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]](更新已有的值)
myHashMap.get(2); // 返回 1 ,myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据,myHashMap 现在为 [[1,1]]
myHashMap.get(2); // 返回 -1(未找到),myHashMap 现在为 [[1,1]]提示:
0 <= key, value <= 106
- 最多调用
104
次put
、get
和remove
方法
思路
和昨天代码相差无几,昨天是直接存 value
,今天是存键值对 [key, value]
代码
1 | /** |
3.13
题目
705. 设计哈希集合
难度简单
不使用任何内建的哈希表库设计一个哈希集合(HashSet)。
实现
MyHashSet
类:
void add(key)
向哈希集合中插入值key
。bool contains(key)
返回哈希集合中是否存在这个值key
。void remove(key)
将给定值key
从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。示例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 输入:
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出:
[null, null, null, true, false, null, true, null, false]
解释:
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ,(未找到)
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // 返回 False ,(已移除)提示:
0 <= key <= 10^6
- 最多调用
104
次add
、remove
和contains
。**进阶:**你可以不使用内建的哈希集合库解决此问题吗?
思路
无脑法:开辟一个长度为 10^6 + 1
的数组,然后把出现的数字 num
放到 index = num
的位置上去,也就是不做哈希映射。
有脑法:去一个质数,把出现的数字 num
放到 index = num mod 769
的一个链表上去。
代码
无脑
1 | class MyHashSet: |
有脑
1 | /** |
3.12
昨天又收到面试📞,next Wed MS 二面
题目
331. 验证二叉树的前序序列化
难度中等
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如
#
。
1
2
3
4
5
6
7 _9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #例如,上面的二叉树可以被序列化为字符串
"9,3,4,#,#,1,#,#,2,#,6,#,#"
,其中#
代表一个空节点。给定一串以逗号分隔的序列,验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示
null
指针的'#'
。你可以认为输入格式总是有效的,例如它永远不会包含两个连续的逗号,比如
"1,,3"
。示例 1:
1
2 输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true示例 2:
1
2 输入: "1,#"
输出: false示例 3:
1
2 输入: "9,#,#,1"
输出: false
思路
官方题解,这个方法针不戳,偷一张图过来。
根据这个思路,我们只需要
- 将初始槽位设为
1
,可以理解为需要一个槽位放根节点,同时#
也是合法的空树。 - 遍历一遍结点数组,遇到非空结点就
++
,遇到空结点就--
- 如果遍历中发现槽位数小于
0
,说明就构不成树了 - 最后返回
槽位数 == 0
代码
1 | class Solution: |
1 | /** |
3.11
MS 一面总算是过去了,马马虎虎吧,至少让我看到了或许对实习生的要求不会特别高
题目
227. 基本计算器 II
难度中等
给你一个字符串表达式
s
,请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。
示例 1:
1
2 输入:s = "3+2*2"
输出:7示例 2:
1
2 输入:s = " 3/2 "
输出:1示例 3:
1
2 输入:s = " 3+5 / 2 "
输出:5提示:
1 <= s.length <= 3 * 105
s
由整数和算符('+', '-', '*', '/')
组成,中间由一些空格隔开s
表示一个 有效表达式- 表达式中的所有整数都是非负整数,且在范围
[0, 231 - 1]
内- 题目数据保证答案是一个 32-bit 整数
思路
用栈保存所有项,然后最后加起来,这里的项包括可以合并成一个数字的乘数法式子,比如 3 + 1 * 2 - 4
,最后栈中应该就是三项 [3, 2, -4]
。
遍历字符串,记录运算符和数字,并不断地压入栈,最后求栈的和即可。
代码
1 | class Solution: |
3.10
昨天突然通知今天晚上 MS 实习面试,给爷紧张坏了。
题目
224. 基本计算器
难度困难
实现一个基本的计算器来计算一个简单的字符串表达式
s
的值。示例 1:
1
2 输入:s = "1 + 1"
输出:2示例 2:
1
2 输入:s = " 2-1 + 2 "
输出:3示例 3:
1
2 输入:s = "(1+(4+5+2)-3)+(6+8)"
输出:23提示:
1 <= s.length <= 3 * 105
s
由数字、'+'
、'-'
、'('
、')'
、和' '
组成s
表示一个有效的表达式
思路
这道题因为没有乘法和除法,所以对于数值而言不需要用栈存储,只需要用栈存取运算符即可。
我们用 1
来代表 +
,用 -1
代表 +
,一开始默认为 1
。
以 1-(3-4)
为例
opt = 1, num = 0, res = 0
- 遍历到了
1
,opt = 1, num = 1, res = 0
- 遍历到了
-
,要对运算符进行取反,而且由于不是数字,所以对之前的结果进行计算,opt = -1, num = 0, res = 1
- 遍历到了
(
,将之前的运算符压入栈(因为括号内的运算符不能影响外界),stk = [1, -1]
- 遍历到了
3
,暂存数字,num = 3
- 遍历到了
-
,对栈顶运算符取反,由于栈顶原来是-1
,所以现在的运算符变成了1
,即加号;同时计算之前暂存的数字 - 遍历到了
4
,暂存数字 - 遍历到了
)
,将栈顶的操作符压出,因为括号外要维持原运算符,计算暂存的数字
代码
1 | class Solution: |
3.9
题目
1047. 删除字符串中的所有相邻重复项
难度简单
给出由小写字母组成的字符串
S
,重复项删除操作会选择两个相邻且相同的字母,并删除它们。在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例:
1
2
3
4 输入:"abbaca"
输出:"ca"
解释:
例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。提示:
1 <= S.length <= 20000
S
仅由小写英文字母组成。
思路
一开始竟然朝着偶数长度的回文串这个思路去想了,属于前几天的后遗症吧,要抛弃这种思维定势。
其实就是很纯粹的用栈去判断是否要抛弃当前字母罢了。
代码
1 | class Solution: |
1 | /** |
3.8
HAPPY WOMENS DAY
题目
132. 分割回文串 II
难度困难
给你一个字符串
s
,请你将s
分割成一些子串,使每个子串都是回文。返回符合要求的 最少分割次数 。
示例 1:
1
2
3 输入:s = "aab"
输出:1
解释:只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。示例 2:
1
2 输入:s = "a"
输出:0示例 3:
1
2 输入:s = "ab"
输出:1提示:
1 <= s.length <= 2000
s
仅由小写英文字母组成
思路
两次 DP
第一次 DP 求出任意子串是否为回文串。
第二次 DP 求出最少需要分割多少次。
代码
1 | class Solution: |
3.7
又是菜到中等题看题解的一天。
题目
131. 分割回文串
难度中等522
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
1
2
3
4
5
6 输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
思路
回溯(DFS)+ 动态规划
首先用动态规划的思想,求解出任意子串是否为回文串。
然后用 DFS 的方法,从头开始遍历字符串,在可能拆分成子串的时候进行递归。
代码
1 | class Solution: |
3.6
回归校园,网易云 start!
题目
503. 下一个更大元素 II
难度中等
给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。
示例 1:
1
2
3
4
5 输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;
数字 2 找不到下一个更大的数;
第二个 1 的下一个最大的数需要循环搜索,结果也是 2。注意: 输入数组的长度不会超过 10000。
思路
单调栈 + 循环数组。
单调栈,顾名思义就是从栈底到栈顶是单调递增或者单调递减的栈。本题中我们要构造的栈应该是递增栈。
栈中存放的是各个元素的下表,可以说是暂时还没有找到下一个更大元素的元素下标。
例如,[1, 2, 1]
,一开始栈为 []
,所以栈中应该放入下标 0
,当遍历到第二个元素的时候,发现 2 > 1
,所以这时候就找到了下标为 0
的元素的下一个更大元素,因此就把 0
压出栈,然后将下标 1
压入栈。
通过这个方法,还不能确保找到所有元素的下一个更大元素,例如 [3, 2, 1]
,光遍历一遍数组是不够的,需要遍历两边,因此会用到循环数组。
代码
1 | class Solution: |
3.5
easy!
题目
232. 用栈实现队列
难度简单
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作(
push
、pop
、peek
、empty
):实现
MyQueue
类:
void push(int x)
将元素 x 推到队列的末尾int pop()
从队列的开头移除并返回元素int peek()
返回队列开头的元素boolean empty()
如果队列为空,返回true
;否则,返回false
说明:
- 你只能使用标准的栈操作 —— 也就是只有
push to top
,peek/pop from top
,size
, 和is empty
操作是合法的。- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
进阶:
- 你能否实现每个操作均摊时间复杂度为
O(1)
的队列?换句话说,执行n
个操作的总时间复杂度为O(n)
,即使其中一个操作可能花费较长时间。示例:
1
2
3
4
5
6
7
8
9
10
11
12
13 输入:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 1, 1, false]
解释:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false提示:
1 <= x <= 9
- 最多调用
100
次push
、pop
、peek
和empty
- 假设所有操作都是有效的 (例如,一个空的队列不会调用
pop
或者peek
操作)
思路
双栈模拟队列,似乎之前做过一个双队列模拟栈的,所以很快想到了这个方法。
虽然两个都是栈,但是我们使用的时候,第二个栈的逻辑是按照队列的倒叙考虑的。
对于 push
操作,所有的元素放到 stk1
中。
对于 pop
操作,由于需要返回的是队首的元素,也就是第一个进栈的元素,因此需要把 stk1
中的所有元素依次压出并压入 stk2
。这样就实现了一个倒序的队列。即 stk2
的栈顶是队首元素,队伍依次从栈顶排到栈底,这样子出队顺序就合理了。因此 pop
掉 stk2
的栈顶元素即可。
对于 peek
操作,同上。
对于 empty
操作,只需要判断当前两个队列是否均为空。
代码
1 | class MyQueue: |
3.4
题目
354. 俄罗斯套娃信封问题
难度困难
给定一些标记了宽度和高度的信封,宽度和高度以整数对形式
(w, h)
出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。
说明:
不允许旋转信封。示例:
1
2
3 输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
思路
把两个维度的问题分开考虑,我们首先按照宽度对信封进行升序排列,为了确保不会重复考虑一个宽度会算多个信封,需要对同样宽度的信封按降序排列。
为了尝试找到高度的最长递增序列,首先将第一封信的高度放到结果序列中,然后遍历剩下所有的信封高度。
算法流程:
- 如果当前的高度比结果序列中的最后一个高度还要高,就直接放到序列尾部
- 否则,就把当前的高度插入到序列的合适的位置中去,通过二分查找的方式,找到当前高度能够插入的位置。这个位置保证了插入后的序列仍然是递增序列,而且这个位置的数可能会变小。
代码
1 | class Solution: |
3.3
题目
338. 比特位计数
难度中等
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
1
2 输入: 2
输出: [0,1,1]示例 2:
1
2 输入: 5
输出: [0,1,1,2,1,2]进阶:
- 给出时间复杂度为**O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)**内用一趟扫描做到吗?
- 要求算法的空间复杂度为O(n)。
- 你能进一步完善解法吗?要求在C++或任何其他语言中不使用任何内置函数(如 C++ 中的 __builtin_popcount)来执行此操作。
思路
动态规划,参考官方题解。
以 7 为例,它的二进制形式为 111,一共 3 个 1,也就是比 6 多了个末尾的 1。
由此可以联想到,对于奇数来说,它们的二进制 1 的个数都比它们的前一个数字多一个,即最后一个 0 => 1。
由此得到递推式1:res[i] = res[i-1] + 1
再次思考偶数的递推方式,对于 12 的二进制 1100,它的 1 的个数和 6 的二进制 110 相同,因为 12 是 6 的两倍,即左移一位。
因此,对于偶数来说,它们的二进制位数和它们除以二之后的数字相同。
由此得到递推式2:res[i] = res[i//2]
本题的 Base case 为 res[0] = 0
,因为 0 的二进制还是 0,没有1。
代码
1 | /** |
1 | class Solution: |
3.2
真就准备前缀和月呗。
题目
304. 二维区域和检索 - 矩阵不可变
难度中等
给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2)。
上图子矩阵左上角 (row1, col1) = **(2, 1)** ,右下角(row2, col2) = **(4, 3),**该子矩形内元素的总和为 8。示例:
1
2
3
4
5
6
7
8
9
10
11 给定 matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12说明:
- 你可以假设矩阵不可变。
- 会多次调用 sumRegion 方法*。*
- 你可以假设 row1 ≤ row2 且 col1 ≤ col2。
思路
是昨天题目的二维版本,很明显有两种解法。
- 看作是多行的一维前缀和数组,构造函数时间复杂度为
O(mn)
, 查询区域和的时间复杂度为O(N)
- 直接看作二维的前缀和数组,即每一个位置的数代表的是从左上角加到这个位置的总和。构造函数时间复杂度
O(mn)
,查询区域和的时间复杂度O(1)
我为了继续熟悉 JS 语法,就使用了简单的第一种方法。
代码
1 | /** |
3.1
题目
303. 区域和检索 - 数组不可变
难度简单
给定一个整数数组
nums
,求出数组从索引i
到j
(i ≤ j
)范围内元素的总和,包含i
、j
两点。实现
NumArray
类:
NumArray(int[] nums)
使用数组nums
初始化对象int sumRange(int i, int j)
返回数组nums
从索引i
到j
(i ≤ j
)范围内元素的总和,包含i
、j
两点(也就是sum(nums[i], nums[i + 1], ... , nums[j])
)示例:
1
2
3
4
5
6
7
8
9
10
11 输入:
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出:
[null, 1, -1, -3]
解释:
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))提示:
0 <= nums.length <= 104
-105 <= nums[i] <= 105
0 <= i <= j < nums.length
- 最多调用
104
次sumRange
方法
思路
前缀和数组,利用一个数组来记录数组前n项的和。
代码
1 | class NumArray: |
1 | /** |