題目

難度：★★☆☆☆
類型：數(shù)學(xué)

在一根無限長的數(shù)軸上，你站在0的位置。終點(diǎn)在target的位置。

每次你可以選擇向左或向右移動。第 n 次移動（從 1 開始），可以走 n 步。

返回到達(dá)終點(diǎn)需要的最小移動次數(shù)。

注意
target是在[-10^9, 10^9]范圍中的非零整數(shù)。

示例

示例 1
輸入: target = 3
輸出: 2
解釋:
第一次移動，從 0 到 1 。
第二次移動，從 1 到 3 。

示例 2
輸入: target = 2
輸出: 3
解釋:
第一次移動，從 0 到 1 。
第二次移動，從 1 到 -1 。
第三次移動，從 -1 到 2 。

解答

這道題分析思路比較重要。我們無法控制每次移動的步數(shù)，可以控制的是移動的方向。

首先，由于數(shù)軸的對稱性，到達(dá)target的數(shù)字與到達(dá)-target的數(shù)字是一樣的。我們可以默認(rèn)target是正數(shù)；

我們從1開始，第i次向右走i步，逐漸靠近target，第i步時(shí)運(yùn)動的位移s[i]=1+2+3+...+i，有以下幾種情況，舉例說明：

1. 走到第k步時(shí)恰好等于目標(biāo)值，1+2+3+...+k == target，例如，目標(biāo)值是6，1+2+3=6，到達(dá)終點(diǎn)之前走了3步；

2. 走到第k-1步時(shí)，s<target，但是走到第k步時(shí)，s>target，分兩種情況：
   （1）s[k] - target是個(gè)偶數(shù)，此時(shí)我們一定可以通過翻轉(zhuǎn)之前的步數(shù)，實(shí)現(xiàn)剛好到達(dá)target，到達(dá)target的數(shù)字依舊是k。例如，target=8，s[3]=1+2+3=6<8，而s[4]=1+2+3+4=10>8，s[4]-8=2，是一個(gè)偶數(shù)，我們翻轉(zhuǎn)一下第1步，s[4]_flip=-1+2+3+4=8，剛好到達(dá)目標(biāo)值8，這個(gè)要翻轉(zhuǎn)的數(shù)字實(shí)際上就是(s[k]-target)//2，感興趣的讀者可以自行證明；
   （2）s[k]-target是個(gè)奇數(shù)，我們需要再向右運(yùn)動一次，直到獲得的s[k]-target是個(gè)偶數(shù)（其實(shí)只需要再移動一次就夠了），這樣，我們就可以通過翻轉(zhuǎn)的形式獲得奇數(shù)。例如：target=7，1+2+3-4+5=7，target=16，1+2+3+4-5+6。通過再增加一個(gè)數(shù)，就可以構(gòu)造出奇數(shù)。

class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)
        s = 0
        i = 1
        while True:
            s += i
            if s >= target and (s - target) % 2 == 0:
                return i
            i += 1

如有疑問或建議，歡迎評論區(qū)留言~