C++ 程序求具有相同左右旋转的数字的最长子序列
在这个问题中，我们需要找到具有相同左右旋转的子序列的最大长度。左旋转意味着将字符串的所有字符向左移动，并将第一个字符放在末尾。右旋转意味着将字符串的所有字符向右移动，并将最后一个字符放在开头。
问题描述– 我们给出了包含数字的字符串 str，需要找到具有相同左右旋转的最大长度的子序列。
示例
输入– str = "323232",
输出– 6
解释– 具有相同左右旋转的最长子序列是 '323232'。左旋转为'232323'，右旋转为'232323'。
输入– str = '00010100'
输出 – 6
解释 – 具有相同左旋转和右旋转的最长子序列是'000000'。
输入– str = '092312110431010'
输出 – 6
解释 – 有 2 个可能的子序列，长度为 6，具有相同的左旋转和右旋转。第一个是'010101'，第二个是'101010'。
方法 1
在此方法中，我们将找到给定字符串的所有可能的子序列。之后，我们将检查字符串的左旋转和右旋转是否相同。我们将使用递归方法来查找所有可能的子序列。
算法
用零初始化"maxLen"全局变量，以存储具有相同左右旋转的最长子序列的长度。
定义 isRightSameLeft() 函数来检查字符串是否具有相同的左右旋转。
在函数内部，使用 substr() 方法对字符串进行左右旋转。
getAllSubSeq() 函数用于查找给定字符串的所有可能的子序列。
定义基本情况。如果'str'为空，我们获取子序列并执行isRightSameLeft()函数来检查子序列是否具有相同的左右旋转。如果是，则在其长度大于'maxLen'的当前值时更新'maxLen'变量的值。
从'str'中删除第一个字符并将其附加到'out'字符串后进行递归调用。
删除第一个字符并保持'out'字符串不变后再次进行递归函数调用。在此递归调用中，我们排除了'str'的第一个字符。
示例
#include <iostream>
#include <string>
using namespace std;
// 定义全局变量，根据给定条件存储最长子序列的长度
int maxLen = 0;
// 函数检查字符串左旋转后是否相同
bool isRightSameLeft(string str) {
int len = str.length();
return str.substr(1, len - 1) + str[0] == str[len - 1] + str.substr(0, len - 1);
}
// 函数获取字符串的所有子序列
void getAllSubSeqs(string str, string out) {
// 如果字符串为空，则获取子序列。检查其左右旋转是否相同
if (str.empty()) {
if (isRightSameLeft(out))
maxLen = max(maxLen, (int)out.length());
return;
}
// 递归情况从 str 中删除第一个字符，并将其添加到输出中
getAllSubSeqs(str.substr(1), out + str[0]);
// 从 str 中删除第一个字符，并将其丢弃
if (str.length() > 1)
getAllSubSeqs(str.substr(1), out);
}
int main() {
string str = "323232";
string out = "";
getAllSubSeqs(str, out);
cout << "str 中具有相同左右旋转的最长子序列是 " << maxLen;
return 0;
}
输出
str 中具有相同左右旋转的最长子序列是 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 <bits/stdc++.h>
using namespace std;
int getLongSubSeq(string str) {
// 存储字符串的长度
int len = str.size(), res = 0;
// 遍历所有可能的两个数字的组合
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
// 存储当前组合的交替序列的长度
int cnt = 0;
// 跟踪第 i 位或第 j 位数字的轮换
bool first = true;
// 遍历字符串
for (int k = 0; k < len; k++) {
// 如果当前数字等于 I，且第一位为真，则增加计数
if (first == true and str[k] - '0' == i) {
first = false;
cnt++;
} else if (first == false and str[k] - '0' == j) {
// 如果当前数字等于 j，且第一位为假，则增加计数
first = true;
cnt++;
}
}
// 如果序列为奇数且 i 和 j 不同，则减少计数
if (i != j and cnt % 2 == 1)
cnt--;
// 更新 res
res = max(cnt, res);
}
}
return res;
}
int main() {
string str = "00010100";
cout << "具有相同左右旋转的 str 的最长子序列是 " << getLongSubSeq(str);
return 0;
}
输出
具有相同左右旋转的 str 的最长子序列是 6
时间复杂度 – O(10*10*N)，因为我们从包含数字组合的字符串中找到子序列。
空间复杂度 – O(1)，因为我们不使用动态空间。
本教程教我们两种方法来查找包含相同左右旋转的最长子序列。第一种方法是简单的方法，非常耗时，我们不能将它用于大量输入。
第二种方法经过优化，因为其时间复杂度几乎等于 O(N)。
