到达终点数字【LC754】
You are standing at position 0 on an infinite number line. There is a destination at position target.
You can make some number of moves numMoves so that:
- On each move, you can either go left or right.
- During the ith move (starting from i == 1 to i == numMoves), you take i steps in the chosen direction.
Given the integer target, return the minimum number of moves required (i.e., the minimum numMoves) to reach the destination.
在一根无限长的数轴上，你站在0的位置。终点在target的位置。
你可以做一些数量的移动 numMoves :
- 每次你可以选择向左或向右移动。
- 第 i 次移动（从 i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。
给定整数 target ，返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。
还好dp、递归写不出来，就直接看题解了，这不是我能想到的方法
- 思路
1.数轴上的任意点都以起点（0 点）对称，只需要考虑对称点的任意一边
左边所能到达任意一个点，都能通过调整所达路径的方向来将终点调整到右边。
2.先往靠近 target 的方向移动，到达或越过 target 的时候则停止
。若能直接到达 target，此时消耗的必然是最小步数，可直接返回；
。若越过了target，那么需要考虑是否需要增加额外步数到达target
3.我们假设需要调整的步数总和为tot，则有$ dist−2×tot=target，变形可得 ，变形可得，变形可得tot = \frac{dist - target}{2}$
。当tot为整数时，即$ dist−target$为偶数时，不需要引入额外步数，只需要将某些数反向即可
。当tot不为整数时，即$ dist−target$为奇数时，只能引入额外步数，继续往右走，使两者差值为偶数
- 实现
class Solution { public int reachNumber(int target) { while (target < 0){ target = -target; } int dis = 0; int i = 1; while (dis < target || (dis > target && (dis - target) % 2 == 1 ) ){ dis += i; i++; } return i - 1; } }
- 复杂度
。时间复杂度：O ( n )
。空间复杂度：O ( 1 )
- 代码优化：利用等差数列的性质，找到第一个S k > = t a r g e t
。等差数列前n项和计算公式
。当a 0 = 0 、 a 1 = 1 、当前步数为k、d=1时，
。首先找到第一个S k > = t a r g e t ，k = s q r t ( 2 ∗ t a r g e t ) ，此时移动的距离为S k
。代码
只需判断是否需要进行额外移动，额外移动最多4次
class Solution { public int reachNumber(int target) { if (target < 0) target = -target; int k = (int) Math.sqrt(2 * target) , dist = k * (k + 1) / 2; while (dist < target || (dist - target) % 2 == 1) { k++; dist = k * (k + 1) / 2; } return k; } }
。复杂度
- 时间复杂度：O ( 1 )
- 空间复杂度：O ( 1 )
