LeetCode 0754. 到达终点数字

【LetMeFly】754.到达终点数字

力扣题目链接：https://leetcode.cn/problems/reach-a-number/

在一根无限长的数轴上，你站在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

方法一：枚举

如果$target<0$，那么我们就对$target$取个绝对值，因为走到$-100$和$100$所需的步数是一样的

这样，我们就可以先头也不回地往右走，直到恰好走到$target$或超过$target$一两步为止

假设我们走了$n$步，那么总距离就是$result=\frac{n\times (n+1)}{2}$

我们超过了$target$共$result-target$，因此在这$n$步中，我们希望有其中某步是往左的。

假设第$i$步往左，那么我们$n$步的总距离就是$result-2\times i$

也就是说往左一步比一直往右少走的距离一定是偶数。

因此，我们只需要在$result\ge target$且$result-target$不为偶数时，不断往右走

好了，现在我们超过$target$共$result-target$，怎么办呢？我们将往右走的过程中，第$\frac{result-target}{2}$步改成向左走不就行了么？

问题解决。

有的同学可能不相信，那咱就举例说明一下。

假设目标距离是$2$：

1. $1=1<2$
2. $1+2=3>2$，但$(1+2)-2=1$是奇数
3. $1+2+3=6>2$且$(1+2+3)-2=4$是偶数

因此，我们只需要将第$\frac{4}{2}=2$步修改为向左走，总行走距离就变成了$1-2+3=2$。

这得益于几个条件：

1. 将target取绝对值后，模板在原点或原点的右边，我们要尽可能地多往右走
2. 如果一直往右走不能恰好到达$target$，那么就一定要往左走“数次”
3. “往左一次”只能比“全部往右”少走偶数的距离，这就导致了“把其中某一步”改为往左不一定能正好走到$target$
4. 假设这次超过$target$奇数的距离，那么再往前走一步，一定会超过$target$偶数的距离（这是因为我们是奇偶交替走的，总距离也是奇偶交替的），因此超过$target$后最多再往前走一步，就能“将之前某一步改为向左以恰好达到target”（$\frac{result-target}{2}$一定不大于$n$）

总之，头也不回地往右走，直到超过$target$偶数的距离（或恰好位于$target$），修改历史某步为向左（不消耗步数），返回当前步数即可

• 时间复杂度$O(\sqrt{|target|})$（注意这里是“根号下target的绝对值”，目前力扣新版UI中无法正常显示\sqrt）
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int reachNumber(int target) {
        unsigned to = abs(target);
        unsigned n = 0;
        while (true) {
            unsigned result = n * (n + 1) / 2;
            if (result >= to && (result - to) % 2 == 0)
                return n;
            n++;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

方法二：基于方法一的小优化

方法一中我们从$1$开始“枚举”了步数$n$找到了$\frac{n\times (n+1)}{2}\ge target$且$\frac{n\times (n+1)}{2}-target$为偶数的最小$n$

这导致时间复杂度为$\log target$

但是，$\frac{n\times (n+1)}{2}$恰好略大于$target$，这就说明$n$约等于$\sqrt{target\times 2}$

因此我们从$\sqrt{target\times 2}-2$开始枚举$n$就好了，大约不出$5$次就能找到答案。

• 时间复杂度$O(1)$（CPU有专门的计算平方根的指令，aqrt()的复杂度可以视作是$O(1)$）
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int reachNumber(int target) {
        unsigned to = abs(target);
        unsigned simN = max((int)sqrt(to * 2) - 2, 0);
        while (true) {
            unsigned result = simN * (simN + 1) / 2;
            if (result >= to && (result - to) % 2 == 0)
                return simN;
            simN++;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

执行结果确实快了点

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127684453