当前位置: 首页 > article >正文

元音辅音字符串计数leetcode3305,3306

题目链接:3305. 元音辅音字符串计数 I - 力扣(LeetCode)

思路一:暴力枚举

暴力枚举出所有子字符串 ,统计所有满足每个元音字母都出现k个辅音字母的字符串个数

其中可以使用set集合判断子串中是否每个元音字母都出现,用一个变量count来统计辅音字母的出现次数。

class Solution {
public:
    int countOfSubstrings(string word, int k) {
        set<char> vowels={'a','e','i','o','u'};
        int ret=0;
        for(int i=0;i<word.size();i++)
        {
            set<char> cur;
            int count=0;
            for(int j=i;j<word.size();j++)
            {
                if(vowels.count(word[j]))
                cur.insert(word[j]);
                else
                count++;

                if(vowels.size()==cur.size()&&count==k)
                ret++;
            }
        }
        return ret;
    }
};

该思路,只能通过第一题, 第二题的数据范围大,会超时。

思路二:滑动窗口

 暴力解法的思路,我们每次在用两个变量来枚举[i,j]这个子串时,统计完后,i++,j还要再返回i的位置,重新遍历,所以时间复杂度太高, 为O(N^2)。

题目要求出子串中恰好包含k个 辅音字母,我们可以先求出满足至少包含k个辅音字母的子串个数count(k),再求出至少包含k+1个辅音字母的子串个数count(k+1)。而我们想要的结果刚好等于 count(k)-count(k+1)。其中 求count(k)我们可以用滑动窗口实现。

具体过程(配图): 

 具体过程(文字描述):

1,进窗口,固定左端点i,让右端点j开始右移,直到找到一个满足要求的区间,

使用 一个哈希表cur来统计区间中元音字母及其出现次数,使用一个变量cnt来统计区间中辅音字母的出现次数。


2,更新结果,当找到一个满足要求的区间,区间[i,j]满足包含所有的原因字母及至少包含k个辅音字母,这时,j就不需要继续往后移动了,因为后面的也必然满足要求。相当于我们找出了固定左端点i,所有满足要求的子串个数:n-j+1。更新结果,让ret+=n-j+1


3,出窗口,  统计完结果后,左端点i右移,word[i]要出窗口,分两种情况:

 如果word[i]为元音字母,将让哈希表中 对应元音字母的出现次数--,如果减为0,就将该元音字母从哈希表中删除。

如果word[i]为辅音字母,将cnt--即可。

class Solution {
public:
    long long countOfSubstrings(string word, int k) {
        // 求出子串中满足至少出现k个辅音字母的子串个数
        // 求出子串中满足至少出现k+1个辅音字母的子串个数
        // 结果就是count(k)-count(k+1)
        return count(word, k) - count(word, k + 1);
    }
       // 该函数用来求出至少出现k个辅音字母的子串个数
    long long count(string& word, int k) {
        set<char> owels = {'a', 'e', 'i', 'o', 'u'};
        long long ret=0,n=word.size();
        map<char,int> cur;//统计窗口中元音字母及其出现次数,方便窗口的移动
        int cnt=0;//统计辅音字母的个数

        for(int i=0,j=0;i<n;i++)
        {
            //进窗口
            //左端点word[i]固定,word[j]进窗口
            while(j<n&&(cnt<k||cur.size()<owels.size()))
            {
                if(owels.count(word[j]))
                cur[word[j]]++;  //元音字母
                else
                cnt++;   //辅因字母
                j++;
            }
            //更新结果
            if(cnt>=k&&cur.size()==owels.size())
            {
                ret+=n-j+1;
            }
            //出窗口
            //左端点右移,word[i]出窗口
            if(owels.count(word[i]))
            {
                //word[i]为元音字母
                cur[word[i]]--;
                if(cur[word[i]]==0)
                cur.erase(word[i]);
            }
            else
            {
                //word[i]为辅音字母
                cnt--;
            }
        }
        return ret;
    }
};


http://www.kler.cn/a/587005.html

相关文章:

  • 自然语言秒转SQL—— 免费体验 OB Cloud Text2SQL 数据查询
  • 软件行业的“3.15问题”有哪些?如何防止?
  • C++ unordered_map unordered_set 模拟实现
  • Certbot实现SSL免费证书自动续签(CentOS 7版 + Docker部署的nginx)
  • 测试工程师指南:基于需求文档构建本地安全知识库的完整实战
  • HarmonyOS第24天:鸿蒙应用安全秘籍:如何为用户数据筑牢防线?
  • 使用Python实现经典贪吃蛇游戏教程
  • python相关语法的学习文档1
  • 4.3 计算属性与watch的类型守卫实现
  • 软考高级《系统架构设计师》知识点(十三)
  • Day2 导论 之 「存储器,IO,微机工作原理」
  • 代码随想录二刷|图论6
  • 【.Net 9下使用Tensorflow.net---通过LSTM实现中文情感分析】
  • C++中std::count` 和 `std::count_if`的用法和示例
  • 数据结构-单链表专题
  • 【开源代码解读】AI检索系统R1-Searcher通过强化学习RL激励大模型LLM的搜索能力
  • DataEase:一款国产开源数据可视化分析工具
  • 蓝桥杯Python赛道备赛——Day5:算术(一)(数学问题)
  • 在Linux中安装Nginx
  • 机器学习之线性代数