資料結構
網路
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 次檢視
