ການປະຕິບັດງານຂັ້ນຕ່ ຳ ທີ່ຈະປ່ຽນ X ເປັນ Y


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ປັດໃຈ ສະ ເໜ່ ສີ່ພັນ JP Morgan Myntra Samsung Spotify Square
ການຄົ້ນຫາ ທຳ ອິດ ເສັ້ນສະແດງ

ຖະແຫຼງການບັນຫາ

ບັນຫາ“ ການປະຕິບັດງານຂັ້ນຕ່ ຳ ທີ່ຈະປ່ຽນ 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 ຂັ້ນຕອນ

ວິທີການ

ພວກເຮົາສະ ໝັກ a BFS ສູດການຄິດໄລ່. ຫຼັງຈາກນັ້ນພວກເຮົາສາມາດປະຕິບັດການ ດຳ ເນີນງານ 2 ຢ່າງບໍ່ວ່າພວກເຮົາຈະຄູນດ້ວຍ 2 ຫຼືຫັກອອກດ້ວຍ 1. ໂດຍວິທີນີ້ພວກເຮົາສາມາດເຂົ້າຫາຕົວເລກທັງ ໝົດ ທີ່ສາມາດຜະລິດໄດ້ໂດຍໃຊ້ຕົວເລກ X ເລີ່ມຕົ້ນແລະປະຕິບັດສອງປະຕິບັດທີ່ໄດ້ຮັບ. ຖ້າມີຕົວເລກທີ່ຜະລິດເທົ່າກັບເລກປະກອບ Y ແມ່ນໄດ້ຮັບ. ດັ່ງນັ້ນພວກເຮົາພຽງແຕ່ສົ່ງຄືນ ຈຳ ນວນຂັ້ນຕອນທີ່ໄດ້ປະຕິບັດເພື່ອສ້າງ ຈຳ ນວນ Y. ໃນຂະນະທີ່ ກຳ ລັງຜະລິດຕົວເລກມັນເປັນສິ່ງ ສຳ ຄັນທີ່ຈະຈື່ ຈຳ ຈຸດດັ່ງຕໍ່ໄປນີ້:

  1. ພວກເຮົາບໍ່ສົນໃຈຕົວເລກຈາກການເຂົ້າໄປໃນແຖວ BFS ຖ້າຕົວເລກທີ່ຜະລິດບໍ່ຕອບສະ ໜອງ ຂໍ້ ຈຳ ກັດ.
  2. ຖ້າຫາກວ່າຕົວເລກທີ່ຜະລິດໃນປະຈຸບັນໄດ້ຖືກຜະລິດມາກ່ອນແລ້ວ. ພວກເຮົາພຽງແຕ່ບໍ່ສົນໃຈຕົວເລກໂດຍບໍ່ເພີ່ມມັນເຂົ້າໃນແຖວ BFS. ຊຸດ hash ຖືກໃຊ້ເພື່ອຕິດຕາມຕົວເລກທີ່ຜະລິດຈົນເຖິງປະຈຸບັນ.
  3. ພວກເຮົາຕິດຕາມ ຈຳ ນວນການ ດຳ ເນີນງານ (ໃນຕົວແປທີ່ມີຊື່ ລະດັບ) ດໍາເນີນການເພື່ອສ້າງຕົວເລກຈາກການເລີ່ມຕົ້ນຈໍານວນ X ໂດຍປະຕິບັດການດໍາເນີນງານທີ່ກໍານົດໄວ້.

ສູດການຄິດໄລ່ເພື່ອຊອກຫາການ ດຳ ເນີນງານຂັ້ນຕ່ ຳ ເພື່ອປ່ຽນ X ເປັນ Y

  1. ສ້າງເປັນ ຄິວ ສຳ ລັບການປ່ຽນແບບ BFS ແລະໃສ່ເລກເລີ່ມຕົ້ນ X ແລະມັນຢູ່ໃນລະດັບແຖວ. ລະດັບຂອງຕົວເລກເລີ່ມຕົ້ນແມ່ນ 0 ເນື່ອງຈາກ ຈຳ ນວນການ ດຳ ເນີນງານທີ່ ຈຳ ເປັນເພື່ອປ່ຽນ X ເປັນ X ແມ່ນ 0.
  2. ສ້າງເປັນ HashSet ທີ່ເກັບຮັກສາຕົວເລກທີ່ຜະລິດມາເຖິງຕອນນັ້ນ.
  3. ຫຼັງຈາກນັ້ນ, ເລີ່ມຕົ້ນ traversal BFS.
  4. Pop node ຈາກແຖວ, ຖ້າວ່າຄ່າ node ເທົ່າກັບເລກ input Y. ແລະລະດັບກັບຄືນ (ຈຳ ນວນ ຕຳ ່ສຸດທີ່ຂອງການ ດຳ ເນີນງານຈາກ X) ຂອງ node ນີ້.
  5. ອີກອັນ ໜຶ່ງ, ເພີ່ມ node ນີ້ເຂົ້າໃນຊຸດຂອງພວກເຮົາ (ໝາຍ ເອົາວ່າມັນໄດ້ໄປຢ້ຽມຢາມ).
  6. ໃນປັດຈຸບັນ, ຄູນຄ່າຂໍ້ມູນທີ່ເກີດຂື້ນໂດຍ 2 ແລະກວດເບິ່ງວ່າມັນມີຢູ່ໃນຊຸດ.
  7. ຖ້າຫາກວ່າຕົວເລກທີ່ຜະລິດອອກມາແມ່ນບໍ່ມີຢູ່ໃນຊຸດ. ສະນັ້ນໃສ່ ຈຳ ນວນເຂົ້າໃນແຖວພ້ອມກັບລະດັບຂອງມັນ (ລະດັບຂອງຂໍ້ນີ້ທີ່ຜະລິດ = ລະດັບຂອງ popped (parent) node + 1).
  8. ຫຼຸດລົງຄ່າຂໍ້ມູນທີ່ເກີດຂື້ນໂດຍ 1 ແລະກວດເບິ່ງວ່າມັນມີຢູ່ໃນຊຸດ.
  9. ຖ້າຫາກວ່າຕົວເລກທີ່ຜະລິດອອກມາແມ່ນບໍ່ມີຢູ່ໃນຊຸດ. ສະນັ້ນໃສ່ ຈຳ ນວນເຂົ້າໃນແຖວພ້ອມກັບລະດັບຂອງມັນ (ລະດັບຂອງຂໍ້ນີ້ທີ່ຜະລິດ = ລະດັບຂອງ popped (parent) node + 1).
  10. ເຮັດຊ້ ຳ ອີກຂັ້ນຕອນ 3-9 ຈົນກວ່າພວກເຮົາຈະພົບກັບສະພາບການກັບຄືນມາ ຂັ້ນຕອນທີ 4.

ສູດການຄິດໄລ່ແມ່ນສະແດງຢູ່ດ້ານລຸ່ມ:

ການປະຕິບັດງານຂັ້ນຕ່ ຳ ທີ່ຈະປ່ຽນ 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 ແມ່ນອົງປະກອບທີ່ໃຫຍ່ທີ່ສຸດທີ່ເປັນໄປໄດ້ພາຍໃຕ້ຂໍ້ ຈຳ ກັດຕ່າງໆ.

ຄວາມສັບສົນໃນອະວະກາດ

ມັນຍາກທີ່ຈະໃຫ້ ຄຳ ເຫັນກ່ຽວກັບຄວາມສັບສົນໃນອະວະກາດເຊັ່ນກັນ. ແຕ່ຄ້າຍຄືກັບສິ່ງທີ່ພວກເຮົາໄດ້ເຮັດກັບຄວາມສັບສົນເວລາ. ສະນັ້ນມັນກໍ່ແມ່ນຄວາມຈິງ ສຳ ລັບຄວາມສັບສົນໃນອະວະກາດ. ໃນກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດ, ພວກເຮົາຈະເອົາອົງປະກອບທັງ ໝົດ ເຂົ້າໃນແຖວ. ນີ້ເຮັດໃຫ້ສູດການຄິດໄລ່ ໂອ (N) ພື້ນທີ່, ບ່ອນທີ່ N ແມ່ນຕົວເລກໃຫຍ່ທີ່ສຸດທີ່ເປັນໄປໄດ້ພາຍໃຕ້ຂໍ້ ຈຳ ກັດ.