到达终点数字
难度:
标签:
题目描述
代码结果
运行时间: 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`取绝对值是合理的,这对结果有什么影响?
▷🦆
你如何确定二分查找的初始右边界`r`为`target + 1`,这样的设置是否总是足够覆盖所有可能的情况?
▷🦆
在二分查找的过程中,为何选择`(mid + 1) * mid // 2`作为从1到mid的和的计算公式,这里`+1`的目的是什么?
▷🦆
题解中提到如果`(sm - target) % 2 == 0`则可以直接返回`r`,否则根据`r`的奇偶性增加步骤。能否详细解释这种情况下为什么需要考虑`r`的奇偶性?
▷