数据结构
网络
关系数据库管理系统
操作系统
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 次查看
