Python3解leetcode Reach a Number

问题描述:

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

 

上一篇:CF1024E Natasha, Sasha and the Prefix Sums——DP/数学(组合数)


下一篇:python7.4.2二叉树路径问题及LeetCode题目解析