C++의 마법 문자열

<시간/>

문자열이 있다고 가정합니다. 그 문자열을 마법의 문자열 S라고 하며 '1'과 '2'로만 구성되며 다음 규칙을 따릅니다. -

문자 '1'과 '2'의 연속 발생 횟수를 연결하면 문자열 S 자체가 생성되기 때문에 문자열 S는 마법과 같습니다.
문자열 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 ......

이제 입력으로 정수 N이 있다고 가정하고 마법 문자열 S의 첫 번째 N 숫자에서 '1의 수를 찾으십시오. 따라서 입력이 6과 같으면 출력은 마법 문자열의 처음 6개 요소로 3이 됩니다. "12211"입니다. 여기에는 3개의 1이 포함되어 있으므로 3을 반환합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n <=0이면 0, n <=3이면 1을 반환
ret :=1, 배열 arr을 n 크기로 만듭니다.
arr[0] :=1, arr[1] :=2, arr[2] :=2
머리:=2, 꼬리:=3 및 숫자:=1
while 꼬리
0 ~ arr[head] – 1
- arr[꼬리] :=숫자
- num이 1이고 tail
- 꼬리 1 증가
- tail>=n이면 루프를 끊습니다.
숫자 =숫자 XOR 3
머리 1씩 증가

반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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;
      int tail = 3;
      int 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;
   }
};
main(){
   Solution ob;
   cout << (ob.magicalString(6));
}