当前位置:网站首页>leetcode6109. 知道秘密的人数(中等,周赛)
leetcode6109. 知道秘密的人数(中等,周赛)
2022-07-06 06:55:00 【重you小垃】
思路:dp + 前缀和
具体思路:
dp[i]表示第i天新增的人数,而不是第i天知道秘密的人数
dp[i]表示第i天知道秘密的人数,逻辑有问题,存在重复…
状态转移方程:
dp[i] = sum(dp[i-forget+1]…dp[i-delay])
ans:sum(dp[n-forget+1]…dp[n])
class Solution {
public:
const int mod = 1e9 + 7;
int peopleAwareOfSecret(int n, int delay, int forget) {
vector<long long> dp(n + 1), sum(n + 1);
dp[1] = 1;
sum[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i]=(sum[max(i - delay, 0)]) - sum[max(i - forget, 0)];
dp[i] %= mod;
sum[i] = (dp[i] + sum[i - 1]) % mod;;
}
return ((sum[n] - sum[max(0, n - forget)]) % mod + mod) % mod;;
}
};
代码技巧1:
i - delay >= 0 ? sum[i - delay] : 0 可以写成:sum[max(i - delay, 0)]
代码技巧2:
防止ans:(sum[n] - sum[max(0, n - forget)]) % mod 出现负数,再 ( + mod) % mod;
边栏推荐
- Attributeerror successfully resolved: can only use cat accessor with a ‘category‘ dtype
- P5706 [deep foundation 2. Example 8] redistributing fat house water -- February 13, 2022
- SQL Server manager studio(SSMS)安装教程
- ROS2安装及基础知识介绍
- How to find a medical software testing institution? First flight software evaluation is an expert
- 【Hot100】739. 每日温度
- SQL Server Manager studio (SSMS) installation tutorial
- On the first day of clock in, click to open a surprise, and the switch statement is explained in detail
- Basic commands of MySQL
- After sharing the clone remote project, NPM install reports an error - CB () never called! This is an error with npm itself.
猜你喜欢
L'Ia dans les nuages rend la recherche géoscientifique plus facile
Suspended else
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
AttributeError: Can‘t get attribute ‘SPPF‘ on <module ‘models.common‘ from ‘/home/yolov5/models/comm
Market segmentation of supermarket customers based on purchase behavior data (RFM model)
Reflex WMS medium level series 3: display shipped replaceable groups
[ 英语 ] 语法重塑 之 英语学习的核心框架 —— 英语兔学习笔记(1)
Biomedical English contract translation, characteristics of Vocabulary Translation
On the first day of clock in, click to open a surprise, and the switch statement is explained in detail
Fast target recognition based on pytorch and fast RCNN
随机推荐
Call, apply, bind rewrite, easy to understand with comments
[ 英语 ] 语法重塑 之 英语学习的核心框架 —— 英语兔学习笔记(1)
Pymongo gets a list of data
接口自动化测试实践指导(上):接口自动化需要做哪些准备工作
中青看点阅读新闻
《从0到1:CTFer成长之路》书籍配套题目(周更)
雲上有AI,讓地球科學研究更省力
【Hot100】739. 每日溫度
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
BUU的MISC(不定时更新)
前缀和数组系列
librosa音频处理教程
kubernetes集群搭建Zabbix监控平台
SQL Server manager studio(SSMS)安装教程
详解SQL中Groupings Sets 语句的功能和底层实现逻辑
指尖上的 NFT|在 G2 上评价 Ambire,有机会获得限量版收藏品
Fast target recognition based on pytorch and fast RCNN
【软件测试进阶第1步】自动化测试基础知识
Oracle数据库11gr2使用tde透明数据加密报错ora28353,如果运行关闭wallet会报错ora28365,运行打开wallet就报错ora28353无法打开wallet
GET 和 POST 请求类型的区别