Untuk pertanyaan Q, terjemah yang berikut ke dalam bahasa Cina: Dalam rentetan ternary, bilangan minimum aksara yang perlu diganti untuk mengalih keluar semua subrentetan palindromik

Rentetan palindrom ialah rentetan yang sama dengan rentetan terbaliknya. Diberi rentetan yang mengandungi '0', '1' dan '2', dan tatasusunan Q panjang N, setiap indeks tatasusunan yang diberikan mewakili julat, dan julat diwakili oleh sepasang nilai bentuk. Kita perlu mencari bilangan minimum aksara yang perlu diganti dalam julat tertentu untuk memastikan tiada sebarang subrentetan palindromik dalam julat itu.

Contoh Contoh

Input1: string s: “01001020002”, int Q = {{0,4}, {2,5}, {5,10}};

Output: 1 1 3

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Untuk julat 0 hingga 4, kami mempunyai dua palindrom 010 dan 1001, kami boleh menukar indeks 2 kepada '2' supaya tiada palindrom yang tinggal.

Untuk julat 2 hingga 5, kami hanya mempunyai satu nombor palindrom iaitu 010, yang boleh ditukar dengan menukar sifar pertama kepada 2.

Untuk nombor dalam julat 5 hingga 10 kami mempunyai palindrom 020, 000 dan 20002. Kita boleh menukar 2 pertama kepada '1', indeks seterusnya '0' kepada '2', dan nilai indeks kedua hingga terakhir kepada '1' untuk menyingkirkan semua palindrom.

Terjemahan bahasa Cina bagi

Pendekatan Naif

ialah:

Pendekatan Naif

Dalam kaedah ini, ideanya adalah untuk mendapatkan semua kombinasi julat yang diberikan dan mencari bilangan minimum perubahan yang diperlukan untuk gabungan tanpa palindrom. Tetapi masalahnya ialah kerumitan masa.

Untuk melaksanakan kaedah ini, kita perlu membuat panggilan rekursif dan berulang melalui rentetan. Pada setiap indeks, kami mempunyai tiga pilihan, menjadikan kerumitan masa untuk mendapatkan semua rentetan 3^N. Sekarang, kita perlu menjawab pertanyaan Q, dan untuk setiap kes kita perlu menyemak sama ada mengalih keluar rentetan palindrom menjadikan kerumitan masa O(Q*N*(3^N)).

Untuk panggilan rekursif, kita perlu mengekalkan ruang N, yang bermaksud kerumitan ruang ialah O(N).

Perancangan Dinamik

Terjemahan bahasa Cina bagi

Idea

ialah:

Idea

Idea soalan ini ialah kita tidak perlu mencari sebarang nombor palindrom dalam julat yang diberikan. Panjang palindrom minimum yang mungkin ialah 2 untuk nombor genap dan 3 untuk nombor ganjil.

Kami mempunyai tiga aksara berbeza dan kami memerlukan mereka semua untuk membuat rentetan yang diberikan tanpa palindrom. Terdapat jumlah pilihan saiz atau jujukan, kita boleh membentuk jujukan sedemikian rupa sehingga tiada palindrom wujud dan jujukan ini adalah pilih atur rentetan '012'.

Kami akan menggunakan tatasusunan dp atau vektor untuk menyimpan semua kes yang mungkin, setiap jujukan akan memberikan bilangan aksara yang lebih sedikit dan kami akan menggunakan jujukan itu.

Pelaksanaan

Di bahagian pelaksanaan, pertama, kami akan mencipta fungsi yang akan menerima rentetan, jujukan, vektor DP dan bilangan jujukan sebagai parameter dan mengemas kini vektor DP.

Dalam fungsi ini, pertama, kami akan mengemas kini nilai indeks pertama, kemudian untuk setiap kes yang tidak sepadan, kami akan mengemas kini nilai indeks semasa vektor DP.

Kami akan mencipta fungsi lain di mana kami akan memasukkan semua urutan yang mungkin secara manual dan menyimpannya dalam tatasusunan dan mencipta vektor DP.

Kami akan memanggil fungsi di atas dengan menghantar nilai untuk prapemprosesan dan kemudian menjawab setiap pertanyaan dengan melaluinya satu demi satu.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

#include <bits/stdc++.h>
#define SIZE 100005
using namespace std;
// function to get the pre-processing of the results 
void preprocess(string& str, string& seq, vector<vector<int>>&dp, int n, int i){
   dp[i][0] = (str[0] != seq[0]); // initialzie dp vector 
   for (int j = 1; j < n; j++) {
   
      // storing the results if matched then adding zero otherwise one
      dp[i][j] = dp[i][j - 1] + (str[j] != seq[j % 3]);
   }
   return;
}

// function to find the number of changes required for each query 
void changesReq(string str, vector<pair<int, int>> Q){
   int len = str.length(); // size of the given string 
   int q = Q.size(); // number of queries 
   vector<vector<int>>dp(6,vector<int>(len)); // dp vector to store the states results 
   
   // vector to store each possible non-palindromic sequency 
   vector<string> seq= { "012", "021", "102", "120", "201", "210" };
   for (int i = 0; i < 6; i++){
   
      // for each sequence storing state results in vector 
      preprocess(str, seq[i], dp, len, i);
   }	
   
   // getting all the queries 
   for (int i = 0; i < q; i++){
      int l = Q[i].first;
      int	r = Q[i].second;
      int ans = INT_MAX;
      
      // finding the minimum cost amount 
      for (int j = 0; j < 6; j++) {
         // Find the cost
         ans = min(ans, dp[j][r] - dp[j][l] + (str[l] != seq[j][l%3]));
      }
      cout <<ans<<"  ";
   }
}
int main(){
   string str = "01001020002";
   vector<pair<int, int>>Q = {{0,4}, {2,5}, {5,10}};
   
   // calling the function 
   cout<<"The minimum characters to be replaced in the Ternary string to remove all palindromic substrings for Q queries is "<<endl;
   changesReq(str, Q);
   return 0;
}

Output

The minimum characters to be replaced in the Ternary string to remove all palindromic substrings for Q queries is 
1  1  3  

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N + Q), dengan N ialah bilangan aksara dalam rentetan dan Q ialah bilangan pertanyaan.

Kerumitan ruang kod di atas ialah O(N) kerana kami menyimpan keadaan dalam vektor bersaiz N.

Kesimpulan

Dalam tutorial ini, kami melaksanakan sekeping kod untuk mengetahui bilangan minimum aksara yang perlu ditukar apabila melakukan beberapa pertanyaan dalam julat tertentu supaya tidak meninggalkan rentetan palindrom. Kami melaksanakan kod ini menggunakan konsep pengaturcaraan dinamik dengan kerumitan masa O(N+Q) dan kerumitan ruang O(N).

Atas ialah kandungan terperinci Untuk pertanyaan Q, terjemah yang berikut ke dalam bahasa Cina: Dalam rentetan ternary, bilangan minimum aksara yang perlu diganti untuk mengalih keluar semua subrentetan palindromik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!