知道秘密的人数

2327. 知道秘密的人数

在第 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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int peopleAwareOfSecret(int n, int delay, int forget) { } };

golang 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2023-09-14 14:33:47

// 刷表法
func peopleAwareOfSecret(n, delay, forget int) int {
	const mod int = 1e9 + 7
	f := make([]int, n)
	f[0] = 1
	cntB := 0
	for i, v := range f {
		if i+delay >= n {
			cntB = (cntB + v) % mod
		}
		for j := i + delay; j < i+forget && j < n; j++ {
			f[j] = (f[j] + v) % mod
		}
	}
	return (f[n-1] + cntB) % mod
}

// 刷表法（差分）
func peopleAwareOfSecret2(n, delay, forget int) int {
	const mod int = 1e9 + 7
	diff := make([]int, n)
	diff[0] = 1 // f[0] = 1，相当于 diff[0] = 1, diff[1] = -1
	diff[1] = mod - 1
	f, cntB := 0, 0
	for i, d := range diff {
		f = (f + d) % mod
		if i+delay >= n {
			cntB = (cntB + f) % mod
		} else {
			diff[i+delay] = (diff[i+delay] + f) % mod
			if i+forget < n {
				diff[i+forget] = (diff[i+forget] - f + mod) % mod // +mod 是为了保证结果不会出现负数
			}
		}
	}
	return (f + cntB) % mod
}

// 填表法
func peopleAwareOfSecret3(n, delay, forget int) int {
	const mod int = 1e9 + 7
	sum := make([]int, n+1)
	sum[1] = 1
	for i := 2; i <= n; i++ {
		f := (sum[max(i-delay, 0)] - sum[max(i-forget, 0)]) % mod
		sum[i] = (sum[i-1] + f) % mod
	}
	return ((sum[n]-sum[max(n-forget, 0)])%mod + mod) % mod // 防止结果为负数
}

func max(a, b int) int { if b > a { return b }; return a }

cpp 解法, 执行用时: 12 ms, 内存消耗: 6.3 MB, 提交时间: 2023-09-14 14:31:31

class Solution {
    const int MOD = 1e9 + 7;
public:
    // 刷表法
    int peopleAwareOfSecret(int n, int delay, int forget) {
        int f[n]; memset(f, 0, sizeof(f));
        f[0] = 1;
        int cnt_b = 0;
        for (int i = 0; i < n; ++i) {
            if (i + delay >= n) cnt_b = (cnt_b + f[i]) % MOD;
            for (int j = i + delay; j < min(i + forget, n); ++j)
                f[j] = (f[j] + f[i]) % MOD;
        }
        return (f[n - 1] + cnt_b) % MOD;
    }
    // 刷表法(差分)
    int peopleAwareOfSecret2(int n, int delay, int forget) {
        int diff[n]; memset(diff, 0, sizeof(diff));
        diff[0] = 1; // f[0] = 1，相当于 diff[0] = 1, diff[1] = -1
        diff[1] = MOD - 1;
        int f = 0, cnt_b = 0;
        for (int i = 0; i < n; ++i) {
            f = (f + diff[i]) % MOD;
            if (i + delay >= n) cnt_b = (cnt_b + f) % MOD;
            else {
                diff[i + delay] = (diff[i + delay] + f) % MOD;
                if (i + forget < n) diff[i + forget] = (diff[i + forget] - f + MOD) % MOD; // +MOD 是为了保证结果不会出现负数
            }
        }
        return (f + cnt_b) % MOD;
    }
    // 填表法
    int peopleAwareOfSecret3(int n, int delay, int forget) {
        int sum[n + 1];
        sum[0] = 0, sum[1] = 1;
        for (int i = 2; i <= n; ++i) {
            int f = (sum[max(i - delay, 0)] - sum[max(i - forget, 0)]) % MOD;
            sum[i] = (sum[i - 1] + f) % MOD;
        }
        return ((sum[n] - sum[max(n - forget, 0)]) % MOD + MOD) % MOD; // 防止结果为负数
    }
};

java 解法, 执行用时: 24 ms, 内存消耗: 38.3 MB, 提交时间: 2023-09-14 14:29:40

class Solution {
    int n, delay, forget;
    int MOD = (int) 1e9 + 7;
    int[] memo;

    public int peopleAwareOfSecret(int _n, int _delay, int _forget) {
        /*
        Java 记忆化搜索:
        我们记dfs(i)为第i天发现的秘密的人包含自己在内一共可以使得后面多少人知道秘密
        i从i+delay天起,到i+forget-1天都是可以将秘密散播出去的
        也就是[min(i+delay,n),min(i+forget-1,n)]=[a,b]这个时间段是i的传播阶段
        此时知道秘密的人数有1+∑dfs(a,b)
        同时应该注意知道了秘密的人会忘记秘密,因此也会有一个期限
        这里由于子问题的出现可以使用记忆化减少搜索次数
         */
        n = _n;
        delay = _delay;
        forget = _forget;
        memo = new int[n + 1];
        return dfs(1);
    }

    private int dfs(int i) {
        // 在第n天之后才能传播,说明只有自己知道
        if (i + delay > n) return 1;
        // 已经搜索过直接返回
        if (memo[i] != 0) return memo[i];
        // i传播的范围为[min(i+delay,n),min(i+forget-1,n)]=[a,b]
        int a = i + delay, b = Math.min(i + forget - 1, n);
        long res = i + forget <= n ? 0 : 1;    // 自身到[i+forget]就忘记了,在n天内忘记了取0,反之取1
        // 合法的传播范围为[a,b]
        for (int j = a; j <= b; j++) {
            int t = dfs(j);
            memo[j] = t;    // 标记
            res = (res + t) % MOD;
        }
        return (int) res;
    }
}

java 解法, 执行用时: 9 ms, 内存消耗: 38.4 MB, 提交时间: 2023-09-14 14:29:17

class Solution {
    static final int MOD = (int) 1e9 + 7;

    // 刷表法
    public int peopleAwareOfSecret(int n, int delay, int forget) {
        var f = new int[n];
        f[0] = 1;
        var cntB = 0;
        for (var i = 0; i < n; ++i) {
            if (i + delay >= n) cntB = (cntB + f[i]) % MOD;
            for (int j = i + delay; j < Math.min(i + forget, n); ++j)
                f[j] = (f[j] + f[i]) % MOD;
        }
        return (f[n - 1] + cntB) % MOD;
    }

    // 刷表法（差分）
    public int peopleAwareOfSecret2(int n, int delay, int forget) {
        var diff = new int[n];
        diff[0] = 1; // f[0] = 1，相当于 diff[0] = 1, diff[1] = -1
        diff[1] = MOD - 1;
        int f = 0, cntB = 0;
        for (var i = 0; i < n; ++i) {
            f = (f + diff[i]) % MOD;
            if (i + delay >= n) cntB = (cntB + f) % MOD;
            else {
                diff[i + delay] = (diff[i + delay] + f) % MOD;
                if (i + forget < n) diff[i + forget] = (diff[i + forget] - f + MOD) % MOD; // +MOD 是为了保证结果不会出现负数
            }
        }
        return (f + cntB) % MOD;
    }
    
    // 填表法
    public int peopleAwareOfSecret3(int n, int delay, int forget) {
        var sum = new int[n + 1];
        sum[1] = 1;
        for (var i = 2; i <= n; i++) {
            var f = (sum[Math.max(i - delay, 0)] - sum[Math.max(i - forget, 0)]) % MOD;
            sum[i] = (sum[i - 1] + f) % MOD;
        }
        return ((sum[n] - sum[Math.max(n - forget, 0)]) % MOD + MOD) % MOD; // 防止结果为负数
    }


}

python3 解法, 执行用时: 56 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-14 14:27:07

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        MOD = 10 ** 9 + 7
        diff = [0] * n
        diff[0] = 1  # f[0] = 1，相当于 diff[0] = 1, diff[1] = -1
        diff[1] = -1
        f = cnt_b = 0
        for i, d in enumerate(diff):
            f = (f + d) % MOD
            if i + delay >= n:
                cnt_b += f
            else:
                diff[i + delay] += f
                if i + forget < n:
                    diff[i + forget] -= f
        return (f + cnt_b) % MOD

    # 填表法，（用其它状态计算当前状态）
    def peopleAwareOfSecret2(self, n: int, delay: int, forget: int) -> int:
        MOD = 10 ** 9 + 7
        sum = [0] * (n + 1)
        sum[1] = 1
        for i in range(2, n + 1):
            f = sum[max(i - delay, 0)] - sum[max(i - forget, 0)]
            sum[i] = (sum[i - 1] + f) % MOD
        return (sum[n] - sum[max(n - forget, 0)]) % MOD

python3 解法, 执行用时: 304 ms, 内存消耗: 16 MB, 提交时间: 2023-09-14 14:24:49

class Solution:
    # 刷表法，用当前状态更新其它状态
    # A 类：可以产生利息的钱；
    # B 类：尚不能产生利息的钱；
    # C 类：停止产生利息的钱（不参与计算）
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        MOD = 10 ** 9 + 7
        f = [0] * n  # f[i] 表示第i天知道秘密的人数
        f[0] = 1
        cnt_b = 0  # 知道但尚不能传播秘密的人数
        for i, v in enumerate(f):
            if i + delay >= n:
                cnt_b += v
            for j in range(i + delay, min(i + forget, n)):
                f[j] = (f[j] + v) % MOD
        return (f[-1] + cnt_b) % MOD

上一题

下一题

详情