入门力扣自学笔记190 C++ （题目编号：481）

481. 神奇字符串

题目：

神奇字符串 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：

输入：n = 6
输出：3
解释：神奇字符串 s 的前 6 个元素是 “122112”，它包含三个 1，因此返回 3 。 

---

示例 2：

输入：n = 1
输出：1

---

提示：

1 <= n <= 105

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/magical-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路：

这道题的字符串既是索引，也是最终的结果，而且我们发现他是1和2两个数字交替出现，所以我们采用双指针的办法来解决这个问题。

首先，我们将第一组的数据存入容器，避免类型转换运算的麻烦。

其次，我们对这个进行遍历，在容器中存入之后的数字，因为第一组为122，所以下一组一定是以1开始，我们在这个中间采用两个循环，分别存入1和2，输出这一组数字。

最后，我们采用一个flag，来标记1的个数，返回flag即可。

---

代码：

class Solution {
public:
    int magicalString(int n) {
        vector<int> s{1,2,2};
        int flag = 1;
        for(int i = 2;s.size() < n;)
        {
            for(int j = s[i++];j > 0 && s.size() < n;j--)
            {
                s.push_back(1);
                flag++;
            }
            for(int j = s[i++];j > 0 && s.size() < n;j--)
                s.push_back(2);
        }
        return flag;
    }
};