<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 0754. 到達終點數字 ## 題目地址(754. 到達終點數字) <https://leetcode-cn.com/problems/reach-a-number/> ## 題目描述 ``` <pre class="calibre18">``` 在一根無限長的數軸上,你站在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]范圍中的非零整數。 ``` ``` ## 前置知識 - 數學 ## 公司 ## 思路 不難看出, 問題的本質就是一個有限序列, 1,2,3,4... 。我們的目標是給這個序列的元素添加正負號,是的其和為 target。這和 494.target-sum 的思路是一樣的。 拿題目的 target = 3 來說, 就是 1 + 2 = 3。 拿題目的 target = 2 來說, 就是 1 - 2 + 3 = 2。 為什么是有限序列? 因為我們始終可以在 target 次以內走到 target。嚴格來說, 最少在根號 target 左右就可以走到 target。 和 494.target-sum 不同的是, 這道題數組是無限的,看起來似乎更難,實際上更簡單, 因為數組是有規律的,每次都遞增 1。 > 由于 target 正負是對稱的, 因此 target 最少走多少布,-target 也是多少步。因此我們只考慮一種情況即可, 不妨只考慮正數的情況。 其實,只要找出第一個滿足 1 + 2 + 3 + .... + steps > target 的 steps 即可。 - 如果 steps 是偶數, 那么我們總可以找出若干數字使其變為符號,滿足 1 + 2 + 3 + .... + steps == target - 如果 steps 是奇數, 1 + 2 + 3 + .... + steps + steps + 1 或者 1 + 2 + 3 + .... + steps + steps + 1 + steps + 2 中有且僅有一個是偶數。我們仍然可以套用上面的方法,找出若干數字使其變為符號,滿足 1 + 2 + 3 + .... + steps + steps + 1 == target 或者 1 + 2 + 3 + .... + steps + steps + 1 + steps + 2 == target ## 關鍵點解析 - 對元素進行分組,分組的依據是符號, 是`+` 或者 `-` - 通過數學公式推導可以簡化我們的求解過程,這需要一點`數學知識和數學意識` ## 代碼(Python) Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">reachNumber</span><span class="hljs-params">(self, target)</span>:</span> target = abs(target) steps = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> target > <span class="hljs-params">0</span>: steps += <span class="hljs-params">1</span> target -= steps <span class="hljs-keyword">if</span> target & <span class="hljs-params">1</span> == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> steps steps += <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> (target - steps) & <span class="hljs-params">1</span> == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> steps <span class="hljs-keyword">return</span> steps + <span class="hljs-params">1</span> ``` ``` ## 相關題目 - [494.target-sum](https://github.com/azl397985856/leetcode/blob/master/problems/494.target-sum.md)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看