LeetCode 1143.最长公共子序列
最长公共子序列
给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,”ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列,则返回 0。
示例 1:1
2输入:text1 = "abcde", text2 = "ace"
输出:3
解释:最长公共子序列是 “ace”,它的长度为 3。
示例 2:1
2输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 “abc”,它的长度为 3。
示例 3:1
2输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0。
提示:1
21 <= text1.length <= 1000
1 <= text2.length <= 1000
输入的字符串只含有小写英文字符。
题解
动态规划,不过要设计一个二维数组dp,来统计dp[i][j]
时对应 text1 在 i 位置与text2 在 j 位置时两子字符串对应的最长公共子序列。
1 | class Solution(object): |
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-common-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
两个字符串的删除操作(最长公共子序列的变体)
给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。
示例 1:
输入: “sea”, “eat”
输出: 2
解释: 第一步将”sea”变为”ea”,第二步将”eat”变为”ea”
说明:
给定单词的长度不超过500。
给定单词中的字符只含有小写字母。
思路 + 代码
最长公共子序列的变体,其实就是求最长公共自序列。
1 | class Solution(object): |
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/delete-operation-for-two-strings
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:1
2
3
4输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:1
2
3
4输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
题解
这是一道以 0-1 背包问题为背景的算法练习题,我们把这个题目翻译一下:
给定一个只包含正整数的非空数组。是否可以从这个数组中挑选出一些正整数,每个数只能用一次,使得这些数的和等于整个数组元素的和的一半。
0-1 背包问题也是最基础的背包问题,它的特点是:待挑选的物品有且仅有一个,可以选择也可以不选择。下面我们定义状态,不妨就用问题的问法定义状态试试看。
dp[i][j]:表示从数组的 [0, i] 这个子区间内挑选一些正整数,每个数只能用一次,使得这些数的和等于 j。
根据我们学习的 0-1 背包问题的状态转移推导过程,新来一个数,例如是 nums[i],根据这个数可能选择也可能不被选择:
如果不选择 nums[i],在 [0, i - 1] 这个子区间内已经有一部分元素,使得它们的和为 j ,那么 dp[i][j] = true;
如果选择 nums[i],在 [0, i - 1] 这个子区间内就得找到一部分元素,使得它们的和为 j - nums[i] ,我既然这样写出来了,你就应该知道,这里讨论的前提条件是 nums[i] <= j。
以上二者成立一条都行。于是得到状态转移方程是:
1 | dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]], (nums[i] <= j) |
于是按照 0-1 背包问题的模板,我们不难写出以下代码。
1 | class Solution(object): |
优化版:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
size = len(nums)
s = sum(nums)
if s & 1 == 1:
return False
target = s // 2
dp = [False for _ in range(target+1)]
for i in range(target+1):
if nums[0]==i:
dp[i] = True
for i in range(1,size):
n = nums[i]
for j in range(target, n-1, -1):
if j>=n:
dp[j] = dp[j] or dp[j-n]
return dp[-1]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。