数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
- head := 2，tail := 3 以及 num := 1
- 当 tail < n 时
- 对于 i 的范围从 0 到 arr[head] – 1
- arr[tail] := num
- 如果 num 为 1 且 tail < n，则将 ret 增加 1
- 将 tail 增加 1
- 如果 tail >= n，则中断循环
- num = num XOR 3
- 将 head 增加 1
- 对于 i 的范围从 0 到 arr[head] – 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
更新于： 2020年5月2日
625 次查看
广告