数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究通过为每个字符分配范围 [1, 26] 内的值来最大化字符串值
英语语言中总共有 26 个不同的字母。如果我们想将字母字符转换为数值，则需要仅将字母值分配到 1 到 26 之间。
现在，在这个问题中，我们需要通过为每个字符分配范围 [1, 26] 内的值来最大化字符串值。让我们看看我们应该如何解决这个问题。
让我们通过一些示例来了解这个问题。
输入
s = “blpsBpPtT”
输出
221
解释
在这里，在这个问题中，为了最大化给定字符串的值，我们将分配 -
26 给 p、P
25 给 b、B
24 给 t、T
23 给 l
22 给 s
因此，净输出将变为 ((26 * 3) + (25 * 2) + (24 * 2) + (23 * 1) + (22 * 1))，等于 221。
输入
s = “Aa$#&*@!Bsbb”
输出
152
解释
在这里，在这个问题中，为了最大化给定字符串的值，我们将分配 -
26 给 b、B
25 给 a、A
24 给 s
其余字符将不会获得任何值，即其值为零
因此，净输出将变为 ((26 * 3) + (25 * 2) + (24 * 1))，等于 152。
问题解释
让我们尝试理解问题并找到解决方案。在这个问题中，我们应该通过分配 1 到 26 之间的值来最大化字符串的值，如果字符是字母，但如果它不是字母，对于任何其他字符，如“$”、“#”、“&”，等，我们将取值为零。对于大写和小写字符，如果它们是同一类型，我们将认为它们相同，即“p”和“P”将被视为相似。我们可以通过为出现频率最高的字母字符分配最大值来快速最大化数字。在下面的文章中，有两种方法可以存储频率，我们很快就会看到这两种方法。
方法 1：使用映射
算法
定义一个映射，例如 m。
运行一个循环，以将给定字符串的字符频率（包括大写和小写字母）存储在映射中。
将频率推入向量中
对包含频率的向量进行排序
从后往前，将频率分别乘以 26、25、24，依此类推，直到 1。
将相乘的值加在一起以获得最终答案
示例
以下是各种编程语言中映射解决方案的实现 -
#include <bits/stdc++.h>
using namespace std;
// Function to maximize the String value by assigning values in the range [1, 26] to each character
int Helper(string s){
// Define a map to store the characters in it to count the frequency of each character
map<int,int>m;
// Run a loop to initiate the map
for (int i=0; i<s.size(); i++) {
char chr=s[i];
// To store lowercase character
if (chr >= 'a' && chr <= 'z') {
m[chr - 'a']++;
}
// To store uppercase character
else if (chr >= 'A' && chr <= 'Z') {
m[chr - 'A']++;
}
}
vector<int>v;
// Push the frequencies in the vector
for(auto a:m) {
v.push_back(a.second);
}
// Sort the frequencies
sort(v.begin(),v.end());
// Intialise ans variable
int ans=0, num=26;
// Get the answer in accordance with the frequencies and range [1, 26]
for(int i=v.size()-1; i>=0; i--) {
// Add the highest frequency with num which is initially set to 26
ans+=(num*v[i]);
// Decrement num to move to the next largest frequency
num--;
}
// Return the final output
return ans;
}
int main(){
// Give the input string
string S = "aBAbgha";
// Call the helper function to maximize the String value by assigning values in the range [1, 26] to each character
cout << "The maximum string value by assigning values in the range [1, 26] to each character is: "<<Helper(S);
return 0;
}
输出
The maximum string value by assigning values in the range [1, 26] to each character is: 175
import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
public static int Helper(String s) {
// Define a map to store the characters and their frequencies
Map<Character, Integer> charFrequency = new HashMap<>();
// Run a loop to initiate the map
for (char c : s.toCharArray()) {
// To store lowercase character
if (Character.isLetter(c)) {
char lowercaseChar = Character.toLowerCase(c);
charFrequency.put(lowercaseChar, charFrequency.getOrDefault(lowercaseChar, 0) + 1);
}
}
// Create a list to store the frequencies
List<Integer> frequencies = new ArrayList<>(charFrequency.values());
// Sort the frequencies in ascending order
Collections.sort(frequencies);
int ans = 0;
int num = 26;
// Calculate the maximum string value by assigning values in the range [1, 26] to each character
for (int i = frequencies.size() - 1; i >= 0; i--) {
ans += num * frequencies.get(i);
num--;
}
return ans;
}
public static void main(String[] args) {
// Input string
String S = "aBAbgha";
// Call the Helper function to maximize the string value
int maxValue = Helper(S);
// Print the maximum string value
System.out.println("The maximum string value by assigning values in the range [1, 26] to each character is: " + maxValue);
}
}
输出
The maximum string value by assigning values in the range [1, 26] to each character is: 175
def Helper(s):
# Define a dictionary to store the characters and their frequencies
char_frequency = {}
# Run a loop to initiate the map
for char in s:
if char.isalpha():
lowercase_char = char.lower()
char_frequency[lowercase_char] = char_frequency.get(lowercase_char, 0) + 1
# Create a list to store the frequencies
frequencies = list(char_frequency.values())
# Sort the frequencies in ascending order
frequencies.sort()
ans = 0
num = 26
# Calculate the maximum string value by assigning values in the range [1, 26] to each character
for i in range(len(frequencies) - 1, -1, -1):
ans += num * frequencies[i]
num -= 1
return ans
# Input string
S = "aBAbgha"
# Call the Helper function to maximize the string value
max_value = Helper(S)
# Print the maximum string value
print("The maximum string value by assigning values in the range [1, 26] to each character is:", max_value)
输出
The maximum string value by assigning values in the range [1, 26] to each character is: 175
上述代码的复杂度
时间复杂度 - O(n*(log(n)))；在这里我们使用了循环，但它们将运行“n”次，但是，排序函数将花费 (n * log(n)) 时间来执行，因此我们将代码的总体复杂度视为 n * log(n)。
空间复杂度 - O(26)；因为英语中只有 26 个不同的字母。
方法 2：使用频率向量
算法
定义一个向量，例如 v，大小为 26，所有初始值都为“0”
运行一个循环，以将给定字符串的字符频率（包括大写和小写字母）存储在向量中，现在称为频率向量。
对包含频率的向量进行排序
从后往前，将频率分别乘以 26、25、24，依此类推，直到 1，并在频率达到“0”时中断循环。
将相乘的值加在一起以获得最终答案
示例
以下是上述方法在各种编程语言中的实现。在 C++ 中，我们使用向量；在 C、Java 和 Python 中，我们使用数组和列表。“-
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// Function to maximize the String value by assigning values in the range [1, 26] to each character
int Helper(const char* s){
// Define an array to store the character frequencies
int v[26] = {0};
// Populating the array by iterating through the string
for (int i = 0; s[i]; i++) {
char chr = s[i];
if (chr >= 'a' && chr <= 'z') {
v[chr - 'a']++;
} else if (chr >= 'A' && chr <= 'Z') {
v[chr - 'A']++;
}
}
// Sorting the array in ascending order
for (int i = 0; i < 26; i++) {
for (int j = i + 1; j < 26; j++) {
if (v[i] > v[j]) {
int temp = v[i];
v[i] = v[j];
v[j] = temp;
}
}
}
int ans = 0;
int num = 26;
// Calculating the maximum string value by assigning values in the range [1, 26] to each character
for (int i = 25; i >= 0; i--) {
if (v[i] == 0) {
break;
} else {
ans += v[i] * (i + 1);
}
}
return ans;
}
int main(){
// Giving the input string
const char* S = "aBAbgha";
// Calling the Helper function to maximize the String value
printf("The maximum string value by assigning values in the range [1, 26] to each character is: %d\n", Helper(S));
return 0;
}
输出
The maximum string value by assigning values in the range [1, 26] to each character is: 175
#include <bits/stdc++.h>
using namespace std;
// Function to maximize the String value by assigning values in the range [1, 26] to each character
int Helper(string s){
// Define a frequency vector of size 26 with initial elements as 0
vector<int> v(26, 0);
// Run a loop to initiate the vector
for (int i=0; i<s.size(); i++) {
char chr=s[i];
// To store lowercase character
if (chr >= 'a' && chr <= 'z') {
v[chr - 'a']++;
}
// To store uppercase character
else if (chr >= 'A' && chr <= 'Z') {
v[chr - 'A']++;
}
}
// Sort the vector
sort(v.begin(), v.end());
// Intialise answer variable
int ans = 0;
// Get the answer in accordance with the frequencies and range [1, 26]
for (int i = 25; i >= 0; i--) {
// Check if the value of frequency is 0 or not, if 0 then stop the loop
if (v[i] == 0) {
break;
} else {
// Add the highest frequency with a number that is initially set to 26
ans+=v[i] * (i + 1);
}
}
// Return the maximum sum obtained
return ans;
}
int main(){
// Give the input string
string S = "aBAbgha";
// Call the helper function to maximize the String value by assigning values in the range [1, 26] to each character
cout << "The maximum string value by assigning values in the range [1, 26] to each character is: "<<Helper(S);
return 0;
}
输出
The maximum string value by assigning values in the range [1, 26] to each character is: 175
public class Main {
public static int Helper(String s) {
// Define an array to store the character frequencies
int[] v = new int[26];
// Populating the array by iterating through the string
for (int i = 0; i < s.length(); i++) {
char chr = s.charAt(i);
if (chr >= 'a' && chr <= 'z') {
v[chr - 'a']++;
} else if (chr >= 'A' && chr <= 'Z') {
v[chr - 'A']++;
}
}
// Sorting the array in ascending order
for (int i = 0; i < 26; i++) {
for (int j = i + 1; j < 26; j++) {
if (v[i] > v[j]) {
int temp = v[i];
v[i] = v[j];
v[j] = temp;
}
}
}
int ans = 0;
int num = 26;
// Calculating the maximum string value by assigning values in the range [1, 26] to each character
for (int i = 25; i >= 0; i--) {
if (v[i] == 0) {
break;
} else {
ans += v[i] * (i + 1);
}
}
return ans;
}
public static void main(String[] args) {
// Giving the input string
String S = "aBAbgha";
// Calling the Helper function to maximize the String value
System.out.println("The maximum string value by assigning values in the range [1, 26] to each character is: " + Helper(S));
}
}
输出
The maximum string value by assigning values in the range [1, 26] to each character is: 175
def Helper(s):
# Define a list to store the character frequencies
v = [0] * 26
# Populating the list by iterating through the string
for i in range(len(s)):
chr = s[i]
if 'a' <= chr <= 'z':
v[ord(chr) - ord('a')] += 1
elif 'A' <= chr <= 'Z':
v[ord(chr) - ord('A')] += 1
# Sorting the list in ascending order
v.sort()
ans = 0
num = 26
# Calculating the maximum string value by assigning values in the range [1, 26] to each character
for i in range(25, -1, -1):
if v[i] == 0:
break
else:
ans += v[i] * (i + 1)
return ans
# Giving the input string
S = "aBAbgha"
# Calling the Helper function to maximize the String value
print("The maximum string value by assigning values in the range [1, 26] to each character is:", Helper(S))
输出
The maximum string value by assigning values in the range [1, 26] to each character is: 175
上述代码的复杂度
时间复杂度 - O(n*(log(n)))；在这里我们使用了循环，但它们将运行“n”次，但是，排序函数将花费 (n * log(n)) 时间来执行，因此我们将代码的总体复杂度视为 n * log(n)。
空间复杂度 - O(26)；因为英语中只有 26 个不同的字母。
注意 - 上述方法使用频率向量而不是将频率存储在映射中。
结论
在本文中，为了通过为每个字符分配范围 [1, 26] 内的值来最大化字符串值，我们将采用两种方法来存储每个元素的频率。在第一种方法中，我们将使用映射来存储每个字母的频率，无论字母是大写还是小写。但是，在第二种方法中，我们可以避免映射占用的额外空间，并可以直接使用频率向量。
更新于： 2024 年 2 月 5 日
189 次浏览
广告