【114】

754. 到达终点数字  

在一根无限长的数轴上，你站在0的位置。终点在target的位置。

你可以做一些数量的移动 numMoves :

• 每次你可以选择向左或向右移动。
• 第 i 次移动（从  i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。

给定整数 target ，返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。

示例 1:

输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。

示例 2:

输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。
------------------------------------------------------------------------------------------------
仅仅考虑了单向移动，没有抓住问题的本质是一个求和问题

 1 class Solution {
 2     public int reachNumber(int target) {
 3         int numMoves = 0;
 4         int begin = 0;
 5         if(target > 0){
 6             for(int i = 1; begin != target; i++){
 7                 if(i == Math.abs(target-begin)){
 8                     numMoves++;
 9                     break;
10                 }else if(i < Math.abs(target-begin)){
11                     begin+=i;
12                     numMoves++;
13                 }else{
14                     begin-=i;
15                     numMoves++;
16                 }
17             }
18         }
19         if(target < 0){
20             for(int i = 1; begin != target; i++){
21                 if(i == Math.abs(target-begin)){
22                     numMoves++;
23                     break;
24                 }else if(i < Math.abs(target-begin)){
25                     begin-=i;
26                     numMoves++;
27                 }else{
28                     begin+=i;
29                     numMoves++;
30                 }
31             }
32         }
33         return numMoves;
34     }
35 }

------------------------------------------------------------------------------------------------
这道题的本质问题是一个求和问题，从1开始累加，给自然数加上符号表示向左或者向右移动，最后累加的结果就是 target 。
例如：1 = 1, 2 = 1+（-2）+3， 3 = 1+2， 4 = （-1）+2+3， 5 = 1+2+3+4+（-5）， 6 = 1+2+3.
7 = 1+2+3+（-4）+5因此只用考虑单侧方向，到达1和-1过程的区别只有后边的符号不同。

 1 class Solution {
 2     public int reachNumber(int target) {
 3         int numMoves = 0;
 4         int place = 0;
 5         int step = 1;
 6         target = Math.abs(target);
 7         while(place < target){
 8             place+=step;
 9             step++;
10             numMoves++;
11         }
12         if((place-target) % 2 == 0){
13             return numMoves;
14         }else{
15             while((place-target) % 2 != 0){
16                 place+=step;
17                 step++;
18                 numMoves++;
19             }
20         }
21         return numMoves;
22         
23     }
24 }

又简化了下代码

 1 class Solution {
 2     public int reachNumber(int target) {
 3         int numMoves = 0;
 4         int place = 0;
 5         int step = 1;
 6         target = Math.abs(target);
 7         while(place < target || (place-target) % 2 != 0){
 8             place+=step;
 9             step++;
10             numMoves++;
11         }
12         return numMoves;
13         
14     }
15 }

------------------------------------------------------------------------------------------------
答案的题解，思路大致一致，只不过代码更简单

 1 class Solution {
 2     public int reachNumber(int target) {
 3         target = Math.abs(target);
 4         int k = 0;
 5         while (target > 0) {
 6             k++;
 7             target -= k;
 8         }
 9         return target % 2 == 0 ? k : k + 1 + k % 2;
10     }
11 }
12 
13 作者：力扣官方题解
14 链接：https://leetcode.cn/problems/reach-a-number/solutions/1946020/dao-da-zhong-dian-shu-zi-by-leetcode-sol-ak90/
15 来源：力扣（LeetCode）
16 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。