0818. Race Car¶
题目信息¶
- 题号:
0818
- 难度:
Hard
- 主题:
状态空间、位置与速度、最少指令
- 原题:
- 重点:
汽车初始位置为 0、速度为 +1;加速会按当前速度移动并使速度翻倍,倒车只改变速度方向而不移动
题目重述¶
一辆汽车在整数数轴上,初始位置为 0,初始速度为 +1。可以依次执行两种指令:
A:位置增加当前速度,然后速度变为原来的两倍;R:位置不变,若当前速度为正则改为-1,若当前速度为负则改为+1。
给定正整数目标位置 target,请返回使汽车恰好到达该位置所需的最少指令数。汽车在过程中可以越过目标,也可以到达负位置;只要求某次执行完指令后位置等于目标。
1 <= target <= 10^4。
自建示例¶
先越过前的邻近位置再调整方向:
输入:target = 4
输出:5
解释:执行 "AARRA":位置依次变为 1、3、3、3、4,最终用 5 条指令到达目标;不存在更短的指令序列。
目标是最小正整数:
输入:target = 1
输出:1
解释:target 达到题目允许的最小值。初始速度为 +1,执行一条 A 指令后位置从 0 变为 1,因此最少只需一条指令。