文章目录
- 75. 颜色分类
- 76. 最小覆盖子串
- 78. 子集
- 79. 单词搜索
- 84. 柱状图中最大的矩形
75 78 79
75. 颜色分类
就用了一个排序算法。
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums or len(nums) == 0:
return
n = len(nums)
for i in range(n - 1):
for j in range(i + 1, n):
if nums[i] > nums[j]:
nums[i], nums[j] = nums[j], nums[i]
return nums
双指针的方法，回头再翻回来看吧。
第二遍复盘，两遍双指针。
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if not nums or len(nums) == 0:
return
left, right = 0, len(nums) - 1
while left < right:
while left < right and nums[left] == 0:
left += 1
while left < right and (nums[right] == 2 or nums[right] == 1):
right -= 1
nums[left], nums[right] = nums[right], nums[left]
right = len(nums) - 1
while left < right:
while left < right and nums[left] == 1:
left += 1
while left < right and nums[right] == 2:
right -= 1
nums[left], nums[right] = nums[right], nums[left]
return nums
76. 最小覆盖子串
看了答案，挺难的，先跳过吧。
78. 子集
知道要用回溯，但是不会写
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
if not nums or len(nums) == 0:
return
n = len(nums)
pth = []
res = []
for i in nums:
if i not in pth:
pth.append(i)
pth.pop()
def backtracking(nums, pth, res):
下面是答案：
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
def helper(i, tmp):
res.append(tmp)
for j in range(i, n):
helper(j + 1,tmp + [nums[j]] )
helper(0, [])
return res
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
tmp = []
def backtrace(nums, startindex):
#if startindex >= len(nums):
res.append(tmp[:])
for i in range(startindex, len(nums)):
tmp.append(nums[i])
backtrace(nums, i + 1)
tmp.pop()
nums = sorted(nums)
backtrace(nums, 0)
return res
写出来了，还得复习
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
if not nums or len(nums) == 0:
return
n = len(nums)
pth = []
res = []
def backtracking(pth, start):
res.append(pth[:])
for i in range(start, n):
pth.append(nums[i])
backtracking(pth, i + 1)
pth.pop()
backtracking(pth, 0)
return res
第二遍写了，还是懵懵懂懂，递归九讲，必须再复习刷一下题。
class Solution:
def subsets(self, nums: List[int]):
if not nums or len(nums) == 0:
return
res, tmp = [], []
def helper(start):
res.append(tmp[:])
for i in range(start, len(nums)):
tmp.append(nums[i])
helper(i + 1)
tmp.pop()
nums = sorted(nums)
helper(0)
return res
79. 单词搜索
面试考过，不会。
const exist = (board, word) => {
const m = board.length;
const n = board[0].length;
const used = new Array(m); // 二维矩阵used，存放bool值
for (let i = 0; i < m; i++) {
used[i] = new Array(n);
}
// canFind 判断当前点是否是目标路径上的点
const canFind = (row, col, i) => { // row col 当前点的坐标，i当前考察的word字符索引
if (i == word.length) { // 递归的出口 i越界了就返回true
return true;
}
if (row < 0 || row >= m || col < 0 || col >= n) { // 当前点越界 返回false
return false;
}
if (used[row][col] || board[row][col] != word[i]) { // 当前点已经访问过，或，非目标点
return false;
}
// 排除掉所有false的情况，当前点暂时没毛病，可以继续递归考察
used[row][col] = true; // 记录一下当前点被访问了
// canFindRest：基于当前选择的点[row,col]，能否找到剩余字符的路径。
const canFindRest = canFind(row + 1, col, i + 1) || canFind(row - 1, col, i + 1) ||
canFind(row, col + 1, i + 1) || canFind(row, col - 1, i + 1);
if (canFindRest) { // 基于当前点[row,col]，可以为剩下的字符找到路径
return true;
}
used[row][col] = false; // 不能为剩下字符找到路径，返回false，撤销当前点的访问状态
return false;
};
for (let i = 0; i < m; i++) { // 遍历找起点，作为递归入口
for (let j = 0; j < n; j++) {
if (board[i][j] == word[0] && canFind(i, j, 0)) { // 找到起点且递归结果为真，找到目标路径
return true;
}
}
}
return false; // 怎么样都没有返回true，则返回false
};
这个想法太优美了。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
used = [[False] * n for _ in range(m)]
def dfs(row, col, i): # 判断当前点是否是目标路径上的点. row col 当前点的坐标，i当前考察的word字符索引
if i == len(word): # 递归结束条件 : 找到了单词的最后一个
return True
if row < 0 or row >= m or col < 0 or col >= n: # 越界
return False
if used[row][col] or board[row][col] != word[i]:# 已经访问过,或者不是word里的字母
return False
# 排除掉上面的false情况，当前点是合格的，可以继续递归考察
used[row][col] = True # 记录一下当前点被访问了
if dfs(row+1, col, i+1) or dfs(row-1, col, i+1) or dfs(row, col+1, i+1) or dfs(row, col-1, i+1): # 基于当前点[row,col]，可以为剩下的字符找到路径
return True
used[row][col] = False # 不能为剩下字符找到路径，返回false，撤销当前点的访问状态，继续考察别的分支
return False
for i in range(m):
for j in range(n):
if board[i][j] == word[0] and dfs(i, j, 0):
return True
return False
尝试自己写了下，还要复习第二遍。
class Solution:
def exist(self, board: List[List[str]], word: str):
m, n = len(board), len(board[0])
print(m, n)
visited = [[False] * n for _ in range(m)]
def dfs(row, col, i):
if i == len(word):
return True
if row < 0 or row >= m or col < 0 or col >= n:
return False
if visited[row][col] or board[row][col] != word[i]:
return False
visited[row][col] = True
if dfs(row + 1, col, i + 1) or dfs(row - 1, col, i + 1) or dfs(row, col + 1, i + 1) or dfs(row, col - 1, i + 1):
return True
visited[row][col] = False
return False
for i in range(m):
for j in range(n):
if board[i][j] == word[0] and dfs(i, j, 0):
return True
return False
84. 柱状图中最大的矩形
不会。
from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
size = len(heights)
res = 0
for i in range(size):
left = i
cur_height = heights[i]
while left > 0 and heights[left - 1] >= cur_height:
left -= 1
right = i
while right < size - 1 and heights[right + 1] >= cur_height:
right += 1
max_width = right - left + 1
res = max(res, max_width * cur_height)
return res
我写的暴力解法：
class Solution:
def largestRectangleArea(self, heights: List[int]):
if not heights or len(heights) == 0:
return 0
n = len(heights)
res = 0
for i in range(n):
cur_height = heights[i]
left = i
while left > 0 and heights[left - 1] >= cur_height:
left -= 1
right = i
while right < n - 1 and heights[right + 1] >= cur_height:
right += 1
max_width = right - left + 1
res = max(res, max_width * cur_height)
return res
