C++のマジックストリング

文字列があるとします。その文字列はマジックストリングSと呼ばれ、「1」と「2」のみで構成され、次の規則に従います-

• 文字列Sは、文字「1」と「2」の連続した出現回数を連結すると文字列S自体が生成されるため、魔法のようです。
• 文字列Sの最初のいくつかのコンポーネントは次のとおりです-S="1221121221221121122……"
• Sで連続する「1」と「2」をグループ化すると、次のようになります。-1 22 11 2 1 22 1 22 11 2 1122......各グループでの「1」または「2」の出現は− 1 2 2 1 1 2 1 2 2 1 2 2 ......

ここで、入力として整数Nがあるとし、マジックストリングSの最初のN個の数字の「1」の数を見つけます。したがって、入力が6の場合、出力は3になり、マジックストリングの最初の6個の要素になります。 「12211」です。これには3つの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
• テール
• 0からarr[head]–1
  の範囲のiの場合
  • arr [tail]：=num
  • numが1で、tailが
  • テールを1つ増やします
  • tail> =nの場合、ループを解除します
• num =num XOR 3
• 頭を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