X-ті Y-ге түрлендіруге арналған минималды операциялар


Күрделілік дәрежесі орта
Жиі кіреді Amazon Деректер жинағы Фанатика Фуркиттер JP Morgan Минтра Samsung Spotify шаршы
Бірінші іздеу Графика

Проблемалық мәлімдеме

«Х-ті Y-ге түрлендіруге арналған минималды операциялар» есебінде сізге екі X және Y сандары берілген, келесі әрекеттерді қолдану арқылы X-ді Y-ге айналдыру қажет деп көрсетілген.

Бастапқы нөмір - Х. Келесі әрекеттерді Х және аралық нәтиже ретінде алынған сандар бойынша орындауға болады.

  1. санды 2-ге көбейту.
  2. санын 1-ге азайтыңыз.

Жоғарыда көрсетілген амалдарды қолданып Х-ті 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. Біз операциялардың санын қадағалаймыз (аталған айнымалыда) деңгей) қажетті операцияларды орындау арқылы Х санынан бастап сан құру үшін орындалды.

Х-ті Y-ге түрлендіруге арналған минималды амалдарды табу алгоритмі

  1. а жасау құйрық BFS травералы үшін және бастапқы X санын енгізіңіз, және ол кезекке тұрыңыз. Бастапқы санның деңгейі 0-ге тең, өйткені Х-ті Х-ға түрлендіру үшін қажет операциялар саны 0-ге тең.
  2. а жасау HashSet осы уақытқа дейін жасалған сандарды сақтайтын.
  3. Содан кейін BFS травералын бастаңыз.
  4. Кезектен түйінді шығарыңыз, егер түйін мәні Y кіріс нөміріне тең болса, және осы түйіннің қайтару деңгейі (Х-тен операциялардың минималды саны).
  5. Басқа жағдайда, бұл түйінді біздің хэш-жиынтығымызға қосыңыз (оны барған ретінде белгілеңіз).
  6. Енді қойылған түйін мәнін 2-ге көбейтіп, оның жиынтықта бар-жоғын тексеріңіз.
  7. Егер солай шығарылған сан жиынтықта болмаса. Сонымен, санды кезекке оның деңгейімен бірге енгізіңіз (осы түйіннің деңгейі = пайда болған түйіннің деңгейі (1)).
  8. Қойылған түйін мәнін 1-ге азайтып, оның жиынтықта бар-жоғын тексеріңіз.
  9. Егер солай шығарылған сан жиынтықта болмаса. Сонымен, санды кезекке оның деңгейімен бірге енгізіңіз (осы түйіннің деңгейі = пайда болған түйіннің деңгейі (1)).
  10. Қайтару шарты пайда болғанға дейін 3-9 қадамдарды қайталаңыз 4-қадам.

Алгоритм төменде көрсетілген:

X-ті Y-ге түрлендіруге арналған минималды операциялар

код

X-ті Y-ге түрлендіруге арналған минималды амалдарды табу үшін C ++ коды

#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

Күрделілікті талдау

Уақыттың күрделілігі

Жоғарыда аталған тәсілді қолдана отырып, санды табу уақытының күрделілігі туралы түсініктеме беру қиын. Бірақ біз ең нашар уақыт күрделілігі туралы пікір айта аламыз. Нашар жағдайда, біз шектеулердің барлық сандарын қарастырамыз. Барлық нөмірлерден өтіп жатсақ та, біз қажетті нөмірді таба алмаймыз. Осылайша уақыттың күрделілігі O (N), мұндағы N - берілген шектеулер кезінде мүмкін болатын ең үлкен элемент.

Ғарыштың күрделілігі

Ғарыштың күрделілігі туралы да пікір айту қиын. Бірақ уақыттың күрделілігімен жасағанға ұқсас. Сонымен, ғарыштың күрделілігіне де қатысты. Ең нашар жағдайда, біз барлық элементтерді кезекке енгіземіз. Бұл алгоритмді қабылдауға мәжбүр етеді O (N) кеңістік, мұндағы N - берілген шектеу кезінде мүмкін болатын ең үлкен сан.