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,用于存放遍历到的所有子集,同时需要往数组中首先加一个空数组,代表空集
  • 逐个遍历数组中的所有数,针对每个数字而言有两种情况
    1. 加入这个数
    2. 不加入这个数
  • 对于上一次遍历所获得所有集合,都需要实行这两个操作
  • 一般来说,假设原数组长度为 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function(nums) {
nums.sort()
let res = [[]]
let last = [-11]
for(let i = 0; i < nums.length; i++) {
// 每次有加入数字/不加入数字两个选项
const tmp = []
const nxt = []
for(let j = 0; j < res.length; j++){
tmp.push(res[j])
nxt.push(nums[i])
if(nums[i] != last[j]) {
tmp.push([...res[j],nums[i]])
nxt.push(-11)
}
}
res = tmp
last = nxt
}
return res
};

3.30

昨日事多,刷题没写日志

题目

74. 搜索二维矩阵

难度中等352

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

示例 1:

img

1
2
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true

示例 2:

img

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# 二维二分
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = (left + right) // 2
row, col = mid // n, mid % n
if matrix[row][col] < target:
left = mid + 1
elif matrix[row][col] > target:
right = mid - 1
else:
return True
return False

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 的中序遍历中至少存在一个下一个数字。

示例:

img

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
  • 最多调用 105hasNextnext 操作

进阶:

  • 你可以设计一个满足下述条件的解决方案吗?next()hasNext() 操作均摊时间复杂度为 O(1) ,并使用 O(h) 内存。其中 h 是树的高度。

思路

迭代,利用栈模拟递归

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* @param {TreeNode} root
*/
var BSTIterator = function(root) {
this.stk = []
this.cur = root
};

/**
* @return {number}
*/
BSTIterator.prototype.next = function() {
while (this.cur) {
this.stk.push(this.cur)
this.cur = this.cur.left
}
this.cur = this.stk.pop()
const res = this.cur.val
this.cur = this.cur.right
return res
};

/**
* @return {boolean}
*/
BSTIterator.prototype.hasNext = function() {
return this.stk.length > 0 || this.cur !== null
};

3.27

美好的周六,哦哈哟

题目

61. 旋转链表

难度中等

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。

示例 1:

img

1
2
输入:head = [1,2,3,4,5], k = 2
输出:[4,5,1,2,3]

示例 2:

img

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var rotateRight = function(head, k) {
if (! head) {
return head
}
const dummy = new ListNode(0, head)
let fast = head
let slow = head
let cnt = 1
// 先将快指针往后移动k个
while (k>0) {
if (fast.next) {
fast = fast.next
cnt += 1
k -= 1
}
else {
fast = head
k -= 1
k %= cnt
}
}
// 两根指针同时往后移,直到快指针指向尾结点
while(fast.next) {
fast = fast.next
slow = slow.next
}
// 将慢指针后面的链表迁移到原头节点前
fast.next = dummy.next
dummy.next = slow.next
slow.next = null
return dummy.next
};

3.26

昨天每日一题的简化版。

题目

83. 删除排序链表中的重复元素

难度简单

存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除所有重复的元素,使每个元素 只出现一次

返回同样按升序排列的结果链表。

示例 1:

img

1
2
输入:head = [1,1,2]
输出:[1,2]

示例 2:

img

1
2
输入:head = [1,1,2,3,3]
输出:[1,2,3]

提示:

  • 链表中节点数目在范围 [0, 300]
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序排列

代码

1
2
3
4
5
6
7
8
9
10
11
12
var deleteDuplicates = function(head) {
const dummy = new ListNode(101, head)
let node = dummy
while(node.next) {
if(node.next.val == node.val) {
node.next = node.next.next
} else {
node = node.next
}
}
return dummy.next
};

3.25

题目

82. 删除排序链表中的重复元素 II

难度中等

存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除链表中所有存在数字重复情况的节点,只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

示例 1:

img

1
2
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]

示例 2:

img

1
2
输入:head = [1,1,1,2,3]
输出:[2,3]

提示:

  • 链表中节点数目在范围 [0, 300]
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序排列

思路

一次遍历

设置一个哑节点 dummy 放到 head 的前面,从 dummy 开始向后遍历。

当遇到后一个结点的值和后一个的后一个的结点的值一样的时候,就记录下后一个结点的值 x,然后把之后所有值为 x 的结点全部去掉。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var deleteDuplicates = function(head) {
const dummy = new ListNode(0)
dummy.next = head
let node = dummy
while(node.next && node.next.next) {
if(node.next.val == node.next.next.val) {
let x = node.next.val
while (node.next && node.next.val == x) {
node.next = node.next.next
}
} else {
node = node.next
}
}
return dummy.next
};

3.24

题目

456. 132模式

难度中等363

给你一个整数数组 nums ,数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]nums[j]nums[k] 组成,并同时满足:i < j < knums[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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
n = len(nums)
left_min = [0] * n
cur = nums[0]
for i in range(n):
cur = min(cur, nums[i])
left_min[i] = cur
stk = []
for j in range(n-1, -1, -1):
while stk and stk[-1] <= left_min[j]:
stk.pop()
if stk and stk[-1] < nums[j]:
return True
stk.append(nums[j])
return False

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]。

思路

  1. 递归:在初始化函数中就利用深搜把数组处理成扁平的
  2. 迭代:在 hasNext 方法中用栈模拟递归,每次把栈顶元素转换成数字之后再返回 True

代码

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
nums = []
def dfs(nestedList):
for nest in nestedList:
if nest.isInteger():
nums.append(nest.getInteger())
else:
dfs(nest.getList())
dfs(nestedList)
self.val = nums[::-1]


def next(self) -> int:
return self.val.pop()

def hasNext(self) -> bool:
if len(self.val):
return True
return False

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
self.stk = nestedList

def next(self) -> int:
return self.stk.pop(0).getInteger()

def hasNext(self) -> bool:
while self.stk:
if self.stk[0].isInteger():
return True
else:
nest = self.stk.pop(0)
self.stk = nest.getList() + self.stk

3.21

题目

73. 矩阵置零

难度中等428

给定一个 *m* x *n* 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法**。**

进阶:

  • 一个直观的解决方案是使用 O(*m**n*) 的额外空间,但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(*m* + *n*) 的额外空间,但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗?

示例 1:

img

1
2
输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]

示例 2:

img

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function(tokens) {
const nums = new Array()
const n = tokens.length
for (let i = 0; i < n; i++) {
const token = tokens[i]
if (isNumber(token)) {
nums.push(Number(token))
} else {
const num2 = nums.pop()
const num1 = nums.pop()
let res = 0
if (token == '+') {
res = num1 + num2
} else if(token == '-') {
res = num1 - num2
} else if (token == '*') {
res = num1 * num2
} else if (token == '/') {
res = parseInt(num1 / num2)
}
nums.push(res)
}
}
return nums[0]
};

const isNumber = (token) => {
return !(token == '+' || token == '-' || token == '*' || token == '/')
}

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
  • st 由英文字母组成

思路

动态规划,设字符串 s 长度为 mt 长度为 n

  • DP table:m+1 行,n+1 列,初始化为 0dp[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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m, n= len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# dp[i][j] 代表的意思是 s[i:] 和 t[j:] 的子序列数
for i in range(m+1):
# 最后一列初始化为 1
dp[i][n] = 1
for i in range(n):
# 最后一行初始化为 0
dp[m][i] = 0
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
if s[i] == t[j]:
dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
else:
dp[i][j] = dp[i+1][j]
return dp[0][0]

3.17

题目

118. 杨辉三角

难度简单

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number} numRows
* @return {number[][]}
*/
var generate = function(numRows) {
const res = []
for (let i = 0; i < numRows; i++) {
const arr = new Array(i+1).fill(1);
for(let j = 1; j < i; j++){
arr[j] = res[i-1][j-1] + res[i-1][j]
}
res.push(arr)
}
return res
};

3.15

久违的原题

题目

54. 螺旋矩阵

难度中等

给你一个 mn 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

示例 1:

img

1
2
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:

img

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. 模拟螺旋:想象成有一个小人从左上角出发,他的方向顺序分别是:[右,下,左,上],当即将撞到墙或者走上回头路的时候,小人都会非常机智地调整方向。
  2. 按圈迭代:将整个迷宫看成由若干个矩形边框组成,这个边框由最外层往最里层,逐渐缩小。每次只需要确定一个左上角,一个右下角,就可以很方便地遍历整个方框。我们依次迭代左上角和右下角的位置,直到两个点重合。

代码

模拟螺旋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
# 右 下 左 上
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
m, n = len(matrix), len(matrix[0])
visited = [[0]* n for _ in range(m)]
i, j, k = 0, 0, 0
res = []
res.append(matrix[0][0])
visited[0][0] = 1
x, y = 0, 1
for _ in range(m*n-1):
while not (0 <= i + x < m) or not(0 <= j + y < n) or visited[i+x][j+y]:
k = (k + 1) % 4
x, y = directions[k]
i += x
j += y
res.append(matrix[i][j])
visited[i][j] = 1
return res

按圈迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function(matrix) {
const res = new Array();
const m = matrix.length;
const n = matrix[0].length;
let left = 0, right = n - 1, bottom = 0, top = m - 1
while (left <= right && bottom <= top){
for (let i = left; i <= right; i++) res.push(matrix[bottom][i]);
for (let i = bottom + 1; i <= top; i++) res.push(matrix[i][right])
if (left < right && bottom < top) {
for (let i = right - 1; i > left; i--) res.push(matrix[top][i]);
for (let i = top ; i > bottom; i--) res.push(matrix[i][left]);
}
[left, right, bottom, top] = [left + 1, right - 1, bottom + 1, top - 1]
}
return res;
};

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
  • 最多调用 104putgetremove 方法

思路

和昨天代码相差无几,昨天是直接存 value,今天是存键值对 [key, value]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
* Initialize your data structure here.
*/
var MyHashMap = function() {
this.BASE = 769;
this.arr = new Array(this.BASE).fill(0).map(() => new Array());
};

MyHashMap.prototype.hash = function(key) {
return key % this.BASE;
}

/**
* value will always be non-negative.
* @param {number} key
* @param {number} value
* @return {void}
*/
MyHashMap.prototype.put = function(key, value) {
const h = this.hash(key);
for (const subArr of this.arr[h]) {
if (subArr[0] == key) {
subArr[1] = value;
return;
}
}
this.arr[h].push([key, value]);
};

/**
* Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
* @param {number} key
* @return {number}
*/
MyHashMap.prototype.get = function(key) {
const h = this.hash(key);
for (const subArr of this.arr[h]){
if (subArr[0] == key) {
return subArr[1];
}
}
return -1;
};

/**
* Removes the mapping of the specified value key if this map contains a mapping for the key
* @param {number} key
* @return {void}
*/
MyHashMap.prototype.remove = function(key) {
const h = this.hash(key);
const subs = this.arr[h];
for (let i = 0; i < subs.length; i++){
if(subs[i][0] == key) {
subs.splice(i, 1);
}
}
};

/**
* Your MyHashMap object will be instantiated and called as such:
* var obj = new MyHashMap()
* obj.put(key,value)
* var param_2 = obj.get(key)
* obj.remove(key)
*/

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
  • 最多调用 104addremovecontains

**进阶:**你可以不使用内建的哈希集合库解决此问题吗?

思路

无脑法:开辟一个长度为 10^6 + 1 的数组,然后把出现的数字 num 放到 index = num 的位置上去,也就是不做哈希映射。

有脑法:去一个质数,把出现的数字 num 放到 index = num mod 769 的一个链表上去。

代码

无脑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MyHashSet:

def __init__(self):
"""
Initialize your data structure here.
"""
self.cnts = [0] * 1000001

def add(self, key: int) -> None:
self.cnts[key] = 1

def remove(self, key: int) -> None:
if self.cnts[key]:
self.cnts[key] -= 1


def contains(self, key: int) -> bool:
"""
Returns true if this set contains the specified element
"""
if self.cnts[key] > 0:
return True
else:
return False

有脑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
* Initialize your data structure here.
*/
var MyHashSet = function() {
this.BASE = 769;
this.data = new Array(this.BASE).fill(0).map(() => new Array());
};

/**
* @param {number} key
* @return {void}
*/
MyHashSet.prototype.add = function(key) {
const h = this.hash(key);
for (const element of this.data[h]) {
if (element == key) {
return
}
}
this.data[h].push(key);
};

/**
* @param {number} key
* @return {void}
*/
MyHashSet.prototype.remove = function(key) {
const h = this.hash(key);
const d = this.data[h];
for (let i = 0; i < d.length; i++) {
if (d[i] == key) {
d.splice(i, 1)
return
}
}
};

/**
* Returns true if this set contains the specified element
* @param {number} key
* @return {boolean}
*/
MyHashSet.prototype.contains = function(key) {
const h = this.hash(key);
const d = this.data[h];
for (let i = 0; i < d.length; i++) {
if (d[i] == key) {
return true
}
}
return false
};

MyHashSet.prototype.hash = function(key) {
return key % this.BASE;
}

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

思路

官方题解,这个方法针不戳,偷一张图过来。

fig1

根据这个思路,我们只需要

  • 将初始槽位设为 1,可以理解为需要一个槽位放根节点,同时 # 也是合法的空树。
  • 遍历一遍结点数组,遇到非空结点就 ++,遇到空结点就 --
  • 如果遍历中发现槽位数小于 0,说明就构不成树了
  • 最后返回 槽位数 == 0

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isValidSerialization(self, preorder: str) -> bool:
nodes = preorder.split(",")
cnt = 1
for i in nodes:
if cnt <= 0:
return False
if i == '#':
cnt -= 1
else:
cnt += 1
return cnt == 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {string} preorder
* @return {boolean}
*/
var isValidSerialization = function(preorder) {
const nodes = preorder.split(",")
let cnt = 1;
for (let node of nodes) {
if (cnt <= 0) {
return false
}
if (node == '#') {
cnt -= 1
} else{
cnt += 1
}
}
return cnt == 0
};

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def calculate(self, s: str) -> int:
s = s.replace(" ", "") # 先去除字符串内的空格
s += "+" # 使得循环中能够处理最后一个项
n = len(s)
num = int()
nums = []
opt = "+"
for i in range(n):
ch = s[i]
if ch.isdigit():
num = num * 10 + int(ch)
else:
if opt == '+':
nums.append(num)
elif opt == '-':
nums.append(-num)
elif opt == '*':
nums.append(nums.pop() * num)
elif opt == '/':
nums.append(int(nums.pop() / num))
opt = s[i]
num = 0
return sum(nums)

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
  • 遍历到了 1opt = 1, num = 1, res = 0
  • 遍历到了 -,要对运算符进行取反,而且由于不是数字,所以对之前的结果进行计算,opt = -1, num = 0, res = 1
  • 遍历到了 (,将之前的运算符压入栈(因为括号内的运算符不能影响外界),stk = [1, -1]
  • 遍历到了 3,暂存数字,num = 3
  • 遍历到了 -,对栈顶运算符取反,由于栈顶原来是 -1,所以现在的运算符变成了 1,即加号;同时计算之前暂存的数字
  • 遍历到了 4,暂存数字
  • 遍历到了 ),将栈顶的操作符压出,因为括号外要维持原运算符,计算暂存的数字

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def calculate(self, s: str) -> int:
stk = [1] # 存储标点符号的栈
s = s.replace(" ", "")
res ,num, opt =0, 0, 1 # 默认初始的标点符号为 +
for i in s:
if i.isdigit():
num = num * 10 + int(i)
else:
res += num * opt
num = 0
if i == '+':
opt = stk[-1]
elif i == '-':
opt = -stk[-1]
elif i == '(':
stk.append(opt)
elif i == ')':
stk.pop()
res += num * opt
return res

3.9

题目

1047. 删除字符串中的所有相邻重复项

难度简单

给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例:

1
2
3
4
输入:"abbaca"
输出:"ca"
解释:
例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。

提示:

  1. 1 <= S.length <= 20000
  2. S 仅由小写英文字母组成。

思路

一开始竟然朝着偶数长度的回文串这个思路去想了,属于前几天的后遗症吧,要抛弃这种思维定势。

其实就是很纯粹的用栈去判断是否要抛弃当前字母罢了。

代码

1
2
3
4
5
6
7
8
9
10
class Solution:
def removeDuplicates(self, S: str) -> str:
n = len(S)
stk = []
for i in S:
if not stk or stk[-1] != i:
stk.append(i)
else:
stk.pop()
return "".join(stk)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {string} S
* @return {string}
*/
var removeDuplicates = function(S) {
const stk = new Array();
for (const ch of S) {
if(stk.length == 0 || stk[stk.length - 1] != ch){
stk.push(ch);
} else {
stk.pop();
}
}
return stk.join("")
};

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

  1. 第一次 DP 求出任意子串是否为回文串。

  2. 第二次 DP 求出最少需要分割多少次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
f = [[True]*n for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(i+1,n):
f[i][j] = f[i+1][j-1] and (s[i] == s[j])
dp = [float('inf')] * n
for i in range(n):
if f[0][i]:
dp[i] = 0
else:
for j in range(i):
if f[j+1][i]:
dp[i] = min(dp[i], dp[j] + 1)
return dp[n-1]

3.7

又是菜到中等题看题解的一天。

题目

131. 分割回文串

难度中等522

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

1
2
3
4
5
6
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]

思路

回溯(DFS)+ 动态规划

首先用动态规划的思想,求解出任意子串是否为回文串。

然后用 DFS 的方法,从头开始遍历字符串,在可能拆分成子串的时候进行递归。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def partition(self, s: str) -> List[List[str]]:
n = len(s)
dp = [[True] * n for _ in range(n)]
for i in range(n-1, -1, -1):
for j in range(i+1,n):
dp[i][j] = dp[i+1][j-1] and (s[i] == s[j])

res, tmp = [], []
def dfs(i):
if i == n:
res.append(tmp[:])
return
for j in range(i, n):
if dp[i][j]:
tmp.append(s[i:j+1])
dfs(j+1)
tmp.pop()
dfs(0)
return res

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
2
3
4
5
6
7
8
9
10
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
stk, res = [], [-1 for _ in range(n)]
for i in range(n*2 - 1):
index = i % n
while stk and nums[stk[-1]] < nums[index]:
res[stk.pop()] = nums[index]
stk.append(index)
return res

3.5

easy!

题目

232. 用栈实现队列

难度简单

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作(pushpoppeekempty):

实现 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
  • 最多调用 100pushpoppeekempty
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)

思路

双栈模拟队列,似乎之前做过一个双队列模拟栈的,所以很快想到了这个方法。

虽然两个都是栈,但是我们使用的时候,第二个栈的逻辑是按照队列的倒叙考虑的。

对于 push 操作,所有的元素放到 stk1 中。

对于 pop 操作,由于需要返回的是队首的元素,也就是第一个进栈的元素,因此需要把 stk1 中的所有元素依次压出并压入 stk2。这样就实现了一个倒序的队列。即 stk2 的栈顶是队首元素,队伍依次从栈顶排到栈底,这样子出队顺序就合理了。因此 popstk2 的栈顶元素即可。

对于 peek 操作,同上。

对于 empty 操作,只需要判断当前两个队列是否均为空。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class MyQueue:

def __init__(self):
"""
Initialize your data structure here.
"""
self.stk1 = []
self.stk2 = []


def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stk1.append(x)


def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if not self.stk2:
while self.stk1:
self.stk2.append(self.stk1.pop())
return self.stk2.pop()



def peek(self) -> int:
"""
Get the front element.
"""
if not self.stk2:
while self.stk1:
self.stk2.append(self.stk1.pop())
return self.stk2[-1]




def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return len(self.stk1)+len(self.stk2) == 0



# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

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
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key = lambda x:(x[0], -x[1]))
if not envelopes: return 0
f = [envelopes[0][1]]
for i in range(1, len(envelopes)):
if (num := envelopes[i][1]) > f[-1]:
f.append(num)
else:
index = bisect.bisect_left(f, num) # 找到num可以插入的位置
f[index] = num
return len(f)

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number} num
* @return {number[]}
*/
var countBits = function(num) {
const res = new Array(num + 1).fill(0);
for(let i = 1; i <= num; i++) {
if (i % 2 == 1){
res[i] = res[i-1] + 1;
} else {
res[i] = res[i/2];
}
}
return res
};
1
2
3
4
5
6
7
8
9
class Solution:
def countBits(self, num: int) -> List[int]:
res = [0]*(num+1)
for i in range(1,num+1):
if i % 2 == 1:
res[i] = res[i-1] + 1
else:
res[i] = res[i//2]
return res

3.2

真就准备前缀和月呗。

题目

304. 二维区域和检索 - 矩阵不可变

难度中等

给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2)。

Range Sum Query 2D 上图子矩阵左上角 (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

说明:

  1. 你可以假设矩阵不可变。
  2. 会多次调用 sumRegion 方法*。*
  3. 你可以假设 row1 ≤ row2 且 col1 ≤ col2。

思路

是昨天题目的二维版本,很明显有两种解法。

  1. 看作是多行的一维前缀和数组,构造函数时间复杂度为 O(mn), 查询区域和的时间复杂度为 O(N)
  2. 直接看作二维的前缀和数组,即每一个位置的数代表的是从左上角加到这个位置的总和。构造函数时间复杂度 O(mn),查询区域和的时间复杂度 O(1)

我为了继续熟悉 JS 语法,就使用了简单的第一种方法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* @param {number[][]} matrix
*/
var NumMatrix = function(matrix) {
const m = matrix.length;
if(m>0){
const n = matrix[0].length;
this.allSums = new Array(m).fill(0).map(() => new Array(n + 1).fill(0));
for(let i = 0;i<m;i++){
for (let j = 1;j<n+1;j++){
this.allSums[i][j] = this.allSums[i][j-1] + matrix[i][j-1];
}
}
}

};

/**
* @param {number} row1
* @param {number} col1
* @param {number} row2
* @param {number} col2
* @return {number}
*/
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
let res = 0;
for(let i = row1; i <= row2; i++){
res += this.allSums[i][col2+1]-this.allSums[i][col1];
}
return res;
};

/**
* Your NumMatrix object will be instantiated and called as such:
* var obj = new NumMatrix(matrix)
* var param_1 = obj.sumRegion(row1,col1,row2,col2)
*/

3.1

题目

303. 区域和检索 - 数组不可变

难度简单

给定一个整数数组 nums,求出数组从索引 iji ≤ j)范围内元素的总和,包含 ij 两点。

实现 NumArray 类:

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 从索引 iji ≤ j)范围内元素的总和,包含 ij 两点(也就是 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
  • 最多调用 104sumRange 方法

思路

前缀和数组,利用一个数组来记录数组前n项的和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class NumArray:

def __init__(self, nums: List[int]):
sums = [0]
for i in nums:
sums.append(i+sums[-1])
self.sums = sums

def sumRange(self, i: int, j: int) -> int:
return self.sums[j+1]-self.sums[i]


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
const n = nums.length;
this.sums = new Array(nums.length+1).fill(0);
for(let i = 1;i<n+1;i++){
this.sums[i] = this.sums[i-1] + nums[i-1];
}
};

/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i, j) {
return this.sums[j+1]-this.sums[i];
};

/**
* Your NumArray object will be instantiated and called as such:
* var obj = new NumArray(nums)
* var param_1 = obj.sumRange(i,j)
*/