LeetCode 754. 到达终点数字

754. 到达终点数字

【贪心】分情况讨论，因为坐标轴都是对称的，直接对target取个绝对值，只考虑正方向即可，假设从1累加到n的和为sum：

1.sum == target，直接返回n即可。

2.如果（sum - target）% 2 == 0，那么把其中一个i取负数即可，例如差值为2，就把1取负数，差值为6，就把第3步取负数，还是返回n。

3.如果（sum - target）% 2 == 1，那么再走一步如果为差值为偶数了，就是n 1.

4.如果再走一步还没变成偶数，那再走一步必然是偶数了，因为相邻两个数必定一个奇数一个偶数，此时答案是n 2.

所以如果暴力的话，可以直接for循环个i，去找这个n。

1.  
   class Solution {
2.  
    
3.  
   // 10；52
4.  
    
5.  
   public int reachNumber(int target) {
6.  
   long sum = -Math.abs(target);
7.  
   int n = (int)1e5;
8.  
   for (int i = 1; i <= n; i ) {
9.  
   sum = i;
10.  
    if (sum >= 0 && sum % 2 == 0) return i;
11.  
    }
12.  
    return -1;
13.  
    }
14.  
    }

通过等差数列求和公式来优化 

1.  
   class Solution {
2.  
    
3.  
   // 4:45
4.  
    
5.  
   public int reachNumber(int target) {
6.  
   int t = Math.abs(target);
7.  
   int n = (int)Math.ceil((Math.sqrt(8 * (long)t 1) - 1)/ 2);
8.  
   long tmp = ((long)n 1) * n / 2 - t;
9.  
   if (tmp % 2 == 0) return n;
10.  
    if ((tmp n 1) % 2 == 0) return n 1;
11.  
    return n 2;
12.  
    }
13.  
    }

1.  
   class Solution {
2.  
    
3.  
   typedef long long ll;
4.  
    
5.  
   public:
6.  
   int reachNumber(int target) {
7.  
   ll t = abs(target);
8.  
   ll n = ceil((sqrt(1 8 * t) - 1) / 2);
9.  
   ll tmp = (n 1) * n / 2 - t;
10.  
    if (tmp % 2 == 0) return int(n);
11.  
    if ((tmp n 1) % 2 == 0) return int(n 1);
12.  
    return int(n 2);
13.  
    }
14.  
    };

这篇好文章是转载于：学新通技术网