Chuỗi ma thuật trong C ++

Giả sử có một chuỗi. Chuỗi đó được gọi là chuỗi huyền diệu S, chỉ bao gồm '1' và '2' và tuân theo các quy tắc sau -

• Chuỗi S rất kỳ diệu vì việc ghép số lần xuất hiện liền kề của các ký tự '1' và '2' sẽ tạo ra chính chuỗi S.
• Một vài thành phần đầu tiên của chuỗi S là sau - S ="1221121221221121122 ……"
• Nếu chúng ta nhóm các chữ '1 và' 2 liên tiếp thành S, nó sẽ là - 1 22 11 2 1 22 1 22 11 2 11 22 ...... và số lần xuất hiện của '1 hoặc' 2 trong mỗi nhóm là - 1 2 2 1 1 2 1 2 2 1 2 2 ......

Bây giờ, giả sử chúng ta có một số nguyên N làm đầu vào, hãy tìm số '1 trong số N đầu tiên trong chuỗi huyền diệu S. Vì vậy, nếu đầu vào là 6, thì đầu ra sẽ là 3, như 6 phần tử đầu tiên trong chuỗi huyền diệu là "12211". Điều này chứa ba số 1, vì vậy trả về 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu n <=0 thì trả về 0, nếu n <=3 thì trả về 1
• ret:=1, tạo một mảng có kích thước n
• arr [0]:=1, arr [1]:=2, arr [2]:=2
• head:=2, tail:=3 và num:=1
• while tail
• cho tôi trong phạm vi từ 0 đến arr [head] - 1
  • arr [tail]:=num
  • nếu num là 1 và tail
  • tăng đuôi lên 1
  • if tail> =n, then break loop
• num =num XOR 3
• tăng đầu thêm 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

6

Đầu ra

3