資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++賽車
假設我們有一輛車，它從位置0出發，速度為+1，在一個無限長的數軸上行駛。這輛車根據一系列指令自動執行：A表示加速，R表示反向。當我們收到指令“A”時，我們的車會執行以下操作：
- 位置 := 位置 + 速度，然後速度 = 速度 * 2。
當我們收到指令“R”時，我們的車會執行以下操作：
- 如果速度為正，則速度 = -1；
- 否則速度 = 1。
例如，執行指令“AAR”後，我們的車的位置變化為0->1->3->3，速度變化為1->2->4->-1。
現在假設我們有一個目標位置；我們必須找到到達該位置的最短指令序列的長度。
因此，如果輸入為target = 6，則輸出為5，因為其中一個可能的序列是AAARA，位置序列將為0->1->3->7->7->6
為了解決這個問題，我們將遵循以下步驟：
- 定義一個集合visited
- 定義一個佇列q
- 將{0, 1}插入q
- 初始化level := 0，當q不為空時，更新（level加1），執行：
- 初始化k := q的大小，當k > 0時，更新（k減1），執行：
- 定義一個對curr := q的隊首元素，從q中刪除該元素
- 如果curr的第一個元素等於目標值，則：
- 返回level
- forward := curr的第一個元素 + curr的第二個元素
- forwardSpeed := curr的第二個元素 * 2
- key := 將forward轉換為字串，連線" * "，連線將forwardSpeed轉換為字串
- 如果forward > 0 且 |forward - target| < target 且 key 不在visited中，則：
- 將key插入visited
- 將{forward, forwardSpeed}插入q
- key := 將curr的第一個元素轉換為字串，連線" * "，如果curr的第二個元素 > 0，則連線0，否則連線-1
- 如果curr.first > 0 且 |target - curr.first| < target 且 key 不在visited中，則：
- 將key插入visited
- 將{curr.first, (如果curr.second > 0，則-1，否則1)}插入q
- 初始化k := q的大小，當k > 0時，更新（k減1），執行：
- 返回-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
更新於：2020年6月2日
919 次瀏覽
廣告