leetcode 754. Reach a Number 到达终点数字-耗时100%

Problem: 754. Reach a Number 到达终点数字

解题过程

耗时100%

通过观察下面的式子，可以发现可以向左移动多次，而且每次向左移动，相当于向右少移动偶数次， 1 - 2 + 3 = 1+2+3 - 2*2，

-1+2+3 = 1+2+3 - 1 * 2 ，

1 + 2 + 3 + 4 - 5 = 1 + 2 + 3 + 4 + 5 - 2 * 5

所以向左移动相当于减去一个偶数，所以最后的结果是 1+2+3+。。。+k - 偶数= (1+k)*k/2 - 偶数

答案首先找到满足条件的不需要减去的数字，然后找到累加和>target的n，奇数-偶数=奇数，偶数-偶数=偶数，所以 被减数 和 差 的奇偶性相同，不满足的话n++

而且被减去的偶数，一定可以通过1，2，。。。，k这些数字凑出来，具体的可以翻看官方题解的

就像12: 1 + 2 - 3 + 4 - 5 + 6 + 7，偶数可以通过-3 -5凑出来

// 1-2+3 2 // 1+2 3 // -1+2+3 4 // 1 + 2 + 3 + 4 - 5 5 // 1 + 2 + 3 6 // 1 + 2 + 3 - 4 + 5 7 // 1 + 2 - 3 + 4 - 5 + 6 + 7 12

Code

class Solution { public: int reachNumber(int target) { // 1-2+3 2 // 1+2 3 // -1+2+3 4 // 1 + 2 + 3 + 4 - 5 5 // 1 + 2 + 3 6 // 1 + 2 + 3 - 4 + 5 7 // 1 + 2 - 3 + 4 - 5 + 6 + 7 12 target = abs(target); int n = sqrt( (double)( target * 2 ) ); double f1 = n * (n+1) / 2.0f; double f2 = (n+1) * (n+2) / 2.0f; if(f1==(double)target) { return n; } if(f2==(double)target) { return n+1; } while(f1 < target) { n++; f1 = n * (n+1) / 2.0f; } while( true ) { int l = 2, r = n * 2, mid, sum; sum = n * (n + 1) / 2; // while(l <= r) { // mid = (l + r) / 2; // if(sum - mid==target && (mid%2==0)) return n; // if(l==r) break; // if(sum - mid < target) { // r = mid-1; // } else { // l = mid+1; // } // } if(sum%2==1 && target%2==0) { n++; continue; } else if(sum%2==0 && target%2==1) { n++; continue; } else { return n; } } return 0; } };