KK's blog

LeetCode

<div>

You are given a 0-indexed 2D integer array questions where questions[i] = [points<sub>i</sub>, brainpower<sub>i</sub>].

The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you points<sub>i</sub> points but you will be unable to solve each of the next brainpower<sub>i</sub> questions. If you skip question i, you get to make the decision on the next question.

• For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:
  • If question 0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.
  • If instead, question 0 is skipped and question 1 is solved, you will earn 4 points but you will be unable to solve questions 2 and 3.

Return the maximum points you can earn for the exam.

Example 1:

<pre>Input: questions = [[3,2],[4,3],[4,4],[2,5]] Output: 5 Explanation: The maximum points can be earned by solving questions 0 and 3.

• Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
• Unable to solve questions 1 and 2
• Solve question 3: Earn 2 points Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points. </pre>

Example 2:

<pre>Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]] Output: 7 Explanation: The maximum points can be earned by solving questions 1 and 4.

• Skip question 0
• Solve question 1: Earn 2 points, will be unable to solve the next 2 questions
• Unable to solve questions 2 and 3
• Solve question 4: Earn 5 points Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points. </pre>

Constraints:

• 1 <= questions.length <= 10<sup>5</sup>
• questions[i].length == 2
• 1 <= points<sub>i</sub>, brainpower<sub>i</sub> <= 10<sup>5</sup>

</div>

题目大意：

(points, brainpower)解决一个问题得到points分，但是接下来的brainpower个问题都不能回答。求最大分数

一维DP解题思路(推荐)：

类似于LeetCode 198 House Robber，但此不再是固定的相邻不能偷，而是动态多个不能偷。
这题求最值，且数组有序访问，暴力法是多项式复杂度，所以考虑用DP。详见解法二。考虑优化算法二
首先考虑用累计dp，但是即使这样，由于前n-1个问题每个不能回答的范围都不同，并不能容易由第n-1个累计DP获得dp[n]
巧妙地利用从后往前计算，这样dp值不能回答范围包含在了已经计算的dp值中，如计算dp[3] <- dp[i + questions[3][1] + 1] + questions[3][0], 后者最大的话，当前结果也是最大，符合归纳条件。

解题步骤：

N/A

注意事项：

1. 如哈雷彗星，限制条件是向后，所以从后往前计算
2. 用累计DP： F[i] = max(F[i + 1], f)

Python代码：

1
2
3
4
5
6
7
8

def mostPoints(self, questions: List[List[int]]) -> int:
	dp = [0] * (len(questions) + 1)
	for i in range(len(dp) - 2, -1, -1):
		next_val = 0
		if i + questions[i][1] + 1 < len(dp):
			next_val = dp[i + questions[i][1] + 1]
		dp[i] = max(dp[i + 1], questions[i][0] + next_val)
	return dp[0]

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

二维DP算法II解题思路：

一开始我的思路是比较直接，此算法TLE。 dp[i]为以回答了第i个问题及之前的问题所得分数。递归式为：

1

dp[i] = max(dp[j] + questions[i][0]) if j + questions[j][1] < i, 0 <= j < i

Python代码：

1
2
3
4
5
6
7
8

def mostPoints2(self, questions: List[List[int]]) -> int:
	dp = [0] * len(questions)
	for i in range(len(dp)):
		dp[i] = questions[i][0]
		for j in range(i):
			if j + questions[j][1] < i:
				dp[i] = max(dp[i], dp[j] + questions[i][0])
	return max(dp)

算法分析：

时间复杂度为<code>O(n²)</code>，空间复杂度O(n)。

LeetCode

<div>

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

• For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:

<pre>Input: root = [1,2,3] Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Therefore, sum = 12 + 13 = 25. </pre>

Example 2:

<pre>Input: root = [4,9,0,5,1] Output: 1026 Explanation: The root-to-leaf path 4->9->5 represents the number 495. The root-to-leaf path 4->9->1 represents the number 491. The root-to-leaf path 4->0 represents the number 40. Therefore, sum = 495 + 491 + 40 = 1026. </pre>

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• 0 <= Node.val <= 9
• The depth of the tree will not exceed 10.

</div>

题目大意：

由root到叶子节点的数字组成多位数的数，求这些数的总和

解题思路：

题目提到叶子节点，所以DFS中要含叶子节点的情况

解题步骤：

N/A

注意事项：

1. 题目提到叶子节点，所以DFS中要含叶子节点的情况。当然还要有root为空的情况，这样root.left和root.right不用非空检查，代码更简洁

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def sumNumbers(self, root: TreeNode) -> int:
	return self.dfs(root, 0)

def dfs(self, root, path):
	if not root:
		return 0
	current = path * 10 + root.val
	if not root.left and not root.right:
		return current
	#if root.left #if root.right:
	return self.dfs(root.left, current) + self.dfs(root.right, current)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

LeetCode

<div>

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

<pre>Input: nums = [2,2,1] Output: 1 </pre>

Example 2:

<pre>Input: nums = [4,1,2,1,2] Output: 4 </pre>

Example 3:

<pre>Input: nums = [1] Output: 1 </pre>

Constraints:

• 1 <= nums.length <= 3 * 10<sup>4</sup>
• -3 * 10<sup>4</sup> <= nums[i] <= 3 * 10<sup>4</sup>
• Each element in the array appears twice except for one element which appears only once.

</div>

题目大意：

数列中，所有数都出现两次除了一个数，求这一个数

异或解题思路(推荐)：

Easy题

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5

def singleNumber(self, nums: List[int]) -> int:
	res = 0
	for n in nums:
		res ^= n
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

HashMap算法II解题思路：

记录频数，最直观解法

Python代码：

1
2
3

def singleNumber2(self, nums: List[int]) -> int:
	num_to_count = collections.Counter(nums)
	return [n for n, count in num_to_count.items() if count == 1][0]

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

Math算法III解题思路：

用set求单一元素和乘以2减去原数组的和

Python代码：

1
2

def singleNumber3(self, nums: List[int]) -> int:
	return 2 * sum(set(nums)) - sum(nums)

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

LeetCode 010 Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

<pre>'.' Matches any single character. '*' Matches zero or more of the preceding element. </pre>

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

<pre>Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa". </pre>

Example 2:

<pre>Input: s = "aa" p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". </pre>

Example 3:

<pre>Input: s = "ab" p = "." Output: true Explanation: "." means "zero or more (*) of any character (.)". </pre>

Example 4:

<pre>Input: s = "aab" p = "cab" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab". </pre>

Example 5:

<pre>Input: s = "mississippi" p = "misisp*." Output: false </pre>

题目大意：

这道求正则表达式匹配的题和那道Leetocde 044 Wildcard Matching很类似，不同点在于*的意义不同，在之前那道题中，
*表示可以代替任意个数的不同字符，而这道题中的*表示之前一个字符（同样字符）可以有0-N个匹配。此题更难一些。

解题思路：

这是经典题。两字符串匹配题基本就是DP而且知道子问题答案可以推导下一个。

1. 定义dp[i][j]为字符串s[i-1]和p[j-1]是否能匹配。
2. 递归式为dp[i][j] = dp[i-1][j-1] && (p[j-1] == . || s[i-1] == p[j-1])
   OR ((dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == .)) || dp[i][j-2]) && p[j-1] == *
   第一种情况为非*，通配一样字符或.
   第二种情况为*，如果通配**（有条件：与p的前一个字符相等或p为.）就是只移动s，dp[i-1][j]。若不通配就只移动p及其前一个字符**。
3. 方向为从左到右，从上到下。初始值为dp[0][0] = true。以及若s为空，p为多个*时候，dp[0][j]=true。

与Wildcard Matching不同之处用黑体标注了：

1. 用.代替?
2. *情况，不匹配p移动两位而不是一位。
3. *情况，匹配带条件而不是无条件。
4. 初始化用dp[0][j-2]而不是j-1。

注意事项：

1. 递归式含*不匹配情况dp[i][j-2]。
2. 初始化s为空，p为多个*。此情况其实与递归式符合，因为i=1开始，所以i=0的时候，dp[i-1][j]为负值省去，
   只取dp[i][j-2]。
3. 循环中j按理应该从2开始，因为递归式含p[j-2], 这样要初始化第1列(第0列已经初始化为False)。由于题目条件保证星号前一定有其他字符，所以p的第0位不能是星号，所以j可以从1开始
4. Python中任何矩阵初始化都只能用两重for循环而不能用乘号

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

def isMatch(self, s: str, p: str) -> bool:
	dp = [[False for _ in range((len(p) + 1))] for _ in range(len(s) + 1)]
	dp[0][0] = True
	for j in range(2, len(dp[0])):
		dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'

	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if p[j - 1] != '*':
				dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.')
			else:
				dp[i][j] = (dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.')) or (dp[i][j - 2])
	return dp[-1][-1]

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public boolean isMatch(String s, String p) {
	boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
	dp[0][0] = true;
	for(int j = 2; j < dp[0].length; j++)
		if(p.charAt(j-1) == '*') // remember s="", p="a*"
			dp[0][j] = dp[0][j-2];
	for(int i = 1; i < dp.length; i++)
		for(int j = 1; j < dp[0].length; j++) {
			if(p.charAt(j-1) == '*')
				dp[i][j] = (dp[i][j-2] || ((s.charAt(i-1) == p.charAt(j-2) 
				|| p.charAt(j-2) == '.') && dp[i-1][j]));
			else
				dp[i][j] = dp[i-1][j-1] && (s.charAt(i-1) == p.charAt(j-1) 
				|| p.charAt(j-1) == '.');
		}
	return dp[dp.length -1][dp[0].length - 1];
}

算法分析：

时间复杂度为O(n*m)，空间复杂度为O(n*m)。

LeetCode 042 Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

<small>The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!</small>

Example:

<pre>Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6</pre>

题目大意：

给出 n 个非负整数，代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少（面积）雨水。

解题思路：

画图解题。 比较直观的方法是找低谷，只有低谷才可以藏水。用一个递减栈来存所有呈递减趋势的下标，而当上升时就计算藏水量。

从图可以看出，栈中有最高的，3,2,1，最矮的已经出栈了。蓝色的bar准备入栈。计算水量是水平计算的。具体而言，
右边界是确定的，左边界以及高度都是由此bar相邻的在栈中的bar确定的。如1的水量由bar2的高度和位置确定。
同理bar2的水量由bar3确定。实质上，是求出栈的元素之间的水量，既然是之间，最后一个出栈就要特殊处理，需要准入栈
元素来确定。特殊之处是计算栈中最后一个将要被新bar踢出栈的bar3时，并没有相邻的bar作参考，
导致它需要用新bar作为参考，所以它不能在while中处理，需要特别处理，主要因为它是最后一个，属于edge case。

解题步骤：

1. 遍历数组
2. 若比上一个高度递增，出栈直至栈中下标对应高度大于当前高度（保持递减栈）。每次出栈，用上一轮的高度作为底部计算高度差
   乘以下标距离即为横向藏水增量，更新底部进入下一次出栈。
3. 出栈完成后，根据新bar计算最后一个bar的水量，用当前高度计算藏水增量。
4. 加入下标到栈中

公式：

1

水量 = 准入栈下标与相邻栈(栈顶)的下标i - stack[-1] - 1 乘以 (相邻栈高度 - 刚出栈高度)

注意事项：

1. [公式]水量 = 准入栈下标与**相邻栈(栈顶)**的下标i - stack[-1] - 1 乘以 (相邻栈高度 - 刚出栈高度)
   水量的宽度并不是用刚出栈的下标，因为如上图，2-3之间可能实际上不相邻（有些高度已出栈），若用当前栈的下标会忽略了2-3之间的水量。
2. 最后一个出栈的宽度计算要还有相邻栈(栈顶)i - stack[-1] - 1才计算也就是栈不为空if stack。
3. 最后一个出栈的高度公式要改成相邻栈高度 -> 准入栈高度。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

def trap(self, height: List[int]) -> int:
	stack = []
	sum = 0
	for i in range(len(height)):
		j = -1
		while stack and height[i] > height[stack[-1]]:
			j = stack.pop()
			if stack and height[i] > height[stack[-1]]:
				sum += (height[stack[-1]] - height[j]) * (i - stack[-1] - 1) # stack[-1] is the neighboring index
		if stack and j > 0:
			sum += (height[i] - height[j]) * (i - stack[-1] - 1)
		stack.append(i)
	return sum

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

算法II解题思路(推荐)：

算法I主要从面考虑，现在我们从点来考虑。下标4的水量取决于向左最大值（下标0）和向右最大值（下标12）中的较小值。
问题转化为求每个点的向左向右最大值。数组从左到右扫描，把当前最大值存入leftHeight中，这是向左最大值。
同理，数组从又到左扫描，得到向右最大值。对每个点取向左向右最大值的较小者，从而计算水量。此法实现起来简单很多。

先写空间为O(n)版本容易理解

注意事项：

1. 减去底部高度height[i]
2. 计算右边时cur_max要reset

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def trap(self, height: List[int]) -> int:
	left, right = [], []
	cur_max, res = 0, 0
	for i in range(len(height)):
		cur_max = max(cur_max, height[i])
		left.append(cur_max)
	cur_max = 0
	for i in reversed(range(len(height))):
		cur_max = max(cur_max, height[i])
		right.append(cur_max)
	right = right[::-1]
	for i in range(len(left)):
		res += min(left[i], right[i]) - height[i]
	return res

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def trap(self, height: List[int]) -> int:
	max_height = max(height)
	max_index = height.index(max_height)
	sum, left_max, right_max = 0, 0, 0
	for i in range(max_index):
		sum += max(0, left_max - height[i])
		left_max = max(left_max, height[i])
	for i in range(len(height) - 1, max_index, -1):
		sum += max(0, right_max - height[i])
		right_max = max(right_max, height[i])
	return sum

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。