新手如何做移动端网站,网站开发页面设计,可以自己做安卓app的网站,最便宜的购物网站排名本文涉及知识点
C贪心
LeetCode1616. 分割两个字符串得到回文串
给你两个字符串 a 和 b #xff0c;它们长度相同。请你选择一个下标#xff0c;将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串#xff1a; aprefix 和 asuffix #xff0c;满足 a aprefi…本文涉及知识点
C贪心
LeetCode1616. 分割两个字符串得到回文串
给你两个字符串 a 和 b 它们长度相同。请你选择一个下标将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串 aprefix 和 asuffix 满足 a aprefix asuffix 同理由 b 可以得到两个字符串 bprefix 和 bsuffix 满足 b bprefix bsuffix 。请你判断 aprefix bsuffix 或者 bprefix asuffix 能否构成回文串。 当你将一个字符串 s 分割成 sprefix 和 ssuffix 时 ssuffix 或者 sprefix 可以为空。比方说 s “abc” 那么 “” “abc” “a” “bc” “ab” “c” 和 “abc” “” 都是合法分割。 如果 能构成回文字符串 那么请返回 true否则返回 false 。 注意 x y 表示连接字符串 x 和 y 。 示例 1 输入a “x”, b “y” 输出true 解释如果 a 或者 b 是回文串那么答案一定为 true 因为你可以如下分割 aprefix “”, asuffix “x” bprefix “”, bsuffix “y” 那么 aprefix bsuffix “” “y” “y” 是回文串。 示例 2 输入a “xbdef”, b “xecab” 输出false 示例 3 输入a “ulacfd”, b “jizalu” 输出true 解释在下标为 3 处分割 aprefix “ula”, asuffix “cfd” bprefix “jiz”, bsuffix “alu” 那么 aprefix bsuffix “ula” “alu” “ulaalu” 是回文串。 提示 1 a.length, b.length 105 a.length b.length a 和 b 都只包含小写英文字母
贪心
f(a,b) 判断a的前缀b的后缀能否构成回文。返回值f(a,b) || f(b,a)。 令最优解len1 min(a前缀的长度,b后缀的长度)。 g(len)函数计算 apre(len)bsuf(len)是否是回文。 h(len)函数 a[len…n-len-1]或 b[len…n-len-1]是否是回文。 性质一如果g(len)不成立则一定不是回文。 性质二如果len2 len1g(len)不成立则g(len2)一定不成立。 推论一当g(len)不成立不需要判断更大的len。 性质三len1 len2g(len1)和g(len2)成立,h(len1)成立。则h(len2)也成立。 h(len2)涉及的子串比h(len1)短且中心相同。 推论二只需要判断f(len)成立的最大len。 两层循环时间复杂度都是O(n)。
代码
核心代码
class Solution {public:bool checkPalindromeFormation(string a, string b) {auto h [](const string str,int len) {for (int i len; i a.length()/2; i){if (str[i] ! str[a.length() - 1 - i]) {return false; }}return true;};auto f [](string a, string b) {for (int i 0; i a.length() / 2; i){if (a[i] ! b[a.length() - 1 - i]) { return h(a,i)||h(b,i); }}return true;};return f(a, b) || f(b, a);}};单元测试
string a,b;TEST_METHOD(TestMethod11){a x, b y;auto res Solution().checkPalindromeFormation(a, b);AssertEx(true, res);}TEST_METHOD(TestMethod12){a xbdef, b xecab;auto res Solution().checkPalindromeFormation(a, b);AssertEx(false, res);}TEST_METHOD(TestMethod13){a ulacfd, b jizalu;auto res Solution().checkPalindromeFormation(a, b);AssertEx(true, res);}TEST_METHOD(TestMethod14){a aejbaalflrmkswrydwdkdwdyrwskmrlfqizjezd, b uvebspqckawkhbrtlqwblfwzfptanhiglaabjea;auto res Solution().checkPalindromeFormation(a, b);AssertEx(true, res);}扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
