Program C++: cari urutan nombor terpanjang dengan putaran kiri dan kanan yang sama

Dalam masalah ini, kita perlu mencari panjang maksimum urutan dengan putaran kiri dan kanan yang sama. Putaran kiri bermaksud memindahkan semua aksara dalam rentetan ke kiri, dan menggerakkan aksara pertama pada penghujungnya. Putaran kanan bermaksud memindahkan semua aksara rentetan ke kanan dan mengalihkan aksara terakhir ke permulaan.

Pernyataan Masalah – Kami diberi rentetan str yang mengandungi nombor dan perlu mencari urutan panjang maksimum dengan putaran kiri dan kanan yang sama.

Contoh

Masukkan -str="323232",

Output– 6

Penjelasan - Susunan terpanjang dengan pusingan kiri dan kanan yang sama ialah "323232". Putar ke kiri ke '232323' dan putar ke kanan ke '232323'.

Masukkan -str = ‘00010100’

Output– 6

Penjelasan – Susunan terpanjang dengan putaran kiri dan kanan yang sama ialah "000000".

Masuk -str = ‘092312110431010’

Output– 6

Penjelasan – Terdapat 2 kemungkinan urutan panjang 6 dengan putaran kiri dan kanan yang sama. Yang pertama ialah "010101" dan yang kedua ialah "101010".

Kaedah 1

Dalam kaedah ini kita akan menemui semua kemungkinan urutan rentetan yang diberikan. Selepas itu kita akan menyemak sama ada putaran kiri dan kanan rentetan adalah sama. Kami akan menggunakan kaedah rekursif untuk mencari semua kemungkinan susulan.

Algoritma

• Mulakan pembolehubah global "maxLen" kepada sifar untuk menyimpan panjang urutan terpanjang yang sama untuk putaran kiri dan kanan.

• Tentukan fungsi isRightSameLeft() untuk menyemak sama ada putaran kiri dan kanan rentetan adalah sama.

• Di dalam fungsi, gunakan kaedah substr() untuk memutar rentetan ke kiri dan kanan.

Fungsi

• getAllSubSeq() digunakan untuk mencari semua kemungkinan urutan rentetan yang diberikan.

• Tentukan kes asas. Jika str kosong, kita mendapat urutan dan laksanakan fungsi isRightSameLeft() untuk menyemak sama ada jujukan mempunyai putaran kiri dan kanan yang sama. Jika ya, kemas kini nilai pembolehubah "maxLen" jika panjangnya lebih besar daripada nilai semasa "maxLen".

• Buat panggilan rekursif selepas mengalih keluar aksara pertama daripada "str" ​​​​dan menambahkan rentetan "keluar".

• Selepas mengalih keluar aksara pertama dan membiarkan rentetan "keluar" tidak berubah, buat satu lagi panggilan fungsi rekursif. Dalam panggilan rekursif ini, kami mengecualikan aksara pertama "str".

Contoh

#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;
}

Output

The longest subsequence of str having same left and right rotation is 6

Kerumitan masa - O(N*2N). Di sini O(N) untuk membandingkan putaran kiri dan kanan dan O(2N) untuk mencari semua kemungkinan susulan.

Kerumitan ruang - O(1) kerana kami tidak menggunakan ruang tambahan.

Kaedah 2

Di sini, kami telah mengoptimumkan kaedah di atas. Kita boleh melihat penyelesaian input sampel. Putaran kiri dan kanan bagi suatu urutan adalah sama hanya jika urutan tersebut mengandungi aksara yang sama atau secara berselang-seli mengandungi dua aksara yang berbeza dan mempunyai panjang genap.

Algoritma

• Gunakan dua gelung bersarang untuk menggabungkan mana-mana dua nombor.

• Takrifkan pembolehubah 'cnt' untuk mencari panjang urutan yang mengandungi dua nombor secara berselang-seli, dan mulakannya kepada sifar.

• Tentukan pembolehubah "pertama" boolean untuk menjejaki sama ada aksara seterusnya harus menjadi aksara ke-i atau ke-j.

• Gunakan gelung untuk melintasi rentetan.

• Jika dahulu == benar dan str[k] - '0' == I, gantikan nilai 'first' dan tambahkan 'cnt' sebanyak 1.

• Jika dahulu == false dan str[k] - '0' == j, gantikan nilai 'first' sekali lagi dan tambahkan 'cnt' sebanyak 1.

• Jika i dan j tidak sama dan nilai "cnt" adalah ganjil, kurangkan ia sebanyak 1.

• Jika nilai cnt lebih besar daripada "res", kemas kini nilai pembolehubah "res".

Contoh

#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;
}

Output

The longest subsequence of str having same left and right rotation is 6

Kerumitan masa - O(10*10*N) kerana kita menemui urutan daripada rentetan yang mengandungi gabungan nombor.

Kerumitan ruang - O(1) kerana kami tidak menggunakan ruang dinamik.

Tutorial ini mengajar kita dua kaedah untuk mencari urutan terpanjang yang mengandungi putaran kiri dan kanan yang sama. Kaedah pertama ialah kaedah mudah, kaedah ini sangat memakan masa dan kami tidak boleh menggunakannya untuk jumlah input yang banyak.

Kaedah kedua dioptimumkan dan kerumitan masanya hampir sama dengan O(N).

Atas ialah kandungan terperinci Program C++: cari urutan nombor terpanjang dengan putaran kiri dan kanan yang sama. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!