LeetCode每日一题系列
题目:754. 到达终点数字
难度:普通
文章目录
- LeetCode每日一题系列
- 题目
- 示例
- 思路
- 题解
题目
在一根无限长的数轴上,你站在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 。
提示:
-109 <= target <= 109
target != 0
思路
数学问题, 这里target的值为正或负对结果无影响,这里取target的绝对值作为target,假设我们从0一直往前走,且能走到target或target之前,会遇到以下几种情况:
- 走n步刚好走到了target,这时n就是最终答案
- 走n步,超过了target偶数间距index,我们只需要将第index/2这一步往回走即可,这时n也是最终答案
- 走n步,超过了target奇数间距。1、继续向前走一步,如果间距为偶数则和第二种情况相同2、继续向前走一步,如果间距为奇数,那就再向前走一步,此时二者间距必为偶数(奇数+偶数+奇数=偶数),此时和第二种情况相同。
题解
class Solution:
def reachNumber(self, target: int) -> int:
# 目标取绝对值
target = abs(target)
# 步数和步长
step, n = 0, 0
# 当步长小于target或者间距为奇数时,一直往前走,直到间距为偶数时返回步长即可
while step < target or (step - target) % 2 != 0:
n += 1
step += n
return n