首頁 >後端開發 >C++ >翻譯:對於M個查詢,反轉給定字串的範圍

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

王林
王林轉載
2023-08-25 20:09:091278瀏覽

翻譯:對於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中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除