Use Queue to save space


  • 0
    M

    Most of solutions straight use an array of size n to store the string, actually we can remove the used char, which makes queue an ideal data structure to save space:

    class Solution {
    public:
        int magicalString(int n) {
            if(n==0)
                return 0;
            if(n<=3)
                return 1;
            queue<char> Q;
            int count=3,count1=1;
            Q.push('2');
            char p,q;
            while(count<n){
                p=Q.back();
                q=Q.front();
                Q.pop();
                if(p=='1')
                    p='2';
                else
                    p='1';
                for(int k=q-'0';k>0;k--){
                    count++;
                    if(p=='1')
                        count1++;
                    if(count>=n)
                        return count1;
                    Q.push(p);
                }
            }
            return count1;
        }
    };
    

Log in to reply
 

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