力扣周赛252题解

Posted on | Post modified:

力扣周赛252题解

T1. 三除数

直接枚举因子个数，时间复杂度为$O(\sqrt{n})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isThree(int n) {
        int ans=0;
        for(int i=1;i*i<=n;i++){
            if(n%i==0){
                if(i*i==n){
                    ++ans;
                }else{
                    ans+=2;
                }
            }
        }
        return ans==3;
    }
};

T2. 你可以工作的最大周数

如果阶段任务最多的可以做完，则剩余的也一定可以做完。

假设除了最多的阶段任务，剩下的阶段任务有$res$个。

答案为$min(2*res+1,n)$，$n$为总个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    long long numberOfWeeks(vector<int>& milestones) {
        long long s=0;
        long long maxx=0;
        for(int v:milestones){
            s+=v;
            maxx=max(maxx,v*1LL);
        }
        long long res=s-maxx;
        return min(s,2*res+1);
    }
};

T3. 收集足够苹果的最小花园周长

假设右上角顶点坐标为$(n,n)$，则第一象限的苹果个数为：

$nn(n+1)$，则总的苹果个数为$4nn(n+1)+2(n+1)*n$。

二分/暴力即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    long long cal(long long x){
        long long first=x*x*(x+1)*4+2*(x+1)*x;
        return first;
    }
    long long minimumPerimeter(long long ned) {
        long long l=1,r=5e5;
        while(l<=r){
            long long mid=(l+r)/2;
            if(cal(mid)>=ned){
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return 8*(r+1);
    }
};

T4. 统计特殊子序列的数目

令$dp[i][j]$表示$a_{1},…,a_{i}$中以$j$结尾的特殊子序列个数。

则有：

$dp[i][0]=2*dp[i-1][0]+1$

$dp[i][1]=2*dp[i-1][1]+dp[i-1][0]$

$dp[i][2]=2*dp[i-1][2]+dp[i-1][1]$

实际上可以做到空间$O(1)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int mod = 1e9+7;
class Solution {
public:
    int countSpecialSubsequences(vector<int>& nums) {
        long long A,B,C;
        A=B=C=0;
        for(int v:nums){
            if(v==0) A=A*2+1;
            if(v==1) B=2*B+A;
            if(v==2) C=2*C+B;
            A%=mod;
            B%=mod;
            C%=mod;
        }
        return C;
    }
};

彩蛋

image-20221106162215445