資料結構
網路
關係資料庫管理系統 (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 次瀏覽
