到达终点数字-递归做法
在一根无限长的数轴上，你站在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 。
下面是一种递归做法，但是时间开销往往通过不了
int bfs(int x,int index,int n,int target){
int a,b;
// if(n>5) return 10000;
if(target ==x) return n;
else{
a=bfs(x+index,index+1,n+1,target);
b=bfs(x-index,index+1,n+1,target);
}
if(a>b)return b;
else return a;
}
int reachNumber(int target){
int n=bfs(0,1,0,target);
return n;
}
转化为对1，2，3，4，5…i,添加正负号，使得其和等于target的最小的数目。
设数组里面的正数的和为N，负数的和为-P，数组的和为S；
则N+P=S;
N-P=target;
则S-target=2N,S=(i*(i+1))/2;
因此就变为找找到最小的i,使得S>=target且S-target为偶数!!!
。
int reachNumber(int target){
target = abs(target);
int s, dt;
// 1+2+...+n求和公式Sn = n*(n+1)/2
// 由求和公式逆推得n = sqrt(2*Sn - 0.25) - 0.5
s = sqrt(2 * target + 0.25) - 0.5;
s += s * (s + 1)/2 < target? 1:0;
dt = s * (s + 1)/2 - target;
return dt % 2 == 0? s: s + 1 + s % 2;
}
