千峰网络安全培训西安网站seo

神奇字符串的规律：

神奇字符串 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个字符中'1'的个数，则我们就构造n个字符的神奇字符串 

1、初始条件：给出神奇字符串前三个组成的字符串，为什么？

①、前三个字符中'1'的个数可以明显得出

②、给出前三个组成的字符串后，我们才能利用规律求解题目（主要原因）

2、利用指针，一开始p就指向字符串末尾，p用来判断要添加几个字符，而字符串的末尾字符是'1'，则要尾插'2'，是'2'，则要尾插'1'，而添加几个字符就看p指向的字符是几就添加几个就好了，末尾字符是什么我们可以用个Add变量来记录

最后统计前n个字符中'1'的个数，我们可直接用iostream中的count函数来帮我们统计，但要注意，count的参数中最后的迭代器不能用s.end( )，因为可能s的大小>=n，当s>n时就出错了，故用s.begin( ) + n即可 

class Solution {
public:int magicalString(int n) {if (n < 4) return 1;    //如果在前三个范围内，则直接返回即可string s = "122";//构造出前三个字符，往后就有规律了int p = 2;//作为指针，代表需要添加多少个字符while (s.size() < n) {//只需构造n个字符即可char Add = s.back();//Add用来判断添加'1'还是'2'if (s[p] == '2'){if (Add == '2')s += "11";elses += "22";}else{if (Add == '1')s += '2';elses += '1';}++p;//每次p都向后走一位}//法一、统计'1'的个数，直接用count函数来统计int cnt = count(s.begin(), s.begin() + n, '1');//利用count函数求出'1'的个数//法二、统计'1'的个数，直接用循环/* for (int i = 0; i < n; i++)if (s[i] == '1')cnt++;*/return cnt;}
};