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种字母的前缀和

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

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++) {
            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 < n; 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 = %d, m = %d\n", i, j, M, m);  //***********
                ans += M - m;
            }
        }
        return ans;
    }
};

方法二：边遍历边计算

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

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

AC代码

C++

class Solution {
public:
    int beautySum(string s) {
        int ans = 0;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            int cnt[26] = {0};  // 只需要开辟O(C)的空间
            for (int j = i; j < n; j++) {
                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;
    }
};

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

赞 (0)

相关推荐

  • C C++ 题解LeetCode1417重新格式化字符串

    目录 题目描述 整理题意 解题思路分析 具体实现 复杂度分析 代码实现 总结 题目描述 题目链接:1417. 重新格式化字符串 给你一个混合了数字和字母的字符串 s,其中的字母均为小写英文字母. 请你将该字符串重新格式化,使得任意两个相邻字符的类型都不同.也就是说,字母后面应该跟着数字,而数字后面应该跟着字母. 请你返回 重新格式化后 的字符串:如果无法按要求重新格式化,则返回一个 空字符串 . 提示: 1⩽s.length⩽5001 s 仅由小写英文字母和/或数字组成. 示例 1: 输入:s

  • C++ LeetCode1832题解判断句子是否为全字母句

    目录 LeetCode 1832.判断句子是否为全字母句 方法一:统计 AC代码 C++ LeetCode 1832.判断句子是否为全字母句 力扣题目链接:leetcode.cn/problems/ch… 全字母句 指包含英语字母表中每个字母至少一次的句子. 给你一个仅由小写英文字母组成的字符串 sentence ,请你判断 sentence 是否为 全字母句 . 如果是,返回 true :否则,返回 false . 示例 1: 输入:sentence = "thequickbrownfoxju

  • C C++ LeetCode题解在二叉树中增加一行示例详解

    C C++ LeetCode题解在二叉树中增加一行示例详解

    目录 题目描述 整理题意 解题思路分析 层序遍历(广度优先搜索) 递归(深度优先搜索) 具体实现 复杂度分析 代码实现 层序遍历(广度优先搜索) 递归(深度优先搜索) 总结 题目描述 题目链接:623. 在二叉树中增加一行 给定一个二叉树的根 root 和两个整数 val 和 depth ,在给定的深度 depth 处添加一个值为 val 的节点行. 注意,根节点 root 位于深度 1 . 加法规则如下: 给定整数 depth,对于深度为 depth - 1 的每个非空树节点 cur ,创建两

  • LeetCode题解C++生成每种字符都是奇数个的字符串

    目录 题目描述 整理题意 解题思路分析 具体实现 复杂度分析 代码实现 总结 题目描述 题目链接:1374. 生成每种字符都是奇数个的字符串 给你一个整数 n,请你返回一个含 n 个字符的字符串,其中每种字符在该字符串中都恰好出现 奇数次 . 返回的字符串必须只含小写英文字母.如果存在多个满足题目要求的字符串,则返回其中任意一个即可. 提示: 1 <= n <= 500 示例 1: 输入:n = 4输出:"pppz"解释:"pppz" 是一个满足题目要求

  • C++ LeetCode1945题解字符串转化后的各位数字之和

    目录 1945.字符串转化后的各位数字之和 方法一:计算 AC代码 C++ 1945.字符串转化后的各位数字之和 力扣题目链接:leetcode.cn/problems/su… 给你一个由小写字母组成的字符串 s ,以及一个整数 k . 首先,用字母在字母表中的位置替换该字母,将 s 转化 为一个整数(也就是,'a' 用 1 替换,'b' 用 2 替换,... 'z' 用 26 替换).接着,将整数 转换 为其 各位数字之和 .共重复 转换 操作 k 次 . 例如,如果 s = "zbax&qu

  • C C++算法题解LeetCode1408数组中的字符串匹配

    C C++算法题解LeetCode1408数组中的字符串匹配

    目录 题目描述 整理题意 解题思路分析 优化 具体实现 复杂度分析 代码实现 暴力 暴力 + 优化 KMP 总结 题目描述 题目链接:1408. 数组中的字符串匹配 给你一个字符串数组 words ,数组中的每个字符串都可以看作是一个单词.请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词. 如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ,那么字符串 words[i] 就是 words[j] 的一个子字符串. 提示: 示例 1: 输入:wo

  • C++ LeetCode0547题解省份数量图的连通分量

    目录 LeetCode 547.省份数量 方法一:BFS求图的连通分量 AC代码 C++ LeetCode 547.省份数量 力扣题目链接:leetcode.cn/problems/nu… 有 n 个城市,其中一些彼此相连,另一些没有相连.如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连. 省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市. 给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i

  • C C++ 题解LeetCode2360图中的最长环示例

    C C++ 题解LeetCode2360图中的最长环示例

    目录 题目描述 整理题意 解题思路分析 具体实现 复杂度分析 代码实现 总结 题目描述 题目链接:2360. 图中的最长环 给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,其中每个节点 至多 有一条出边. 图用一个大小为 n 下标从 0 开始的数组 edges 表示,节点 i 到节点 edges[i] 之间有一条有向边.如果节点 i 没有出边,那么 edges[i] == -1 . 请你返回图中的 最长 环,如果没有任何环,请返回 -1 . 一个环指的是起点和终点是 同一个 

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

    目录 LeetCode 1781.所有子字符串美丽值之和 方法一:前缀和 AC代码 C++ 方法二:边遍历边计算 AC代码 C++ LeetCode 1781.所有子字符串美丽值之和 力扣题目链接:leetcode.cn/problems/su… 一个字符串的 美丽值 定义为:出现频率最高字符与出现频率最低字符的出现次数之差. 比方说,"abaacc" 的美丽值为 3 - 1 = 2 . 给你一个字符串 s ,请你返回它所有子字符串的 美丽值 之和. 示例 1: 输入:s = &quo

  • Java遍历json字符串取值的实例

    java遍历json字符串,取得相应KV值时,各种麻烦,比如将json中的list取出来转为JSONArray,再将list中的object转化为map,再取值(之前的做法),仙子啊通过阿里的fastjson,可以很方便的直接将str转化为JSONArray,再将里面的object强转为JSONObject,然后再通过obj.getInteger("key")和obj.getString("key")等取值. JSONArray json = (JSONArray)

  • python 获取字符串MD5值方法

    工作中用到了MD5值来进行对文件校验,MD5本身就是一个很出色的算法,一定程度上解决了hash散列的冲突,关于MD5的内容网上也有很多,这里只要是进行一个实验,验证一下文件校验方面的工作,因为习惯使用了python来完成这样的任务,这里也是使用python,了解到python本身自带有hashlib模块,该模块中就包含了所需的MD5方法,当然python也有专门的MD5模块可以使用,使用得当发的大同小异,但是个人觉得hashlib模块更好用一些,今天就使用python的os.commands还有

  • javascript实现获取字符串hash值

    性能很高的计算字符串或文件hash值的函数,比md5速度快得多,自己一直用着,重复的几率为很底,一般的应用足够, var I64BIT_TABLE = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-'.split(''); function hash(input){ var hash = 5381; var i = input.length - 1; if(typeof input == 'string'){ f

  • php数组函数序列之array_sum() - 计算数组元素值之和

    array_sum()定义和用法 array_sum() 函数返回数组中所有值的总和. 如果所有值都是整数,则返回一个整数值.如果其中有一个或多个值是浮点数,则返回浮点数. PHP 4.2.1 之前的版本修改了传入的数组本身,将其中的字符串值转换成数值(大多数情况下都转换成了零,根据具体制而定). 语法 array_sum(array) 参数 描述 array 必需.规定输入的数组. 例子1 复制代码 代码如下: <?php $a=array(0=>"5",1=>&q

  • javascript中json对象json数组json字符串互转及取值方法

    javascript中json对象json数组json字符串互转及取值方法

    今天用到了json数组和json对象和json类型字符串之间互转及取值,记录一下: 1.json类型的字符串转换为json对象及取值 var jsonString = '{"bar":"property","baz":3}'; var jsObject = JSON.parse(jsonString); //转换为json对象 alert(jsObject.bar); //取json中的值  2.json对象转为json类型的字符串 var js

  • C#使用第三方组件实现动态解析和求值字符串表达式

    C#使用第三方组件实现动态解析和求值字符串表达式

    目录 介绍 1.Z.Expressions.Eval 表达式解析 2.NReco.LambdaParser 表达式解析 3.DynamicExpresso 表达式解析 4.SQL条件语句的正则表达式和字符串求值处理 介绍 在进行项目开发的时候,刚好需要用到对字符串表达式进行求值的处理场景,因此寻找了几个符合要求的第三方组件LambdaParser.DynamicExpresso.Z.Expressions,它们各自功能有所不同,不过基本上都能满足要求.它们都可以根据相关的参数进行字符串表达式的求

  • Python数据类型详解（一）字符串

    一.基本数据类型 整数:int 字符串:str(注:\t等于一个tab键) 布尔值: bool 列表:list 列表用[] 元祖:tuple 元祖用() 字典:dict 注:所有的数据类型都存在想对应的类列里 二.字符串所有数据类型: 基本操作: 索引,切片,追加,删除,长度,切片,循环,包含 class str(object): """ str(object='') -> str str(bytes_or_buffer[, encoding[, errors]]) -

  • ASP中Split分割字符串函数的实例用法

    ASP中Split函数的用法 分割截取字符串看几个例子就能理解了 复制代码 代码如下: mystr="1,2,3,4,5" mystr=split(mystr,",") for i=0 to ubound(mystr) response.write mystr(i) next  '返回值为123456 mystr="xlei.net/http/student/x/index.asp" mystr=split(mystr,"/http/s

  • Lua字符串模式匹配函数小结

    模式匹配函数 在string库中功能最强大的函数是: 复制代码 代码如下: string.find(字符串查找) string.gsub(全局字符串替换) string.gfind(全局字符串查找) string.gmatch(返回查找到字符串的迭代器) 这些函数都是基于模式匹配的.与其他脚本语言不同的是,Lua并不使用POSIX规范的正则表达式[4](也写作regexp)来进行模式匹配.主要的原因出于程序大小方面的考虑:实现一个典型的符合POSIX标准的regexp大概需要4000行代码,这比

随机推荐