754. 到达终点数字
题目:
在一根无限长的数轴上,你站在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
来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/reach-a-number 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路:
?
这道题分为以上四种情况,主要是要看当超出目标点后,距离目标点的距离
如果距离是偶数,那就之前先提前多走一步就行了。
如果是奇数,那也多走一步,如果变成了偶数,那就变为了上面的情况,证明再多走一次就行了
如果相距还是奇数,那就再多走一步,只带变为偶数即可。
换句话说,其实当变成偶数的时候,因为你多走一步才超过目标点,所以这多的一步就已经算进了偶数多走的那一步里面了。
当时奇数的时候,我们只需要让他多加一次就行了。
代码:
class Solution {
public:
int reachNumber(int target) {
target = abs(target);
int s = 0, n = 0;
while(s < target || (s - target) %2)
s += ++n;
return n;
}
};
|