深圳最专业的高端网站建设,河南企业网站建设公司,宁波做360网站推广,linux主机做网站博客主页#xff1a;誓则盟约系列专栏#xff1a;IT竞赛 专栏关注博主#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出#xff0c;及时修改感谢大家点赞#x1f44d;收藏⭐评论✍ 521.最长特殊序列 I【简单】
题目#xff1a;
给你两个字符串 a 和 b誓则盟约系列专栏IT竞赛 专栏关注博主后期持续更新系列文章如果有错误感谢请大家批评指出及时修改感谢大家点赞收藏⭐评论✍ 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 100a 和 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] 1dp[2] 2dp[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 - 1dp [0] * (n 1)dp[1] 1dp[2] 2dp[3] 3for 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 13 拆分后最大乘积为 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 n4: return n-1match 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》
