รถแข่งใน C++

สมมติว่าเรามีรถที่เริ่มต้นที่ตำแหน่ง 0 และความเร็ว +1 บนเส้นจำนวนอนันต์ รถวิ่งโดยอัตโนมัติตามลำดับคำสั่ง A:สำหรับการเร่งความเร็วและ R – สำหรับการถอยหลัง เมื่อเราได้รับคำสั่ง "A" รถของเราจะทำสิ่งต่อไปนี้ -

ตำแหน่ง :=ตำแหน่ง + ความเร็ว จากนั้น ความเร็ว =ความเร็ว * 2.

เมื่อเราได้รับคำสั่ง "R" รถของเราจะทำสิ่งต่อไปนี้ -

ถ้าความเร็วเป็นบวก ความเร็ว =-1
มิฉะนั้น ความเร็ว =1.

ตัวอย่างเช่น หลังจากทำตามคำแนะนำ "AAR" รถของเราไปที่ตำแหน่ง 0->1->3->3 และความเร็วไปที่ 1->2->4->-1

สมมติว่าเรามีตำแหน่งเป้าหมายอยู่บ้าง เราต้องหาความยาวของลำดับคำสั่งที่สั้นที่สุดเพื่อไปที่นั่น

ดังนั้น ถ้าอินพุตเหมือนเป้าหมาย =6 เอาต์พุตจะเป็น 5 เนื่องจากหนึ่งในลำดับที่เป็นไปได้คือ AAARA ลำดับตำแหน่งจะเป็น 0->1->3->7->7->6

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดการเยี่ยมชมหนึ่งชุด
กำหนดหนึ่งคิว q
แทรก { 0, 1 } ลงใน q
สำหรับระดับเริ่มต้น:=0 เมื่อไม่มี q ว่างเปล่า ให้อัปเดต (เพิ่มระดับขึ้น 1) ทำ −
- สำหรับการเริ่มต้น k :=ขนาดของ q เมื่อ k> 0, อัปเดต (ลด k ลง 1) ทำ −
  - กำหนดหนึ่งคู่ curr :=องค์ประกอบด้านหน้าของ q ลบองค์ประกอบออกจาก q
  - ถ้าตัวแรกของเคอร์เท่ากับเป้าหมาย −
    - ระดับผลตอบแทน
  - forward :=อันดับแรกของสกุลเงิน + วินาทีของสกุลเงิน
  - forwardSpeed :=วินาทีของสกุลเงิน * 2
  - key :=convert forward to string concatenate " * " concatenate convert forwardSpeed to string
  - ถ้าส่งต่อ> 0 และ |forward - target|
  - ใส่คีย์เข้าไป
  - แทรก { forward, forwardSpeed } ลงใน q
- key :=แปลงค่าแรกของ curr เป็น string concatenate " * " concatenate 0 เมื่อวินาทีของ curr> 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));
}

รถแข่งใน C++

ตัวอย่าง

อินพุต

ผลลัพธ์