难度: Medium
神奇字符串 s 仅由 '1' 和 '2' 组成，并需要遵守下面的规则：
'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 <= n <= 105运行时间: 55 ms
内存: 20.2 MB
class Solution:
def magicalString(self, n: int) -> int:
# 此题规定了第一个数是1，故神奇字符串唯一
res = 1
s = '1'
cur, num_sub = 0, 1
while len(s) < n:
if s[cur] == '1':
s += '2'
if s[num_sub] =='1':
cur += 1
else:
s += '2'
cur += 2
num_sub += 1
if len(s) >= n:
break
else:
s += '1'
res += 1
if len(s) == n:
break
if s[num_sub] =='1':
cur += 1
else:
s += '1'
res += 1
cur += 2
num_sub += 1
if len(s) >= n:
break
return res
此题解采用了模拟生成神奇字符串的过程。神奇字符串的生成规则是：利用当前字符串的字符来决定接下来添加的字符型号和数量。题解中，初始化神奇字符串为'1'，从第一个字符开始，根据字符的值（'1' 或 '2'）来决定接下来添加的字符（'2' 或 '1'）。如果当前字符为'1'，则添加一个'2'；如果为'2'，则添加两个'1'。同时，题解中使用了变量cur来表示当前处理的字符位置，num_sub表示已添加的字符数量。循环继续直到构建的字符串长度达到或超过n。最后，返回字符串中'1'的数量。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def magicalString(self, n: int) -> int:
res = 1 # 初始化'1'的数量
s = '1' # 神奇字符串的起始值
cur, num_sub = 0, 1 # cur为当前读取的位置，num_sub为已生成的字符数
while len(s) < n: # 生成字符串直到长度至少为n
if s[cur] == '1': # 当前位置是'1'
s += '2' # 根据规则添加'2'
if s[num_sub] == '1': # 检查下一个用于生成字符的值
cur += 1
else:
s += '2' # 再添加一个'2'
cur += 2
num_sub += 1
if len(s) >= n: # 检查长度
break
else: # 当前位置是'2'
s += '1' # 根据规则添加'1'
res += 1 # 计数器增加
if len(s) == n: # 检查长度
break
if s[num_sub] == '1': # 检查下一个用于生成字符的值
cur += 1
else:
s += '1' # 再添加一个'1'
res += 1
cur += 2
num_sub += 1
if len(s) >= n: # 检查长度
break
return res
在算法中，cur变量指向当前用于决定添加字符的位置，其值增加的目的是移动到下一个用于生成字符的字符。当当前字符为'1'时，根据规则，我们只添加一个'2'。如果紧接着的字符（由num_sub指向）也为'1'，则cur增加1，移动到下一个字符；如果是'2'，则我们会连续添加两个'2'（每个'2'对应一个字符），因此，cur需要增加2以跳过已经处理的字符。这样的逻辑确保了每个生成字符的决策点都被正确地处理，同时避免了重复或遗漏任何字符的生成。
当当前字符为'2'时，根据生成规则，我们需要添加两个'1'。由于我们的目标是构建长度至少为n的字符串，每次添加字符后都需要检查已生成的字符串长度是否满足要求。第一次检查是在添加第一个'1'后，以确保如果长度已达到n就停止进一步添加。如果第一个'1'后字符串长度仍未达到n，则添加第二个'1'，并再次检查长度。这样的重复检查是必要的，因为每次添加字符后都可能达到或超过所需长度，从而避免过度生成字符。
在题解中，num_sub变量用于记录已生成的字符数量，它指示当添加新字符时应该参考的位置。而cur变量则用于读取当前字符，以决定接下来应该添加什么字符以及数量。尽管两者似乎都涉及到字符位置的处理，但它们的功能并不重叠。cur主要负责读取和解释当前字符应该如何影响接下来的字符添加，而num_sub则确保我们在正确的位置添加字符。cur负责“读取规则”，num_sub负责“执行规则”。这种分工使得算法既清晰又有效地扩展字符串至所需长度。