当前位置:网站首页>20220703 week race: number of people who know the secret - dynamic rules (problem solution)
20220703 week race: number of people who know the secret - dynamic rules (problem solution)
2022-07-05 23:41:00 【A Xuan is about to graduate~】
Topic link : Power button https://leetcode.cn/problems/number-of-people-aware-of-a-secret/
Ideas :
At first, the idea was to have rabbits . The current number of people who know the secret = The number of people who knew the secret the day before +(i-delay) The number of people -(i-forget) The number of people . Later, in the process of derivation, it was found that ,(i-delay) People who , The first i The sky may not be still , It may have been forgotten .(i-forget) The number of people is also not allowed , Maybe (i-forget ——i) Have forgotten .
Here's the thing : The formula should be : Number of people in the day = Number of people in the previous day -( The first i Days forget the number )+ Number of new people . that The first i Days forget the number and Number of new people How should I ask . In fact, just add an array get The array represents the number of new messages .
Let's take an example .
The first 1 The number of people receiving news from Tianxin is 1, namely get[1] = 1.
The first 2 The number of people receiving news from Tianxin is 0( Because it will take two days , To have the ability to publicize information ), namely get[2] = 0.
The first 3 The number of people receiving news from Tianxin is get[3] = get[3-2] = get[1] = 1.
The first 4 The number of people receiving news from Tianxin is get[4] = get[4-2]+get[4-3] = get[2] +get[1] = 1.( Because the people who got the propaganda news on the first day haven't forgotten , So you can still promote the news . We need to pay attention here . People in the past can't spread the news after they forget it .)
therefore : At present, the number of new people with information is :
for(int k = i-forgrt+1; k <= i-delay; k++) {
get[i] += get[k]
}
therefore : The first 5 The number of people receiving news from Tianxin is :get[5] = get[5-2] + get[5-3] = get[3]+get[2] = 1.( Because the first day of new information people , By the fifth day, he had no ability to spread news , And the first 4 Tianxin gets the news , It takes until the sixth day to have the ability to spread information .)
Let's look at our previous formula : Number of people in the day = Number of people in the previous day -( The first i Days forget the number )+ Number of new people . We already know the number of new arrivals , So the first i How can I ask for the number of people I forget , Actually, the first one is i The number of people forgotten by heaven is get[i-forget]. So this problem has to be solved .
Code :
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);
}
}
边栏推荐
- Rethinking about MySQL query optimization
- The PNG image is normal when LabVIEW is opened, and the full black image is obtained when Photoshop is opened
- 20.移植Freetype字体库
- 2022.6.20-6.26 AI industry weekly (issue 103): new little life
- How to improve eloquence
- Object detection based on impulse neural network
- Redis高可用——主从复制、哨兵模式、集群
- In C#, why can't I modify the member of a value type instance in a foreach loop?
- 【LeetCode】5. Valid Palindrome·有效回文
- 21.PWM应用编程
猜你喜欢
开源crm客户关系统管理系统源码,免费分享
Spire.PDF for NET 8.7.2
5. Logistic regression
orgchart. JS organization chart, presenting structural data in an elegant way
Brushless drive design -- on MOS drive circuit
Object detection based on impulse neural network
Spécifications techniques et lignes directrices pour la sélection des tubes TVS et ESD - Recommandation de jialichuang
Practice of concurrent search
Spire. PDF for NET 8.7.2
零犀科技携手集智俱乐部:“因果派”论坛成功举办,“因果革命”带来下一代可信AI
随机推荐
Part III Verilog enterprise real topic of "Niuke brush Verilog"
How to enable relationship view in phpMyAdmin - how to enable relationship view in phpMyAdmin
Scala concurrent programming (II) akka
Redis高可用——主从复制、哨兵模式、集群
【SQL】各主流数据库sql拓展语言(T-SQL 、 PL/SQL、PL/PGSQL)
11gR2 Database Services for &quot;Policy&quot; and &quot;Administrator&quot; Managed Databases (文件 I
How to improve eloquence
STM32__06—单通道ADC
Creative mode 1 - single case mode
(4) UART application design and simulation verification 2 - RX module design (stateless machine)
开源crm客户关系统管理系统源码,免费分享
(4)UART应用设计及仿真验证2 —— TX模块设计(无状态机)
Bao Yan notebook IV software engineering and calculation volume II (Chapter 8-12)
asp. Net pop-up layer instance
Spécifications techniques et lignes directrices pour la sélection des tubes TVS et ESD - Recommandation de jialichuang
White hat talks about web security after reading 2
YML configuration, binding and injection, verification, unit of bean
【原创】程序员团队管理的核心是什么?
Neural structured learning - Part 2: training with natural graphs
golang代码检查工具