java - 从0开始用最少的步数达到目标数

Question

问题陈述:找出从 0(零)达到目标数字 x 所需的最少步数，仅使用两个操作:+1 (将数字加 1) 或 *2 (将 2 乘以数)。

所以这是我想出的逻辑:

最好的方法是逆向工作。从您需要的数字开始:

1. 如果数字是奇数则减 1。
2. 如果是偶数则除以 2。
3. 当你达到零时停止。

例如，对于 29，您将得到 28、14、7、6、3、2、1、0。

而且，这是我尝试做的事情(Java 7):

kValues 是一个包含 x 值的数组，需要为其计算 steps 并将其存储在名为 结果。

static int[] countOperationsToK(long[] kValues) {
    int size = kValues.length,x,i,steps;
    int result[] = new int[size];

    for (i = 0; i < size; ++i)
    {
        steps = 0;
        for (x = (int)kValues[i]; x != 0 ; ++steps)
        {
            if((x % 2) == 0)
                x /= 2;
            else x--;
        }
        result[i] = steps;
    }

    return result;
}

我的问题:

这是一个 Hackerrank 问题，我应该写一个高效的代码。我成功地完成了 7/11 测试用例，其他的都超时了。由于这是一个 Hackerrank 问题，我无法更改函数定义或返回类型。这就是为什么我在我的 for 循环中从 long 转换为 int 以便使用 % (模数)。我想知道我哪里出错了。我的算法计算时间是否太长(对于接近一百万的值)？情况显然如此，但我如何更改我的算法才能通过所有测试用例？

提前谢谢你:)

Answer 1

for (x = (int)kValues[i]; x != 0 ; ++steps)

将 long 转换为 int 的事实非常可疑。当你这样做时，你可能会得到一个负数。

说 x == -2:你将它除以 2 得到 -1，然后减去 1 得到 -2。您将无限期地继续这样做。

只需将 x 定义为一个 long，然后移除强制转换。