到达终点数字

题目

在一根无限长的数轴上，你站在0的位置。终点在target的位置。

你可以做一些数量的移动 numMoves :

每次你可以选择向左或向右移动。
第 i 次移动（从 i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。
给定整数 target ，返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reach-a-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解

1. $target$可以根据对称性，只考虑为正。
2. 模拟这个过程，不停的往target点进行移动，直到超出范围。 超出部分，如果为偶数我们后撤；如果奇数，那么我们接着往前进行移动，使得超范围的步数为偶数，这个取决于我们之前的移动次数。
3. 推导：$x\ast (x+1)/2\ge target$,得到$x\ge \sqrt{(2\ast target+0.25)}-0.5$, 向上取整，然后，再分情况讨论。

import math
class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)
        t = math.ceil(math.sqrt(2*target + 0.25) - 0.5)
        cs = (t + 1) * t // 2
        delta = cs - target 
        return t if delta % 2 == 0 else t + (t & 1) + 1 
        
1
2
3
4
5
6
7
8
9