Link: 754. Reach a Number
先解释题目, 给定一个坐标轴然后在坐标轴上左右移动, 第 n 步移动的时候可以向左或者向右移动 n, 给定一个目标 target, 求出移动到目标位置所需要的最小步数.
一开始看到这道题的时候, 我是想到用动态规划来做, 因为根据第 n 步可以移动到的位置, 我们分别加减 n+1, 就可以得到所有第 n+1 步可以达到的位置, 但是题目描述中 target 的范围是 -10^9-10^9, 这样粗暴的 dp 最后肯定会因为规模太大超时.
我们尝试另一个思路, 假设我们每一步都向右移, 那么到第 n 步的时候, 能够获得的最大值, 其实就是 1+2+3+...+n 也就是 (n + n * n) / 2
, 如果 target 为正数并且大于这个值, 那么第 n 步是无论如何都无法到到达 target 的, 有这个前提的话我们可以整理出两种情况:
至于复数的情况, 因为每一步都可以左右移动, 所以需要的步数应该是和其绝对值所需要的步数一致.
根据以上的分析, 代码如下:
/**
* @param {number} target
* @return {number}
*/
var reachNumber = target => {
target = Math.abs(target);
for (let n = 1; true; n++) {
const sum = (n + n * n) / 2;
if (sum === target || (sum > target && 0 === (sum - target) % 2))
return n;
}
};
Copyright © 2022 - xhu - Powered by Gin, jQuery, Animate.css