C ++中的神奇字符串

假设有一个字符串。该字符串称为魔术字符串S，它仅由“ 1”和“ 2”组成，并遵循以下规则-

• 字符串S之所以具有魔力，是因为将字符“ 1”和“ 2”的连续出现次数串联起来可以生成字符串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，那么输出将是3，作为魔幻字符串中的前6个元素是“ 12211”。它包含三个1，因此返回3。

为了解决这个问题，我们将遵循以下步骤-

• 如果n <= 0，则返回0，如果n <= 3，则返回1

• ret：= 1，设置大小为n的数组arr

• arr [0]：= 1，arr [1]：= 2，arr [2]：= 2

• 头：= 2，尾巴：= 3和num：= 1

• 而尾巴<n

• arr [tail]：= num

• 如果num为1并且tail <n，则将ret增加1

• 将尾巴增加1

• 如果tail> = n，则中断循环

• 对于我，范围从0到arr [head] – 1

• num = num XOR 3

• 头增加1

• 返回ret

让我们看下面的实现以更好地理解-

示例

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

输入项

6

输出结果

3