資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究當某些 ASCII 值重新定義時，具有最大 ASCII 值和的子字串
在這個問題中，我們將找到給定字串的子字串，當我們重新定義 ASCII 值時，其字元的 ASCII 值之和最大。
解決該問題的樸素方法是找到所有子字串字元的 ASCII 值之和，並獲得具有最大和的子字串。
解決該問題的另一種方法是使用 Kadane 演算法找到最大子陣列和。
問題陳述 - 我們給定了一個大小為 N 的字串 alpha，其中包含字母字元。我們還給定了大小為 M 的 chars[] 和 ASCII[] 陣列，其中 chars[] 包含字元，Ascii[i] 包含 chars[i] 字元的更新 ASCII 值。此外，請考慮字串區分大小寫。
我們需要找到字元的 ASCII 值之和最大的子字串。
示例
輸入
alpha = "apper"; chars[char_len] = {'p'}; Ascii[char_len] = {-800};
輸出
'er'
解釋 - 在這裡，'p' 的 ASCII 值為 -800。因此，'er' 的 ASCII 值之和最大。
輸入
alpha = "accebd"; chars[char_len] = {'b'}; Ascii[char_len] = {-500};
輸出
'acce'
解釋 - 在這裡，我們不能將 'b' 包含在子字串中，因為它的 ASCII 值為負數，這會降低字串字元的 ASCII 值之和。
輸入
alpha = "ababc"; chars[char_len] = {'a', 'b', 'c'}; Ascii[char_len] = {100, -100, 200};
輸出
'ababc'
解釋 - 我們可以將整個字串作為子字串，因為它具有字元的 ASCII 值的最大和。
方法 1
在這種方法中，我們將找到給定字串的所有子字串。之後，我們將對所有字元的 ASCII 值求和。如果我們給定了特定字元的更新 ASCII 值，我們將使用它。否則，我們將使用原始的 ASCII 值。
此外，我們將跟蹤 ASCII 值之和最大的子字串。
演算法
步驟 1 - 初始化 'temp' 和 'result' 字串分別用於儲存臨時子字串和結果字串。
步驟 2 - 如果字串長度為 '1'，則返回字串本身。
步驟 3 - 使用最小值初始化 'maxVal' 變數以儲存最大和，並使用 0 初始化 'sum' 以儲存子字串字元的 ASCII 值之和。此外，定義一個 map 來儲存字元的更新頻率。
步驟 4 - 將所有具有更新 ASCII 值的字元新增到 map 中。
步驟 5 - 開始遍歷字串。此外，使用另一個巢狀迴圈從 p 到 q 索引獲取子字串。
步驟 6 - 在巢狀迴圈內，使用 substr() 方法獲取從 p 索引開始且長度等於 q - p + 1 的子字串。此外，將其儲存到 'temp' 字串中，並將 'sum' 變數重新初始化為 0。
步驟 7 - 遍歷 temp 字串以獲取其字元的 ASCII 值之和。如果當前字元存在於 map 中，則將其值新增到 sum 中。否則，添加當前字元的原始 ASCII 值。
步驟 8 - 如果 sum 大於 'maxVal'，則將 'maxVal' 更新為 sum，並將 'result' 更新為 'temp'。
步驟 9 - 返回 result 值。
示例
#include <bits/stdc++.h>
using namespace std;
string getMaximumSum(string alpha, char chars[], int Ascii[], int chars_len) {
string temp = "", result = "";
// For string of size 1
if (alpha.length() == 1)
return alpha;
long long maxVal = INT_MIN, sum = 0;
unordered_map<char, int> charMap;
// Storing new ASCII values to map
for (int p = 0; p < chars_len; p++) {
charMap[chars[p]] = Ascii[p];
}
// Get all substrings and sum its characters ASCII values
for (int p = 0; p < alpha.length(); p++) {
for (int q = p; q < alpha.length(); q++) {
// Get substring
temp = alpha.substr(p, q - p + 1);
sum = 0;
// Traverse substring to count the sum of ASCII values
for (int r = 0; r < temp.length(); r++) {
// If Character exists in the map
if (charMap.find(temp[r]) != charMap.end()) {
sum += charMap[temp[r]];
} else {
// If the character doesn't exist in the map
sum += temp[r];
}
}
// Update maximum value if the sum is greater
if (sum > maxVal) {
maxVal = sum;
result = temp;
}
}
}
return result;
}
int main() {
string alpha = "apper";
int char_len = 1;
char chars[char_len] = {'p'};
int Ascii[char_len] = {-800};
cout << "The maximum sum of ASCII values of any substring of the given string is " << getMaximumSum(alpha, chars, Ascii, char_len) << endl;
return 0;
}
輸出
The maximum sum of ASCII values of any substring of the given string is er
時間複雜度 - 獲取所有子字串的 O(N*N*N)。
空間複雜度 - O(N + M)，用於將子字串儲存在 'temp' 字串中，並將更新的 ASCII 值儲存在 map 中。
方法 2
Kadane 演算法用於查詢子陣列的最大和。在這裡，我們可以將字串視為字元陣列，並找到具有最大 ASCII 值和的子字串。
在 Kadane 演算法中，當 sum 變為負數時，我們將其重新初始化為 0，並從新的子字串開始。
演算法
步驟 1 - 如果字串長度為 1，則返回字串。
步驟 2 - 將更新的 ASCII 值儲存在 map 中。
步驟 3 - 開始遍歷字串，並將當前字元附加到 'temp' 字串。
步驟 4 - 如果當前字元存在於 map 中，則將其值新增到 sum 中。否則，新增字元的原始 ASCII 值。
步驟 5 - 如果 sum 為負數，則將 sum 重新初始化為 0，並清空 temp 字串。
步驟 6 - 如果 sum 大於 'maxVal'，則將 'maxVal' 更新為 sum，並將 'result' 更新為 'temp' 字串。
步驟 7 - 返回 result 字串。
示例
#include <bits/stdc++.h>
using namespace std;
string getMaximumSum(string alpha, char chars[], int Ascii[], int chars_len) {
string temp = "", result = "";
// For string of size 1
if (alpha.length() == 1)
return alpha;
long long maxVal = INT_MIN, sum = 0;
unordered_map<char, int> charMap;
// Storing new ASCII values to map
for (int p = 0; p < chars_len; p++) {
charMap[chars[p]] = Ascii[p];
}
// Iterate the string
for (int p = 0; p < alpha.length(); p++) {
// Store the string in temp.
temp += alpha[p];
// To get updated ASCII value
if (charMap.find(alpha[p]) == charMap.end()) {
sum += alpha[p];
} else {
sum += charMap[alpha[p]];
}
// For negative sum, we make it 0 and clear the string
if (sum < 0) {
sum = 0;
temp.clear();
}
// When the sum is greater than maxVal, update it.
if (sum > maxVal) {
maxVal = sum;
result = temp;
}
}
return result;
}
int main() {
string alpha = "accebd";
int char_len = 1;
char chars[char_len] = {'b'};
int Ascii[char_len] = {-500};
cout << "The maximum sum of ASCII values of any substring of the given string is " << getMaximumSum(alpha, chars, Ascii, char_len) << endl;
return 0;
}
輸出
The maximum sum of ASCII values of any substring of the given string is acce
時間複雜度 - 遍歷字串的 O(N)。
空間複雜度 - 用於儲存子字串的 O(N)。
當我們需要獲取具有最大和的子陣列時，Kadane 演算法非常有用，因為我們可以在 O(N) 時間內獲得答案。樸素方法需要 O(N^2) 時間。
101 次檢視
