C ++中的神奇字符串
假设有一个字符串。该字符串称为魔术字符串S，它仅由“1”和“2”组成，并遵循以下规则-
字符串S之所以具有魔力，是因为将字符“1”和“2”的连续出现次数串联起来可以生成字符串S本身。
字符串S的前几个组成部分如下-S=“1221121221221121122……”
如果我们在S中将连续的'1'和'2'分组，则将是−1221121221221121122......并且每组中出现'1'或'2'的情况是-122112122122......
现在假设我们有一个整数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=numXOR3
头增加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