double sequence issue

xiaolingtong@bilibili.com · xiaolingtong@bilibili.com · commit 648f284426d2 · 2023-11-11T16:56:27.000+08:00
diff --git a/src/com/blankj/hard/_115/Solution.kt b/src/com/blankj/hard/_115/Solution.kt
@@ -0,0 +1,50 @@
+package com.blankj.hard._115
+
+import com.blankj.ext.print
+import kotlin.math.min
+
+class Solution {
+    fun numDistinct(s: String, t: String): Int {
+        if (s.length < t.length) return 0
+        val dp = Array(s.length + 1) { IntArray(t.length + 1) }
+        for (i in s.indices) {
+            dp[i][0] = 1
+        }
+        for (i in t.indices) {
+            dp[0][i] = 0
+        }
+        dp[0][0] = 1
+        for (i in s.indices) {
+            for (j in 0 until min(i + 1, t.length)) {
+                if (s[i] == t[j]) {
+                    dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1]
+                } else {
+                    dp[i + 1][j + 1] = dp[i][j + 1]
+                }
+            }
+        }
+        return dp[s.length][t.length]
+    }
+
+    fun numDistinctWithLessSpace(s: String, t: String): Int {
+        if (s.length < t.length) return 0
+        val dp = IntArray(t.length + 1)
+        if (s.isNotEmpty()) {
+            dp[0] = 1
+        }
+        for (i in s.indices) {
+            for (j in min(i, t.length - 1) downTo 0) {
+                if (s[i] == t[j]) {
+                    dp[j + 1] += dp[j]
+                }
+            }
+        }
+        return dp[t.length]
+    }
+
+}
+
+fun main() {
+    Solution().numDistinct("rabbbit", "rabbit").print()
+    Solution().numDistinct("babgbag", "bag").print()
+}
diff --git a/src/com/blankj/hard/_132/Solution.kt b/src/com/blankj/hard/_132/Solution.kt
@@ -0,0 +1,37 @@
+package com.blankj.hard._132
+
+import com.blankj.ext.print
+import kotlin.math.min
+
+class Solution {
+    fun minCut(s: String): Int {
+        val isPal = Array(s.length) { BooleanArray(s.length) }
+        for (right in s.indices) {
+            for (left in 0..right) {
+                if (s[right] == s[left] && (right - left <= 2 || isPal[left + 1][right - 1])) {
+                    isPal[left][right] = true
+                }
+            }
+        }
+        val dp = IntArray(s.length)
+        for (i in s.indices) {
+            if (isPal[0][i]) {
+                dp[i] = 0
+            } else {
+                dp[i] = i
+                for (j in 1..i) {
+                    if (isPal[j][i]) {
+                        dp[i] = min(dp[i], dp[j - 1] + 1)
+                    }
+                }
+            }
+        }
+        return dp.last()
+    }
+}
+
+fun main() {
+    Solution().minCut("aab").print()
+    Solution().minCut("a").print()
+    Solution().minCut("ab").print()
+}
diff --git a/src/com/blankj/medium/_1143/Solution.kt b/src/com/blankj/medium/_1143/Solution.kt
@@ -0,0 +1,32 @@
+package com.blankj.medium._1143
+
+import com.blankj.ext.print
+import kotlin.math.max
+
+
+class Solution {
+    fun longestCommonSubsequence(text1: String, text2: String): Int {
+        val len1 = text1.length
+        val len2 = text2.length
+        if (len1 < len2) {
+            return longestCommonSubsequence(text2, text1)
+        }
+        val dp = Array<IntArray>(2) { IntArray(len2 + 1) }
+        for (i in text1.indices) {
+            for (j in text2.indices) {
+                if (text1[i] == text2[j]) {
+                    dp[(i + 1) % 2][j + 1] = dp[i % 2][j] + 1
+                } else {
+                    dp[(i + 1) % 2][j + 1] = max(dp[i % 2][j + 1], dp[(i + 1) % 2][j])
+                }
+            }
+        }
+        return dp[len1 % 2][len2]
+    }
+}
+
+fun main() {
+    Solution().longestCommonSubsequence("abcde", "ace").print()
+    Solution().longestCommonSubsequence("abc", "abc").print()
+    Solution().longestCommonSubsequence("abc", "def").print()
+}
diff --git a/src/com/blankj/medium/_873/Solution.kt b/src/com/blankj/medium/_873/Solution.kt
@@ -0,0 +1,29 @@
+package com.blankj.medium._873
+
+import com.blankj.ext.print
+import kotlin.math.max
+
+
+class Solution {
+    fun lenLongestFibSubseq(arr: IntArray): Int {
+        if (arr.isEmpty()) return 0
+        val dp = Array(arr.size) { IntArray(arr.size) }
+        var res = 2
+        val map = arr.mapIndexed { index, i -> i to index }
+            .associate { it }
+            .toMutableMap()
+        for (i in 1 until arr.size) {
+            for (j in 0 until i) {
+                val k = map.getOrDefault(arr[i] - arr[j], -1)
+                dp[i][j] = if (k in 0 until j) dp[j][k] + 1 else 2
+                res = max(res, dp[i][j])
+            }
+        }
+        return if (res > 2) res else 0
+    }
+}
+
+fun main() {
+    Solution().lenLongestFibSubseq(intArrayOf(1,2,3,4,5,6,7,8)).print()
+    Solution().lenLongestFibSubseq(intArrayOf(1,3,7,11,12,14,18)).print()
+}
diff --git a/src/com/blankj/medium/_926/Solution.kt b/src/com/blankj/medium/_926/Solution.kt
@@ -0,0 +1,28 @@
+package com.blankj.medium._926
+
+import com.blankj.ext.print
+import kotlin.math.min
+
+
+class Solution {
+    fun minFlipsMonoIncr(s: String): Int {
+        if (s.isEmpty()) return 0
+        val dp = Array(2) { IntArray(2) }
+        dp[0][0] = if (s[0] == '0') 0 else 1
+        dp[1][0] = if (s[0] == '1') 0 else 1
+
+        for (i in 1 until s.length) {
+            val prev0 = dp[0][(i - 1) % 2]
+            val prev1 = dp[1][(i - 1) % 2]
+            dp[0][i % 2] = prev0 + if (s[i] == '1') 1 else 0
+            dp[1][i % 2] = min(prev1, prev0) + if (s[i] == '0') 1 else 0
+        }
+        return min(dp[0][s.lastIndex % 2], dp[1][s.lastIndex % 2])
+    }
+}
+
+fun main() {
+    Solution().minFlipsMonoIncr("00110").print()
+    Solution().minFlipsMonoIncr("010110").print()
+    Solution().minFlipsMonoIncr("00011000").print()
+}
diff --git a/src/com/blankj/medium/_97/Solution.kt b/src/com/blankj/medium/_97/Solution.kt
@@ -0,0 +1,76 @@
+package com.blankj.medium._97
+
+import com.blankj.ext.print
+
+class Solution {
+    // 状态方程 dp[i][j] 表示 s1[0..i] 和 s2[0..j] 能不能交织成 s3[0..i+j+1]
+    /**              dp[i-1][j]       s1[i] == s3[i+j+1]
+     * dp[i][j] =
+     *               dp[i][j - 1]     s2[i] == s3[i + j + 1]
+     * 当 i == 0 或者 j == 0 时, i - 1 或者 j - 1 == -1, 意味着当其中一方变为空串了,只剩另一个数组,
+     * 这时的 dp[i][j] 就取决于 非空的数组下标元素是否于 s3 下标相等的同时, 以及前一位 dp[i - 1][j - 1] 的值
+     * 因为实际数据结构不存在 -1 下标, 故整体数组需要右移一格
+     */
+    fun isInterleave(s1: String, s2: String, s3: String): Boolean {
+        if (s1.length + s2.length != s3.length) return false
+//        因为数组不支持表示 -1 下标, 故整体右移一格
+        val dp = Array(s1.length + 1) { BooleanArray(s2.length + 1) }
+        dp[0][0] = true
+        for (i in s1.indices) {
+            dp[i + 1][0] = s1[i] == s3[i] && dp[i][0]
+        }
+        for (i in s2.indices) {
+            dp[0][i + 1] = s2[i] == s3[i] && dp[0][i]
+        }
+        for (i in s1.indices) {
+            for (j in s2.indices) {
+                val ch1 = s1[i]
+                val ch2 = s2[j]
+                val ch3 = s3[i + j + 1]
+                dp[i + 1][j + 1] = (ch1 == ch3 && dp[i][j + 1])
+                        || (ch2 == ch3 && dp[i + 1][j])
+            }
+        }
+        return dp[s1.length][s2.length]
+    }
+
+
+    fun isInterleaveWithLessSpace(s1: String, s2: String, s3: String): Boolean {
+        if (s1.length + s2.length != s3.length) return false
+//        因为数组不支持表示 -1 下标, 故整体右移一格
+        if (s1.length < s2.length) return isInterleaveWithLessSpace(s2, s1, s3)
+        val dp = BooleanArray(s2.length + 1)
+        dp[0] = true
+
+        for (i in s2.indices) {
+            dp[i + 1] = s2[i] == s3[i] && dp[i]
+        }
+        // 二维转一维后, 逐行遍历并更新 dp 数组的值
+        // dp[j] 相当于之前的 f(j, j)
+        for (i in s1.indices) {
+            dp[0] = s1[i] == s3[i] && dp[0]
+            for (j in s2.indices) {
+                val ch1 = s1[i]
+                val ch2 = s2[j]
+                val ch3 = s3[i + j + 1]
+                dp[j + 1]= (ch1 == ch3 && dp[j + 1])
+                        || (ch2 == ch3 && dp[j])
+            }
+        }
+        return dp[s2.length]
+    }
+}
+
+fun main() {
+    Solution().isInterleave(
+        "aabcc",
+        "dbbca",
+        "aadbbcbcac"
+    ).print()
+    Solution().isInterleave(
+        "aabcc", "dbbca", "aadbbbaccc"
+    ).print()
+    Solution().isInterleave(
+        "", "", ""
+    ).print()
+}
