前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >图解LeetCode——754. 到达终点数字(难度:中等)

图解LeetCode——754. 到达终点数字(难度:中等)

作者头像
爪哇缪斯
发布2023-05-10 11:53:38
1980
发布2023-05-10 11:53:38
举报
文章被收录于专栏:爪哇缪斯

一、题目

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

你可以做一些数量的移动 numMoves :

  • • 每次你可以选择向左或向右移动。
  • • 第 i 次移动(从 i == 1 开始,到 i == numMoves ),在选择的方向上走 i 步。

给定整数 target ,返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。

二、示例

2.1> 示例 1:

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

2.2> 示例 2:

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

提示:

  • -10^9 <= target <= 10^9
  • target != 0

三、解题思路

其实题目描述得有点不好理解。题意其实就是如下两个因素:

移动的方向】可以向左走或者向右走行走的步长】第 i 步移动的距离就是 i

  • • 第1步,移动距离是1
  • • 第2步,移动距离是2
  • • ……
  • • 第20步,移动距离是20

理解了题意之后,我们就来思考一下,如何计算到达 target 所需的 最小 移动次数(numMoves) 。我们可以针对target的值做如下2种假设:

假设1】向一个方向(向左 or 向右)移动numMoves次,正好可以到达target。 【假设2】向两个方向(向左 and 向右)移动numMoves次,才能到达target

“假设1”这种情况其实很好处理,我们再此就不再赘述了。主要问题是如何去处理“假设2”的这种情况,有什么好的计算办法或者规律吗? 其实是有的。具体规律如下图所示:

由于2*A一定是偶数,所以找到了这个规律后,我们就可以首先只朝一个方向移动(由于target会有负数的情况,所以为了统一计算方式,我们将target取绝对值即可,即:t = Math.abs(target)),只有当移动的总距离 num 的值大于等于 t (target的绝对值),并且 numt偶数,才表示当前情况满足题目要求,即:满足到达 target 所需的最小移动次数。具体代码实现,请见如下部分内容。

四、代码实现

代码语言:javascript
复制
class Solution {
    public int reachNumber(int target) {
        int result = 0, num = 0, t = Math.abs(target); // 由于target有负数情况,为了统一计算逻辑,所以取绝对值
        // 直到num值大于等于t,并且num减t是偶数,才结束while循环
        while (num < t || (num - t) % 2 != 0) 
            num += ++result; // num=1+2+3+4+……
        return result;
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-11-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 爪哇缪斯 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目
  • 二、示例
    • 2.1> 示例 1:
      • 2.2> 示例 2:
        • 提示:
        • 三、解题思路
        • 四、代码实现
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档