力扣周赛252题解
T1. 三除数
直接枚举因子个数,时间复杂度为O(√n)
1 | class Solution { |
T2. 你可以工作的最大周数
如果阶段任务最多的可以做完,则剩余的也一定可以做完。
假设除了最多的阶段任务,剩下的阶段任务有res个。
答案为min(2∗res+1,n),n为总个数。
1 | class Solution { |
T3. 收集足够苹果的最小花园周长
假设右上角顶点坐标为(n,n),则第一象限的苹果个数为:
$nn(n+1),则总的苹果个数为4nn(n+1)+2(n+1)*n$。
二分/暴力即可。
1 | class Solution { |
T4. 统计特殊子序列的数目
令dp[i][j]表示a1,…,ai中以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 | const int mod = 1e9+7; |