C++ Solution, O(n) Time, O(1) Space, Simple DP


  • 0

    A(absence), L(last continuous late )
    A-1, L-0 -> L0
    A-1, L-1 -> L1
    A-1, L-2 -> L2
    A-0, L-0 -> l0
    A-0, L-1 -> l1
    A-0, L-2 -> l2

    dp[i] -> dp[i + 1]
    Just use A/L/P to test each state.
    You can find the state transfer formulation in the following code.

    class Int used to handle int overflow.

    class Solution {
        
        int NUM = 1000000007;
        class Int {
        public:
            Int(int val) : val_(val) {}
            operator int() {return val_;}
            Int operator+(const Int& lhs) {
                return Int((val_ + lhs.val_) % 1000000007);
            }
            int val_;
        };
        
    public:
        int checkRecord(int n) {
            IntL0 = 1, L1 = 0, L2 = 0,  l0 = 1, l1 = 1, l2 = 0;
            for (int i = 1; i < n; i++) {
                Int L0_ = L0 + L1 + L2 + l0 + l1 + l2;
                Int L1_ = L0;
                Int L2_ = L1;
                Int l0_ = l0 + l1 + l2;
                Int l1_ = l0;
                Int l2_ = l1;
                
                L0 = L0_, L1 = L1_, L2 = L2_, l0 = l0_, l1 = l1_, l2 = l2_;
            }
            return L0 + L1 + L2 + l0 + l1 + l2;
        }
    };
    

    This version is a little bit faster...... UM..

    int checkRecord(int n) {
            int l0 = 1, l1 = 1, l2 = 0, L0 = 1, L1 = 0, L2 = 0;
            for (int i = 1; i < n; i++) {
                int L0_ = (((L0 + L1) % NUM + L2) % NUM + ((l0 + l1) % NUM + l2) % NUM) % NUM;
                int L1_ = L0;
                int L2_ = L1;
                int l0_ = ((l0 + l1) % NUM + l2) % NUM;
                int l1_ = l0;
                int l2_ = l1;
                
                L0 = L0_, L1 = L1_, L2 = L2_, l0 = l0_, l1 = l1_, l2 = l2_;
            }
            //cout << L0 << endl << L1 << endl << L2 << endl << l0 << endl << l1 << endl << l2 << endl;
            return (((L0 + L1) % NUM + L2) % NUM + ((l0 + l1) % NUM + l2) % NUM) % NUM;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.