从源到目标的最小操作数。

Question

我在采访中遇到了这个问题 - 以最少的操作次数将数字源转换为目标。

允许的操作

乘以 2。
加1。
减1。

0 < 来源，目标 <= 1000。

我试着走朴素的递归路线（O（3 ^ n））即。在每个级别减去 1、加 1 并乘以 2，以尝试找到一个我可以扩展到动态规划但由于无限循环而无法扩展的解决方案。

//Naive approach Via Recursion 

int minMoves(int source, int target){

    if(source <1 || source > target){
        return -1;
    }

    int moves =0;
    // Potential infinite loop - consider 3,6-> 2,6- >1,6->(0,6)x (2,6)->1,6->(0,6)x (1,6)->(0,6)x (2,6)->1,6..
    int movesLeft  = minMoves(source -1, target) ==-1? Integer.MAX_VALUE:minMoves(source -1, target);
    int movesRight  = minMoves(source +1, target) ==-1? Integer.MAX_VALUE:minMoves(source +1, target);
    int moves2X  = minMoves(2*source, target) ==-1? Integer.MAX_VALUE:minMoves(2*source, target);

    moves = 1+ Math.min(Math.min(movesRight,movesLeft), moves2X);
    return moves;

}

关于如何调整我的解决方案有什么想法吗？或者可能有更好的解决方法？

Answer 1

您可以在保持递归实现的同时加速（并可能修复）此代码的一种方法是使用 memoization.

这里的问题是您多次重新计算相同的值。相反，您可以使用 map 来存储您已经计算出的结果，并在您再次需要时重新使用它们。

Answer 2

这个问题可以建设性的解决。首先，简单的情况。如果s=t，则答案为0。如果s > t，则答案为s-t，因为减1是唯一降低s的操作，其他两个只能增加所需的减法次数。

现在假设 s < t。由于给定了 s>0，因此加倍始终是最快的增加方式（如果 s 为 1，则与递增相关）。因此，如果挑战是使 s >= t，答案将始终是实现该目标所需的翻倍次数。此过程可能会超过 t，但第一个大于 t 的加倍和最后一个不大于 t 的加倍必须在 t 的 2 倍内。

让我们看看加法或减法的效果。一、只看加法：

(((s*2) * 2) * 2) + 1 = 8s + 1

对比：

((((s+1)*2) * 2) * 2) = 8s + 8

在 n 次加倍之前加法会使最终结果大 2^n。所以考虑如果 s 是 3 并且 t 是 8。最后一个不大于 8 的双精度数是 6。这是 2 off，所以如果我们在最后一个双精度数之前加上 1 双精度数，我们得到我们想要的：(3+1) * 2. 或者我们可以尝试超调到第一个大于 8 的双倍数，即 12。这是 4 减去，所以我们需要在最后一个双倍数之前减去两个倍数：(3-1)*2*2 = 8

一般来说，如果我们低于目标值 x，如果 x 的二进制表示在第 n 位为 1，我们需要在最后一个之前的 n 次加倍处放置一个 +1。

同样，如果我们比目标高出 x，我们也会对 -1 进行同样的处理。

此过程对 x 的二进制表示中的 1 位置超过加倍次数的位置没有帮助。比如s=100，t=207，只需要做1次倍增，但是x是7，也就是111，我们可以先做加法去掉中间的那个，剩下的再做一个一个 (s+1)*2 + 1 + 1 + 1 + 1 + 1.

这是一个具有调试标志的实现，该标志在定义标志时也会输出操作列表。运行时间为 O(log(t)):

#include <iostream>
#include <string>
#include <sstream>

#define DEBUG_INFO

int MinMoves(int s, int t)
{
    int ans = 0;
    if (t <= s)
    {
        return s - t; //Only subtraction will help
    }
    int firstDoubleGreater = s;
    int lastDoubleNotGreater = s;
    int nDouble = 0;
    while(firstDoubleGreater <= t)
    {
        nDouble++;
        lastDoubleNotGreater = firstDoubleGreater;
        firstDoubleGreater *= 2;
    }
    int d1 = t - lastDoubleNotGreater;
    int d2 = firstDoubleGreater - t;
    if (d1 == 0)
        return nDouble -1;
    int strat1 = nDouble -1;        //Double and increment
    int strat2 = nDouble;           //Double and decrement


#ifdef DEBUG_INFO
std::cout << "nDouble: " << nDouble << "\n";
    std::stringstream s1Ops;
    std::stringstream s2Ops;
    int s1Tmp = s;
    int s2Tmp = s;
#endif

    int mask = 1<<strat1;
    for(int pos = 0; pos < nDouble-1; pos++)
    {
#ifdef DEBUG_INFO
        if (d1 & mask)
        {
            s1Ops << s1Tmp << "+1=" << s1Tmp+1 << "\n" << s1Tmp+1 << "*2= " << (s1Tmp+1)*2 << "\n";
            s1Tmp = (s1Tmp + 1) * 2;
        }
        else
        {
            s1Ops << s1Tmp << "*2= " << s1Tmp*2 << "\n";
            s1Tmp = s1Tmp*2;
        }
#endif
        if(d1 & mask)
            strat1++;
        d1 = d1 & ~mask;
        mask = mask >> 1;
    }
    strat1 += d1;
#ifdef DEBUG_INFO
    if (d1 != 0)
        s1Ops << s1Tmp << " +1 " << d1 << " times = " << s1Tmp + d1 << "\n";
#endif

    mask = 1<<strat2;
    for(int pos = 0; pos < nDouble; pos++)
    {
#ifdef DEBUG_INFO
        if (d2 & mask)
        {
            s2Ops << s2Tmp << "-1=" << s2Tmp-1 << "\n" << s2Tmp-1 << "*2= " << (s2Tmp-1)*2 << "\n";
            s2Tmp = (s2Tmp-1)*2;
        }
        else
        {
            s2Ops << s2Tmp << "*2= " << s2Tmp*2 << "\n";
            s2Tmp = s2Tmp*2;
        }
#endif


        if(d2 & mask)
            strat2++;
        d2 = d2 & ~mask;
        mask = mask >> 1;
    }
    strat2 += d2;
#ifdef DEBUG_INFO
    if (d2 != 0)
        s2Ops << s2Tmp << " -1 " << d2 << " times = " << s2Tmp - d2 << "\n";



    std::cout << "Strat1:   "  << strat1 << "\n";
    std::cout << s1Ops.str() << "\n";
    std::cout << "\n\nStrat2:   "  << strat2 << "\n";
    std::cout << s2Ops.str() << "\n";
#endif
    if (strat1 < strat2)
    {
        return strat1;
    }
    else
    {
        std::cout << "Strat2\n";
        return strat2;
    }

}




int main()
{
    int s = 25;
    int t = 193;
    std::cout << "s = " << s << "  t = " << t << "\n";
    std::cout << MinMoves(s, t) << std::endl;
}

Answer 3

如果您将解决方案视为图形遍历，其中每个节点都是您可以生成的中间值，那么您的递归解决方案就像深度优先搜索 (DFS)。您必须完全展开，直到尝试了搜索 "branch" 中 space 的所有解决方案，然后才能继续其他任何地方。如果你有一个无限循环，这意味着它永远不会终止，即使存在更短的路径，即使你没有无限循环，你仍然必须搜索解决方案的其余部分 space 以确保最佳。

相反，考虑一种类似于广度优先搜索 (BFS) 的方法。你统一向外扩展，永远不会搜索比最优解更长的路径。只需使用 FIFO 队列来调度下一个访问哪个节点。这是我对求解器采用的方法。

from queue import Queue

def solve(source, target):
    queue = Queue()
    path = [source]
    queue.put(path)
    while source != target:
        queue.put(path + [source * 2])
        queue.put(path + [source + 1])
        queue.put(path + [source - 1])

        path = queue.get()
        source = path[-1]
    return path

if __name__ == "__main__":
    print(solve(4,79))

Answer 4

短 BFS 算法。它找到图中每个顶点 x 都连接到 x + 1、x - 1 和 x * 2 的最短路径； O(n)

#include <bits/stdc++.h>

using namespace std;

const int _MAX_DIS = 2020;
const int _MIN_DIS = 0;

int minMoves(int begin, int end){
    queue<int> Q;
    int dis[_MAX_DIS];
    fill(dis, dis + _MAX_DIS, -1);

    dis[begin] = 0;
    Q.push(begin);

    while(!Q.empty()){
        int v = Q.front(); Q.pop();
        int tab[] = {v + 1, v - 1, v * 2};
        for(int i = 0; i < 3; i++){
            int w = tab[i];
            if(_MIN_DIS <= w && w <= _MAX_DIS && dis[w] == -1){
                Q.push(w);
                dis[w] = dis[v] + 1;
            }
        }
    }

    return dis[end];
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cout << minMoves(1, 1000);

    return 0;
}

从源到目标的最小操作数。

Minimum number of operations to get from source to target.

language-agnostic

algorithm

dynamic-programming