將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是在給定約束下可能的最大數字。