C++ 中的神奇字符串
c++server side programmingprogramming
假设有一个字符串。该字符串称为神奇字符串 S，它仅由"1"和"2"组成，并遵循以下规则 −
- 字符串 S 之所以神奇，是因为将字符"1"和"2"的连续出现次数连接起来会生成字符串 S 本身。
- 字符串 S 的前几个组成部分如下 − S = "122112122122112122……"
- 如果我们将 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
- head := 2，tail := 3 且 num := 1
- while tail
- for i in range 0 to arr[head] – 1
- arr[tail] := num
- if num 为 1 且 tail < n，然后将 ret 加 1
- 将 tail 加 1
- 如果 tail >= n，则跳出循环
- num = num 异或 3
- 将 head 加 1
- for i in range 0 to arr[head] – 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));
}
输入
6
输出
3
