翻譯：對於M個查詢，反轉給定字串的範圍

在本題中，我們將根據陣列值對給定的字串執行M次反向查詢。

解決問題的簡單方法是根據給定的陣列值反轉每個字串段。

優化方法使用的邏輯是，當我們反轉相同的子字串兩次時，我們得到原始字串。

問題陳述 - 我們給了一個包含字母字元的字母字串。此外，我們也給出了一個大小為 M 的 arr[] 數組，其中包含正整數。我們需要對給定的字串執行 M 次操作並傳回最終的字串。

在每個操作中，我們需要取得 arr[i] 並將子字串 arr[i] 轉換為 N − arr[i] 1.

範例

輸入

雷雷

輸出

雷雷 ＃＃＃＃＃＃解釋＃＃＃ ＃

執行第一個查詢後，字串變成'psrqt'。

• 執行第二個查詢後，我們得到了 'tqrsp'。

• 輸入

雷雷

輸出

雷雷

說明 - 如果我們對同一個查詢執行偶數次，我們會得到相同的字串。

輸入

雷雷

輸出

雷雷

解釋 - 如果我們執行相同的查詢奇數次，我們會得到字串的反轉。

方法1 在這種方法中，我們將使用reverse()方法來反轉子字串。我們將使用給定的查詢來獲取起始和結束指針，並反轉給定字串的子字串。

演算法

1

- 開始步驟查詢快照。

步驟2 - 使用arr[p] - 1初始化'left'變數。

步驟 3 - 使用 str_len - arr[p] 初始化「right」變數 1.

Step 4 - 使用reverse()方法將子字串從左指標反轉到右指標。

＃＃＃例＃＃＃ 雷雷

輸出 雷雷 時間複雜度 - O(N*M)，用於反轉子字串 M 次。

空間複雜度 - O(1)，因為我們不使用任何動態空間。

方法二

在這種方法中，我們將使用給定的查詢計算該特定索引以及包含在反轉中的次數。如果任何索引被包含偶數次，我們不需要反轉它。如果在所有給定查詢中任何索引包含奇數次，我們需要反轉特定索引處的字元。

演算法

步驟 1

- 初始化長度等於字串長度的 'cnt' 列表，用 0 儲存特定索引在食材中出現的次數。

Step 2

- 遍歷給定查詢的數組，並根據當前查詢獲取字串的左指針和右指針。

Step 3

- 同時執行changeRange()函數，根據目前查詢的左指標和右指標更新‘cnt’列表。

Step 3.1

- 在changeRange()函數中，增加「cnt」清單中「left」索引處的值。

第3.2步

- 減少「cnt」清單中位於「right 1」指標右側的所有值。 這裡，我們需要將‘cnt’列表中[左、右]範圍內的所有值加1。因此，我們只將 cnt[left] 增加 1，因為採用前綴和將使所有值增加 1，即「左」索引的右側。另外，我們不想增加 [right, str_len] 索引之間的 cnt 值，因此我們已經將其減 1，因為前綴和會將其增加 1。

Step 4 - 接下來，執行 getPrefixSum() 函數來計算「cnt」清單的前綴和。

Step 4.1

- 在 getPrefixSum() 函數中，遍歷字串並將前一個元素的值加到目前元素。

步驟 5

- 後續，以逆序遍歷‘cnt’列表。如果當前元素是奇數，則將其追加到‘tmp’字串中。

6

- 使用0初始化步驟‘p’和‘q’，按照原始順序遍歷‘cnt’列表。

步驟 7

− 如果‘cnt’清單中的目前元素是奇數，則使用tmp[q]更新alpha[p]。

Step 8

- 最後，傳回字母字串。 範例

的中文翻譯為：

範例 雷雷 輸出

雷雷

時間複雜度 - O(M*N N)，其中 O(M*N) 是根據查詢更新 ‘cnt’ 列表，O(N) 是更新給定的字串。

空間複雜度 - 使用 'cnt' 列表為 O(N)。

在第一個方法中，我們使用了reveres()方法來執行給定字串上的所有查詢。在第二個方法中，我們使用了外部和技術來計算食物中出現的特定索引的次數。

以上是翻譯：對於M個查詢，反轉給定字串的範圍的詳細內容。更多資訊請關注PHP中文網其他相關文章！