資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告