Берілген санның ең кіші екілік разрядын табыңыз


Күрделілік дәрежесі орта
Жиі кіреді Amazon Фуркиттер LinkedIn Microsoft Шапшаң
Бірінші іздеу Графика

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

«Берілген санның ең кіші екілік цифрлық еселігін табыңыз» деген есепте сізге ондық N саны берілетіндігі айтылған, сондықтан '0' және '1' екілік цифрларынан тұратын N-дің ең кіші еселігін табыңыз.

мысал

37
111

Толық түсіндірмені төменде ендірілген кескіннен табуға болады.

жақындау

А тәсілін орындау керек BFS : '1' жолын түбірлік түйін ретінде пайдалану. Біз осы түйінге '0' және '1' қосамыз және нәтижесінде '10' және '11' алынған жолдарды құйрық. Жолды кезектен шығарған сайын, біз '0' және '1' белгілерін қойылған қатарға қосып, алынған жолды кезекке қайта итереміз. Қозғалыс кезінде. Егер біз кіріс нөмірін толығымен бөлетін жолды тапсақ, онда біз жай ғана осы жолды қайтарамыз.

  1. Күрделілікті азайту: Санын азайту арқылы тәсіліміздің күрделілігін төмендетеміз жолдар BFS қозғалысы кезінде өңделген. Әр өңделген жолға біз оны қосамыз мод мәні (өңделген жол кіріс санына бөлінген кезде қалған) а хэш жиынтығы. Егер белгілі бір жол үшін болса, онда бұл мән мәні жиынтықта бұрыннан бар. Содан кейін біз жолды BFS өтпелі кезегіне қоспаймыз.
  2. себебі: Күрделілікті азайту үшін біз бірдей жолдарды қосудан аулақ боламыз мод мәні кезекке. Егер белгілі бір мод мәні бар жол кезекте тұрса немесе өңделген болса. Содан кейін кез-келген келесі жол мод мәні кезекке қосылмайды. Мұның себебі: бірдей мән мәндеріне ие екі жолды X және Y деп санаңыз (өңделген жолды кіріс санына бөлгенде қалдық), X мәні Y-ге қарағанда кіші болады. Z тағы бір жол болсын, оны Y қосқанда бізге береді егер енгізілген санға бөлінетін сан N болса, онда біз бұл жолды X-ге қосып, N санына бөлінетін санды ала аламыз, осылайша біз BFS кезегіне Y қосудан аулақ бола аламыз.

Алгоритм

  1. Кезек жасаңыз BFS жүру.
  2. а жасау хэш жиынтығы нақты мод мәні бар жолдың кездескенін немесе кездеспегенін тексеру үшін.
  3. «1» бастапқы жолды кезекке итергеннен кейін BFS травералын бастаңыз.
  4. Траверсаль кезінде:
    1. Жолды кезектен шығарыңыз.
    2. Оның модульдік мәнін тексеріңіз
      1. егер модульдік мән 0 болса, онда бұл нақты жол біздікі қажетті жауап.
      2. Басқа жағдайда, модульдік мән жиынтықта бар-жоғын тексеріңіз.
  5. Егер бұл модульдік мән хэштер жиынтығында болмаса, онда '0' және '1' қосымшасына (әр түрлі көшірмелер) қосыңыз.
  6. '0' және '1' қосқаннан кейін алынған осы екі жолды BFS өтпелі кезегіне қосыңыз.
  7. 4,5 және 6 қадамдарды енгізілген ондық санның екілік санының еселігі табылғанша қайталаңыз.

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

Берілген санның ең кіші екілік разрядын табыңыз

код

Берілген санның ең кіші екілік таңбалы еселігін табуға арналған C ++ коды

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

/* finds remainder when num is divided by N */
int mod(string num, int N)
{
    int value = 0;
    for(int i=0;i<num.length();i++)
    {
        value = 10*value + int(num[i] - '0');
        value %= N;
    }
    
    return value;
}

/* produces smallest binary digit multiple of given integer */
string smallestBinaryMultiple(int N)
{
    queue <string> q;
    unordered_set <int> us;
    
    string num = "1";
    q.push(num);
    
    /* BFS traversal */
    while(!q.empty())
    {
        string top = q.front(); q.pop();
        
        int modulus = mod(top,N);
        
        if(modulus == 0)
        return top;
        
        if(us.find(modulus) == us.end())
        {
            us.insert(modulus);
            q.push(top+"0");
            q.push(top+"1");
        }
    }
}

int main()
{
    int N = 37;
    cout<<smallestBinaryMultiple(N)<<endl;
    return 0;
}
111

Берілген санның ең кіші екілік таңбалы еселігін табуға арналған Java коды

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

class TutorialCup 
{
    /* finds remainder when num is divided by N */
    static int mod(StringBuffer num, int N)
    {
        int value = 0;
        for(int i=0;i<num.length();i++)
        {
            value = 10*value + num.charAt(i) - '0';
            value %= N;
        }
        
        return value;
    }
    
    /* produces smallest binary digit multiple of given integer */
    static StringBuffer smallestBinaryMultiple(int N)
    {
        Queue <StringBuffer> q = new LinkedList<>();
        HashSet <Integer> us = new HashSet<Integer>();
        
        StringBuffer num = new StringBuffer("1");
        q.add(num);
        
        /* BFS traversal */
        while(!q.isEmpty())
        {
            StringBuffer top = q.poll();
            
            int modulus = mod(top,N);
            
            if(modulus == 0)
            return top;
            
            if(!us.contains(modulus))
            {
                us.add(modulus);
                
                StringBuffer appendZero = new StringBuffer(top);
                appendZero.append('0');
                
                StringBuffer appendOne = new StringBuffer(top);
                appendOne.append('1');
                
                q.add(appendZero);
                q.add(appendOne);
            }
        }
        
        return num;
    }

  public static void main (String[] args) 
  {
      int N = 37;
        System.out.println(smallestBinaryMultiple(N));
  }
}
111

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

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

T (n) = O (V + E), уақыттың күрделілігі қажетті нәтижеге жеткенге дейін кездесетін элементтер санына тең.

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

A (n) = O (V), кеңістіктің күрделілігі де сол метрикаға тәуелді. Қажетті нәтижеге жеткенге дейін біз кездесетін элементтер саны.

Осылайша, қажетті нәтижеге жеткенге дейін графикте қанша түйін болатынын анықтау қиын.

V = түйіндер саны

E = графиктің шеттері