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