lintcode 797. 到达一个数字

你站在一个无穷数轴上的 0 位置。在位置目标上有一个目标。
在每一个动作中,你可以向左或向右。在第n次移动中(从1开始),你行走n步。
返回到达目的地所需的最小步骤数。

样例
样例1

输入: target = 3
输出: 2
解释:
在第一步,我们从0到1。
在第二步,我们从1到3。
样例2

输入: target = 2
输出: 3
解释:
在第一步,我们从0到1。
在第二个步骤中,我们从1到-1。
在第三步,从-1到2。
注意事项
目标将是一个非零的整数范围[-10^9, 10^9]。

思路:先将数加到大于目标数,并得到当前步数。
1、如果步数和刚好为目标数,则直接返回步数。如6=1+2+3.
2、如果步数-目标数为偶数,如目标数为4,而6=1+2+3.此时可以得到二者差值为6-4=2。差值的一半为1,把差值一半变为-即可得到,即4=-1+2+3.故答案仍旧为第一次大于目标数的步数。
3、如果步数-目标为奇数,且步数为偶数,如目标数为20,21=1+2+3+4+5+6,此时需要加上一个奇数,21+7=28为偶数,减去目标数为偶数,再重复步骤二,故答案为步数+1.
4、如果步数-目标数为奇数,且步数为奇数,如目标数12,15=1+2+3+4+5,同理此时应该加上下一个偶数和下下一个奇数使其和目标数之差为偶数,再重复步骤二,故答案为步数+2.

class Solution {
public:
    /**
     * @param target: the destination
     * @return: the minimum number of steps
     */
    int reachNumber(int target) {
        // Write your code here
       int sum=0;
       int temp=1;
       target=abs(target);
       while(sum<target)
       {
           sum+=temp++;
       }
       temp--;
       if(sum==target) return temp;
       sum-=target;
       if(sum%2==0) return temp;//如果二者差为偶数,这只需要在大于的基础上直接减掉一个数即可
       else if(temp%2==0) return temp+1;//两者差为奇数,且step为偶数,则在原基础上加下一个,并将二者差值/2减去
       else return temp+2;//如果step为奇数,则应该先增加一个再减去一个,再同上一个办法。
    }
};
上一篇:【SpringMVC笔记整理八】表单标签库


下一篇:Model ModelMap ModelView三者的区别你造吗