What is the main approach to solve Number of People Aware of a Secret?

Use state transition dynamic programming to track the number of people aware each day, considering delay before sharing and forgetting after a set period.

How do delay and forget affect the simulation?

Delay determines when a person starts sharing, while forget determines when they stop, directly impacting daily state updates in DP.

Can space be optimized in this DP solution?

Yes, a rolling array can reduce space from O(n * forget) to O(forget) by only keeping the previous day's states.

Why use modulo 10^9 + 7?

The number of people aware can grow exponentially, so modulo prevents integer overflow and keeps calculations within bounds.

What is a common off-by-one mistake in this problem?

Misaligning delay and forget indices in the DP table, leading to counting people too early or after they forget.

#2327

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

知道秘密的人数

在第 1 天，有一个人发现了一个秘密。给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天给一个新的人分享秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会忘记这个秘密。一个人不能在忘记秘密那一天及之后的日子里分享秘密。…

动态规划队列模拟

题目描述

在第 1 天，有一个人发现了一个秘密。

给你一个整数 delay ，表示每个人会在发现秘密后的 delay 天之后，每天给一个新的人分享秘密。同时给你一个整数 forget ，表示每个人在发现秘密 forget 天之后会忘记这个秘密。一个人不能在忘记秘密那一天及之后的日子里分享秘密。

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 10⁹ + 7 取余后返回。

示例 1：

输入：n = 6, delay = 2, forget = 4
输出：5
解释：
第 1 天：假设第一个人叫 A 。（一个人知道秘密）
第 2 天：A 是唯一一个知道秘密的人。（一个人知道秘密）
第 3 天：A 把秘密分享给 B 。（两个人知道秘密）
第 4 天：A 把秘密分享给一个新的人 C 。（三个人知道秘密）
第 5 天：A 忘记了秘密，B 把秘密分享给一个新的人 D 。（三个人知道秘密）
第 6 天：B 把秘密分享给 E，C 把秘密分享给 F 。（五个人知道秘密）

示例 2：

输入：n = 4, delay = 1, forget = 3
输出：6
解释：
第 1 天：第一个知道秘密的人为 A 。（一个人知道秘密）
第 2 天：A 把秘密分享给 B 。（两个人知道秘密）
第 3 天：A 和 B 把秘密分享给 2 个新的人 C 和 D 。（四个人知道秘密）
第 4 天：A 忘记了秘密，B、C、D 分别分享给 3 个新的人。（六个人知道秘密）

提示：

2 <= n <= 1000
1 <= delay < forget <= n

lightbulb

解题思路

方法一：差分数组

我们用一个差分数组 $d[i]$ 来记录第 $i$ 天知道秘密的人数变化情况，用一个数组 $cnt[i]$ 来记录第 $i$ 天新得知秘密的人数。

那么，对于第 $i$ 天新得知秘密的 $cnt[i]$ 个人来说，他们会在 $[i+\text{delay}, i+\text{forget})$ 这段时间内每天都能分享给另外 $cnt[i]$ 个人。

答案为 $\sum_{i=1}^{n} d[i]$ 。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为题目给定的整数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        m = (n << 1) + 10
        d = [0] * m
        cnt = [0] * m
        cnt[1] = 1
        for i in range(1, n + 1):
            if cnt[i]:
                d[i] += cnt[i]
                d[i + forget] -= cnt[i]
                nxt = i + delay
                while nxt < i + forget:
                    cnt[nxt] += cnt[i]
                    nxt += 1
        mod = 10**9 + 7
        return sum(d[: n + 1]) % mod

speed

复杂度分析

指标	值
时间	complexity is O(n * forget) because we iterate over each day and track up to 'forget' days of states. Space complexity is O(n * forget) for the DP table but can be optimized to O(forget) using rolling arrays.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Emphasize your DP state and why each state represents people aware for exact days.
question_mark
Explain how the delay and forget constraints affect the sharing process.
question_mark
Discuss rolling array optimization to reduce space complexity.

warning

常见陷阱

外企场景

error
Forgetting to exclude people from sharing on the day they forget.
error
Incorrectly summing states, counting those who already forgot.
error
Confusing delay and forget days, leading to off-by-one errors in DP indices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Calculate the total number of people aware if multiple people discover the secret on different days.
arrow_right_alt
Find the earliest day when the number of people aware reaches a target value.
arrow_right_alt
Modify the problem to allow sharing with multiple people per day instead of just one.

help

常见问题

外企场景

继续练习

#2380 二进制字符串重新安排顺序需要的时间 #2407 最长递增子序列 II #2073 买票需要的时间