不连续子序列
- 300.最长递增子序列
- 1143.最长公共子序列
- 1035.不相交的线
连续子序列
- 674.最长连续递增序列
- 贪心
- 动态规划（滚动数组后，发现和贪心思路一样）
- 718.最长重复子数组
- 53.最大子数组和
编辑距离
回文
最长重复子数组 - 二维dp
func findLength(nums1 []int, nums2 []int) int {
n1 := len(nums1)
n2 := len(nums2)
res := 0
// dp[i][j]: 以下标i - 1为结尾的nums1，和以下标j - 1为结尾的nums2，最长重复子数组长度
dp := make([][]int, n1 + 1)
for i := range dp {
dp[i] = make([]int, n2 + 1)
}
for i := 1; i <= n1; i++ {
for j := 1; j <= n2; j++ {
if nums1[i - 1] == nums2[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + 1
res = max(res, dp[i][j])
}
}
}
return res
}最长重复子数组 - 一维 dp
func findLength(nums1 []int, nums2 []int) int {
n1 := len(nums1)
n2 := len(nums2)
res := 0
dp := make([]int, n2 + 1)
for i := 1; i <= n1; i++ {
for j := n2; j > 0; j-- { // 反序
if nums1[i - 1] == nums2[j - 1] {
dp[j] = dp[j - 1] + 1
res = max(res, dp[j])
} else {
dp[j] = 0
}
}
}
return res
}最长重复子数组 - 滑动窗口
func findLength(nums1 []int, nums2 []int) int {
n1 := len(nums1)
n2 := len(nums2)
res := 0
for i := 0; i < n1; i++ {
res = max(res, process(nums1, nums2, i, 0, min(n1 - i, n2)))
}
for i := 0; i < n2; i++ {
res = max(res, process(nums1, nums2, 0, i, min(n1, n2 - i)))
}
return res
}
func process(nums1, nums2 []int, start1, start2, size int) int {
res := 0
cur := 0
for i := 0; i < size; i++ {
if nums1[start1 + i] == nums2[start2 + i] {
cur++
res = max(res, cur)
} else {
cur = 0
}
}
return res
}最长重复子数组 - 二分查找 + 哈希
如果数组 A 和 B 有一个长度为 k 的公共子数组，那么它们一定有长度为 j <= k 的公共子数组。这样我们可以通过二分查找的方法找到最大的 k。
而为了优化时间复杂度，在二分查找的每一步中，我们可以考虑使用哈希的方法来判断数组 A 和 B 中是否存在相同特定长度的子数组。
注意到序列内元素值小于 100 ，我们使用 Rabin-Karp 算法来对序列进行哈希：形象地说，就是把 S 看成一个类似 base 进制的数（左侧为高位，右侧为低位），它的十进制值就是这个它的哈希值。由于这个值一般会非常大，因此会将它对另一个素数 mod 取模。
当我们要在一个序列 S 中算出所有长度为 len 的子序列的哈希值时，我们可以用类似滑动窗口的方法，在线性时间内得到这些子序列的哈希值。例如，如果我们当前得到了 S[0:len] 的哈希值，希望算出 S[1:len+1] 的哈希值时，有下面这个公式：
在二分查找的每一步中，我们使用哈希表分别存储这两个数组的所有长度为 len 的子数组的哈希值，将它们的哈希值进行比对，如果两序列存在相同的哈希值，则认为两序列存在相同的子数组。为了防止哈希碰撞，我们也可以在发现两个子数组的哈希值相等时，进一步校验它们本身是否确实相同，以确保正确性。但该方法在本题中很难发生哈希碰撞，因此略去进一步校验的部分。
const (
base = 113
mod = 1000000009
)
var (
A []int
B []int
)
func findLength(nums1 []int, nums2 []int) int {
A = nums1
B = nums2
// 长度为 left | right 的公共子数组
// [)
left, right := 1, min(len(nums1), len(nums2)) + 1
for left < right {
mid := left + ((right - left) >> 1)
if check(mid) { // 有长度为 mid 的公共子数组
left = mid + 1
} else {
right = mid
}
}
// left = mid + 1，所以这里要 - 1
return left - 1
}
func check(length int) bool {
hashA := 0
for i := 0; i < length; i++ {
// base 进制，由于数值太大，模一个大质数
hashA = (hashA * base + A[i]) % mod
}
bucketA := map[int]bool{ hashA: true }
mult := qPow(base, length - 1)
for i := length; i < len(A); i++ {
// 大体意思是：删除A[i - length]的影响，添加A[i]的影响
hashA = ((hashA - A[i - length] * mult % mod + mod) % mod * base + A[i]) % mod
bucketA[hashA] = true
}
hashB := 0
for i := 0; i < length; i++ {
hashB = (hashB * base + B[i]) % mod
}
if bucketA[hashB] {
return true
}
for i := length; i < len(B); i++ {
hashB = ((hashB - B[i - length] * mult % mod + mod) % mod * base + B[i]) % mod
if bucketA[hashB] {
return true
}
}
return false
}
func qPow(x, n int) int {
res := 1
for n != 0 {
if n & 1 != 0 {
res = res * x % mod
}
x = x * x % mod
n >>= 1
}
return res
}判断子序列 - 双指针
func isSubsequence(s string, t string) bool {
sLen, tLen := len(s), len(t)
i, j := 0, 0
for i < sLen && j < tLen {
if s[i] == t[j] {
i++
j++
} else {
j++
}
}
return i == sLen
}判断子序列 - 动态规划
func isSubsequence(s string, t string) bool {
sLen, tLen := len(s), len(t)
// dp[i][j]: 以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度
dp := make([][]int, sLen + 1)
for i := range dp {
dp[i] = make([]int, tLen + 1)
}
for i := 1; i <= sLen; i++ {
for j := 1; j <= tLen; j++ {
if s[i - 1] == t[j - 1] {
// 找到了一个相同的字符，要在dp[i-1][j-1]的基础上加1
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
// 相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j]的数值就是看s[i - 1]与t[j - 2]的比较结果了
dp[i][j] = dp[i][j - 1]
}
}
}
return dp[sLen][tLen] == sLen
}回文子串 - 双指针
func countSubstrings(s string) int {
n := len(s)
res := 0
for i := 0; i < n; i++ {
// 中心点为 i
left, right := i, i
for left >= 0 && right < n && s[left] == s[right] {
res++
left--
right++
}
// 中心点为 i 和 i + 1 的中间
left, right = i, i + 1
for left >= 0 && right < n && s[left] == s[right] {
res++
left--
right++
}
}
return res
}回文子串 - 动态规划
func countSubstrings(s string) int {
n := len(s)
res := 0
// dp[i][j]: 子串 s[i:j + 1] 是否回文
dp := make([][]bool, n)
for i := range dp {
dp[i] = make([]bool, n)
}
// dp[i][j] 依赖 dp[i + 1][j - 1]，所以要调整遍历顺序
for i := n - 1; i >= 0; i-- {
for j := i; j < n; j++ {
if s[i] == s[j] {
// 相同字符或相邻字符
if j - i == 0 || j - i == 1 {
dp[i][j] = true
} else {
dp[i][j] = dp[i + 1][j - 1]
}
if dp[i][j] {
res++
}
}
}
}
return res
}