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