leetcode周赛,leetcode周赛难度
609.知道秘密的人数第一天，一个人发现了一个秘密。
给你一个整数延迟，意思是每个人在发现秘密后的延迟天数后，每天都会和一个新的人分享秘密。同时我给你一个整数锻炉，意思是大家发现秘密锻炉天后就忘了秘密。一个人不能在忘记秘密的当天和之后的日子里分享秘密。
给你一个整数n，请返回第n天结束时知道秘密的人数。由于答案可能很大，请取109 ^ 7的余数返回。
示例1:
输入：n=6，延迟=2，忘记=4
输出：5
解释：
第一天：假设第一个人的名字是a。(一个知道秘密的人)
第二天：A是唯一知道这个秘密的人。(知道秘密的人)
第三天：A和b分享这个秘密。(两个人都知道这个秘密)
第四天：A和一个新的人c分享这个秘密。(三个人知道这个秘密)
第五天：A忘记了这个秘密，B与一个新的人分享了这个秘密d .(三个人知道这个秘密)
第六天：B和E分享秘密，C和f分享秘密。(五个人知道秘密)
示例2:
输入：n=4，延迟=1，忘记=3
产出：6
解释：
第一天：第一个知道秘密的人是a。(一个知道秘密的人)
第二天：A和b分享这个秘密。(两个人都知道这个秘密)
第三天：A和B与两个新人C和d分享他们的秘密。(四个人知道这个秘密)
第四天：A忘记了秘密，B、C、D分别与3个新人分享。(六个人知道这个秘密)
提示：
2=n=1000
1=延迟忘记=n
资料来源：LeetCode
链接：3359leetcode.cn/problems/number-of-people-aware-of-a-secret
版权归领网所有。商业转载请联系官方授权，非商业转载请注明出处。
方案一：使用哈希表的实现思路：
用哈希表存储第I天已知的人数，然后减去第I天遗忘的人数，再加上当天新增的人数。最后用哈希表存储当天新增人数，到第n天时退出循环。
代码如下：
类别解决方案{
公共：
int peopleawarofsecret(int n，int delay，int forget)
{
long mod=1e 9 7；
std:unordered_map long，long m；//key==星期几，value==有多少人知道这一天？
m[1]=1；
long I=1；//哪天？
长总计=1；
while (i=n)
{
如果(我忘了)//那天被遗忘的人数
{
if (m.find(i - forget)！=m.end())
{
long v=m[I-forget]；
if(总v)
{
total=mod
}
total-=v；
m . erase(I-forget)；
}
}
如果(我延迟)
{
今天长=0；//当天新增人数
for(长k=I；k=i -忘记；- k)
{
中频(i - k延迟)
{
继续；
}
if (m.find(k)==m.end())
{
继续；
}
今天=m[k]；
}
如果(今天0)
{
today %=mod
total=(今日总计)% mod
m[i]=今天；
}
}
我；
}
返回总计% mod
}
};方法二：动态规划求解思路：
定义dp[i]为第I天新加入的知道秘密的人数：dp[0]=0，dp[1]=1。状态转移方程：DP[I]=accumulate(DP(I-遗忘1)，DP(I-延迟))-DP[I-遗忘]，即第I天新增的人数。I-delay区间之和，再减去dp[i-forget](意思是这一天会忘记那么多人)。返回值：用一个塑料累计每天新增的人数，减去每天被遗忘的人数。代码省略。有兴趣可以看看其他解决方案~ ~
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。