神奇字符串【LC481】
神奇字符串 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的个数后返回
- 规律
。神奇字符串 s 称为“原串”，对 s 进行连续段划分所得的串叫“划分串”，对划分串进行计数的串叫“计数串”。
。划分串的长度只能是1或者2
。计数串总是短于原串，因此使用变量i记录当前构造到原串的位置，使用变量j来记录计数串对应的位置
。可以分四种情况构造神奇字符串
1.当原串当前字符为1，计数串当前字符为1
那么原串只能添加字符’2’，原串指针后移一位
2.当原串当前字符为1，计数串当前字符为2
那么原串只能添加字符’12’，原串指针后移两位
3.当原串当前字符为2，计数串当前字符为1
那么原串只能添加字符’1’，原串指针后移一位
4.当原串当前字符为2，计数串当前字符为2
那么原串只能添加字符’21’，原串指针后移两位
- 代码
class Solution { public int magicalString(int n) { char[] chars = new char[100001]; chars[0] = '0';// 哨兵 chars[1] = '1'; int count = 1; if (n < 4){ return count; } int i = 1, j = 1; while (i < n){ if (chars[i] == '1'){ if (chars[j] == '1'){ chars[++i] = '2'; }else { chars[++i] = '1'; chars[++i] = '2';// 多构造一位不影响结果 count++; } }else { if (chars[j] == '1'){ chars[++i] = '1'; count++; }else { chars[++i] = '2'; if (i + 1 <= n){// 多构造一位影响结果 chars[++i] = '1'; count++; } } } j++; } return count; } }
- 复杂度
。时间复杂度：O ( n )
。空间复杂度：O ( n )
