481. Magic string

Magical stringS only contains '1' and '2' and adheres to the following rules:

StringS is magical because the consecutive occurrences of the concatenation characters '1' and '2' generate a stringS itself.

StringThe first few elements of S are as follows:= “1221121221221121122 ......”

If we willGrouping consecutive 1 and 2 in S will become:

1 22 11 2 1 22 1 22 11 2 11 22 ......

And the number of occurrences of '1' or '2' in each group are:

1 2 2 1 1 2 1 2 2 1 2 2 ......

You can see that the number of occurrences above isS itself.

Given an integer N as input, return a magic stringThe number of '1's in the first N numbers in S||.中前 N 个数字中的 '1' 的数目。

Note: N does not exceed 100,000.

Example:

Input: 6Output: 3Explanation:  The first six elements of the magic string S are "12211", which contains three 1, so it returns 3.

The idea is as follows: summarizing the law, when the subscript i is even, the number of repo[i] corresponding to the number should be 1;

When i is an odd number, the number of repo[i] corresponding to the number shall be 2;

And each time you add, you can simulate 1, 2, 1, 2 with 3-1=2, 3-2=1. . . The change.

The following is the code:

class Solution {
public:
    int magicalString(int n) {
        if(n<1)
            return 0;
        if(n<=3)
            return 1;
        vector<int> repo;
        repo.push_back(1);
        repo.push_back(2);
        repo.push_back(2);
        long total=3;
        int num;
        long coun=1;
        for(int i=2;total<n;i++){
            if(i%2==0){
                num=1;
                coun+=repo[i];
            }
            else num=2;
            for(int k=0;k<repo[i];k++){
                repo.push_back(num);
            } 
            total+=repo[i];
        }
        if(num==1&&total-n==1)
            return coun-1;
        return coun;
    }
};