到达终点数字【简单】
题目描述
在一根无限长的数轴上，你站在0的位置。终点在target的位置。
每次你可以选择向左或向右移动。第 n 次移动（从 1 开始），可以走 n 步。
返回到达终点需要的最小移动次数。
示例 1:
输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。
示例 2:
输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。
注意:
-
target是在[-10^9, 10^9]范围中的非零整数。
解题思路
首先要明确一点的是target不管是是正数或者是负数所走的步数都是一样的，无非就是把整式的左右两边都取反，比如说：1-2+3=2和-1+2-3=-2步数一样，所以我们一律按正数做。通过观察思考，我们可以得出：-1和1相差2，-2和2相差4，依此类推······我们就拥有了2~2n(步数为n)所有的偶数，假如我们每一步都走正值的话，直到步数之和sum比target大为止，然后用sum-target所得的结果如果为偶数的话，我们就可以通过调整前面几步的方向来抵消这个数，所以步数为n。但是，如果sum-target的结果为奇数呢？这样的话我们只需要看下一步是否为奇数步，如果为奇数步的话，用sum-tanget+（n+1）（也就是再走一步）的结果不就又是偶数，所以最终结果为n+1步。照这样的思路推下去，如果下一步为偶数步的话，则只需要再多走两步便可以使sum-target的结果又为偶数，所以最终结果是n+2步。
class Solution:
def reachNumber(self, target):
"""
:type target: int
:rtype: int
"""
sum = 0
n = 0
target = abs(target)
while(1):
if sum >= target:
if sum == target or (sum - target) % 2 == 0:
return n
elif n % 2 == 0:
return n + 1
else:
return n + 2
n = n + 1
sum = sum + n
另一种解题思路
这种方法和第一种方法的思路大致一样，用等差数列求和 n(n+1)/2=target 反算出n，然后直接转换为整型去掉多余部分，就得到了一个最接近target的一个步数n。然后利用这个n直接求和，再进行累加判断，节省了资源。
class Solution:
def reachNumber(self, target):
"""
:type target: int
:rtype: int
"""
target = abs(target)
n = math.sqrt(2*target+0.25)-0.5;
n = int(n)
sum = (n*n+n)/2
while(sum < target or (sum - target) % 2 != 0):
n = n + 1
sum = sum + n
return n
