Kod yang ditulis dalam C++: Cari rentetan terkecil dari segi leksikografi yang terdiri daripada huruf K pertama abjad dan aksara bersebelahan tidak boleh sama

Dalam dunia pengaturcaraan, menyelesaikan masalah manipulasi rentetan adalah cabaran biasa dan menarik. Masalah utama yang dihadapi ialah bagaimana untuk mendapatkan rentetan leksikografi minimum menggunakan hanya huruf K abjad, sambil mematuhi kekangan tambahan seperti tidak sepadan dengan aksara bersebelahan. Dalam artikel ini, kami berhasrat untuk menyelidiki masalah ini dan mencadangkan penyelesaian yang berkesan menggunakan bahasa pengaturcaraan C++. Dengan memperincikan kaedah berbeza yang digunakan dalam tatabahasa dan menyediakan butiran algoritma langkah demi langkah, kami boleh memperkenalkan teknik inovatif yang bertujuan untuk mencapai hasil yang baik dalam bidang yang berbeza. Kami menyediakan panduan kod boleh laku yang lengkap untuk setiap kaedah untuk menjadikannya praktikal untuk pengguna.

Tatabahasa

Sebelum meneroka algoritma dan teknik, anda perlu menetapkan sintaks yang digunakan dalam coretan kod yang berikut.

std::string findLexSmallestString(int n, int k);

Dalam sintaks ini, n merujuk kepada bilangan huruf dalam abjad, k merujuk kepada bilangan huruf yang digunakan dan fungsi menjana rentetan tersusun leksikografi terendah yang memenuhi syarat yang ditetapkan.

Algoritma

Untuk menangani dan menyelesaikan cabaran mencari rentetan leksikografi minimum tanpa pengulangan antara aksara bersebelahan hanya menggunakan sehingga K huruf abjad, kami merumuskan pendekatan berkaedah dalam bentuk algoritma.

• Mulakan rentetan kosong "ans" dan tatasusunan/vektor "digunakan" untuk menjejak aksara yang digunakan.

• Mulakan lelaran daripada aksara pertama abjad.

• Tambahkan aksara semasa pada `ans` dan tandakannya sebagai digunakan.

• Jika "ans" mempunyai berbilang aksara dan dua aksara terakhir adalah sama, cari aksara yang tersedia seterusnya dengan mengulang daripada aksara semasa kepada "n".

• Jika tiada aksara yang tersedia ditemui, undur dengan mengalih keluar aksara terakhir daripada "ans" dan tandakannya sebagai tidak digunakan.

• Ulang langkah 3-5 sehingga "ans" mencapai panjang "k".

• Kembalikan "ans" sebagai rentetan terkecil dari segi leksikografi di mana tiada dua aksara bersebelahan adalah sama, menggunakan semua huruf K pertama abjad.

Kaedah 1: Algoritma Tamak

Dalam kaedah ini, kami akan menggunakan strategi tamak untuk membina rentetan terkecil dari segi leksikografi. Proses yang sama menekankan pertimbangan yang teliti bagi setiap aksara dalam urutan sambil memastikan pilihan yang dibuat sepanjang proses ditumpukan pada meminimumkan nilai leksikografi keluaran keseluruhan.

Contoh

#include <iostream>
#include <vector>

std::string findLexSmallestGreedy(int n, int k) {
   std::string ans = "";
   std::vector<bool> used(n, false);

   for (int i = 0; i < n; i++) {
      for (int j = 0; j < k; j++) {
         if (!used[j]) {
            if (ans.empty() || ans.back() != 'a' + j) {
               ans += 'a' + j;
               used[j] = true;
               break;
            }
         }
      }
   }

   return ans;
}

int main() {
   int n = 5; // Assuming there are 5 letters in the alphabet
   int k = 3; // Assuming 3 letters will be used

   std::string result = findLexSmallestGreedy(n, k);
   std::cout << "Lexicographically Smallest String: " << result << std::endl;

   return 0;
}

Output

Lexicographically Smallest String: abc

Kaedah 2: Algoritma penjejakan ke belakang

Strategi ini melibatkan penggunaan menjejak ke belakang untuk mencari secara menyeluruh setiap gabungan watak sambil memastikan aksara berturut-turut tidak diulang. Oleh itu, dengan mempertimbangkan setiap aksara pada setiap kedudukan, kita boleh mencari rentetan terkecil dari segi leksikografi yang memenuhi kekangan yang diberikan.

Contoh

#include <iostream>
#include <vector>

bool findLexSmallestBacktracking(int n, int k, std::vector<char>& ans, std::vector<bool>& used) {
   if (ans.size() == k) {
      return true;
   }

   for (int i = 0; i < n; i++) {
      if (!used[i]) {
         if (ans.empty() || ans.back() != 'a' + i) {
            ans.push_back('a' + i);
            used[i] = true;

            if (findLexSmallestBacktracking(n, k, ans, used)) {
               return true;
            }

            ans.pop_back();
            used[i] = false;
         }
      }
   }

   return false;
}

std::string findLexSmallestStringBacktracking(int n, int k) {
   std::vector<char> ans;
   std::vector<bool> used(n, false);

   if (findLexSmallestBacktracking(n, k, ans, used)) {
      return std::string(ans.begin(), ans.end());
   }

   return "";
}

int main() {
   int n = 22;  // Assuming n = 22
   int k = 4;  // Assuming k = 4

   std::string result = findLexSmallestStringBacktracking(n, k);
   std::cout << "Lexicographically Smallest String: " << result << std::endl;

   return 0;
}

Output

Lexicographically Smallest String: abcd

Kesimpulan

Dalam artikel ini, kami meneroka masalah mencari rentetan terkecil dari segi leksikografi menggunakan huruf K pertama abjad, dengan kekangan bahawa dua aksara bersebelahan tidak boleh sama. Kami membincangkan sintaks dan menyediakan dua pendekatan berbeza untuk menyelesaikan masalah ini: algoritma tamak dan algoritma penjejakan ke belakang. Algoritma tamak menggunakan strategi untuk meminimumkan nilai leksikografi rentetan yang terhasil, manakala algoritma penjejakan belakang meneroka semua kombinasi yang mungkin untuk mencari rentetan yang dikehendaki. Contoh kod C++ yang disediakan menunjukkan pelaksanaan setiap kaedah dan membolehkan kami menjana rentetan minimum secara leksikografik dengan cekap. Berbekalkan pengetahuan ini, anda kini boleh menyelesaikan masalah manipulasi rentetan yang serupa dengan yakin dan mengoptimumkan kod anda dengan sewajarnya.

Atas ialah kandungan terperinci Kod yang ditulis dalam C++: Cari rentetan terkecil dari segi leksikografi yang terdiri daripada huruf K pertama abjad dan aksara bersebelahan tidak boleh sama. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!