資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學透過遞增給定長度的字首查詢最終字串
在這個問題中，我們需要增加陣列中給定大小的多個字首的每個字元。解決這個問題的簡單方法是獲取陣列中給定大小的每個字首，並將字首的每個字元遞增 1。
最佳方法是使用給定陣列建立字首陣列，並在單個迭代中更新每個字串字元。
問題陳述 − 我們給定一個長度為 N 的字串 alpha。此外，我們還給定一個包含正整數的字首陣列。prefixes[i] 表示從字串中獲取長度為 prefixes[i] 的字首，並將字首的每個字元遞增 1。還給定迴圈遞增字元。因此，'z' 變為 'a'。
示例
輸入
alpha = "abcd"; prefixes[] = { 1, 1, 3 };
輸出
‘dcdd’
解釋
由於 arr[0] 為 1，因此取長度為 1 的字首，並將每個字首字元遞增。結果字串將為 'bbcd'。
對於第二個操作，取長度為 1 的字首，並將每個字元遞增。結果字串將為 'cbcd'。
在最後一個操作中，我們需要取長度為 3 的字首，結果字串將為 'dcdd'。
輸入
alpha = "aabc"; prefixes[] = { 1, 2, 3, 4, 4, 3 };
輸出
‘gffe’
解釋
遞增給定大小的每個字首的每個字元後，結果字串為 'gffe'。
輸入
alpha = "xyz"; prefixes[] = { 3, 2, 1 };
輸出
‘aaa’
解釋
遞增前 3 個字元後，字串變為 'yza'。
遞增前 2 個字元後，字串變為 'zaa'。
遞增第一個字元後，字串變為 'aaa'。
方法 1
在這種方法中，我們將遍歷陣列並獲取長度為 prefixes[i] 的字串字首。之後，我們將遍歷字首字串並將每個字元增加 1。
演算法
步驟 1 − 使用 for 迴圈遍歷陣列 prefixes。
步驟 2 − 遍歷從索引 0 到 prefixes[p] 的字串。
步驟 3 − 如果字串中索引處的字元為 'z'，則將字元更新為 'a'。否則，向字元新增 1。
步驟 4 − 完成所有迴圈迭代後，返回 alpha 字串。
示例
#include <bits/stdc++.h>
using namespace std;
string getFinalString(string alpha, int pref_array[], int pref_len) {
// Traverse prefix array
for (int p = 0; p < pref_len; p++) {
// Incrementing the pref_array[p] elements cyclically
for (int q = 0; q < pref_array[p]; q++) {
// If the current character is 'z'
if (alpha[q] == 'z') {
alpha[q] = 'a';
} else {
// Increment character by 1
alpha[q] += 1;
}
}
}
return alpha;
}
int main() {
string alpha = "abcd";
int prefixes[] = { 1, 1, 3 };
int pref_len = sizeof(prefixes) / sizeof(prefixes[0]);
cout << "The final string is " << getFinalString(alpha, prefixes, pref_len) << endl;
return 0;
}
輸出
The final string is dcdd
時間複雜度 – O(N*M)，其中 N 是字串長度，M 是陣列長度。
空間複雜度 – O(1)，因為我們更新了 alpha 字串。
方法 2
在這種方法中，我們將建立一個字首陣列並在單個迭代中遞增字串的所有字元。
演算法
步驟 1 − 定義一個名為 'arr' 的陣列，其長度等於字首陣列長度 + 1，並將所有元素初始化為 0。
步驟 2 − 開始遍歷字首陣列並將 arr[pref_array[p]] 遞減 1。此外，在每次迭代中遞增 arr[0]。
步驟 3 − 現在，從第一個索引遍歷 'arr' 陣列，並將前一個元素新增到當前陣列元素以準備字首陣列。
步驟 4 − 接下來，開始遍歷字串並根據 'arr' 元素的值遞增每個字元的值。
步驟 5 − 在迴圈中取陣列元素與 26 的模。
步驟 6 − 如果 arr[p] + alpha[p] 大於 'z'，則將 arr[p] – 26 新增到 alpha[p]。否則，只將 arr[p] 新增到 alpha[p]。
步驟 7 − 返回更新後的 alpha 字串。
示例
讓我們使用示例輸入除錯下面的示例，以瞭解其工作原理。
最初，陣列 arr 為 [0, 0, 0, 0, 0, 0, 0]。
陣列 'arr' 使用基於 0 的索引。字首陣列包含 1 到字串長度之間的元素。因此，可以說在執行 prexies[p] 操作時，我們需要遞增直到 prefixes[p] – 1 索引的字串字元。在每個操作中，我們總是需要遞增第一個元素，因為 prexies 包含 1 到字串長度範圍內的元素。因此，我們在每次迭代中遞增 arr[0]。
在 prexies 陣列迭代之後，arr 將為 [6, -1, -1, -2, -2, 0, 0]。
在下一步中，我們將前一個元素新增到當前陣列元素。因此，arr 將為 [6, 5, 4, 2, 2, 2, 2]。
接下來，取前 4 個元素並迴圈遞增字串字元。
#include <bits/stdc++.h>
using namespace std;
string getFinalString(string alpha, int pref_array[], int pref_len) {
// Array initialized with 0
int arr[pref_len + 1] = { 0 };
// Update the array according to the prefix array value
for (int p = 0; p < pref_len; p++) {
arr[pref_array[p]] -= 1;
arr[0] += 1;
}
// Create prefix array
for (int p = 1; p < pref_len; p++) {
arr[p] += arr[p - 1];
}
// Change character cyclically
for (int p = 0; p < pref_len; p++) {
arr[p] = (arr[p]) % 26;
if (arr[p] + alpha[p] > 'z')
alpha[p] = (alpha[p] + arr[p] - 26);
else
alpha[p] = alpha[p] + arr[p];
}
return alpha;
}
int main() {
string alpha = "aabc";
int prefixes[] = { 1, 2, 3, 4, 4, 3 };
int pref_len = sizeof(prefixes) / sizeof(prefixes[0]);
cout << "The final string is " << getFinalString(alpha, prefixes, pref_len) << endl;
return 0;
}
輸出
The final string is gffe
時間複雜度 – O(N) 用於遍歷陣列和字串。
空間複雜度 – O(N) 用於將元素儲存在字首陣列中。
我們使用了兩種方法來查詢遞增字串字首字元後的結果字串。第一種方法遍歷每個陣列元素並更新字串字首。第二種方法更合乎邏輯，因為我們建立字首陣列並同時遞增字元，而不是在每個操作中多次遞增。
92 次檢視
