481、神奇字符串

神奇字符串 s 仅由‘1’和 ‘2’ 组成，并需要遵守下面的规则：

• 神奇字符串 s 的神奇之处在于，串联字符串中 '1' 和 '2' 的连续出现次数可以生成该字符串。

s 的前几个元素是 s = "1221121221221121122……" 。如果将 s 中连续的若干 1 和 2 进行分组，可以得到 "1 22 11 2 1 22 1 22 11 2 11 22 ......" 。每组中 1 或者 2 的出现次数分别是 "1 2 2 1 1 2 1 2 2 1 2 2 ......" 。上面的出现次数正是 s 自身。

给你一个整数 n ，返回在神奇字符串 s 的前 n 个数字中 1 的数目。

示例 1：

输入：n = 6
输出：3
解释：神奇字符串 s 的前 6 个元素是 “122112”，它包含三个 1，因此返回 3 。 

示例 2：

输入：n = 1
输出：1

解题思路： 

（1）了解Kolakoski序列

该题是一个Kolakoski序列，是一个仅由1和2组成的无限数列，是一种通过“自描述”来定义的数列。

他的前几项为1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,…(OEIS上的A000002)

它的定义很简单，若把数列中相同的数定为一组，令a(1)=1，a(2)=2，则a(n)等于第n组数的长度。

可以根据这个定义来推算第三项以后的数：例如由于a(2)=2，因此第2组数的长度是2，因此a(3)=2,；

由于a(3)=2，所以第三组数的长度是2，因此a(4)=a(5)=1；由于a(4)=1，a(5)=1，所以第四组数和第五组数的长度都为1，因此a(6)=2，a(7)=1，以此类推。

（2）解题过程

（边构造边统计）

当n<=3时，无需向下继续构造，直接返回1即可；

构造一个长度为n的字符串，将其全部初始化为'0'；

初始化字符串 s='122'，用指针 i 来指向现在需要构造的对应的组的大小，用指针 j 来指向现在需要构造的对应组的位置，此时 i = 2，j = 3；

因为相邻组中的数字一定不会相同，所以我们可以通过 j 的前一个位置的数来判断当前需要填入的组中的数字。又因为每组的大小只为 1 或者 2，这保证了 j > i 在构造的过程中一定成立，即在指针 j 处填入组时一定能确定此时需要填入的组的大小。这样我们就可以不断往下进行构造直到字符串长度到达 n。

int magicalString(int n) {
    if (n <= 3)
    {
        return 1;
    }
    char s[n+1];
    memset(s, '0', sizeof(s));
    s[0] = '1', s[1] = '2', s[2] = '2';
    int i = 2;
    int j = 3;
    int res = 1;
    while (j < n)
    {
        int size = s[i] - '0';
        int num = 3-(s[j - 1] - '0');
        while (size > 0 && j < n)
        {
            s[j] = '0' + num;
            if (num == 1)
                ++res;
            ++j;
            --size;
        }
        ++i;
  }
    return res;
}