子串分值和(十一届蓝桥杯省赛)
子串分值和
动态规划+哈希法,实现O(n)时间复杂度
unordered_map<char, int> map; //记录距离正在遍历字母的最近位置
vector<int> nums; //以字母第i个字母结尾的所有字符串的分值和为nums[i]
令所有未被遍历到的字母的位置为-1,因为字符串下标位置从0开始
void init() {
for (char ch = 'a'; ch <= 'z'; ch++) {
map[ch] = -1;
}
}
令输入的字符串为
动态规划递归方法: nums[i]=nums[i-1]+w;
这里的w就是:字母下标位置i - 该字母最近的位置map[str[i]]
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<char, int> map; //记录距离正在遍历字母的最近位置
vector<int> nums; //以字母第i个字母结尾的所有字符串的分值和为nums[i]
void init() {
for (char ch = 'a'; ch <= 'z'; ch++) {
map[ch] = -1;
}
}
int main() {
init();
string str;
cin >> str;
int n = str.size();
map[str[0]] = 0;
nums.push_back(1);
int ans = 1;
for (int i = 1; i < n; i++) {
int t = nums[i - 1] + i - map[str[i]];
map[str[i]] = i;
nums.push_back(t);
ans += t;
}
cout << ans << endl;
return 0;
}
这里看到关于动态规划用到的只有两个变量nums[i]和nums[i-1],因此可以不用那个数组,以把O(n)的空间复杂度变为O(1)。
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
unordered_map<char, int> map; //记录距离正在遍历字母的最近位置
int t1, t2; //以字母第i个字母结尾的所有字符串的分值和为nums[i]
void init() {
for (char ch = 'a'; ch <= 'z'; ch++) {
map[ch] = -1;
}
}
int main() {
init();
string str;
cin >> str;
int n = str.size();
map[str[0]] = 0;
t1 = 1;
int ans = 1;
for (int i = 1; i < n; i++) {
t2 = t1 + i - map[str[i]];
map[str[i]] = i;
t1 = t2;
ans += t2;
}
cout << ans << endl;
return 0;
}
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码