leetcode
leetcode 651 ~ 700
到达终点数字

到达终点数字

难度:

标签:

题目描述

代码结果

运行时间: 26 ms, 内存: 16.0 MB


/*
题目思路:
在 Java Stream 中,我们可以利用 IntStream 生成一个无限流,然后通过 limit 和 iterate 操作实现步数的累加。为了达到目标 target,我们需要找到一个最小的 numMoves,使得 numMoves 次移动的总步数与 target 的距离一致。
*/
import java.util.stream.IntStream;

public class Solution {
    public int reachNumber(int target) {
        target = Math.abs(target);
        return IntStream.iterate(1, i -> i + 1) // 从 1 开始,每次步数增加 1
                .limit(Integer.MAX_VALUE) // 无穷大限制
                .filter(sum -> (sum * (sum + 1) / 2) >= target && ((sum * (sum + 1) / 2) - target) % 2 == 0) // 判断条件
                .findFirst()
                .orElse(0);
    }
}

解释

方法:

这个题解使用了二分查找的方法来寻找最小的移动次数。首先,将目标值 target 取绝对值,因为向左和向右移动是对称的,所以只需要考虑非负的情况。接着使用二分查找来寻找一个数 r,使得从 1 到 r 的和大于等于 target。这个和可以用公式 (1 + r) * r // 2 来计算。最后,检查从 1 到 r 的和是否与 target 相等,或者它们的差是偶数。如果是,那么 r 就是答案。如果不是,那么需要额外的一步或两步来达到 target,具体取决于 r 是奇数还是偶数。

时间复杂度:

O(log(target))

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在二分查找算法中将目标值`target`取绝对值是合理的,这对结果有什么影响?
在这个问题中,无论是向左还是向右移动,都可以看作是向目标值的正或负方向逼近。因此,目标值的正负并不影响最终需要的步数,只是方向不同。将`target`取绝对值是为了简化问题,只考虑从0到正数的情况,这样做可以不用分别处理正负两种情况,从而简化代码和逻辑。
🦆
你如何确定二分查找的初始右边界`r`为`target + 1`,这样的设置是否总是足够覆盖所有可能的情况?
设置初始右边界`r`为`target + 1`是基于从1到`r`的和至少需要达到`target`的考量。由于数列1到`r`的和是递增的,`target + 1`确保在最坏情况下,即`target`正好是从1到`r`的和时,二分查找不会错过可能的正确答案。在实际应用中,这个设置通常是足够的,因为它保证了右边界初始时一定大于或等于所需的最小`r`值。
🦆
在二分查找的过程中,为何选择`(mid + 1) * mid // 2`作为从1到mid的和的计算公式,这里`+1`的目的是什么?
公式`(mid + 1) * mid // 2`是等差数列求和公式的应用,计算的是从1到`mid`的整数和。这里`+1`是因为等差数列的公式通常形式为`(首项 + 末项) * 项数 / 2`,在这里首项是1,末项是`mid`,项数是`mid`。因此,`(mid + 1)`是首项加末项,`mid`是项数,整个公式计算的是1到`mid`的整数和。
🦆
题解中提到如果`(sm - target) % 2 == 0`则可以直接返回`r`,否则根据`r`的奇偶性增加步骤。能否详细解释这种情况下为什么需要考虑`r`的奇偶性?
当`(sm - target) % 2 == 0`时,表示从1到`r`的和与目标值`target`之间的差可以通过改变某些步骤的方向(即将部分正向步骤改为负向)来精确抵消。这是因为每次改变一个数的方向,等于在总和中减去这个数的两倍。只有当这个差是偶数时,才可能通过整数次的方向改变达到目标。如果差是奇数,无法通过简单的方向改变达到平衡,此时需要考虑`r`的奇偶性。如果`r`是奇数,再加一步可以使得总和变化的差也是偶数,从而可能通过方向改变满足条件;如果是偶数,可能需要更多步骤调整。

相关问题