c++,字符串的 引力 定义为:字符串中 不同 字符的数量。例如,"abbca" 的引力为 3 ,因为其中有 3 个不同字符 'a'、'b' 和 'c' 。 给你一个字符串 s ,返回 其所有子字符串的总引力 。s 由小写英文字母组成。 子字符串 定义为:字符串中的一个连续字符序列
时间: 2024-03-23 11:43:58 浏览: 81
这道题可以用滑动窗口来解决。具体来说,我们可以枚举每个子字符串的起始位置和终止位置,然后计算该子字符串的引力,并将所有子字符串的引力相加。
对于每个子字符串,我们可以使用哈希表来统计其中不同字符的数量。具体来说,我们可以使用一个数组或哈希表来记录字符串中每个字符出现的次数,然后遍历该数组或哈希表,统计出现次数不为零的字符数量。
以下是代码实现:
```c++
#include <string>
#include <unordered_map>
using namespace std;
int getGravity(string s) {
unordered_map<char, int> cnt;
for (auto c : s) {
cnt[c]++;
}
int gravity = 0;
for (auto p : cnt) {
if (p.second > 0) {
gravity++;
}
}
return gravity;
}
int totalGravity(string s) {
int n = s.size();
int total = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
total += getGravity(s.substr(i, j - i + 1));
}
}
return total;
}
```
在上面的代码中,我们使用了 unordered_map 来统计每个字符出现的次数。getGravity 函数用于计算一个子字符串的引力,totalGravity 函数用于计算所有子字符串的总引力。
阅读全文