Magical String สตริงเวทมนตร์นับจำนวน 1 ใน C++

สตริงเวทมนตร์ S ประกอบด้วย '1' และ '2' โดยการนับตัวติดกันของ 1 และ 2 จะสร้าง S เอง

S = "1221121221221121122..."

จัดกลุ่ม: 1, 22, 11, 2, 1, 22, 1, 22, 11, 2, 11, 22... → จำนวน: 1,2,2,1,1,2,1,2,2,1,2,2... = S เอง

ให้ N หาจำนวน '1' ใน N ตัวแรกของ S

ตัวอย่าง: N=6 → "122112" → 3 ตัว

วิธีแก้ปัญหา (Two Pointers Generation)

1. ถ้า N ≤ 0 → 0, ถ้า N ≤ 3 → 1
2. ret = 1, arr[N], arr[0]=1, arr[1]=2, arr[2]=2
3. head = 2, tail = 3, num = 1
4. while tail < N:
   • วน i = 0 ถึง arr[head]-1:
     • arr[tail] = num
     • ถ้า num==1 และ tail
     • tail++, ถ้า tail≥N break
   • num ^= 3 (สลับ 1↔2)
   • head++
5. คืนค่า ret

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int magicalString(int n) {
        if (n <= 0) return 0;
        if (n <= 3) return 1;
        int ret = 1;
        vector<int> arr(n);
        arr[0] = 1; arr[1] = 2; arr[2] = 2;
        int head = 2, tail = 3, num = 1;
        while (tail < n) {
            for (int i = 0; i < arr[head]; i++) {
                arr[tail] = num;
                if (num == 1 && tail < n) ret++;
                tail++;
                if (tail >= n) break;
            }
            num ^= 3;
            head++;
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.magicalString(6);
    return 0;
}

Input

6

Output

3