KK's blog

LeetCode 091 Decode Ways

Posted on 2022-01-16 Disqus:

A message containing letters from A-Z can be encoded into numbers using the following mapping:

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6) "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = “12”
Output: 2
Explanation: “12” could be decoded as “AB” (1 2) or “L” (12).

Example 2:

Input: s = “226”
Output: 3
Explanation: “226” could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

Example 3:

Input: s = “06”
Output: 0
Explanation: “06” cannot be mapped to “F” because of the leading zero (“6” is different from “06”).

Constraints:

1 <= s.length <= 100 s contains only digits and may contain leading zero(s).

题目大意：

数字1-26可以解码成A-Z字母。给定一串数字，求解码方法数。

解题思路：

求种数是DP和DFS，这题有递归关系，所以考虑用DP。类似于Fibonacci数列和LeetCode 070 Climbing Stairs，但此题带限制条件

递归式：

1	dp[i] = dp[i-1] + dp[i-2] if 0 < s[i-1] <= 9, 10 <= s[i-2:i] <= 26

解题步骤：

利用DP五点注意事项

注意事项：

不合法的情况为空字符和含0. 这是求个数，根据DP知识点(数值到个数DP模板)，dp[0] = 1, 但这与题目空字符要求不同，所以特别处理。至于单个含0在循环中处理’0’ < s[i - 1] <= ‘9’
验证单位范围[1, 9], 双位范围[10, 26]才加入到结果中。由于dp长度只多了一位而递归式含两个前状态，所以要验证i >= 2

Python代码：

# dp[i] = dp[i-1] + dp[i-2] if 0 < s[i-1] <= 9, 10 <= s[i-2:i] <= 26
def numDecodings(self, s: str) -> int:
	if not s:
		return 0
	dp = [0] * (len(s) + 1)
	dp[0] = 1
	for i in range(1, len(dp)):
		if '0' < s[i - 1] <= '9':
			dp[i] = dp[i - 1]
		if i >= 2 and '10' <= s[i - 2: i] <= '26':
			dp[i] += dp[i - 2]
	return dp[-1]

算法分析：

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

O(1)空间算法II解题思路：

类似于Fibonacci数列和LeetCode 070 Climbing Stairs，由于涉及到两个前状态，所以用两个变量来节省空间

Python代码：

# dp[i] = dp[i-1] + dp[i-2] if 0 < s[i-1] <= 9, 10 <= s[i-2:i] <= 26
def numDecodings2(self, s: str) -> int:
	if not s:
		return 0
	first, second = 1, 1
	for i in range(1, len(s) + 1):
		res = 0
		if '0' < s[i - 1] <= '9':
			res = second
		if i >= 2 and '10' <= s[i - 2: i] <= '26':
			res += first
		first, second = second, res
	return res

算法分析：

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

LeetCode 092 Reverse Linked List II

Posted on 2022-01-15 Edited on 2022-02-02 Disqus:

LeetCode

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:

The number of nodes in the list is n. 1 <= n <= 500
-500 <= Node.val <= 500 1 <= left <= right <= n

Follow up: Could you do it in one pass?

题目大意：

反转链表中的子链表[left, right]，start和end是1-index位置, inclusive

解题思路：

锁定start和end节点，将end的后续节点一个个加到start直接后续

LeetCode 206 Reverse Linked List 反转整个LL
LeetCode 092 Reverse Linked List II 反转部分LL，此题更加一般化

模板：
不断将end直接后面的节点加到start直接后面
start(group n) -> NodeA （新状态） -> … -> end(group n+1) -> NodeA （前状态） -> …

找出start和end，start为反转部分的前一个，end为反转部分的首个节点

循环删除end直接后，再加入到start直接后

Python代码：

start, end = fake_head, head
while <反转链表长度>:
	# delete the node
	moved_node, end.next = end.next, end.next.next
	# insert the moved_node
	start.next, moved_node.next = moved_node, start.next

解题步骤：

N/A

注意事项：

经典题，见LeetCode 2074 Reverse Nodes in Even Length Groups。思路是锁定start和end节点，将end的后续节点一个个加到start直接后续
第二个循环中，right要记得减一，否则死循环

Python代码：

def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
	left, right = left - 1, right - 1
	fake_head = ListNode(0)
	fake_head.next = head
	it = fake_head
	while left > 0:
		it = it.next
		left -= 1
		right -= 1
	start, end = it, it.next
	while right > 0:
		moved_node, end.next = end.next, end.next.next # delete a node
		start.next, moved_node.next = moved_node, start.next # insert a node
		right -= 1 # remember
	return fake_head.next

算法分析：

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

LeetCode 090 Subsets II

Posted on 2022-01-15 Disqus:

LeetCode

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10 -10 <= nums[i] <= 10

题目大意：

求所有子集，元素可能相同，不能含相同子集

解题思路：

类似于L078 Subsets，但元素可能相同，所以排序且比较相邻元素，若相等就跳过

解题步骤：

N/A

注意事项：

元素可能相同，所以排序且比较相邻元素，若相等就跳过

Python代码：

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
	if not nums:
		return []
	nums.sort()
	res = [[]]
	self.dfs(nums, 0, [], res)
	return res

def dfs(self, nums, st, path, res):
	if st == len(nums):
		return
	for i in range(st, len(nums)):
		if i > st and nums[i] == nums[i - 1]:
			continue
		path.append(nums[i])
		res.append(list(path))
		self.dfs(nums, i + 1, path, res)
		path.pop()

算法分析：

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

LeetCode 2139 Minimum Moves to Reach Target Score

Posted on 2022-01-15 Disqus:

LeetCode

You are playing a game with integers. You start with the integer 1 and you want to reach the integer target.

In one move, you can either:

Increment the current integer by one (i.e., x = x + 1). Double the current integer (i.e., x = 2 * x).

You can use the increment operation any number of times, however, you can only use the double operation at most maxDoubles times.

Given the two integers target and maxDoubles, return the minimum number of moves needed to reach target starting with 1.

Example 1:

Input: target = 5, maxDoubles = 0
Output: 4
Explanation: Keep incrementing by 1 until you reach target.

Example 2:

Input: target = 19, maxDoubles = 2
Output: 7
Explanation: Initially, x = 1
Increment 3 times so x = 4
Double once so x = 8
Increment once so x = 9
Double again so x = 18
Increment once so x = 19

Example 3:

Input: target = 10, maxDoubles = 4
Output: 4
Explanation:Initially, x = 1
Increment once so x = 2
Double once so x = 4
Increment once so x = 5
Double again so x = 10

Constraints:

1 <= target <= 109 0 <= maxDoubles <= 100

题目大意：

加1或者乘2达到target，乘2有次数限制，求到达target的最小步数

DFS解题思路(推荐)：

由于是最值，一开始用DP，但得到TLE，分析后觉得是因为加法太慢，所以用贪心法，尽量用乘法。此题类似于求幂值。改用DFS。

解题步骤：

N/A

注意事项：

若允许乘法次数为0，直接返回加法次数，而不应再用递归，否则会出现超过系统栈深度

Python代码：

def minMoves(self, target: int, maxDoubles: int) -> int:
	if target == 1:
		return 0
	if maxDoubles == 0:
		return target - 1
	if target % 2 == 0 and maxDoubles > 0:
		return self.minMoves(target // 2, maxDoubles - 1) + 1

	return self.minMoves(target - 1, maxDoubles) + 1

算法分析：

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

DP算法II解题思路：

TLE

Python代码：

# dp[i][j] = dp[i - 1][j], dp[i // 2][j - 1]
def minMoves2(self, target: int, maxDoubles: int) -> int:
	dp = [[0] * (maxDoubles + 1) for _ in range(target + 1)]
	dp[1][0] = 0
	for i in range(2, len(dp)):
		for j in range(len(dp[0])):
			dp[i][j] = dp[i - 1][j] + 1
			if j >= 1 and i % 2 == 0:
				dp[i][j] = min(dp[i][j], dp[i // 2][j - 1] + 1)
	return dp[-1][-1]

算法分析：

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

LeetCode 2140 Solving Questions With Brainpower

Posted on 2022-01-15 Edited on 2022-01-16 Disqus:

LeetCode

You are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri].

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 pointsi points but you will be unable to solve each of the next brainpoweri 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:

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.

Example 2:

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.

Constraints: 1 <= questions.length <= 105
questions[i].length == 2 1 <= pointsi, brainpoweri <= 105

题目大意：

(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

注意事项：

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

Python代码：

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代码：

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)

算法分析：

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