Leetcode-6109: number of people who know secrets

subject

Topic linking
In the 1 God , A man discovered a secret .

Give you an integer delay , It means that everyone will find the secret delay After heaven , Every day To a new person Share Secret . I'll give you an integer at the same time forget , It means that everyone is discovering secrets forget Days later forget The secret . A person You can't Share secrets on and after the day you forget them .

Give you an integer n , Please go back to n At the end of the day , Number of people who know the secret . Because the answer could be big , Please put the result to 10^9 + 7 Remainder After the return .

Example 1：

 Input ：n = 6, delay = 2, forget = 4
 Output ：5
 explain ：
 The first  1  God ： Suppose the first person is  A .（ One knows the secret ）
 The first  2  God ：A  Is the only one who knows the secret .（ One knows the secret ）
 The first  3  God ：A  Share the secret with  B .（ Two people know the secret ）
 The first  4  God ：A  Share the secret with a new person  C .（ Three people know the secret ）
 The first  5  God ：A  Forget the secret ,B  Share the secret with a new person  D .（ Three people know the secret ）
 The first  6  God ：B  Share the secret with  E,C  Share the secret with  F .（ Five people know the secret ）

Example 2：

 Input ：n = 4, delay = 1, forget = 3
 Output ：6
 explain ：
 The first  1  God ： The first person who knows the secret  A .（ One knows the secret ）
 The first  2  God ：A  Share the secret with  B .（ Two people know the secret ）
 The first  3  God ：A  and  B  Share the secret with  2  A new person  C  and  D .（ Four people know the secret ）
 The first  4  God ：A  Forget the secret ,B、C、D  Share with  3  A new person .（ Six people know the secret ）

Problem solving

Method 1 ： simulation （ Overtime ）

Set up two queues to simulate

• Delay queue ： Already know the secret , But I can't share yet
• Share queue ： Already know the password , And can share

All stored in the queue are expiration dates , When the element in the delay queue expires , Will pop up and join the sharing queue , The element in the sharing queue expires , It will pop up , Description forgot .

The last person who knows the secret , Is the total number of delay queues and sharing queues

shortcoming ： But for this problem , Don't care who knows the secret , The topic scene is simple , This method is not optimal , Dynamic planning will be more appropriate .

class Solution {
    
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
    
        queue<int> q_delay;
        queue<int> q_shareing;
        q_delay.push(1+delay);
        for(int i=1;i<=n;i++){
    
            while(!q_delay.empty()&&i>=q_delay.front()){
    
                q_shareing.push(q_delay.front()+forget-delay);
                q_delay.pop();
            }
            while(!q_shareing.empty()&&i>=q_shareing.front()){
    
                q_shareing.pop();
            }
            for(int j=0;j<q_shareing.size();j++){
    
                q_delay.push(i+delay);
            }
        }
        return q_delay.size()+q_shareing.size();
    }
};

Method 2 ： Dynamic programming - Brush table method

Reference link

According to the meaning , There are two kinds of people ：

• A class ： Know the secret , But I can't share yet ;
• B class ： Know the secret , And can share .

dp[i] It means the first one i+1 God , Yes dp[i] individual B Humanoid

Pay special attention to the details of the index , For example, the equal sign .
about if(i+delay>=n), such as n=3,delay=2
The first day i=0, and i+delay=2, At this point, for the n For heaven's sake , It can't be counted A Human like because the next day became B Humanoid , So add an equal sign

in addition dp[0]=1, It does not accord with dp The definition of , Just to initialize , Convenient for subsequent calculation .

class Solution {
    
public:
    const int MOD=1e9+7;
    int peopleAwareOfSecret(int n, int delay, int forget) {
    
        int cnt_a=0;
        vector<int> dp(n);// Record No. i Days of B Humanoid 
        dp[0]=1;
        for(int i=0;i<n;i++){
    
            if(i+delay>=n) cnt_a=(cnt_a+dp[i])%MOD;// The first n Days of A Humanoid 
            for(int j=i+delay;j<min(n,i+forget);j++){
    
                dp[j]=(dp[j]+dp[i])%MOD;
            }
        }
        return (cnt_a+dp[n-1])%MOD;// People who know secrets =A Humanoid +B Humanoid 
    }
};