【leetcode刷题】T212-到达终点数字

• 2019 年 12 月 23 日
• 筆記

木又连续日更第88天（88/100）

木又的第212篇leetcode解题报告

数学类型第28篇解题报告

leetcode第754题：到达终点数字

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

【题目】

在一根无限长的数轴上，你站在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是正数还是负数，所需要的最小步数是一样的，因此可以先将target取绝对值。

其次，我们可以先假设全向右移动，一步一步移动，即求1+2+…+n的和sum0=n * (n+1) / 2，如果sum0小于target，则再移动一次，再进行判断；否则，如果(sum0 – target) % 2 ！= 0，同样再移动一次；如果(sum0 – target) % 2 == 0， 那么(sum – target) / 2这一步改为向左移动，这样sum0刚好为target。

最后，有一个小trick，可以先求sqrt(target)，找到初始的n值，大量节省遍历时间。

【代码】

python版本

class Solution(object):      def reachNumber(self, target):          """          :type target: int          :rtype: int          """          target = abs(target)          n = int(math.sqrt(target))          diff =  n * (n + 1) / 2 - target          while diff < 0 or diff % 2 != 0:              n += 1              diff += n          return n  

C++版本

class Solution {  public:      int reachNumber(int target) {          target = abs(target);          int n = (int)sqrt(target);          int diff = n * (n + 1) / 2 - target;          while(diff < 0 || diff % 2 != 0){              n++;              diff += n;          }          return n;      }  };