資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究針對 M 個查詢，反轉給定字串的範圍
在這個問題中，我們將根據陣列值對給定的字串執行 M 次反轉查詢。
解決該問題的樸素方法是根據給定的陣列值反轉每個字串片段。
最佳化方法利用了以下邏輯：當我們對同一個子字串反轉兩次時，我們會得到原始字串。
問題陳述 - 我們給定一個包含字母字元的 alpha 字串。此外，我們還給定一個大小為 M 的 arr[] 陣列，其中包含正整數。我們需要對給定的字串執行 M 個操作並返回最終字串。
在每個操作中，我們需要獲取 arr[i] 並反轉從 arr[i] 到 N − arr[i] + 1 的子字串。
示例
輸入
alpha = "pqrst"; arr = {2, 1};
輸出
tqrsp
解釋
執行第一個查詢後，字串變為“psrqt”。
執行第二個查詢後，我們得到“tqrsp”。
輸入
− alpha = "pqrst"; arr = {1, 1};
輸出
− ‘pqrst’
解釋 - 如果我們對同一個查詢執行偶數次，我們會得到相同的字串。
輸入
− alpha = "pqrst"; arr = {1, 1, 1};
輸出
− ‘tsrqp’
解釋 - 如果我們對同一個查詢執行奇數次，我們會得到字串的反轉。
方法 1
在這種方法中，我們將使用 reverse() 方法反轉子字串。我們將使用給定的查詢獲取起始和結束指標，並反轉給定字串的子字串。
演算法
步驟 1 - 開始遍歷查詢陣列。
步驟 2 - 使用 arr[p] − 1 初始化“left”變數。
步驟 3 - 使用 str_len − arr[p] + 1 初始化“right”變數。
步驟 4 - 使用 reverse() 方法反轉從左指標到右指標的子字串。
示例
#include <bits/stdc++.h>
using namespace std;
void reverseStrings(string &alpha, int str_len, vector<int> &arr, int arr_len){
// Traverse all queries
for (int p = 0; p < arr_len; p++){
// Get starting pointer
int left = arr[p] - 1;
// Ending pointer
int right = str_len - arr[p] + 1;
// Reverse the string
reverse(alpha.begin() + left, alpha.begin() + right);
}
}
int main(){
int str_len = 5;
string alpha = "pqrst";
int arr_len = 2;
vector<int> arr = {2, 1};
reverseStrings(alpha, str_len, arr, arr_len);
cout << "The string after performing queries is " << alpha << endl;
return 0;
}
輸出
The string after performing queries is tqrsp
時間複雜度 - 反轉子字串 M 次的時間複雜度為 O(N*M)。
空間複雜度 - O(1)，因為我們沒有使用任何動態空間。
方法 2
在這種方法中，我們將計算特定索引以及在給定查詢中包含反轉的次數。如果任何索引在偶數次包含在反轉中，我們不需要反轉它。如果任何索引在所有給定查詢中奇數次包含在反轉中，我們需要反轉特定索引處的字元。
演算法
步驟 1 - 初始化長度等於字串長度的“cnt”列表，並將其值初始化為 0，以儲存特定索引包含在反轉中的次數。
步驟 2 - 遍歷給定查詢的陣列，並根據當前查詢獲取字串的左指標和右指標。
步驟 3 - 還執行 changeRange() 函式以根據當前查詢的左指標和右指標更新“cnt”列表。
步驟 3.1 - 在 changeRange() 函式中，增加“cnt”列表中“left”索引處的值。
步驟 3.2 - 減小“cnt”列表中所有位於“right + 1”指標右側的值。
這裡，我們需要在 [left, right] 範圍內將“cnt”列表的所有值加 1。因此，我們只將 cnt[left] 加 1，因為獲取字首和會將所有位於“left”索引右側的值加 1。此外，我們不希望增加 [right, str_len] 索引之間的 cnt 值，因此我們已經將其減 1，因為字首和會將其加 1。
步驟 4 - 接下來，執行 getPrefixSum() 函式以計算“cnt”列表的字首和。
步驟 4.1 - 在 getPrefixSum() 函式中，遍歷字串並將前一個元素的值新增到當前元素。
步驟 5 - 接下來，以相反的順序遍歷“cnt”列表。如果當前元素為奇數，則將其追加到“tmp”字串。
步驟 6 - 使用 0 初始化“p”和“q”，以原始順序遍歷“cnt”列表。
步驟 7 - 如果“cnt”列表中的當前元素為奇數，則使用 tmp[q] 更新 alpha[p]。
步驟 8 - 最後，返回 alpha 字串。
示例
#include <iostream>
#include <vector>
using namespace std;
void changeRange(vector<int>& cnt, int left, int right) {
// Increase the value of the left index
cnt[left]++;
// Decrement value for all indexes after the right index
if (right + 1 < cnt.size())
cnt[right + 1]--;
}
void getPrefixSum(vector<int>& cnt) {
// Calculate prefix sum
for (int p = 1; p < cnt.size(); p++) {
cnt[p] += cnt[p - 1];
}
}
string reverseStrings(string alpha, int str_len, vector<int>& arr, int arr_len) {
vector<int> cnt(str_len, 0);
// Traverse the array
for (int p = 0; p < arr_len; p++) {
int left = arr[p] <= (str_len + 1) / 2 ? arr[p] - 1 : str_len - arr[p];
int right = arr[p] <= (str_len + 1) / 2 ? str_len - arr[p] : arr[p] - 1;
// Changes index ranges between left and right
changeRange(cnt, left, right);
}
getPrefixSum(cnt);
string tmp;
// Store characters with the odd reversal in the reverse order in the tmp string
for (int p = cnt.size() - 1; p >= 0; p--) {
if (cnt[p] % 2 != 0)
tmp.push_back(alpha[p]);
}
int p = 0, q = 0;
// For even reversal, pick the character from the original string.
// For odd reversal, pick the character from the temp string.
for (p = 0; p < cnt.size(); p++) {
if (cnt[p] % 2 != 0)
alpha[p] = tmp[q++];
}
// Answer string
return alpha;
}
int main() {
int str_len = 5;
string alpha = "pqrst";
int arr_len = 2;
vector<int> arr = { 2, 1 };
alpha = reverseStrings(alpha, str_len, arr, arr_len);
cout << "The string after performing queries is: " <<alpha << endl;
return 0;
}
輸出
The string after performing queries is: tqrsp
時間複雜度 - O(M*N + N)，其中 O(M*N) 用於根據查詢更新“cnt”列表，O(N) 用於更新給定字串。
空間複雜度 - O(N)，用於使用“cnt”列表。
在第一種方法中，我們使用 reveres() 方法對給定字串執行所有查詢。在第二種方法中，我們使用字首和技術來計算特定索引包含在反轉中的次數。
235 次檢視
