首页 > 其他分享 >Leetcode 2559. 统计范围内的元音字符串数

Leetcode 2559. 统计范围内的元音字符串数

时间:2023-06-02 19:23:11浏览次数:44  
标签:cnt && 2559 字符串 vector words queries 元音 Leetcode

题目:

给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries

每个查询 queries[i] = [l, r] 会要求我们统计在 words 中下标在 lr 范围内(包含 这两个值)并且以元音开头和结尾的字符串的数目。

返回一个整数数组,其中数组的第 i 个元素对应第 i 个查询的答案。

注意:元音字母是 'a''e''i''o''u'

难度:中等

示例1:

输入:words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
输出:[2,3,0]
解释:以元音开头和结尾的字符串是 "aba"、"ece"、"aa" 和 "e" 。
查询 [0,2] 结果为 2(字符串 "aba" 和 "ece")。
查询 [1,4] 结果为 3(字符串 "ece"、"aa"、"e")。
查询 [1,1] 结果为 0 。
返回结果 [2,3,0] 。

示例2:

输入:words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
输出:[3,2,1]
解释:每个字符串都满足这一条件,所以返回 [3,2,1] 。

提示:

  • 1 <= words.length <= 105
  • 1 <= words[i].length <= 40
  • words[i] 仅由小写英文字母组成
  • sum(words[i].length) <= 3 * 105
  • 1 <= queries.length <= 105
  • 0 <= queries[j][0] <= queries[j][1] < words.length

代码实现:

class Solution {
    public:
        vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
            // 前缀和数组处理
            // cnt[i] 表示 words数组中 前i个单词中的 元音字符串
            vector<int> cnt(words.size() + 1, 0);
            for(int i = 0; i < words.size(); ++i){
                cnt[i + 1] = cnt[i] + isValid(words[i]);
            }

            // 遍历求解
            vector<int> res;
            for(const auto& q : queries){
                // queries 数组为 [l, r] 左闭右闭,因此 为 cnt[l + 1] - cnt[r];
                res.emplace_back(cnt[q[1] + 1] - cnt[q[0]]);
            }
            return res;
        }

        bool isValid(const string& str){
            return valid(*str.begin()) && valid(*(--str.end()));
        }
        bool valid(char c){
            return !((c - 'a') && (c - 'e') && (c - 'i') && (c - 'o') && (c - 'u'));
        }
    };

标签:cnt,&&,2559,字符串,vector,words,queries,元音,Leetcode
From: https://www.cnblogs.com/DL1024/p/17452754.html

相关文章

  • LeetCode 236_ 二叉树的最近公共祖先
    classSolution{public:vector<TreeNode*>path1,path2;booldfs(TreeNode*root,TreeNode*p,vector<TreeNode*>&path){if(!root)returnfalse;if(root==p||dfs(root->left,p,path)||dfs(root->right,p,path))......
  • LeetCode235. 二叉搜索树的最近公共祖先
    classSolution{public:TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){if(p->val<root->val&&q->val<root->val)returnlowestCommonAncestor(root->left,p,q);if(p->v......
  • leetcode 1341 电影评分
    leetcode1341 电影评分(selectu1.nameasresultsfromUsersu1leftjoin(selectmr1.user_id,count(mr1.rating)asc1fromMovieRatingasmr1groupbymr1.user_idhavingc1=(selectmax(p.c2)fromUsersasu2......
  • leetcode 65. 有效数字 66. 寻找两个正序数组的中位数
    leetcode65.有效数字66.寻找两个正序数组的中位数65.有效数字难度困难295有效数字(按顺序)可以分成以下几个部分:一个小数或者整数(可选)一个'e'或'E',后面跟着一个整数小数(按顺序)可以分成以下几个部分:(可选)一个符号字符('+'或'-')下述格式之一:至少一位数字,后面跟着一个......
  • 图解LeetCode——98. 验证二叉搜索树
    一、题目给你一个二叉树的根节点root,判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。二、示例2.1>示例1:【输入】root=[......
  • LeetCode/叶值的最小代价生成树
    给你一个正整数数组 arr,考虑所有满足以下条件的二叉树:每个节点都有0个或是2个子节点。数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。在所有这样的二叉树中,返回每个非叶节点的值的最小可能总......
  • LeetCode 96.不同的二叉搜索树
    1.题目:给你一个整数n,求恰由n个节点组成且节点值从1到n互不相同的二叉搜索树有多少种?返回满足题意的二叉搜索树的种数。示例1:输入:n=3输出:5示例2:输入:n=1输出:1来源:力扣(LeetCode)链接:https://leetcode.cn/problems/unique-binary-search-trees著作权归领扣网络所有......
  • LeetCode 343.整数拆分
    1.题目:给定一个正整数 n ,将其拆分为k个正整数的和( k>=2 ),并使这些整数的乘积最大化。返回你可以获得的最大乘积 。示例1:输入:n=2输出:1解释:2=1+1,1×1=1。示例 2:输入:n=10输出:36解释:10=3+3+4,3× 3× 4=36。来源:力扣(LeetCo......
  • 图解LeetCode——102. 二叉树的层序遍历
    一、题目给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地,从左到右访问所有节点)。二、示例2.1>示例1:【输入】root=[3,9,20,null,null,15,7]【输出】[[3],[9,20],[15,7]]2.2>示例2:【输入】root=[1]【输出】[[1]]2.3>示例3:【输入】root=[]......
  • [leetcode每日一题]5.31
    1130. 叶值的最小代价生成树提示中等324相关企业给你一个正整数数组 arr,考虑所有满足以下条件的二叉树:每个节点都有 0 个或是 2 个子节点。数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。在所有这......