LeetCode---374周赛

题目列表

2951. 找出峰值

2952. 需要添加的硬币的最小数量

2953. 统计完全子字符串

2954. 统计感冒序列的数目

一、找到峰值

这个简单的模拟，代码如下

class Solution {
public:
    vector<int> findPeaks(vector<int>& mountain) {
        int n=mountain.size();
        vector<int>ans;
        for(int i=1;i<n-1;i++){
            if(mountain[i]>mountain[i-1]&&mountain[i]>mountain[i+1])
                ans.push_back(i);
        }
        return ans;
    }
};

二、需要添加的硬币的最小数量

题目要求我们添加最小的金币数，使得我们能用已有的金币凑出1~target中的任何一个数值，这题看着简单，但是思维难度比第三题高，是那种思维题，这里讲一下思路：要先排序，因为我们在顺序时，会更容易找出规律

我们要保证1~target中的每一个元素都能被构造，那么什么情况下一个数是不能被构造出来的？假设我们能用前i个数构造出[1,x]，现在我们要构造x+1这个数，怎么办？

1.如果coins[i+1] == x+1，我们当然能构造出来x+1，且一直到x+x+1我们都能构造出来

2.如果coins[i+1] < x+1，我们也能构造出x+1，且一直到x+coin[i+1]我们都能构造出来

3.如果coins[i+1]>x+1呢？显然我们就无法构造出x+1了(因为我们已经排过序了，所以coins[i+1]!=1)，那么我们是补1呢？还是直接补一个x+1？显然我们肯定是补x+1，这样我们能构造出的数据区间最大为[1，2*x+1]

如此循环，得到答案，因为我们每次加的金币都会让数据区间最大化，贪心的思路如下图

这题的关键是我们要往加粗的两个语句上去思考，本质是一个数学归纳的思想

代码如下

class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        int ans=0;
        int t=0;//表示[1,t]区间内的值可以构造
        sort(coins.begin(),coins.end());
        int i=0,n=coins.size();//用来遍历数组
        while(t<target){
            while(i<n&&t+1>=coins[i]){
                t+=coins[i];
                i++;
                if(t>=target)
                    return ans;
            }
            t+=(t+1);
            ans++;
        }
        return ans;
    }
};

?三、统计完全子字符串

这题的完全字符串有两个条件，分别对应我们思路的两个部分：

1.条件1是标准的滑动窗口问题，共有26种固定大小的窗口需要考虑

2.条件2意味着需要将字符串拆分成符合条件的子字符串来考虑，因为子字符串是连续的，一旦出现两个相邻字符的大小相差>2，那么就不可能有一个满足条件的子字符串同时包含这两个字符

代码如下

class Solution {
public:
    int countCompleteSubstrings(string word, int k) {
        int i=0;
        int n=word.size(),ans=0;
        function<int(int,int)>getNum=[&](int start,int end)->int{
            int ret=0;
            for(int i=1;i<=26;i++){//一共有26个大小不同的窗口
                //滑动窗口
                int sz=i*k;
                if(sz>end-start) break;
                int cnt[26]={0};
                for(int l=start,r=start,s=0;r<end;r++){
                    int idx=word[r]-'a';
                    if(++cnt[idx]==k) s++;
                    if(cnt[idx]==k+1) s--;//注意不是>k
                    if(r-l+1>sz){
                        idx=word[l]-'a';
                        if(--cnt[idx]==k) s++;
                        if(cnt[idx]==k-1) s--;//注意不是<k
                        l++;
                    }
                    if(i==s) ret++;
                }  
            }
            return ret;
        };

        while(i<n){
            int begin=i;
            i++;
            while(i<n&&abs(word[i]-word[i-1])<=2)
                i++;
            if(i-begin>=k) ans+=getNum(begin,i);//[begin,i)的区间符合条件二 
        }
        return ans;
    }
};

四、统计感冒序列的数目

数学题，题解如下?

?代码如下

const int MX=100000;
const int MOD=1e9+7;
typedef long long LL;
LL fac[MX],inv_fac[MX];
//快速幂
LL POW(LL x,LL y){
    LL ret=1;
    while(y){
        if(y&1) ret=(ret*x)%MOD;
        x=(x*x)%MOD;
        y>>=1;
    }
    return ret;
}

//预处理
int init=[](){
    fac[0]=1;
    for(int i=1;i<MX;i++){
        fac[i]=fac[i-1]*i%MOD;
    }

    //逆元
    inv_fac[MX-1]=POW(fac[MX-1],MOD-2);
    for(int i=MX-1;i>0;i--){
        inv_fac[i-1]=inv_fac[i]*i%MOD;
    }
    return 0;
}();

long long comb(int n,int k){//n!/((n-k)!*k!)
    return fac[n]*inv_fac[k]%MOD*inv_fac[n-k]%MOD;
}

class Solution {
public:
    int numberOfSequence(int n, vector<int>& sick) {
        int m=sick.size();
        int total=n-m;
        long long ans=comb(total,sick[0])*comb(total-sick[0],n-sick.back()-1)%MOD;
        total-=sick[0]+n-sick.back()-1;
        int x=0;
        for(int i=0;i<m-1;i++){
            int k=sick[i+1]-sick[i]-1;
            if(k){
                x+=k-1;
                ans=ans*comb(total,k)%MOD;
                total-=k;
            }
        }
        return ans*POW(2,x)%MOD;
    }
};