LeetCode每日一题——754. 到达终点数字

LeetCode每日一题系列

题目：754. 到达终点数字
难度：普通

---

---

题目

在一根无限长的数轴上，你站在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
1
2
3
4
5
6
7
8
9
10
11