到达终点数字（754,leetcode技巧题）-------------------c++实现

到达终点数字（754,leetcode技巧题）-------------------c++实现

题目表述

在一根无限长的数轴上，你站在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 。

条件

-109 <= target <= 109
target != 0

思路

一直往一个方向奔赴即可，当走到最后一步超过了target时，
1.这时候如果多走了偶数步，则多走的步数/2一定是走过的步数，取反就行.
2.如果是奇数步，则可以看看再下一步是否能把多走的步数变成偶数步，变不成那就再下一步往返走，这时肯定是多余偶数步(有可能是0步).

注意点

注意总步数的奇数偶数变化以及步数的奇偶数变化

太久没做过这么高的排名了

ac代码

c++:

class Solution {
public:
    int reachNumber(int target) {
     int sum=0,result;
     if(target<0)
     target=(0-target);

     for(int i = 1;i<10000000;i++)
     {
         sum+=i;
         if(sum>=target)
         {   if(sum==target)
             return i;
            result = i;
            break;
             }   //走到超过 target的位置
     }
   if((sum-target)%2)//比target多了奇数步(偶数步则直接变(sum-target)/2步为负就行)，则下一步如果是奇数步，则只走一步(变偶)，如果是偶数步则走两步（两步变偶）
        {
            if((result+1)%2)
            result+=1;
            else
            result+=2;
        }

     return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reach-a-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。