问题描述:
You are standing at position 0
on an infinite number line. There is a goal at position target
.
On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.
Return the minimum number of steps required to reach the destination.
Example 1:
Input: target = 3 Output: 2 Explanation: On the first move we step from 0 to 1. On the second step we step from 1 to 3.
Example 2:
Input: target = 2 Output: 3 Explanation: On the first move we step from 0 to 1. On the second move we step from 1 to -1. On the third move we step from -1 to 2.
Note:
-
target
will be a non-zero integer in the range[-10^9, 10^9]
.
思路:
这道题让我们从起点0开始,每次可以向数轴的左右两个方向中的任意一个走,第一步走距离1,第二步走距离2,以此类推,第n步走距离n,然后给了我们一个目标值 target,问我们最少用多少步可以到达这个值。
最开始想的是用贪婪算法来做,就是如果加上距离大于目标值的话,就减去这个距离,到是当目标值是4的话,贪婪算法会fail。
一般贪婪算法不行的话,很自然的就会想想能否用DP来做,但这道题感觉很难很难重现为子问题,因为每一步走的步数都不一样,这个步数又跟最小步数息息相关,所以很难写出状态转移方程啊,只得放弃。
其实这道题的正确解法用到了些数学知识,还有一些小 trick,首先来说说小 trick,第一个 trick 是到达 target 和 -target 的步数相同,因为数轴是对称的,只要将到达 target 的每步的距离都取反,就能到达 -target。下面来说第二个 trick,这个是解题的关键,比如说目标值是4,那么如果我们一直累加步数,直到其正好大于等于target时,有:
0 + 1 = 1
1 + 2 = 3
3 + 3 = 6
第三步加上3,得到了6,超过了目标值4,超过了的距离为2,是偶数,那么实际上我们只要将加上距离为1的时候,不加1,而是加 -1,那么此时累加和就损失了2,那么正好能到目标值4,如下:
0 - 1 = -1
-1 + 2 = 1
1 + 3 = 4
那么,我们的第二个 trick 就是,当超过目标值的差值d为偶数时,只要将第 d/2 步的距离取反,就能得到目标值,此时的步数即为到达目标值的步数。
那么,如果d为奇数时,且当前为第n步,那么我们看下一步 n+1 的奇偶,如果 n+1 为奇数,那么加上 n+1 再做差,得到的差值就为偶数了,问题解决,如果 n+1 为偶数,那么还得加上 n+2 这个奇数,才能让差值为偶数,这样就多加了两步。
那么,我们的第三个 trick 就是,可以利用求和公式,直接求出当前的n和对应的sums,在当前n和sums的基础上进行判断,这样可以大大减少前期累加的时间,提高效率
代码:
1 class Solution: 2 def reachNumber(self, target: int) -> int: 3 target , sums = abs(target) , 0 4 n = int(math.sqrt(2*target)) 5 sums = ((n + 1)*n)/2 6 7 while True: 8 if sums > target: 9 if (sums - target) % 2 : 10 if (n + 1) % 2: 11 return n + 1 12 else: 13 return n + 2 14 else: 15 return n 16 elif sums == target: 17 return n 18 n += 1 19 sums += n