481.神奇字符串

链接：481.神奇字符串
难度：Medium
标签：双指针、字符串
简介：给你一个整数 n ，返回在神奇字符串 s 的前 n 个数字中 1 的数目。

题解 1 - cpp

• 编辑时间：2022-10-31
• 执行用时：8ms
• 内存消耗：8.5MB
• 编程语言：cpp
• 解法介绍：双指针记录。

class Solution {
public:
    int magicalString(int n) {
        vector<int> list(max(3, n));
        list[0] = 1; list[1] = list[2] = 2;
        int ans = 1, i1 = 2, i2 = 3, surplus = 2, curVal = 1, curMode = 1;
        while (i2 < n) {
            if (surplus == 0) {
                surplus = list[++i1];
                curVal += curMode;
                curMode = -curMode;
            }
            list[i2++] = curVal;
            surplus--;
            if (curVal == 1) ans++;
        }
        return ans;
    }
};