Thursday, October 19, 2017

481. Magical String

https://leetcode.com/problems/magical-string/description/
    int magicalString(int n) {
        if(n == 0) return 0;
        string ms = "122";
        int res = 1;
        for(int i = 2; i<n; i++) {
            if(ms.size()<n)
                ms += string(ms[i]-'0', ms.back()=='1'? '2':'1');
            res += (ms[i] == '1');
        }
        return res;
    }
or,
    int magicalString(int n) {
        if(n == 0) return 0;
        string ms = "122";
        int res = 1;
        for(int i = 2; i<n; i++) {
            if(ms.size()<n)
            if(ms[i] == '1') {
                if(ms.back() == '1') ms += "2";
                else ms += "1";
            }
            else {
                if(ms.back() == '1') ms += "22";
                else ms += "11";
            }
            res += (ms[i] == '1');
        }
        return res;
    }

No comments:

Post a Comment