桂林网站建设 腾云,做ps兼职的网站,256内存vps装wordpress,做地方网站如何盈利作者#xff1a;翟天保Steven 版权声明#xff1a;著作权归作者所有#xff0c;商业转载请联系作者获得授权#xff0c;非商业转载请注明出处 题目描述#xff1a;
好久没做题目了#xff0c;近期刷抖音碰到一个题目#xff0c;乍一看不是很难#xff0c;但是手生了翟天保Steven 版权声明著作权归作者所有商业转载请联系作者获得授权非商业转载请注明出处 题目描述
好久没做题目了近期刷抖音碰到一个题目乍一看不是很难但是手生了就写个玩玩大家轻喷。
两个字符串比较如abcdefg和25abdfxx返回位置0多出:25位置2缺少:c位置4缺少:e位置6错误应为g。 解题思路
我看很多人说双指针法、动态规划能解我暂时没想那么多就用了简单的双循环滑动窗口。
取idx1和idx2作为滑动窗口起点。以字符串1为基准遍历字符串2寻找相同的字符。当两个字符一致时判断下j和idx2的大小情况如果j大且i和idx1一致说明字符串2相同字符前面有一段字符是多出的。之后将idx1加1再使idx2等于j1这样可以使两个字符串的滑动窗口从相同字符后的一个位置开始。如果i大于idx1且j和idx2一致同理说明字符串1相同字符前面缺少了一段字符。之后idx2加1idx1等于i1即可。如果i大于idx1j也大于idx2说明两个字符串相同字符前各有一段不相同字符即匹配错误。若上述三个条件都不满足那就说明碰到了连续相同字符串。令idx1和idx2都加1跳过即可。如果i走到最后都没找到匹配对象则从idx1到字符串1结尾所有字符都匹配失败了。 测试代码
#include iostream
#include string
using namespace std;void compareStrings(std::string str1, std::string str2) {int len1 str1.length();int len2 str2.length();int idx1 0;int idx2 0;for (int i 0; i len1; i) {for (int j idx2; j len2; j) {if (str1[i] str2[j]) {if (j idx2 i idx1) {cout 位置 i 多出 str2.substr(idx2, j - idx2) endl;idx1;idx2 j 1;}else if (i idx1 j idx2) {cout 位置 idx1 缺少 str1.substr(idx1, i - idx1) endl;idx1 i 1;idx2;}else if (i idx1 j idx2) {cout 位置 idx1 错误应为 str1.substr(idx1, i - idx1) endl;idx1 i 1;idx2 j 1;}else{idx1;idx2;}break;} }if (i (len1 - 1) (idx1 len1)) {cout 位置 idx1 错误应为 str1.substr(idx1, i - idx1 1) endl;}}
}int main() {std::string str1 abcdefg;std::string str2 25abdfxx;cout 字符串1 str1 endl;cout 字符串2 str2 endl;compareStrings(str1, str2);return 0;
}
测试结果
字符串如题目要求时结果如下可以发现是满足的。 加几个字符再试试依然可行。 中间内容再打乱一些暂无问题。 多几个重复字符按照我的逻辑输出结果是对的但不知道题目是不是这意思。 如果代码有什么需要改进的或者有什么bug欢迎评论留言我会及时更正以免误导他人~ 如果文章帮助到你了可以点个赞让我知道我会很快乐~加油
