資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告