LC 754. Reach a Number

https://leetcode.com/problems/reach-a-number/

这个 解答 不错，我们可以观察到在第n步的时候可以到达的点

0:                                                           0
1:                                                       -1   1
2:                                                -3   -1   1  3
3:                                  -6     -4     -2   0   2   4   6
4:                   -10   -8 -6   ............................6   8  10
5:-15 -13 -11..................................................9   11  13  15

• 到达的节点是奇偶交替的，奇奇偶偶如此
• n%4=1, n%4=2 是奇数位置
• n%4=3, n%4=0 是偶数位置
• 为了到达target, 最快需要行走 n(n+1)//2>=target

所以策略就是先到达target附近，然后去寻找对应奇偶点。

class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)

        # (n + 1) * n // 2 <= target
        n = int(((1 + 8 * target) ** 0.5 - 1) // 2)
        while (n + 1) * n // 2 < target:
            n += 1

        if target % 2 == 0:
            while n % 4 != 0 and n % 4 != 3:
                n += 1
        else:
            while n % 4 != 1 and n % 4 != 2:
                n += 1
        return n