KK's blog

LeetCode 072 Edit Distance

Posted on 2022-01-15 Edited on 2026-06-03 Disqus:

<div>

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character

Example 1:

<pre>Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') </pre>

Example 2:

<pre>Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u') </pre>

Constraints:

0 <= word1.length, word2.length <= 500
word1 and word2 consist of lowercase English letters.

</div>

题目大意：

求编辑两个字符串的最短距离。编辑操作含加删一个字符，替换一个字符。

解题思路：

求最值且涉及到字符串考虑用DP。递归式为

1 2	dp[i][j] = dp[i-1][j-1] if word1[i-1] == word[j-1] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, otherwise

解题步骤：

N/A

注意事项：

初始值先word2长度再word1.
初始化上和左边界，表示当一个字符串为空时，另一个字符串的编辑距离是其长度。

Python代码：

# dp[i][j] = dp[i-1][j-1] if word1[i-1] == word[j-1]
#          = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, otherwise
def minDistance(self, word1: str, word2: str) -> int:
	dp = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]
	for i in range(1, len(dp)):
		dp[i][0] = i
	for j in range(1, len(dp[0])):
		dp[0][j] = j
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if word1[i - 1] == word2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1]
			else:
				dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
	return dp[-1][-1]

算法分析：

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

LeetCode 073 Set Matrix Zeroes

Posted on 2022-01-15 Edited on 2026-06-03 Disqus:

LeetCode

<div>

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's, and return the matrix.

You must do it in place.

Example 1:

<pre>Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]] </pre>

Example 2:

<pre>Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]] </pre>

Constraints:

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2<sup>31</sup> <= matrix[i][j] <= 2<sup>31</sup> - 1

Follow up:

A straightforward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

</div>

题目大意：

若矩阵某元素为0，设置它所在的行和列所有元素均为0，不能用额外区间

解题思路：

用第0行和第0列作为统计。由于第0行和第0列会被覆盖，所以先查看他们有无0

解题步骤：

N/A

注意事项：

用第0行和第0列作为统计。由于第0行和第0列会被覆盖，所以先查看他们有无0。两大步骤：先统计，再根据结果设置0
第二步中，根据第0和和第0列的结果回设，均从1开始，不含左上cell，因为统计结果不保存在它上。它仅在统计第一行和第一列是否有0时用到。

Python代码：

def setZeroes(self, matrix: List[List[int]]) -> None:
	# calculate
	is_zero_row_zero = True if len([0 for n in matrix[0] if n == 0]) > 0 else False
	is_zero_col_zero = True if len([0 for i in range(len(matrix)) if matrix[i][0] == 0]) > 0 else False
	for i in range(1, len(matrix)):
		for j in range(1, len(matrix[0])):
			if matrix[i][j] == 0:
				matrix[i][0], matrix[0][j] = 0, 0
	# Set			
	for i in range(1, len(matrix)): # remember to start with 1
		if matrix[i][0] == 0:
			for j in range(1, len(matrix[0])):
				matrix[i][j] = 0
	for j in range(1, len(matrix[0])): # remember to start with 1
		if matrix[0][j] == 0:
			for i in range(1, len(matrix)):
				matrix[i][j] = 0
	if is_zero_row_zero:
		for j in range(len(matrix[0])):
			matrix[0][j] = 0
	if is_zero_col_zero:
		for i in range(len(matrix)):
			matrix[i][0] = 0

算法分析：

时间复杂度为<code>O(n<sup>2</sup>)</code>，空间复杂度O(1)

LeetCode 085 Maximal Rectangle

Posted on 2022-01-15 Edited on 2026-06-03 Disqus:

LeetCode

<div>

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1:

<pre>Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 6 Explanation: The maximal rectangle is shown in the above picture. </pre>

Example 2:

<pre>Input: matrix = [["0"]] Output: 0 </pre>

Example 3:

<pre>Input: matrix = [["1"]] Output: 1 </pre>

Constraints:

rows == matrix.length
cols == matrix[i].length
1 <= row, cols <= 200
matrix[i][j] is '0' or '1'.

</div>

题目大意：

0-1矩阵求全部都是1的最大的子矩阵

解题思路：

类似于LeetCode 084 Largest Rectangle in Histogram，按每行生成连续1的直方图，求最大矩形面积。然后逐行调用L084的方法。

解题步骤：

N/A

注意事项：

由于L084的方案是修改原数组，所以不能直接调用，必须修改L084的方法，copy一份数组再往首尾插入0.

Python代码：

def maximalRectangle(self, matrix: List[List[str]]) -> int:
	heights, res = [0] * len(matrix[0]), 0
	for i in range(len(matrix)):
		for j in range(len(matrix[0])):
			if matrix[i][j] == '0':
				heights[j] = 0
			else:
				heights[j] += 1
		area = self.largestRectangleArea(heights)
		res = max(res, area)
	return res

def largestRectangleArea(self, height_list: List[int]) -> int:
	stack, res = [], 0
	heights = list(height_list)
	heights.insert(0, 0) # remember
	heights.append(0)
	for i in range(len(heights)):
		while stack and heights[i] < heights[stack[-1]]:
			index = stack.pop()
			res = max(res, (i - stack[-1] - 1) * heights[index]) # remember i - stack[-1] - 1 not i - index
		stack.append(i)
	return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(m), n, m分别为行数和列数

LeetCode 090 Subsets II

Posted on 2022-01-15 Edited on 2026-06-03 Disqus:

LeetCode

<div>

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:

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

Example 2:

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

Constraints:

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

</div>

题目大意：

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

解题思路：

类似于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()

算法分析：

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

LeetCode 2139 Minimum Moves to Reach Target Score

Posted on 2022-01-15 Edited on 2026-06-03 Disqus:

LeetCode

<div>

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:

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

Example 2:

<pre>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 </pre>

Example 3:

<pre>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 </pre>

Constraints:

1 <= target <= 10<sup>9</sup>
0 <= maxDoubles <= 100

</div>

题目大意：

加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)