LeetCode 481 - Magical String

http://bookshadow.com/weblog/2017/01/08/leetcode-magical-string/

A magical string S consists of only '1' and '2' and obeys the following rules:

The string S is magical because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string S itself.

The first few elements of string S is the following: S = "1221121221221121122……"

If we group the consecutive '1's and '2's in S, it will be:

1 22 11 2 1 22 1 22 11 2 11 22 ......

and the occurrences of '1's or '2's in each group are:

1 2 2 1 1 2 1 2 2 1 2 2 ......

You can see that the occurrence sequence above is the S itself.

Given an integer N as input, return the number of '1's in the first N number in the magical string S.

Note: N will not exceed 100,000.

Example 1:

Input: 6
Output: 3
Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.

https://discuss.leetcode.com/topic/74917/simple-java-solution-using-one-array-and-two-pointers

1. Create an int array a and initialize the first 3 elements with 1, 2, 2.
2. Create two pointers head and tail. head points to the number which will be used to generate new numbers. tail points to the next empty position to put the new number. Then keep generating new numbers until tail >= n.
3. Need to create the array 1 element more than n to avoid overflow because the last round head might points to a number 2.
4. A trick to flip number back and forth between 1 and 2: num = num ^ 3

    public int magicalString(int n) {
        if (n <= 0) return 0;
        if (n <= 3) return 1;
        
        int[] a = new int[n + 1];
        a[0] = 1; a[1] = 2; a[2] = 2;
        int head = 2, tail = 3, num = 1, result = 1;
        
        while (tail < n) {
            for (int i = 0; i < a[head]; i++) {
                a[tail] = num;
                if (num == 1 && tail < n) result++;
                tail++;
            }
            num = num ^ 3;
            head++;
        }
        
        return result;
    }

字符串模拟
令魔法字符串ms = '122'，维护指针p，初始令p = 2

若ms[p] == '1' 则向ms追加1个与ms末尾元素不同的字符

否则，向ms追加2个与ms末尾元素不同的字符

def magicalString(self, n): """ :type n: int :rtype: int """ ms = '122' p = 2 while len(ms) < n: ms += str(3 - int(ms[-1])) * int(ms[p]) p += 1 return ms[:n].count('1')

http://www.cnblogs.com/grandyang/p/6286540.html
这道题介绍了一种神奇字符串，只由1和2组成，通过计数1组和2组的个数，又能生成相同的字符串。而让我们求前n个数字中1的个数说白了其实就是让我们按规律生成这个神奇字符串，只有生成了字符串的前n个字符，才能统计出1的个数。其实这道题的难点就是在于找到规律来生成字符串，这里我们就直接说规律了，因为博主也没有自己找到，都是看了网上大神们的解法。根据第三个数字2开始往后生成数字，此时生成两个1，然后根据第四个数字1，生成一个2，再根据第五个数字1，生成一个1，以此类推，生成的数字1或2可能通过异或3来交替生成，在生成的过程中同时统计1的个数即可

    int magicalString(int n) {
        if (n <= 0) return 0;
        if (n <= 3) return 1;
        int res = 1, head = 2, tail = 3, num = 1;
        vector<int> v{1, 2, 2};
        while (tail < n) {
            for (int i = 0; i < v[head]; ++i) {
                v.push_back(num);
                if (num == 1 && tail < n) ++res;
                ++tail;
            }
            num ^= 3;
            ++head;
        }
        return res;
    }

    int magicalString(int n) {
        string s = "122";
        int i = 2;
        while (s.size() < n) {
            s += string(s[i++] - '0', s.back() ^ 3);
        }
        return count(s.begin(), s.begin() + n, '1');
    }

X.
http://www.nowtoshare.com/en/Article/Index/20252

    public int magicalString(int n) {
        if(n==0) return 0;
        StringBuilder sb=new StringBuilder("122");
        int counts=2;
        int ret=1;
        while(sb.length()<n)
        {
            char ch=sb.charAt(counts);
            char prev=sb.charAt(sb.length()-1);
            if(ch=='1')
            {
                if(prev=='1') sb.append('2');
                else{ sb.append('1');  ret++;}
            }
            else
            {
                if(prev=='1') {sb.append("22");}
                else{
                    sb.append("11");  
                   ret= sb.length()==n+1 ? ret+1:ret+2;
 
                }
            }
            counts++;
        }
       // if(sb.length()==n+1&&sb.charAt(sb.length()-1)=='1') return ret-1;
        return ret;
    }

Find the pattern to increse the array, at the same time record the count and return.

https://www.liuchuo.net/archives/3087
直接按照这个字符串的构造方法还原这个字符串s：首先初始化s = “122”,让index指向下标为2处，开始根据index指向的字符在s后面添加字符串，如果指向的是2就添加2个，如果指向的是1就添加一个，具体添加什么字符以当前s的末尾一位的字符是1还是2为准，如果s当前最后一个字符是1就添加2，反之添加1～还原好了之后用count直接计算字符串从begin()到n长度处一共有多少个’1’字符

    int magicalString(int n) {

        string s = "122";

        int index = 2;

        while(s.length() < n) {

            int cnt = s[index] - '0';

            char c = (s.back() == '1' ? '2' : '1');

            string temp(cnt, c);

            s += temp;

            index++;

        }

        return count(s.begin(), s.begin() + n, '1');

    }

https://discuss.leetcode.com/topic/75273/o-log-n-space-java

Based on my Python solution. Here I use a helper class giving me the Kolakoski sequence (that's its name) one element at a time with its next method. It has the first three elements hard-coded, and after that, it uses another instance of the sequence to iterate further. That other instance does the same, so it might eventually use yet another instance. And so on, O(log n) nested Kolakoski objects iterating in parallel at different speeds as needed. Takes O(log n) space and O(n) time.

    public int magicalString(int n) {
        Kolakoski kolakoski = new Kolakoski();
        int ones = 0;
        while (n-- > 0)
            if (kolakoski.next() == 1)
                ones++;
        return ones;
    }

    private class Kolakoski {
        private int[] queue = {1, 2, 2};
        private int first = 0, last = 2;
        private Kolakoski source;
        int next() {
            if (first > last) {
                if (source == null) {
                    source = new Kolakoski();
                    source.next();
                    source.next();
                }
                int output = queue[last % 3] ^ 3;
                for (int k = source.next(); k > 0; k--)
                    queue[++last % 3] = output;
            }
            return queue[first++ % 3];
        }
    }