题目描述
Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)
Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).
When you get an instruction “A”, your car does the following: position += speed, speed *= 2
.
When you get an instruction “R”, your car does the following: if your speed is positive then speed = -1
, otherwise speed = 1
. (Your position stays the same.)
For example, after commands “AAR”, your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.
Now for some target position, say the length of the shortest sequence of instructions to get there.
Example 1:
Input:
target = 3
Output: 2
Explanation:
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.
Example 2:
Input:
target = 6
Output: 5
Explanation:
The shortest instruction sequence is "AAARA".
Your position goes from 0->1->3->7->7->6.
Note:
1 <= target <= 10000
.
题意:你的赛车起始停留在位置 0,速度为 +1,正行驶在一个无限长的数轴上。(车也可以向负数方向行驶。)你的车会根据一系列由 A(加速)和 R(倒车)组成的指令进行自动驾驶 。
当车得到指令 “A” 时, 将会做出以下操作: position += speed, speed *= 2。
当车得到指令 “R” 时, 将会做出以下操作:如果当前速度是正数,则将车速调整为 speed = -1 ;否则将车速调整为 speed = 1。 (当前所处位置不变。)
例如,当得到一系列指令 “AAR” 后, 你的车将会走过位置 0->1->3->3,并且速度变化为 1->2->4->-1。
现在给定一个目标位置,请给出能够到达目标位置的最短指令列表的长度。
算法1
(BFS)
因为求的是最短路径,而且每一步只有两种选择,所有很自然的就会想到BFS的想法,状态表示为st(u,v,dir)
,分别代表当前位置u
,当前速度2^v
,当前方向(0为正向)。同时使用一个dis[u][v][dir]
记录到达每一种状态的最小步数。初始化dis[0][0][0] = 0
,其余为正无穷。取出队列头元素,然后分别当前合法的下一步加入到队列中(非法情况:越界,搜索到一个已经被搜索过的状态即不是最优解),如果到达了target
就直接返回答案。这里需要注意的是数组的第一维需要开到target * 2
即可。第二维开到15即可($2^{15} >20000$)。
class Solution {
public:
struct st{
int u,v,dir;
st(){}
st(int u,int v,int dir):u(u),v(v),dir(dir){}
};
int racecar(int target) {
int mx = target * 2 + 1,dp[mx][15][2];
memset(dp,0x3f,sizeof(dp));
dp[0][0][0] = 0;
queue<st> q;
q.push(st(0,0,0));
while(!q.empty())
{
auto t = q.front();
q.pop();
int u = t.u,v = 1 << t.v,dir = t.dir == 0 ? 1: -1,nxt = u + v * dir;
if(nxt < mx && nxt > 0 && dp[nxt][t.v + 1][t.dir] > dp[t.u][t.v][t.dir] + 1)
{
dp[nxt][t.v + 1][t.dir] = dp[t.u][t.v][t.dir] + 1;
if(nxt == target) return dp[nxt][t.v + 1][t.dir];
q.push(st(nxt,t.v + 1,t.dir));
}
if(dp[t.u][0][1 - t.dir] > dp[t.u][t.v][t.dir] + 1)
{
dp[t.u][0][1 - t.dir] = dp[t.u][t.v][t.dir] + 1;
q.push(st(t.u,0,1 - t.dir));
}
}
return 0;
}
};
算法2
(动态规划) $O(nlogn)$
由于速度变化是[1,2,4,8]
,首先我们可以观察到如果一个位置恰好是$target = 2^{k} - 1 = \sum \limits_{i = 0}^{k - 1}2^i$,这里的k
指的是target
二进制中最高的非零位以及其后面总共有多少个数字,那么我们恰好只需要k
步就可以直接到达终点。如果不是上述情况的话,我们走过的路径肯定是形如AAARAARAAARRAAA
,即两个R
之间有若干个A
(也可以没有)。那我们可以采取两种方案:
方案1:先走到k
步到达位置$2^k - 1$,然后转向R,这时候问题转化成从位置$2^k - 1$以初速度为-1到达位置$target$最少需要多少步,这个字问题等同于从0以初速度1走到$2^k - 1 - target$所需要的步数。
的最优解其实是先走k - 1
次到$2^{k-1} - 1$的地方,然后开始转向R
然后走j
个A
再转向R
,这时候问题又转换成从新的位置$2^{k - 1} - 2^{j}$到$target$以初速度为1需要多少步了,这个子问题其实等同于从0走到位置$target - (2^{k - 1}- 2^j)$所需要的步数。
状态表示:dp[i]
代表从0开始出发以正向初速度为1,最少需要多少步能够到达位置i
。
状态转移:dp[t] = dp[(1 << k) - 1 - t] + k + 1
,情况1,先走了k
步,然后转向。
dp[t] = dp[t - ((1 << (k - 1)) - (1 << j))] = ( k - 1) + j + 2
,情况2,先走了k - 1
步,然后转向,然后再走j
步,然后再转向,其中0 <= j < k - 1
。dp[t]
取所有情况的最小值。
状态初始化:dp[0] = 0
,结果表示dp[target]
class Solution
{
public:
int getValidBit(int x)
{
int res = 0;
while(x > 0)
{
x = x >> 1;
res ++;
}
return res;
}
int racecar(int target)
{
int dp[2 * target + 1];
memset(dp,0x3f,sizeof(dp));
dp[0] = 0,dp[1] = 1;
for(int t = 1 ; t <= target ; t ++)
{
int k = getValidBit(t);
if(t == (1 << k) - 1){
dp[t] = k;
continue;
}
dp[t] = dp[(1 << k) - 1 - t] + k + 1;
for(int j = 0 ; j < k - 1 ; j ++)
dp[t] = min(dp[t],dp[t - ((1 << (k - 1)) - (1 << j))] + (k - 1) + j + 2);
}
return dp[target];
}
};