腾讯笔试题 a,b->A,B

基本思路：因为a,b变到A,B是经过同样的操作。故将a->A的所有操作路径记录下来，从最短的操作路径开始，采用同样的操作匹配b->B,如果匹配，返回最短的操作，如果所有的路径都无法匹配，返回-1。

这样，问题就转化为求小a经过若干的 +1 或者 *2 操作，变为给定的大A问题。此问题的基本思路是采用构造路径二叉树的方法，对于任意数字 n,其操作只有两种 +1 和 *2。我们从a开始，构造其左孩子为 a+1, 右孩子为 a*2,并将其放入队列。每次从队列取出一个结点，如果改结点的值为A,则存入结果路径数组；若该值小于A,则重复上述操作，构造其左右孩子结点并放入队列；若该结点的值大于A,什么也不做。当队列空的时候，所有的路径查找结束，从a到A的所有操作路径都已经在结果路径向量里了。

测试用例：a=3 -> A=12;

输出结果：（此结果路径为逆序路径，1表示\*2，0表示+1）

1 1 （3*2*2）

1 0 0 0 （（3 +1+1+1）*2）

0 0 1 0 0 （（3+1+1）*2+1+1）

0 0 0 0 1 0（（3+1）*2+1+1+1+1）

0 0 0 0 0 0 1 （3*2+1+1+1+1+1+1）

0 0 0 0 0 0 0 0 0

#include <iostream>
#include <vector>
#include <deque>
using namespace std;


struct Node 
{
    int path = 0;//记录路径 0表示加一 1表示乘以2
    Node *parent = nullptr; //父节点指针
    Node *left = nullptr;
    Node *right = nullptr;
    double value = 0;
};

int main()
{
    int a=3;
    int A = 12;

    vector<Node*> PATH; //PATH为结果路径 存放A结点的指针
    Node *root = new Node;
    root->path = -1;
    root->value = a;
    deque<Node*> mque;  
    mque.push_back(root);
    while (!mque.empty())
    {
        //弹出队首
        Node*p = mque.front();
        mque.pop_front();

        if (p->value < A) //如果该节点的值小于A,构造其孩子结点
        {
            //构建两个子孩子
            Node *left = new Node;
            left->value = p->value + 1;
            left->parent = p;
            left->path = 0;

            Node *right = new Node;
            right->value = p->value * 2;
            right->parent = p;
            right->path = 1;
            p->left = left;
            p->right = right;

            //加入队列
            mque.push_back(left);
            mque.push_back(right);
        }
        else if (p->value == A)//如果该节点的值就是A 将其存入结果向量
        {
            PATH.push_back(p);
        }
    }

    for (int i = 0; i < PATH.size(); i++)
    {
        Node*p = PATH[i];
        while (p != root)
        {
            cout << p->path << " ";  //输出路径 note:此路径为逆序路径 
            p = p->parent;
        }
        cout << endl;
    }

    return 0;
}