算法题记录 38
32.最长有效括号（困难）
给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
涉及知识点
动态规划
解决思路
dp[i]表示以i结尾的最长有效括号子串的长度。分两种情况,如果s[i]=’)’,s[i-1]=’()’，那么dp[i]=dp[i-2]+2；如果s[i]=’)’,s[i-1]=’)’,那么dp[i]=dp[i-1]+2+dp[i-2-dp[i-1]]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution:
def longestValidParentheses(self, s: str) -> int:
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
dp = [0] * n
ans = 0
for i in range(1, n):
if s[i] == ')':
if s[i-1] == '(':
if i >= 2:
dp[i] = dp[i-2] + 2
else:
dp[i] = 2
else:
if i - dp[i-1] > 0 and s[i - dp[i-1] - 1] == '(':
if i - dp[i-1] - 2 >= 0:
dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]
else:
dp[i] = dp[i-1] + 2
ans = max(ans, dp[i])
return ans
|
62.不同路径（中等）
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
涉及知识点
多维动态规划
解决思路
可以用动态规划来解决，dp[i]表示前i个字符是否可以被拆分成字典中的单词。
1
2
3
4
5
6
| class Solution:
@cache
def uniquePaths(self, m: int, n: int) -> int:
if m==1 or n==1:
return 1
return self.uniquePaths(m-1,n)+self.uniquePaths(m,n-1)
|
64.最小路径和（中等）
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
涉及知识点
多维动态规划
解决思路
我们用dp[i]来表示以nums[i]结尾的最长递增字序列的长度。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
@cache
def dfs(i:int,j:int)->int:
if i==0 and j==0:
return grid[0][0]
if i==0:
return dfs(i,j-1)+grid[i][j]
if j==0:
return dfs(i-1,j)+grid[i][j]
return min(dfs(i-1,j),dfs(i,j-1))+grid[i][j]
return dfs(len(grid)-1,len(grid[0])-1)
|
5.最长回文子串（中等）
给你一个字符串 s，找到 s 中最长的 回文 子串。
涉及知识点
多维动态规划
解决思路
用do[i][j]表示s[i:j]是否是回文串，初始化为False，然后遍历字符串，判断s[i:j]是否是回文串，如果是，则更新最长回文串的长度和起始位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
f = [[False] * n for _ in range(n)]
max_len = 1
l, r = 0, 0
for i in range(n-1, -1, -1):
f[i][i] = True
for j in range(i+1, n):
if j == i+1 and s[i] == s[j]:
f[i][j] = True
else:
f[i][j] = f[i+1][j-1] and s[i] == s[j]
if f[i][j]:
if max_len < j-i+1:
max_len = j-i+1
l, r = i, j
return s[l:r+1]
|
1143.最长公共子序列（中等）
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
涉及知识点
多维动态规划
解决思路
两个字符串的最长公共子序列可以用动态规划来解决，dp[i][j]表示text1[0:i]和text2[0:j]的最长公共子序列的长度。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n = len(text1)
m = len(text2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]
|
72.编辑距离（中等）
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
涉及知识点
多维动态规划
解决思路
跟上面的题本质一样。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def minDistance(self, s: str, t: str) -> int:
n, m = len(s), len(t)
@cache
def dfs(i: int, j: int) -> int:
if i < 0:
return j + 1
if j < 0:
return i + 1
if s[i] == t[j]:
return dfs(i - 1, j - 1)
return min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1)) + 1
return dfs(n - 1, m - 1)
|
声明
题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。
