對於Q個查詢，將以下內容翻譯成中文：在三進位字串中，需要替換的最小字元數以刪除所有回文子字串

回文字串是指與其反轉字串相等的字串。給定一個包含‘0’、‘1’和‘2’的字串，以及一個長度為N的數組Q，給定數組的每個索引表示一個範圍，範圍由一對形式的值表示。我們需要找到在給定範圍內需要替換的最小字元數，以確保該範圍內沒有任何回文子字串。

範例範例

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

Output: 1 1 3

Explanation

的中文翻譯為：

解釋

對於範圍0到4，我們有兩個回文數010和1001，我們可以將索引2改為'2'，這樣就不會有回文數剩下。

對於範圍2到5，我們只有一個回文數是010，可以透過將第一個零改為2來改變。

對於範圍在5到10之間的數字，我們有回文數020、000和20002。我們可以將第一個2改為'1'，將下一個索引的'0'改為'2'，並將倒數第二個索引的值改為'1'，以移除所有的回文數。

Naive Approach

的中文翻譯為：

天真的方法

在這種方法中，想法是取得給定範圍的所有組合，並找到沒有回文數的組合，所需的最小更改次數。但問題是時間複雜度。

要實作這種方法，我們必須進行遞歸調用，並遍歷字串。在每個索引處，我們有三種選擇，使得取得所有字串的時間複雜度為3^N。現在，我們必須回答Q個查詢，而且對於每個情況，我們必須檢查刪除回文字串是否使得時間複雜度為O(Q*N*(3^N))。

對於遞歸調用，我們必須維護N的空間，這意味著空間複雜度為O(N)。

動態規劃

Idea

的中文翻譯為：

Idea

這個問題的想法是，我們不需要在給定範圍內找到任何回文數，最小可能的回文數長度是偶數長度為2，奇數長度為3。

我們有三個不同的字符，我們需要它們全部來使給定的字串沒有回文。總共有size個選擇或序列，我們可以以這樣的方式形成序列，即沒有回文存在，而這些序列是字串'012'的排列。

我們將使用dp數組或向量來儲存所有可能的情況，每個序列都會給出較少的字元數，我們將使用該序列。

實作

在實作部分中，首先，我們將建立一個函數，該函數將接受一個字串、序列、DP向量和序列數量作為參數，並更新DP向量。

在這個函數中，首先，我們將更新第一個索引的值，然後對於每個未匹配的情況，我們將更新DP向量目前索引的值。

我們將建立另一個函數，在該函數中我們將手動輸入所有可能的序列，並將它們儲存在陣列中，並建立​​DP向量。

我們將透過傳遞值來呼叫上述函數進行預處理，然後透過一一遍歷來回答每個查詢。

Example

的中文翻譯為：

範例

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

輸出

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

時間與空間複雜度

#以上程式碼的時間複雜度為O(N Q)，其中N是字串中字元的數量，Q是查詢的數量。

上述程式碼的空間複雜度為O(N)，因為我們將狀態儲存在大小為N的向量中。

結論

在本教程中，我們實作了一段程式碼來找出在給定範圍內進行一些查詢時需要改變的最小字元數，以便不留下回文字串。我們使用動態規劃的概念實作了該程式碼，時間複雜度為O(N Q)，空間複雜度為O(N)。

以上是對於Q個查詢，將以下內容翻譯成中文：在三進位字串中，需要替換的最小字元數以刪除所有回文子字串的詳細內容。更多資訊請關注PHP中文網其他相關文章！