KK's blog

LeetCode 085 Maximal Rectangle

Posted on 2022-01-15 Disqus:

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:

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.

Example 2:

Input: matrix = [[“0”]]
Output: 0

Example 3:

Input: matrix = [[“1”]]
Output: 1

Constraints:

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

题目大意：

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 084 Largest Rectangle in Histogram

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

LeetCode

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

1 <= heights.length <= 105 0 <= heights[i] <= 104

题目大意：

求直方图中最大的矩形面积

解题思路：

类似于L042 Trapping Rain Water的stack法，但此题水量是反的。所以仍然用Stack，但用递增栈

解题步骤：

N/A

注意事项：

比L042稍简单，不用处理最后一个bar高度和宽度计算，但是用递增栈且公式中宽度计算仍然采用i - stack[-1] - 1，因为bar并不一定连续，如212, 最后一个2入栈，栈中剩下[_, 1]第一个2已经出栈了，但是可以有水量的。
原数组头尾加入0，头0是因为公式有stack[-1]避免越界，尾0是因为让所有留在栈中的bar出栈且计算。

大厦题，首尾加入节点：
LeetCode 084 Largest Rectangle in Histogram
LeetCode 218 The Skyline Problem

Python代码：

def largestRectangleArea(self, heights: List[int]) -> int:
	stack, res = [], 0
	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(n)，空间复杂度O(n)

LeetCode 072 Edit Distance

Posted on 2022-01-15 Disqus:

LeetCode

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:

Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)

Example 2:

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

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

题目大意：

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

解题思路：

求最值且涉及到字符串考虑用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 076 Minimum Window Substring

Posted on 2022-01-15 Edited on 2022-03-21 Disqus:

LeetCode

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring__, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.

Example 2:

Input: s = “a”, t = “a”
Output: “a”
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = “a”, t = “aa”
Output: “”
Explanation: Both ‘a’s from t must be included in the window.
Since the largest window of s only has one ‘a’, return empty string.

Constraints:

m == s.length n == t.length
1 <= m, n <= 105 s and t consist of uppercase and lowercase English letters.

Follow up: Could you find an algorithm that runs in O(m + n) time?

题目大意：

最短摘要：给定s和t两个字符串，求在s中包含所有t的字符的最短子串。这个结果可以包含不在t的字符，某个字符数量也可以多于t中的字符但不能少于。

解题思路：

提到window substring就用滑动窗口或者同向双指针。

解题步骤：

N/A

注意事项：

用同向双指针模板。用map来统计t的字符频率，用unique_count统计满足条件唯一字符个数。while的条件为unique_count达到了map的大小。
while里面的统计与while外面的统计本质一样，但相反。若s中某字符多于s中的，map为负值，left指针右移时，负值会变回正值。

Python代码：

def minWindow(self, s: str, t: str) -> str:
	t_char_to_count = collections.Counter(t)
	left, unique_count, min_len, res = 0, 0, float('inf'), ''
	for i in range(len(s)):
		if s[i] in t_char_to_count:
			t_char_to_count[s[i]] -= 1
			if t_char_to_count[s[i]] == 0:
				unique_count += 1
		while unique_count == len(t_char_to_count):
			if i - left + 1 < min_len:
				min_len = i - left + 1
				res = s[left:i + 1]
			if s[left] in t_char_to_count:
				t_char_to_count[s[left]] += 1
				if t_char_to_count[s[left]] == 1:
					unique_count -= 1
			left += 1
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(m), n和m分别为s和t的长度

LeetCode 073 Set Matrix Zeroes

Posted on 2022-01-15 Disqus:

LeetCode

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:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

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

Constraints:

m == matrix.length n == matrix[0].length
1 <= m, n <= 200 -231 <= matrix[i][j] <= 231 - 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?

题目大意：

若矩阵某元素为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

算法分析：

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