0754. 到达终点数字 · ttttt

# 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">``` class Solution(object): def reachNumber(self, target): target = abs(target) steps = 0 while target > 0: steps += 1 target -= steps if target & 1 == 0: return steps steps += 1 if (target - steps) & 1 == 0: return steps return steps + 1 ``` ``` ## 相关题目 - [494.target-sum](https://github.com/azl397985856/leetcode/blob/master/problems/494.target-sum.md)