将X转换为Y的最小操作


难度级别 中等
经常问 亚马逊 事实集 狂徒 风筝 JP摩根 Myntra Samsung Spotify 广场
广度优先搜索 图表

问题陈述

问题“将X转换为Y的最少操作”指出给您两个数字X和Y,需要使用以下操作将X转换为Y:

起始编号为X。可以对X和作为中间结果生成的编号执行以下操作。

  1. 将该数字乘以2。
  2. 将数字减少1。

找出使用上述操作将X转换为Y所需的最小步骤数。

限制条件: 0 <X,Y <1000

使用案列

X = 3, Y = 11
3

说明:3 * 2 = 6,6 * 2 = 12,12-1 = 11 3步

X = 2, Y = 10
5

说明: 2 * 2 = 4,4-1 = 3,3 * 2 = 6,6-1 = 5,5 * 2 = 10-> 5步

途径

我们应用 BFS 基于算法。 然后,我们可以执行2次运算,或者乘以2或乘以1。这样,我们就可以得出使用起始数字X并执行给定的两个运算可以生成的所有数字。 如果任何生成的数字等于输入数字,则获得Y。 因此,我们只需返回生成数字Y的步骤数。在生成数字时,请记住以下几点很重要:

  1. 如果生成的数字不满足约束条件,我们将忽略该数字插入BFS队列。
  2. 如果以前已经生成了当前生成的号码。 我们只是通过不将该数字添加到BFS队列中而忽略该数字。 哈希集用于跟踪到目前为止生成的数字。
  3. 我们跟踪操作数(在名为的变量中 等级) 通过执行所需的操作,从起始数字X生成数字。

查找将X转换为Y的最小运算的算法

  1. 创建一个 队列 进行BFS遍历,并将起始编号X及其级别插入队列。 起始编号级别为0,因为将X转换为X所需的操作数为0。
  2. 创建一个 哈希集 存储到目前为止生成的数字。
  3. 然后开始BFS遍历。
  4. 如果节点值等于输入数字Y,则从队列中弹出一个节点。然后返回该节点的返回级别(X的最小操作数)。
  5. 否则,将此节点添加到我们的哈希集中(将其标记为已访问)。
  6. 现在,将弹出的节点值乘以2,然后检查它是否存在于集合中。
  7. 如果如此生成的数字不存在于集合中。 因此,将数字及其级别插入队列(生成的此节点的级别=弹出(父)节点的级别+ 1)。
  8. 将弹出的节点值减小1,然后检查其是否存在于集合中。
  9. 如果如此生成的数字不存在于集合中。 因此,将数字及其级别插入队列(生成的此节点的级别=弹出(父)节点的级别+ 1)。
  10. 反复重复步骤3-9,直到遇到以下情况的返回条件: 第四步。

该算法如下所示:

将X转换为Y的最小操作

代码

C ++代码查找将X转换为Y的最小运算

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* class definition to treat 
numbers generated as nodes */
class Node
{
    public:
    int num;
    int level;
    
    Node(int num,int level)
    {
        this->num = num;
        this->level = level;
    }
};

/* function to find minimum number of 
operations required to convert x into y */
int minOperation(int x,int y)
{
    queue<Node*> q;
    unordered_set <int> us;
    
    Node *node = new Node(x,0);
    q.push(node);
    
    while(!q.empty())
    {
        Node *top = q.front();
        q.pop();
        
        if(top->num == y)
        return top->level;
        
        us.insert(top->num);
        
        /* Multiplication Operation */
        if(us.find(2*top->num) == us.end())
        {
            Node *temp = new Node(2*top->num,top->level+1);
            q.push(temp);
        }
        
        /* Subtraction Operation */
        if(us.find(top->num-1) == us.end() && top->num-1 > 0)
        {
            Node *temp = new Node(top->num-1,top->level+1);
            q.push(temp);
        }
    }
}
/* Main function */
int main()
{
    int x = 2,y = 10;
    cout<<minOperation(x,y)<<endl;
    
    return 0;
}
5

Java代码以查找将X转换为Y的最小操作

import java.util.*;
import java.io.*;

class TutorialCup 
{
    /* class definition to treat 
    numbers generated as nodes */
    static class Node
    {
        int num;
        int level;
        
        Node(int num,int level)
        {
            this.num = num;
            this.level = level;
        }
    }
    
    /* function to find minimum number of 
    operations required to convert x into y */
    static int minOperation(int x,int y)
    {
        Queue <Node> q = new LinkedList<>();
        HashSet <Integer> hs = new HashSet<Integer>();
        
        Node node = new Node(x,0);
        q.add(node);
        
        while(!q.isEmpty())
        {
            Node top = q.poll();
            
            if(top.num == y)
            return top.level;
            
            hs.add(top.num);
            
            /* Multiplication Operation */
            if(!hs.contains(2*top.num))
            {
                Node temp = new Node(2*top.num,top.level+1);
                q.add(temp);
            }
            
            /* Subtraction Operation */
            if(!hs.contains(top.num-1) && top.num-1 > 0)
            {
                Node temp = new Node(top.num-1,top.level+1);
                q.add(temp);
            }
        }
        
        return 0;
    }
    /* Main function */
  public static void main (String[] args) 
  {
      int x = 2,y = 10;
        System.out.println(minOperation(x,y));
  }
}
5

复杂度分析

时间复杂度

很难评论使用上述方法查找数字的时间复杂度。 但是我们仍然可以评论最糟糕的时间复杂度。 在最坏的情况下,可能发生的事情是我们遍历约束下存在的所有数字。 即使遍历所有数字,我们也找不到所需的数字。 因此,时间复杂度为 上),其中N是在给定约束下可能的最大元素。

空间复杂度

同样,很难评论空间的复杂性。 但是类似于我们对时间复杂度所做的操作。 因此,对于空间复杂性也是如此。 在最坏的情况下,我们会将所有元素插入队列。 这使得算法采取 上) 空间,其中N是在给定约束下可能的最大数字。