dede淘宝客网站,做交易网站存在什么风险,网络平台制作软件教程,黑龙江新闻联播直播今天视频Problem: 2947. 统计美丽子字符串 I 文章目录 题目思路Code 题目
给你一个字符串 s 和一个正整数 k 。
用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。
如果某个字符串满足以下条件#xff0c;则称其为 美丽字符串 #xff1a;
vowels consonants… Problem: 2947. 统计美丽子字符串 I 文章目录 题目思路Code 题目
给你一个字符串 s 和一个正整数 k 。
用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。
如果某个字符串满足以下条件则称其为 美丽字符串
vowels consonants即元音字母和辅音字母的数量相等。 (vowels * consonants) % k 0即元音字母和辅音字母的数量的乘积能被 k 整除。 返回字符串 s 中 非空美丽子字符串 的数量。
子字符串是字符串中的一个连续字符序列。
英语中的 元音字母 为 ‘a’、‘e’、‘i’、‘o’ 和 ‘u’ 。
英语中的 辅音字母 为除了元音字母之外的所有字母。
示例 1
输入s “baeyh”, k 2 输出2 解释字符串 s 中有 2 个美丽子字符串。
子字符串 “baeyh”vowels 2[“a”,“e”]consonants 2[“y”,“h”]。 可以看出字符串 “aeyh” 是美丽字符串因为 vowels consonants 且 vowels * consonants % k 0 。子字符串 “baeyh”vowels 2[“a”,“e”]consonants 2[“b”,“y”]。 可以看出字符串 “baey” 是美丽字符串因为 vowels consonants 且 vowels * consonants % k 0 。 可以证明字符串 s 中只有 2 个美丽子字符串。
思路 暴力思路就是枚举每个子串符合条件的就加1但是会超时。我们把元音字符的看作1,辅音字符看作-1题目中美丽字符串要求元音字符和辅音字符相等即转化成子串中 (辅音字符元音字符) 0我们求出前缀和找到perSum[j] 和perSum[i]相等,即 perSum[j] perSum[i] j i ji ji。然后 j-i就是子串的长度$m (j-i1)/2 (或者 (j-i) /2 具体看你前缀和下标) $ 元音字符个数 辅音字符个数,如果(m*m)%k 0,就是美丽字符串 Code
class Solution {
public:unordered_mapchar,int strMap ; void init() {char c[5] {a,e,i,o,u} ; for(int i 0 ; i5 ; i) {strMap[c[i]] 1 ; }}int beautifulSubstrings(string s, int k) {// 前缀和的做法 init() ; int n s.size() ; vectorint a(n) ; for(int i 0 ;in ; i ){if(strMap.count(s[i])) {a[i] 1 ; // 元音}else{a[i] -1 ; }}// 前缀和为 0的子串个数vectorint perSum(n1) ; for(int i 1; in ; i) {perSum[i] perSum[i-1] a[i-1] ; }int ans 0 ; for(int i 0 ; in ; i) {for(int j i1 ; jn ; j ) {if(perSum[j] perSum[i] ) {// 元音个数 辅音个数 子串长度/2int v (j-i 1)/2; if ((v *v) %k 0 ) {ans ;} }}}return ans ; }
};
