LeetCode算法题-Reach a Number(Java实现)

这是悦乐书的第310次更新,第331篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第179题(顺位题号是754)。你站在无限数字线的0号位置。在目的地有个target。在每次移动中,您可以向左或向右移动。在第n次移动(从1开始)期间,你可以走n步。返回到达目的地所需的最少步骤数。例如:

输入:target = 3

输出:2

说明:在第一步中,我们从0步进到1。在第二步,我们从1步骤到3。


输入:target = 2

输出:3

说明:在第一步中,我们从0步进到1。在第二步,我们从1步进到-1。在第三步,我们从-1步到2。


注意:target将是[-10 ^ 9,10 ^ 9]范围内的非零整数。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

此解法只是一种思路。因为每一步都有两种选择,往左或往右,一层一层展开,其结构类似树,因此可以构建一个二叉树,在构建二叉树的过程中,判断二叉树的节点值是否等于target。

03 第二种解法

在无从下手的情况下,我们来分析下几种情况:

第一,因为给的target可正可负,所以当target为负数时,其实与target为正数时是对称的,结果一样,所以在方法开始前,可以将其转为正数。

第二,如果一直是向左移动,移动的步数就变成了一个等差数列,总共移动的步数就是Nx(1+N)/2,如果其总步数等于目标值,这就是最优解,就可以直接返回移动的步数。

第三,既有左移,也有右移时,此时计算Nx(1+N)/2的值比target大,分为两种情况:

(1)Nx(1+N)/2 - target的差为偶数。例如总步数为1+2+3=6,target为4,两者相差为2,需要走三次,但是需要将第一步往左走,才能满足条件。只要是相差为偶数,就只需要差除以2的商的那一步往左走即可。

(2)Nx(1+N)/2 - target的差为奇数。此时上面的情况就不能满足了,就只能增加步数,那么是增加几步呢?此时我们需要去判断N了,如果N为偶数,需要再走一步,如果N为奇数,需要再走两步。例如target为5,已经走了三步,此时步数和为6,还需要再走两步,并且第5步需要往左走,也就是1+2+3+4-5=5。

public int reachNumber(int target) {
    target = Math.abs(target);
    int result = 0;
    long i = 0;
    while (i*(i+1) < 2*target) {
        i++;
    }
    if (i*(i+1)/2 == target) {
        result = (int)i;
    } else {
        if ((i*(i+1)/2 - target)%2 == 0) {
            result = (int)i;
        } else {
            if (i%2 == 0) {
                result = (int)i+1;
            } else {
                result = (int)i+2;
            }
        }
    }
    return result;              
}


04 第三种解法

对于上面第二种解法,我们还可以再简化下,将求和和判断放在了一个循环中处理,依旧是做减法判断差值的奇偶,因为不满足条件就一直做累加,只有差值为偶数时才会退出循环。

public int reachNumber(int target) {
    target = Math.abs(target);
    int result = 0, sum = 0;
    while (sum < target || (sum-target)%2 != 0) {
        result++;
        sum += result;
    }
    return result;              
}


05 小结

算法专题目前已日更超过五个月,算法题文章179+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

上一篇:Jump Game II -- LeetCode


下一篇:leetcode55