力扣每日一题 6/16 字符串 + 随机一题 动态规划/数学

521.最长特殊序列 I【简单】

题目：

给你两个字符串 a 和 b，请返回 这两个字符串中 最长的特殊序列 的长度。如果不存在，则返回 -1 。

「最长特殊序列」 定义如下：该序列为 某字符串独有的最长

子序列

（即不能是其他字符串的子序列） 。

字符串 s 的子序列是在从 s 中删除任意数量的字符后可以获得的字符串。

• 例如，"abc" 是 "aebdc" 的子序列，因为删除 "aebdc" 中斜体加粗的字符可以得到 "abc" 。 "aebdc" 的子序列还包括 "aebdc" 、 "aeb" 和 "" (空字符串)。

示例 1：

输入: a = "aba", b = "cdc"

输出: 3

解释: 最长特殊序列可为 "aba" (或 "cdc")，两者均为自身的子序列且不是对方的子序列。

示例 2：

输入：a = "aaa", b = "bbb"

输出：3

解释: 最长特殊序列是 "aaa" 和 "bbb" 。

示例 3：

输入：a = "aaa", b = "aaa"

输出：-1

解释: 字符串 a 的每个子序列也是字符串 b 的每个子序列。同样，字符串 b 的每个子序列也是字符串 a 的子序列。

提示：

• 1 <= a.length, b.length <= 100
• a 和 b 由小写英文字母组成

分析问题：

       这道题很有意思哈，没有自己的主见真的会被题目给带偏，很容易去想如何切割或者如何比较能得到最大长度，但是其实这些都不需要，只需要对比 a是否等于b 即可。

       如果a不等于b的话，直接可以返回a,b的最大长度，可以这样想：如果a!=b， 那取a的全部或者b的全部肯定都不可能是另一方的子序列。

       如果 a等于b ，那可以直接返回 -1。

代码实现：

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        return max(len(a), len(b)) if a != b else -1

总结：

       其实这道题就像是一个脑筋急转弯哈，没啥可讲的，就看能不能转过来这个圈了。

随机一题：343.整数拆分【中等】

题目：

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2

输出: 1

解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10

输出: 36

解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

• 2 <= n <= 58

题目分析：

       这道题其实就是在考数学和动态规划了，但是其实我认为这道题数学是一种做法，动态规划是另一种做法，他们两个并不是一体的。所以这道题我提供了两种解法思路。

动态规划：

• 首先定义一个内部函数 integer_break 来处理具体的计算逻辑。
• 对于小于等于 3 的整数 n，直接返回 n - 1，因为对于 n = 2，拆分为 1 + 1，乘积为 1，而直接返回 1 ；对于 n = 3，拆分为 1 + 2，乘积为 2，而直接返回 2 。
• 然后创建一个长度为 n + 1 的 dp 数组，用于保存中间计算的结果。
• 初始化 dp[1] = 1，dp[2] = 2，dp[3] = 3。
• 从 4 开始到 n 进行遍历，对于每个 i，通过内层循环枚举所有可能的拆分方式。内层循环中，j 从 1 到 i // 2 + 1，表示将 i 拆分为 j 和 i - j 两部分，然后更新 dp[i] 为当前最大值，即之前计算的 dp[j] * dp[i - j] 与当前 dp[i] 的最大值。
• 最终返回 dp 数组的最后一个元素，即 dp[-1]，就是 n 的最大乘积拆分结果。

代码实现：

class Solution:
    def integerBreak(self, n: int) -> int:
        def integer_break(n):
            if n <= 3:
                return n - 1
            dp = [0] * (n + 1)
            dp[1] = 1
            dp[2] = 2
            dp[3] = 3
 
            for i in range(4, n + 1):
                for j in range(1, i // 2 + 1):
                    dp[i] = max(dp[i], dp[j] * dp[i - j])
            return dp[-1]
        return integer_break(n)

数学思维：

• 首先定义了一个内部函数 calc 来处理具体的计算。
• 对于小于 4 的整数 n，直接返回 n - 1。这是因为 2 拆分后最大乘积为 1（即 1 + 1），3 拆分后最大乘积为 2（即 1 + 2）。
• 对于大于等于 4 的整数 n，根据 n 除以 3 的余数进行不同的处理。

• 如果 n 除以 3 余数为 0，那么结果就是 3 的 n // 3 次方。这是因为 3 是拆分后能得到较大乘积的基本单元。
• 如果余数为 1，结果是 4 乘以 3 的 (n // 3 - 1) 次方。这是因为把一个 3 换成 2 和 2 组成 4 能得到更大的乘积。
• 如果余数为 2，结果是 2 乘以 3 的 n // 3 次方。

代码实现：

class Solution:
    def integerBreak(self, n: int) -> int:
        def calc(n):
            if n<4: return n-1
            match n%3 :
                case 0: return 3**(n//3)
                case 1: return 4*3**(n//3-1)
                case 2: return 2*3**(n//3)
        return (calc(n))

总结：

       这两段代码都是解决整数 n 拆分以获取最大乘积的问题，但其思路各有千秋。

考察的内容：

• 动态规划的思想，通过保存中间计算结果来逐步得出最终解。
• 对整数运算和余数的运用，根据不同的余数情况进行特定的处理。

学到的内容：

• 对于类似求最优解的问题，可以考虑使用动态规划来降低计算复杂度。
• 巧妙运用数学规律，如在这段代码中对 3 的组合以及根据余数的特殊处理，能够优化计算。

反思：

• 在解决问题时，要善于分析问题的特点，寻找规律，选择最合适的数据结构和算法。
• 对于整数运算和数学特性的深入理解，能够帮助我们设计更高效的算法。
• 不同的解法可能有不同的效率和适用场景，需要根据具体情况进行选择和优化。 例如，第一段代码使用动态规划，适用于较大规模的计算，但可能在空间复杂度上有一定开销；第二段代码利用数学规律，计算较为简洁，但可能对于问题的普适性需要进一步思考。

“戒除欲望，控制行为，充实生活，美好的世界。”——《yuanziyu》