全栈网站开发流行框架,网站制作公司制作网站,系统优化的目的和意义,鞍钢贴吧神奇字符串的规律#xff1a; 神奇字符串 s 仅由 ‘1’ 和 ‘2’ 组成#xff0c;并需要遵守下面的规则#xff1a; 神奇字符串 s 的神奇之处在于#xff0c;串联字符串中 1 和 2 的连续出现次数可以生成该字符串。 s 的前几个元素是 s “1221121221221121122……” 。如果…
神奇字符串的规律 神奇字符串 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当sn时就出错了故用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还是2if (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;}
};
