[LeetCode] 754. Reach a Number

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:

Input: target = 3
Output: 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.

Example 2:

Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step  from 1 to -1.
On the third move we step from -1 to 2.

Note:

  • target will be a non-zero integer in the range [-10^9, 10^9].

到达终点数字。

在一根无限长的数轴上,你站在0的位置。终点在target的位置。

每次你可以选择向左或向右移动。第 n 次移动(从 1 开始),可以走 n 步。

返回到达终点需要的最小移动次数。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reach-a-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这是一道数学题。你在一根无限长的数轴上,试图去接近一个target值。既然你既可以往左移动也可以往右移动,而且target也有可能是负数,所以我们这里先对target取绝对值,方便计算。target取了绝对值之后,宏观上意味着你是需要从0的位置往右走,可能你无法直接到达target点,所以中间有可能会夹杂着几步往左的移动。而且移动的步数step和你移动的次数 N 是相关的,即你在第 N 次移动的时候,可以移动 N 步。所以我们一开始计算这个累加和,得到你前 N 步往右移动一共能移动多少距离,记为 sum,一直累加,使得 sum > target。如果 sum 大于 target 了,分如下两种情况

  • 如果 sum - target 是偶数,则步数不变,说明你在走到第 (sum - target) / 2 步的时候,是需要往左移动的。举例,比如sum和target的差值是4的话,说明如果一开始你在走第二步的时候是往左走的话,就能正好走到target位置。差值为4说明你向右多走了4步,那么把走两步的那个动作改为向左走即可
  • 如果sum - target是奇数,则需要再累加,直到这个差值是奇数

这个题一开始我试图用BFS做,但是遇到特别大的case是会超时的。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int reachNumber(int target) {
 3         target = Math.abs(target);
 4         int step = 0;
 5         int sum = 0;
 6         // 不断逼近target
 7         while (sum < target) {
 8             step++;
 9             sum += step;
10         }
11 
12         // 如果超过target了但是sum和target的差值是奇数的话,需要再加,确保差值是偶数
13         while ((sum - target) % 2 != 0) {
14             step++;
15             sum += step;
16         }
17         return step;
18     }
19 }

 

LeetCode 题目总结

上一篇:2021-02-20


下一篇:剑指offer65-机器人的运动范围