0818. Race Car

题目信息

题号:

0818

难度:

Hard

主题:

状态空间、位置与速度、最少指令

原题:

LeetCode 0818

重点:

汽车初始位置为 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,因此最少只需一条指令。