สตริงเวทย์มนตร์ใน C ++

สมมติว่ามีสตริง สตริงนั้นเรียกว่าสตริงเวทย์มนตร์ S ซึ่งประกอบด้วย '1' และ '2' เท่านั้น และปฏิบัติตามกฎต่อไปนี้ -

สตริง S นั้นวิเศษมาก เนื่องจากการเชื่อมจำนวนของอักขระ '1' ที่ต่อเนื่องกันและ '2' ที่ต่อเนื่องกันทำให้เกิดสตริง S ขึ้นเอง
ส่วนประกอบสองสามตัวแรกของสตริง S มีดังต่อไปนี้ − S ="1221121221221121122……"
ถ้าเราจัดกลุ่ม '1' และ '2's ติดต่อกันใน S มันจะเป็น − 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 เป็นอินพุต ให้หาจำนวน '1' ในตัวเลข N ตัวแรกในสตริงเวทย์มนตร์ S ดังนั้นหากอินพุตเป็น 6 เอาต์พุตจะเป็น 3 ซึ่งเป็น 6 องค์ประกอบแรกในสตริงเวทย์มนตร์ คือ “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 และ num :=1
ในขณะที่หาง
สำหรับ i ในช่วง 0 ถึง arr[head] – 1
- arr[tail] :=num
- ถ้า num เป็น 1 และ tail
- เพิ่มหางขึ้น 1
- ถ้าหาง>=n ให้แตกวง
num =num 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));
}

สตริงเวทย์มนตร์ใน C ++

ตัวอย่าง

อินพุต

ผลลัพธ์