C++のレースカー

位置0から始まり、無限の数直線上で速度+1の車があるとします。車は一連の指示に従って自動的に走行します。A：加速の場合、R-は後進の場合。 「A」の指示を受けると、私たちの車は次のことを行います-

• 位置：=位置+速度、次に速度=速度*2。

「R」の指示を受けると、私たちの車は次のことを行います-

• 速度が正の場合、速度=-1、
• それ以外の場合、速度=1。

たとえば、「AAR」の命令を実行した後、車は0-> 1-> 3-> 3の位置に移動し、速度は1->2->4->-1に移動します。

ここで、ターゲット位置があるとします。そこに到達するには、命令の最短シーケンスの長さを見つける必要があります。

したがって、入力がtarget =6のような場合、可能なシーケンスの1つがAAARAであるため、出力は5になり、位置シーケンスは0-> 1-> 3-> 7-> 7-> 6>

これを解決するには、次の手順に従います-

• 訪問した1セットを定義する
• 1つのキューを定義するq
• {0、1}をqに挿入
• 初期化レベル：=0の場合、qが空でない場合は、更新（レベルを1増やします）、実行-
  • kの初期化：=qのサイズ、k> 0の場合、更新（kを1つ減らす）、実行-
    • 1ペアのcurrを定義します：=qの前の要素、qから要素を削除します
    • 最初のcurrがターゲットと同じである場合、-
      • リターンレベル
    • forward：=currの最初+currの2番目
    • forwardSpeed：=currの2番目*2
    • key：=forward to string concatenate "*" concatenate convert forwardSpeed to string
    • 転送>0および|転送-ターゲット|の場合<キーではなくターゲットが訪問されていない場合、-
      • 訪問先にキーを挿入
      • {forward、forwardSpeed}をqに挿入します
    • key：=currの最初の文字列を文字列に変換しますconcatenate"*"currの2番目が0より大きい場合は0を連結します。それ以外の場合は-1
    • curr.first>0および|target--curr.first|の場合<ターゲットとキーが訪問されていない場合、-
      • 訪問先にキーを挿入
      • {curr.first、（curr.second> 0の場合は-1、それ以外の場合は1}）をqに挿入します
• 戻り値-1

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int racecar(int target) {
      unordered_set < string > visited;
      queue < pair <int ,int> > q;
      q. push({0, 1});
      for(int level = 0; !q.empty(); level++){
         for(int k = q.size(); k > 0; k-- ){
            pair <int, int> curr = q.front();
            q.pop();
            if(curr.first == target) return level;
            int forward = curr.first + curr.second;
            int forwardSpeed = curr.second * 2;
            string key = to_string(forward) + "*" + to_string(forwardSpeed);
            if(forward > 0 && abs(forward - target) < target && !visited.count(key)){
               visited.insert(key);
               q.push({forward, forwardSpeed});
            }
            key = to_string(curr.first) + "*" + to_string(curr.second > 0 ? - 1: 1);
            if(curr.first > 0 && abs(target - curr.first) < target && !visited.count(key)){
               visited.insert(key);
               q.push({curr.first, curr.second > 0 ? - 1: 1});
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   cout << (ob.racecar(6));
}

入力

6

出力

5