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」的目前值，則更新「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)，因為我們不使用額外的空間。

方法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) {
   // 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++程式：找到具有相同左右旋轉的數字的最長子序列的詳細內容。更多資訊請關注PHP中文網其他相關文章！