开发者

C++ LeetCode1781题解所有子字符串美丽值之和

目录
  • LeetCode 1781.所有子字符串美丽值之和
  • 方法一:前缀和
  • AC代码
    • C++
  • 方法二:边遍历边计算
    • AC代码
      • C++

    LeetCode 1781.所有子字符串美丽值之和

    力扣题目链接:leetcode.cn/problems/su…

    一个字符串的 美丽值 定义为:出现频率最高字符与出现频率最低字符的出现次数之差。

    • 比方说,"abaacc" 的美丽值为 3 - 1 = 2 。

    给你一个字符串 s ,请你返回它所有子字符串的 美丽值 之和。

    示例 1:

    输入:s = "aabcb"

    输出:5

    解释:美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ,每一个字符串的美丽值都为 1 。

    示例 2:

    输入:s = "aabcbaa"

    输出:17

    提示:

    • 1 <= s.length <= 500
    • s 只包含小写英文字母。

    方法一:前缀和

    我们分别统计出26种字母的前缀和

    这样,我们只需要枚举子串区间(两重循环枚举子串首尾),再统计出这个区间中,字母的最大和最小出现频率,累加到答案中即可。

    C++ LeetCode1781题解所有子字符串美丽值之和

    AC代码

    C++

    class Solution {
    public:
        int beautySum(string s) {
            int n = s.size();
            vector<vector<int>> prefix(26, vector<int>(n + 1));
            for (int i = 1; i <= n; i++) {
        js        for (int c = 0; c < 26; c++) {
                    prefix[c][i] = prefix[c][i - 1];
                }
                prefix[s[i - 1] - 'a'][i]++;
            }
            int ans = 0;
            for (int i = 0; i < njs; i++) {
                for (int j = i + 1; j < n; j++) {
                    int M = 0, m = 1000;
                    for (int c = 0; c < 26; c++) {
                        int thisC = prefix[c][j + 1] - prefix[c][i];
                        M = max(M, thisC);
                        if (thisC) {  // 不能出现0次
                            m = min(m, thisC);
                        }
                    }
                    // printf("i = %d, j = %d, M = %pythond, m = %d\n", i, j, M, m);  //***********
                    ans += M - m;
                }
            }
            return ans;
        }
    };
    

    方法二:边遍历边计算

    方法一中,我们预处理使用前缀和计算出了每种元素的出现情况。但是每种字母的前缀和都需要O(len(s))O(len(s))O(len(s))的空间复杂度来保存

    方法二中,我们不提前预处理计算出字母的出现情况,而是在枚举字符串终点的同时计算。这样,空间复杂度就减小了一个维度。

    C++ LeetCode1781题解所有子字符串美丽值之和

    AC代码

    C++

    class Solution {
    public:
        int beautySum(string s) {
            int ans = 0;
            int n = s.size();
            for (int i = 0; i < n; i++)http://www.devze.com {
                int cnt[26] = {0};  // 只需要开辟O(C)的空间
                for (int j = i; j < n; j++) {javascript
                    cnt[s[j] - 'a']++;  // 枚举子串终点的同时统计元素出现的次数
                    int M = 0, m = 1000;
                    for (int d = 0; d < 26; d++) {
                        M = max(M, cnt[d]);
                        if (cnt[d])
                            m = min(m, cnt[d]);
                    }
                    ans += M - m;
                }
            }
            return ans;
        }
    };

    开发者_JAVA上就是C++ LeetCode1781题解所有子字符串美丽值之和的详细内容,更多关于C++ 子字符串美丽值和的资料请关注我们其它相关文章!

    0

    上一篇:

    下一篇:

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    最新开发

    开发排行榜