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 Sitself. 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.
这道题给了一个magic字符串，具体怎么magic题目说得很清楚了。这个字符串只包含字符1和2，依次计算字符串中连续的1或2出现的次数，把这些数字串起来，构成的一个新的字符串和原字符串是完全一样的！然后问字符串中前n个字符出现1的次数。 这是一个模拟题，我们根据magic的规则模拟生成这个字符串，然后统计一下前n个字符中1出现的次数。 模拟的方法就是把字符串中的数当做原字符串中1或2出现的次数，然后不断在原字符串中追加新的字符。比如开始是122：1表示1出现1次；第一个2表示出现两次，因为前面有1出现1次的约束，所以出现两次的只可能是2；第二个2也表示出现两次，因为前面已经出现了两个2了，所以这里不能再接两个2了（要不然就出现4个2了），只能表示出现了两次1，所以我们可以在原字符串中追加两个1，变为12211。如此不断的模拟下去，直到字符串长度满足要求。 完整代码如下： [cpp] class Solution { public: int magicalString(int n) { string magic = "122"; int pos = 2; while (magic.size() < n) { switch (magic[magic.size()-1]) { case ‘1’: magic += string(magic[pos] – ‘0’, ‘2’); break; case ‘2’: magic += string(magic[pos] – ‘0’, ‘1’); break; } ++pos; } int ans = 0; for (int i = 0; i < n; ++i) { ans += magic[i] == ‘1’ ? 1 : 0; } return ans; } }; [/cpp] 本代码提交AC，用时9MS。]]>