C++ using queue (3ms)


  • 0
    S
    int magicalString(int n) {
        if (n==0)
            return 0;
        if (n<4)
            return 1;
        
        // Let's initialize
        // digit stream : 1 22
        // counts       : 1 2
        // We'll keep the 'unused' part of the digit stream in a queue
        // in this case, since the first 2 digits are used in the 'counts' stream, 
        // we initialize the queue with 2, the third digit
        queue<int> s;
        s.push(2);
        // cnt is the number of digits in the stream so far
        int cnt = 3;
        // res is the number of ones so far
        int res = 1;
        
        // last digit used
        int lastOne = 2;
        while (cnt<n){
            // m is the number of time swe used repeat the next digit
            int m = s.front();
            s.pop();
            
            // swith from 1 to 2 or 2 to 1
            if (lastOne == 2)
                lastOne = 1;
            else
                lastOne = 2;
            
            // if we are going to add 1 digit
            if (m == 1){
                s.push(lastOne); // add to the queue
                cnt++;
                if (lastOne==1)
                    res++;
            }else{ 
            // if we are going to add 2 digits
                s.push(lastOne); // add to the queue
                s.push(lastOne); // twice
                cnt = cnt + 2;
                if (lastOne==1)
                    res = res+2;
            }
        }
        // if we pass n by 1, if we added 2 after n-1...
        if (cnt == n+1 && lastOne == 1)
            res--;
    
        return res;   
    }

Log in to reply
 

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