【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;      }  };