leetcode第68双周赛

竞赛链接

T1: 5946. 句子中的最多单词数

---

思路

暴力,并记录句子中最多的空格数

Code

class Solution {
public:
    int mostWordsFound(vector<string>& sentences) {
        int res=0;
        for(auto& i:sentences){
            int cnt=0;
            for(auto& s:i)
                if(s==' ')
                    cnt++;
            res=max(res,cnt+1);
        }
        return res;
    }
};

复杂度分析

时间复杂度：O(n2)
空间复杂度：O(1)

T2: 5947. 从给定原材料中找到所有可以做出的菜

---

思路

法一：因为本题数据范围较小，所以可以通过死循环直到做不出新的菜品为止
法二：拓扑排序（最为重要的是把所有的原材料作为顶点。然后去查看这些菜谱是不是可以被做成功

Code

class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_map<string,bool>ha;
        for(auto& s:supplies)
            ha[s]=true;
        vector<string>ans;
        int n=recipes.size();
        vector<bool>hb(n,false);
        int m=-1,t=-1,flag=0;
        while(1){
            for(int i=0;i<n;++i){
            if(hb[i])
                continue;

            bool f=true;
            for(auto& j:ingredients[i]){
                if(ha.count(j)==0){
                    f=false;
                    break;
                }    
            }
            if(f&&!ha.count(recipes[i]))
                m++;
            if(f)
                ans.emplace_back(recipes[i]),ha[recipes[i]]=true,hb[i]=true; 
        }
            if(m!=t)
                t=m,flag=0;
            else if(m==t)
                flag++;
            if(flag>2)
                break;
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度O(N^3/W)。其中W为字长
• 空间复杂度O(N^3/W)。

T3: 5948. 判断一个括号字符串是否有效

---

思路

首先排除掉字符个数为奇数的情况，再通过正向遍历判断不可更改的右括号，再通过反向遍历判断不可变更的左括号，判断是否均满足条件
几乎一样的题目：678. 有效的括号字符串

Code

class Solution {
public:
    bool canBeValid(string s, string locked) {
        int n=s.size(),cnt=0;
        if(n%2!=0)
            return false;

        for(int i=0;i<n;++i){  //第一次正向遍历保证'(' 和 *      肯定大于 ')'
            if(locked[i]=='0'||s[i]=='(')  //若locked[i]=0我们视为*
                cnt++;
            else{
                if(cnt==0)  return false;
                else    cnt--;
            }    
        }
        reverse(s.begin(),s.end());
        reverse(locked.begin(),locked.end());
        cnt=0;

        for(int i=0;i<n;++i){   //第二次反向遍历保证')' 和 *      肯定大于 '('
            if(locked[i]=='0'||s[i]==')')
                cnt++;
            else{
                if(cnt==0)  return false;
                else    cnt--;
            }    
        }
        return true;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

T4: 5949. 一个区间内所有数乘积的缩写

---

思路

分步考虑，同时要注意数据溢出以及精度问题

Code

class Solution {
public:
    string abbreviateProduct(int left, int right) {
        long long res=1;
        int num=0;    //后缀0的个数
        bool f=false;
        for(int i=left;i<=right;i++){
            res*=i;
            while(res%10==0) res/=10,num++;
            if(res>=10000000000) f=1,res%=1000000;  //这里取余要比预留的多一位否则会出错，取余也可以同时防止溢出
        }
        if(!f)return to_string(res)+"e"+to_string(num);   //如果res所剩数字不大于10则不做修改
        else{
            long double dd=1;
            for(int i=left;i<=right;i++){   //取前5位
                dd*=i;
                while(dd>100000)dd/=10;
            }
            char s[1000]={0};  //存最终结果
            sprintf(s,"%05d...%05de%d",int(dd),res%100000,num);  //res%100000取后5位 sprintf格式化输出，功能很强大
            return s; 
        }
    }
};

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

额外拓展

考虑到标准输出还是蛮常用的所以补充个sprintf详细用法

个人总结

---

本次双周赛，前两题还算比较顺畅，但还不够快，t3被卡了有一会，主要问题是贪心考虑的不够全面，导致wa2，t4看完后没有啥头绪，直接罚坐….