数据结构
网络
关系数据库管理系统 (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 次浏览
广告