
宫水三叶的刷题日记
2022/11/04阅读:16主题:全栈蓝
754. 到达终点数字 : 逐步剖析如何取得最小步数
题目描述
这是 LeetCode 上的 「754. 到达终点数字」 ,难度为 「中等」。
Tag : 「数学」
在一根无限长的数轴上,你站在 0
的位置。终点在 target
的位置。
你可以做一些数量的移动 numMoves :
-
每次你可以选择向左或向右移动。 -
第 i
次移动(从i == 1
开始,到i == numMoves
),在选择的方向上走i
步。
给定整数 target
,返回 到达目标所需的 最小 移动次数(即最小 numMoves
) 。
示例 1:
输入: target = 2
输出: 3
解释:
第一次移动,从 0 到 1 。
第二次移动,从 1 到 -1 。
第三次移动,从 -1 到 2 。
示例 2:
输入: target = 3
输出: 2
解释:
第一次移动,从 0 到 1 。
第二次移动,从 1 到 3 。
提示:
数学
提示一:数轴上的任意点都以起点( 点)对称,只需要考虑对称点的任意一边
由于题目没有限制我们「不能到达哪些点」以及「出发的起始方向」,因此以起点为中心的左右两边对称。
即:左边所能到达任意一个点,都能通过调整所达路径的方向来将终点调整到右边。
同时由于起点是一个特殊的位置 点,因此相应的「正数点」和「负数点」对称,我们仅需考虑一边(例如正数域)即可。
提示二:先往靠近 target
的方向移动,到达或越过 target
的时候则停止
只考虑 target
为正的情况,我们假定起始先往靠近 target
的方向移动(即所有步数均为正值),根据是「到达」还是「越过」target
位置分情况讨论:
-
若能直接到达 target
,此时消耗的必然是最小步数,可直接返回; -
若越过了 target
,假设此时消耗的步数为 ,所走的距离为 ,我们可以考虑是否需要增加额外步数来到达target
。
提示三:越过 target
时,如何不引入额外步数
若不引入额外步数,意味着我们需要将此前某些移动的方向进行翻转,使得调整后的 。
我们假设需要调整的步数总和为 tot
,则有
,变形可得
。
若想满足上述性质,需要确保能找到这样的 tot
,即 tot
合法,
不难推导出当 dist
和 target
差值为「偶数」时(两者奇偶性相同),我们可以找到这样的 tot
,从而实现不引入额外步数来到达 target
位置。
❝由于我们的 是由数列 累加而来,因此必然能够在该数列 中通过「不重复选择某些数」来凑成任意一个小于等于 的数。
❞
提示四:越过 target
时,如何尽量减少引入额外步数
当 dist
和 target
差值不为「偶数」时,我们只能通过引入额外步数(继续往右走)来使得,两者差值为偶数。
可以证明,最多引入步数不超过 步,可使用得两者奇偶性相同,即不超过 步可以覆盖到「奇数」和「偶数」两种情况。
根据 与 的余数关系分情况讨论:
-
余数为 ,即 ,由于 ,其中一数为偶数, 为偶数; -
余数为 ,即 ,由于 ,两个奇数相乘为奇数, 为奇数; -
余数为 ,即 , ,两个奇数相乘为奇数, 为奇数; -
余数为 ,即 , ,其中一数为偶数, 为偶数。
因此在越过 target
后,最多引入不超过
步可使得 dist
和 target
奇偶性相同。
提示五:如何不通过「遍历」或「二分」的方式找到一个合适的 k
值,再通过不超过
步的调整找到答案
我们期望找到一个合适的 k
值,使得
,随后通过增加 k
值来找到答案。
利用求和公式
,我们可以设定
为起始值,随后逐步增大 k
值,直到满足「dist
和 target
奇偶性相同」。
Java 代码:
class Solution {
public int reachNumber(int target) {
if (target < 0) target = -target;
int k = (int) Math.sqrt(2 * target), dist = k * (k + 1) / 2;
while (dist < target || (dist - target) % 2 == 1) {
k++;
dist = k * (k + 1) / 2;
}
return k;
}
}
TypeScript 代码:
function reachNumber(target: number): number {
if (target < 0) target = -target
let k = Math.floor(Math.sqrt(2 * target)), dist = k * (k + 1) / 2
while (dist < target || (dist - target) % 2 == 1) {
k++
dist = k * (k + 1) / 2
}
return k
}
Python 代码:
class Solution:
def reachNumber(self, target: int) -> int:
if target < 0:
target = -target
k = int(math.sqrt(2 * target))
dist = k * (k + 1) / 2
while dist < target or (dist - target) % 2 == 1:
k += 1
dist = k * (k + 1) / 2
return k
-
时间复杂度: -
空间复杂度:
最后
这是我们「刷穿 LeetCode」系列文章的第 No.754
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
作者介绍
