LeetCode Algorithm 754 Reach a Number

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 的, 有这个前提的话我们可以整理出两种情况:

1. 累加和等于 target : 这样直接返回当前的步数 n 即可;
2. 累加和大于 target : 这样想达到 target 的话, 肯定在移动过程中出现了左移, 假设我们在第 i 步进行了左移, 那么最终结果相比于最大值其实是减小了 i*2, 也就是说, 这时候累加和与 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;
  }
};