数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++程序：查找具有相同左右旋转的最长子序列
在这个问题中，我们需要找到具有相同左右旋转的最长子序列的长度。左旋转意味着将字符串的所有字符向左移动，并将第一个字符移动到末尾。右旋转意味着将字符串的所有字符向右移动，并将最后一个字符移动到开头。
问题陈述 – 我们给定一个包含数字字符的字符串str，需要找到具有相同左右旋转的最长子序列。
示例
输入 – str = "323232",
输出 – 6
解释 – 具有相同左右旋转的最长子序列是“323232”。左旋转是“232323”，右旋转是“232323”。
输入 – str = ‘00010100’
输出 – 6
解释 – 具有相同左右旋转的最长子序列是“000000”。
输入 – str = ‘092312110431010’
输出 – 6
解释 – 有两个长度为6的子序列具有相同的左右旋转。第一个是“010101”，第二个是“101010”。
方法一
在这种方法中，我们将找到给定字符串的所有可能的子序列。之后，我们将检查字符串的左旋转和右旋转是否相同。我们将使用递归方法来查找所有可能的子序列。
算法
用零初始化全局变量“maxLen”，以存储具有相同左右旋转的最长子序列的长度。
定义isRightSameLeft()函数来检查字符串是否具有相同的左右旋转。
在函数内部，使用substr()方法来左右旋转字符串。
getAllSubSeq()函数用于查找给定字符串的所有可能的子序列。
定义基本情况。如果“str”为空，我们将获得子序列并执行isRightSameLeft()函数以检查子序列是否具有相同的左右旋转。如果是，则如果其长度大于“maxLen”的当前值，则更新“maxLen”变量的值。
从“str”中移除第一个字符并在其后附加“out”字符串后进行递归调用。
在移除第一个字符并将“out”字符串保持不变后，再次进行递归函数调用。在此递归调用中，我们排除“str”的第一个字符。
示例
#include <iostream>
#include <string>
using namespace std;
// Defining global variable to store the length of the longest subsequence according to the given condition
int maxLen = 0;
// function to check if the string is the same after the left rotation
bool 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 string
void 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)，因为我们不使用额外的空间。
方法二
在这里，我们优化了上述方法。我们可以观察样本输入的解决方案。只有当子序列包含相同的字符或交替的两个不同字符，并且长度为偶数时，子序列的左旋转和右旋转才相同。
算法
使用两个嵌套循环来组合任意两个数字。
定义变量“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) {
// 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)。
74 次浏览
