Leetcode 2327. 知道秘密的人数（思路很棒）

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

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

给你一个整数 n ，请你返回在第 n 天结束时，知道秘密的人数。由于答案可能会很大，请你将结果对 109 + 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 。（五个人知道秘密）

1
2
3
4
5
6
7
8
9
10

注意结果要取模

684
18
496

输出：
653668527

1
2
3
4
5
6
7

---

【思路】：
这题思路很妙。

这是我自己想出来的一个办法：用一个数组解决。

大致情况是这样，以示例1为例：
第一天有一个人知道秘密，arr[1] = 1。我们用arr[1]来记录第一天知道秘密的人数。

第二天，arr[1]向前移动至arr[2]，表示时间过了一天：

知道秘密人数的情况如图：（忽略arr[0]）
第一天：[ 0, 1, 0, 0, 0, 0 ]
第二天：[ 0, 0, 1, 0, 0, 0 ]
1
2
3

---

关键的来了，到了第三天，数组元素继续前移：

此时我们可以看到，已经有一个人到了arr[delay + 1]的位置，
他将会告诉一个新人秘密，所以arr[1]也增加为1
第三天：[0, 1, 0, 1, 0, 0 ]
1
2
3

---

到了第四天，接着看：

之前没忘记秘密的那个人又会告诉一个新人秘密，
因此arr[1]接着增加，而之前第一天知道秘密的人，已经到了第二天。
第四天：[ 0, 1, 1, 0, 1, 0 ]
1
2
3

---

第五天，忘记的时间到了：

最开始知道秘密的那个人已经忘记
此时又有一个人到了arr[delay + 1]，所以会将秘密泄露出去
第五天：[0, 1, 1, 1, 0, 0 ]
1
2
3

---

第六天：

此时会有两个人泄露秘密
因为他们都处于 >= delay + 1的天数。
因此这一天arr[1] = 2.会有两个新人知道秘密
第六天：[ 0, 2, 1, 1, 1, 0 ]
1
2
3
4

因此，我们只需要一个空间在forget +2级别的数组。
根据题目forget <= 1000得知，数组空间最大也就1002不会很大。

---

【代码】：

/**
 * @param {number} n
 * @param {number} delay
 * @param {number} forget
 * @return {number}
 */
var peopleAwareOfSecret = function(n, delay, forget) {
    //数组从1开始。
    var arr = new Array(forget + 2).fill(0);
    var mod = 1000000007;
    //关注delay下标和forget下标
    
    //n天
    for(let i = 1;i <= n;i++){
        if(i == 1){
            //第一天不需要移动
            arr[1] = 1;//1这个下标也要关注，代表每天有多少人最新知道了秘密
        }else{
            //数组所有元素往后移一个单位，模拟新的一天
            for(let j = forget + 1;j >= 2;j--){
                arr[j] = arr[j - 1]
            }
            //这一天清零。forget + 1天的所有人忘记。注意不是forget天
            arr[forget + 1] = 0;        

            //大于等于delay + 1这一天且小于forget + 1天的所有人，
            //都得把秘密告诉一个新人   ；注意题目。不是delay天
            let sum =0 ;
            for(let j = delay + 1;j < forget + 1;j++){
                sum = (sum % mod + arr[j] %mod) %mod;
            }    
            arr[1] = sum;
        } 
        //console.log(arr);
    }
    //到了第n天，看数组上还有多少人知道秘密即可
    var cnt = 0;
    for(let i = 1;i <= forget;i++){
        cnt = (cnt %mod + arr[i] % mod)%mod
    }
    return cnt % mod;

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43