当前位置:网站首页>20220703 周赛:知道秘密的人数-动规(题解)
20220703 周赛:知道秘密的人数-动规(题解)
2022-07-05 23:28:00 【阿旋要毕业~】
题目链接:力扣https://leetcode.cn/problems/number-of-people-aware-of-a-secret/
思路:
一开始的思路是生兔子。当前知道秘密的人数=前一天知道秘密的人数+(i-delay)的人数-(i-forget)的人数。后来推导的过程中发现,(i-delay)的人,第i天不一定还在,说不定已经遗忘了。(i-forget)的人数也是不准的,说不定在(i-forget ——i)之间已经遗忘了。
问题的关键是:得到的式子应该是:当天人数 = 前一天人数-(第i天忘记的人数)+ 新得到消息的人数。那么第i天忘记的人数和新得到消息的人数应该怎么求呢。其实只要添加一个数组get数组表示新得到消息的人数就可以。
我们以示例来看一下。
第1天新得到消息的人数为1,即get[1] = 1。
第2天新得到消息的人数为0(因为需要两天后,才具备宣传消息的能力),即get[2] = 0。
第3天新得到消息的人数为get[3] = get[3-2] = get[1] = 1。
第4天新得到消息的人数为get[4] = get[4-2]+get[4-3] = get[2] +get[1] = 1.(因为第一天新得到宣传消息的人还没有忘记,所以仍可以宣传消息。这里就要注意了。之前的人忘记消息以后就不能传播了。)
所以:当前新具备得到消息的人数为:
for(int k = i-forgrt+1; k <= i-delay; k++) {
get[i] += get[k]
}
所以:第5天新得到消息的人数为 :get[5] = get[5-2] + get[5-3] = get[3]+get[2] = 1.(因为第一天新得到消息的人,到第五天已经不具备传播消息的能力了,而第4天新得到消息的人,要到第六天才能具备传播消息的能力。)
再来看我们之前的公式:当天人数 = 前一天人数-(第i天忘记的人数)+ 新得到消息的人数。新的到消息的人数我们已经知道了,那么第i天忘记的人数怎么求呢,其实第i天忘记的人数就是get[i-forget]。于是此题得解。
代码:
class Solution {
public int peopleAwareOfSecret(int n, int delay, int forget) {
long init = 0;
long[] get = new long[n+1];
long all = 0;
init = 0;
get[1] = 1;
all = 1;
for(int i = 2; i<=n; i++) {
if(i-forget >= 1) {
all = all+1000000007;
init = (all - get[i-forget])%1000000007;
// System.out.println("init"+i+":"+init[i]);
} else {
init = all;
// System.out.println("init"+i+":"+init[i]);
}
for(int k = i-forget+1;k<=(i-delay);k++) {
if(k >= 1) {
get[i] +=get[k];
get[i] %= 1000000007;
// System.out.println("get"+i+":"+get[i]);
}
}
all = (init + get[i]) % 1000000007;
// System.out.println(i+":"+all[i]);
}
return (int)(all % 1000000007);
}
}
边栏推荐
- asp. Net pop-up layer instance
- Rasa 3. X learning series -rasa 3.2.1 new release
- Comparison between webgl and webgpu [3] - vertex buffer
- Switching power supply buck circuit CCM and DCM working mode
- Fiddler Everywhere 3.2.1 Crack
- 【原创】程序员团队管理的核心是什么?
- 4 points tell you the advantages of the combination of real-time chat and chat robots
- 698. Divided into k equal subsets ●●
- C# 反射与Type
- Naoqi robot summary 26
猜你喜欢
4 points tell you the advantages of the combination of real-time chat and chat robots
开源crm客户关系统管理系统源码,免费分享
98. 验证二叉搜索树 ●●
Neural structured learning - Part 3: training with synthesized graphs
Redis高可用——主从复制、哨兵模式、集群
【LeetCode】5. Valid Palindrome·有效回文
成为程序员的你,后悔了吗?
98. Verify the binary search tree ●●
Rasa 3. X learning series -rasa 3.2.1 new release
el-cascader的使用以及报错解决
随机推荐
Go language implementation principle -- lock implementation principle
yate.conf
Dynamic memory management (malloc/calloc/realloc)
Différence entre hors bande et en bande
Scala concurrent programming (II) akka
Initial experience | purchase and activate typora software
SpreadJS 15.1 CN 与 SpreadJS 15.1 EN
Common static methods of math class
VS2010 writes DLL and unit test of dynamic link library, and transfers the correctness of DLL test
TVS管 与 稳压二极管参数对比
TVS管和ESD管的技術指標和選型指南-嘉立創推薦
同事悄悄告诉我,飞书通知还能这样玩
asp. Net pop-up layer instance
2022.6.20-6.26 AI行业周刊(第103期):新的小生命
Development specification: interface unified return value format [resend]
【LeetCode】5. Valid Palindrome·有效回文
CIS基准测试工具kube-bench使用
orgchart. JS organization chart, presenting structural data in an elegant way
yate. conf
YML configuration, binding and injection, verification, unit of bean