在这个问题中，我们需要找到左右旋转相同的子序列的最大长度。左旋转是指将字符串中的所有字符向左移动，并将末尾的第一个字符移动。右旋转意味着将所有字符串字符向右移动，并将最后一个字符移动到开头。
问题陈述 – 我们给定了包含数字的字符串str，需要找到左右旋转相同的最大长度的子序列。
示例
输入-str =“323232”，
输出– 6
立即学习“C++免费学习笔记（深入）”；
解释 – 左右旋转相同的最长子序列是“323232”。左旋转为‘232323’，右旋转为‘232323’。
输入-str = ‘00010100’
输出– 6
立即学习“C++免费学习笔记（深入）”；
说明 – 左右旋转相同的最长子序列是“000000”。
输入-str = ‘092312110431010’
输出– 6
立即学习“C++免费学习笔记（深入）”；
解释 – 有 2 个可能的长度为 6 且左右旋转相同的子序列。第一个是“010101”，第二个是“101010”。
方法 1
在这种方法中，我们将找到给定字符串的所有可能的子序列。之后，我们将检查字符串的左右旋转是否相同。我们将使用递归方法来查找所有可能的子序列。
算法
将“maxLen”全局变量初始化为零，以存储左右旋转相同的最长子序列的长度。
定义 isRightSameLeft() 函数来检查字符串左右旋转是否相同。
在函数内部，使用 substr() 方法左右旋转字符串。
getAllSubSeq() 函数用于查找给定字符串的所有可能的子序列。
定义基本情况。如果str为空，我们获取子序列并执行isRightSameLeft()函数来检查子序列是否具有相同的左右旋转。如果是，如果“maxLen”变量的长度大于“maxLen”的当前值，则更新“maxLen”变量的值。
从“str”中删除第一个字符并附加“out”字符串后进行递归调用。
删除第一个字符并保持“out”字符串不变后，再次进行递归函数调用。在此递归调用中，我们排除“str”的第一个字符。
示例
#include #include using namespace std;// Defining global variable to store the length of the longest subsequence according to the given conditionint maxLen = 0;// function to check if the string is the same after the left rotationbool isRightSameLeft(string str) { int len = str.length(); return str.substr(1, len - 1) + str[0] == str[len - 1] + str.substr(0, len - 1);}// function to get all subsequences of a stringvoid getAllSubSeqs(string str, string out) { // If the string is empty, we get the subsequences. Check if its left and right rotation is the same if (str.empty()) { if (isRightSameLeft(out)) maxLen = max(maxLen, (int)out.length()); return; } // Recursive case remove the first character from str, and add it to the output getAllSubSeqs(str.substr(1), out + str[0]); // remove the first character from str, and drop it if (str.length() > 1) getAllSubSeqs(str.substr(1), out);}int main() { string str = "323232"; string out = ""; getAllSubSeqs(str, out); cout << "The longest subsequence of str having same left and right rotation is " << maxLen; return 0;}
输出
The longest subsequence of str having same left and right rotation is 6
时间复杂度 – O(N*2N)。这里 O(N) 用于比较左右旋转，O(2N) 用于查找所有可能的子序列。
空间复杂度 – O(1)，因为我们不使用额外的空间。
方法2
这里，我们对上面的方法进行了优化。我们可以观察样本输入的解决方案。仅当子序列包含相同字符或交替包含两个不同字符且长度为偶数时，子序列的左右旋转才相同。
算法
使用两个嵌套循环来组合任意两个数字。
定义‘cnt’变量来查找交替包含两个数字的子序列的长度，并初始化为零。
定义布尔类型的“first”变量来跟踪下一个字符应该是第i个还是第j个。
使用循环遍历字符串。
如果first == true且str[k] – ‘0’ == I，则交替’first’的值并将’cnt’增加1。
如果first == false且str[k] – ‘0’== j，则再次交替’first’的值并将’cnt’增加1。
如果 i 和 j 不相等，且“cnt”值为奇数，则将其减 1。
如果 cnt 值大于“res”，则更新“res”变量的值。
示例
#include using namespace std;int getLongSubSeq(string str) { // Store the length of the string int len = str.size(), res = 0; // Traverse the all possible combination of two digits for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { // to store the length of an alternating sequence of the current combination int cnt = 0; // to track the turn of the ith or jth digit bool first = true; // traverse the string for (int k = 0; k < len; k++) { // If the current digit is equal to I, and the first is true, increment the count if (first == true and str[k] - '0' == i) { first = false; cnt++; } else if (first == false and str[k] - '0' == j) { // If the current digit is equal to j, and the first is false, increment the count first = true; cnt++; } } // If the sequence is odd and i and j are different, decrement the count if (i != j and cnt % 2 == 1) cnt--; // Update the answer res = max(cnt, res); } } return res;}int main() { string str = "00010100"; cout << "The longest subsequence of str having same left and right rotation is " << getLongSubSeq(str); return 0;}
输出
The longest subsequence of str having same left and right rotation is 6
时间复杂度 – O(10*10*N)，因为我们从包含数字组合的字符串中找到子序列。
空间复杂度 – O(1)，因为我们不使用动态空间。
本教程教给我们两种方法来查找包含相同左右旋转的最长子序列。第一种方法是简单的方法，这种方法非常耗时，而且我们不能将其用于大量输入。
第二种方法经过优化，其时间复杂度几乎等于 O(N)。
以上就是C++程序：找到具有相同左右旋转的数字的最长子序列的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444103.html
微信扫一扫 
支付宝扫一扫 
