0754._Reach_a_Number.md

754. Reach a Number

难度: Easy

刷题内容

原题连接

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

内容描述

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:
Input: target = 3
Output: 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.
Example 2:
Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step  from 1 to -1.
On the third move we step from -1 to 2.
Note:
target will be a non-zero integer in the range [-10^9, 10^9].

解题方案

思路 1 - 时间复杂度: O(sqrt(target))- 空间复杂度: O(1)******

首先如果target是负数，我们同样可以用正数来做，结果是一样的

想象一下 S = 1 + 2 + ... + k >= target

• 如果S = target，那答案肯定就是k
• 如果S - target 是偶数，那么我们肯定可以通过将 (S - target) / 2 这个数字取负号使得S = target，那么答案还是k
• 如果S - target 是奇数，那么我们就无法通过将 (S - target) / 2 这个数字取负号使得S = target了， 因为(S - target) / 2都不是整数了。那么我们就试着让 S2 = 1 + 2 + ... + k + (k+1)， 然后看看S2 - target是奇数还是偶数，
  • 如果是偶数，直接返回k+1
  • 如果是奇数，我们又要试一下k+2了 但是到k+2的时候肯定可以满足条件了，根据k的奇偶性就可以知道答案是谁了
  • 如果k是偶数，因为前面k没有满足，加上k+1之后S2 - target肯定就是偶数了，答案是k+1
  • 如果k是奇数，因为前面k没有满足，加上k+1还是没有满足，加上k+2之后S2 - target肯定就是偶数了，答案是k+2

class Solution:
    def reachNumber(self, target):
        """
        :type target: int
        :rtype: int
        """
        target = abs(target)
        
        k = 0
        while target > 0:
            k += 1
            target -= k

        return k if target % 2 == 0 else k + 1 + k % 2