LeetCode刷题之路 到达终点数字

作者 : 开心源码 本文共1168个字,预计阅读时间需要3分钟 发布时间: 2022-05-12 共261人阅读

到达终点数字【简单】

题目形容

在一根无限长的数轴上,你站在0的位置。终点在target的位置。

每次你可以选择向左或者向右移动。第 n 次移动(从 1 开始),可以走 n 步。

返回到达终点需要的最小移动次数。

示例 1:

输入: target = 3输出: 2解释:第一次移动,从 0 到 1 。第二次移动,从 1 到 3 。

示例 2:

输入: target = 2输出: 3解释:第一次移动,从 0 到 1 。第二次移动,从 1 到 -1 。第三次移动,从 -1 到 2 。

注意:

  • target是在[-10^9, 10^9]范围中的非零整数。

解题思路

首先要明确一点的是target不论是是正数或者者是负数所走的步数都是一样的,无非就是把整式的左右两边都取反,比方说:1-2+3=2和-1+2-3=-2步数一样,所以我们全部按正数做。通过观察思考,我们可以得出:-1和1相差2,-2和2相差4,依此类推······我们就拥有了2~2n(步数为n)所有的偶数,如果我们每一步都走正值的话,直到步数之和sum比target大为止,而后用sum-target所得的结果假如为偶数的话,我们即可以通过调整前面几步的方向来抵消这个数,所以步数为n。但是,假如sum-target的结果为奇数呢?这样的话我们只要要看下一步能否为奇数步,假如为奇数步的话,用sum-tanget+(n+1)(也就是再走一步)的结果不就又是偶数,所以最终结果为n+1步。照这样的思路推下去,假如下一步为偶数步的话,则只要要再多走两步便可以使sum-target的结果又为偶数,所以最终结果是n+2步。

class Solution:    def reachNumber(self, target):        """        :type target: int        :rtype: int        """        sum = 0        n = 0        target = abs(target)        while(1):            if sum >= target:                if sum == target or (sum - target) % 2 == 0:                    return n                elif n % 2 == 0:                    return n + 1                else:                    return n + 2            n = n + 1                sum = sum + n
另一种解题思路

这种方法和第一种方法的思路大致一样,用等差数列求和 n(n+1)/2=target 反算出n,而后直接转换为整型去掉多余部分,就得到了一个最接近target的一个步数n。而后利用这个n直接求和,再进行累加判断,节省了资源。

class Solution:    def reachNumber(self, target):        """        :type target: int        :rtype: int        """        target = abs(target)        n = math.sqrt(2*target+0.25)-0.5;        n = int(n)        sum = (n*n+n)/2        while(sum < target or (sum - target) % 2 != 0):            n = n + 1            sum = sum + n        return n

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode刷题之路 到达终点数字

发表回复