数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律学C++ 中由字母组成的单词的最大得分
假设我们有一系列单词，一系列单个字母，以及每个字符的分数。我们需要找到使用给定字母形成的任何有效单词集的最大得分。
我们可能不会使用字母中的所有字符，并且每个字母只能使用一次。字母 'a'、'b'、'c'、...、'z' 的得分分别由 score[0]、score[1]、...、score[25] 给出。
因此，如果输入类似于 words = ["god", "good", "toc", "cat"]，letters = [a,g,o,o,d,d,d,c,t,t] 和 score = [5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0]，则输出将为 30，这里 good 和 cat 构成了最大得分。
为了解决这个问题，我们将遵循以下步骤：
定义一个二维数组 dp
定义一个函数 calc()，它将接收一个字符串 s、一个映射 m 和一个数组 sc 作为参数。
ans := 0
对于初始化 i := 0，当 i < s 的大小，更新（i 增加 1），执行：
x := s[i]
如果 m[x] <= 0，则：
返回 0
（m[x] 减 1）
ans := ans + sc[x - 'a']
返回 ans
定义一个函数 solve()，它将接收 i、status、一个由 pairs 组成的数组 v、一个映射 m 和一个数组 s 作为参数。
如果 i 等于 -1，则：
返回 0
x := v[i] 的第二个值
ans := 0
如果 status 等于 1，则：
ans := calc(x, m, s)
如果 ans > 0 且 status 等于 1，则：
对于初始化 j := 0，当 j < x 的大小，更新（j 增加 1），执行：
（m[x[j]] 减 1）
返回 ans + solve(i - 1, 0, v, m, s) 和 solve(i - 1, 1, v, m, s) 的最大值
从主方法中，执行以下操作：
ans := 0
定义一个映射 m
对于初始化 i := 0，当 i < l 的大小，更新（i 增加 1），执行：
（m[l[i]] 加 1）
定义一个由 pairs 组成的数组 v
对于初始化 i := 0，当 i < w 的大小，更新（i 增加 1），执行：
x := w[i]
flag := calc(x, m, s)
如果 flag 不为零，则：
在 v 的末尾插入 { flag, x }
对数组 v 进行排序
dp := 定义一个大小为 (v 的大小) x 2 的二维数组，并将其填充为 -1
返回 solve(v 的大小, 0, v, m, s) 和 solve(v 的大小, 1, v, m, s) 的最大值
让我们看看以下实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int> > dp;
int calc(string s, map<char, int> m, vector<int>& sc){
int ans = 0;
for (int i = 0; i < s.size(); i++) {
char x = s[i];
if (m[x] <= 0)
return 0;
m[x]--;
ans += sc[x - 'a'];
}
return ans;
}
int solve(int i, int status, vector<pair<int, string> > v,
map<char, int> m, vector<int>& s){
if (i == -1)
return 0;
string x = v[i].second;
int ans = 0;
if (status == 1)
ans = calc(x, m, s);
if (ans > 0 && status == 1) {
for (int j = 0; j < x.size(); j++) {
m[x[j]]--;
}
}
return ans + max(solve(i - 1, 0, v, m, s), solve(i - 1, 1, v, m, s));
}
int maxScoreWords(vector<string>& w, vector<char>& l,
vector<int>& s){
int ans = 0;
map<char, int> m;
for (int i = 0; i < l.size(); i++)
m[l[i]]++;
vector<pair<int, string> > v;
for (int i = 0; i < w.size(); i++) {
string x = w[i];
int flag = calc(x, m, s);
if (flag) {
v.push_back({ flag, x });
}
}
sort(v.begin(), v.end());
dp = vector<vector<int> >(v.size(), vector<int>(2, -1));
return max(solve(v.size() - 1, 0, v, m, s), solve(v.size() -
1, 1, v, m, s));
}
};
main(){
Solution ob;
vector<string> words = {"god", "good", "toc", "cat"};
vector<char> letters = {'a','g','o','o','d','d','d','c','t','t'};
vector<int> score = {5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0};
cout << (ob.maxScoreWords(words, letters, score));
}输入
{"god", "good", "toc", "cat"},
{'a','g','o','o','d','d','d','c','t','t'},
{5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0}输出
30
193 次查看
