到达终点数字[简单]
题目描述
在一根无限长的数轴上, 你站在 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
来源: http://www.jianshu.com/p/53f76e9636fb