子串、子序列
300.最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
#以nums[i]为结尾的最长递增子序列
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[i]>nums[j]:
dp[i] = max(dp[i],dp[j]+1)
max_l = 0
for lens in dp:
max_l = max(lens,max_l)
return max_l
674. 最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
#以nums[i]为结尾的最长连续递增子序列
dp = [1]*len(nums)
for i in range(1,len(nums)):
if nums[i]>nums[i-1]:
dp[i]=dp[i-1]+1
max_l = 0
for lens in dp:
max_l = max(max_l,lens)
return max_l
718. 最长重复子数组
力扣题目链接(opens new window)
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3, 2, 1] 。
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
# dp[i][j] 以nums1[i]和nums2[j]结尾的公共数组的长度
dp = [[0] * len(nums2) for _ in range(len(nums1))]
for j in range(len(nums2)):
if nums2[j] == nums1[0]:
dp[0][j] = 1
for i in range(len(nums1)):
if nums1[i] == nums2[0]:
dp[i][0] = 1
for i in range(1,len(nums1)):
for j in range(1,len(nums2)):
if nums1[i] == nums2[j]:
dp[i][j] = dp[i-1][j-1] + 1
max_l = 0
for i in range(len(nums1)):
for j in range(len(nums2)):
max_l = max(max_l,dp[i][j])
return max_l
1143.最长公共子序列
力扣题目链接(opens new window)
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
思考
注意这道题的DP定义和前面都不太一样了
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n1 = len(text1)
n2 = len(text2)
# dp[i][j] 为以text1[0:i-1] text2[0:j-1] 两个字符串的最长公共子序列长度
dp = [[0] * (n2+1) for _ in range(n1+1)]
for i in range(n1):
for j in range(n2):
if text1[i] == text2[j]:
dp[i+1][j+1]=dp[i][j]+1
else:
dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
return dp[n1][n2]
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 以i为结尾的数组的最大子数组和
dp = [0] * len(nums)
dp[0] = nums[0]
max_sum = nums[0]
for i in range(1,len(nums)):
dp[i] = max(dp[i-1] + nums[i] ,nums[i])
max_sum = max(dp[i],max_sum)
return max_sum
647.回文子串的个数
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
class Solution:
def countSubstrings(self, s: str) -> int:
# dp 以i,j为左右边界的字符串是否是回文串
dp = [[False] * len(s) for _ in range(len(s))]
res = 0
# 从 下到上 ，从左到右遍历
for i in range(len(s)-1,-1,-1):
for j in range(i,len(s)):
if s[i] == s[j]:
if j - i <= 1:
dp[i][j] = True
else:
if dp[i+1][j-1]:
dp[i][j] = True
if dp[i][j]:
res+=1
return res
5.最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
思考
跟上面的647是一个解法。
class Solution:
def longestPalindrome(self, s: str) -> str:
# dp[i][j] i,j为闭区间的子串是否是回文串
dp = [[False] * len(s) for i in range(len(s))]
max_len = 0
left,right = 0,0
for i in range(len(s)-1,-1,-1):
for j in range(i,len(s)):
if s[i] == s[j]:
if j-i<=1:
dp[i][j] = True
else:
dp[i][j] = dp[i+1][j-1]
if dp[i][j]:
if j-i+1 > max_len:
max_len = j-i+1
left,right = i,j
return s[left:right+1]
516.最长回文子序列
给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。
示例 2: 输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
# 以[i,j]为区间的字符串的回文子序列的长度
dp = [[0] * len(s) for _ in range(len(s))]
for i in range(len(s)):
dp[i][i] = 1
max_len = 1
for i in range(len(s)-1,-1,-1):
for j in range(i+1,len(s)):
if s[i]==s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i][j-1],dp[i+1][j])
max_len = max(max_len,dp[i][j])
return max_len
初始化也可以放在遍历过程中，可以发现i==j时，是会先进行初始化赋值的，不影响后面的计算。
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
# 以[i,j]为区间的字符串的回文子序列的长度
dp = [[0] * len(s) for _ in range(len(s))]
# for i in range(len(s)):
# dp[i][i] = 1
max_len = 1
for i in range(len(s)-1,-1,-1):
for j in range(i,len(s)):
if i==j:
dp[i][j]=1
continue
if s[i]==s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i][j-1],dp[i+1][j])
max_len = max(max_len,dp[i][j])
return max_len
72. 编辑距离
思考
递推公式还是很难想到的，可以先背下来应付面试。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n1 = len(word1)
n2 = len(word2)
# dp[i][j] word1[0:i-1] 和word[0:j-1] 闭区间编辑距离
dp = [[0] * (n2+1) for _ in range(n1+1)]
for i in range(n1+1):
dp[i][0] = i
for j in range(n2+1):
dp[0][j] = j
for i in range(1,n1+1):
for j in range(1,n2+1):
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[n1][n2]
背包问题
518.零钱兑换II
力扣题目链接(opens new window)
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
思考
物品可重复，完全背包问题。
本题的难点在于遍历顺序！
在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
# dp[i] 组成总数为i的的硬币的组合数
dp = [0] * (amount+1)
dp[0] = 1
# 先物品再背包 求组合问题
for coin in coins:
for i in range(1,amount+1):
if i-coin >=0:
dp[i] += dp[i-coin]
return dp[-1]
322. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# dp[i] 组成总数为i的的硬币最小组合长度
dp = [float('inf')] * (amount+1)
dp[0] = 0
# 先物品再背包
for coin in coins:
for i in range(1,amount+1):
if i-coin >=0:
dp[i] = min(dp[i-coin]+1,dp[i])
if dp[-1] == float('inf'):
return -1
else:
return dp[-1]
416. 分割等和子集
题目难易：中等
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
思考
物品不能重复选择，01背包问题。使用一维滚动数组求解，注意背包反向的遍历顺序。
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if len(nums)==1:
return False
sum_ = sum(nums)
if sum_ % 2 !=0:
return False
k = int(sum_ / 2)
# dp[i] 背包容量i是否可以装满
dp = [False] * (k+1)
dp[0] = True
for num in nums:
for i in range(k,0,-1):
if i>=num:
dp[i] = dp[i] or dp[i-num]
return dp[k]
279.完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
思考
跟零钱兑换一样，完全背包问题。
class Solution:
def numSquares(self, n: int) -> int:
#sqr_n = int(n** 0.5)
coins = []
for i in range(1,n):
if i**2<=n:
coins.append(i**2)
#print(coins)
# 先物品再背包
dp = [float('inf')] * (n+1)
dp[0] = 0
dp[1] = 1
for coin in coins:
for i in range(2,n+1):
if i>=coin:
dp[i] = min(dp[i],dp[i-coin]+1)
#print(dp)
return dp[n]
139.单词拆分
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
思考
物品可以重复选取，完全背包问题。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
而本题其实我们求的是排列数，为什么呢。 拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。
"apple", "pen" 是物品，那么我们要求 物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。
"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我们就是强调物品之间顺序。
所以说，本题一定是 先遍历 背包，再遍历物品。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
#dp[i] 表示 s[0:i]是否可以拆分
dp = [False]* (len(s)+1)
dp[0] = True
for i in range(1,len(s)+1):
for word in wordDict:
if i >=len(word):
#print(word,len(word),i)
dp[i] = dp[i-len(word)] and s[i-len(word):i] == word
if dp[i]:
break
return dp[len(s)]