Шумораи ҳадди ақалро аз пайдарпаии додашуда ташкил кунед  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Акколити Amazon Фараж Голдман Sachs Маълумот Edge Snapchat
тартиботи ҳарбӣ тӯда сатр

Масъалаи "Шакли ҳадди аққал аз пайдарпаии додашуда" изҳор мекунад, ки ба шумо якчанд намунаи Ман ва D's танҳо. Маънии I афзоиш ва коҳиш ба мо таъмин карда шудааст D. Ҳукми масъала дархост мекунад, ки шумораи камтаринро чоп кунанд, ки намунаи додашударо қонеъ гардонанд. Мо бояд рақамҳои аз 1-9-ро истифода барем ва ҳеҷ гуна рақам такрор нашавад.

мисол  

DIID
21354

Шарҳ

Рақами аввал 2 аст, пас пас аз кам кардани он рақами навбатӣ 1 хоҳад буд. Пас афзоиши 2 ба 3 ҳамчун рақами минималӣ, ки аз 2 калонтар аст, табдил меёбад ва пас мо бояд онро боз ҳам афзоиш диҳем, аммо пас аз зиёд шудани он мо бояд онро коҳиш диҳем . Азбаски рақамҳоро такрор кардан мумкин нест. Пас, мо онро 2 зиёд ва сипас 1 коҳиш медиҳем.

Пас натиҷа 2 1 3 5 4 мешавад

пайвандак

Боз рақами ҷориро зиёд мекунем. Аммо ин кор ба мо 4 медиҳад ва пас аз кам шудан мо бояд 1, 2 ё 3 -ро истифода барем. Ва ҳамаи ин рақамҳо аллакай истифода шуда буданд. Пас, ба мо лозим аст, ки рақами ҷориро ба 5 расонем ва ҳамин тавр мо ба ҷавоб мерасем.

Алгоритми ташаккули рақами минималӣ аз пайдарпаии додашуда  

  1. Тафтиш кунед, ки дарозии пайдарпаии додашуда аз 9 калон аст ё ба он баробар аст, агар рост бошад пас -1 баргардед.
  2. Массивҳои андозаи n + 1 -ро эълон кунед ва арзиши ҳисобро ба 1 таъин кунед.
  3. Гузариши массивро аз 0 то n оғоз кунед (ҳамроҳ).
    1. Агар тафтиш кунед i ба. баробар аст n ё аломати ҷории сатр ба "I" баробар аст, агар он гоҳ дуруст бошад
      1. Массивро аз арзиши қаблӣ то -1 гузаред.
        1. Қадамҳои массиви истеҳсолиро тавассути амалҳои зерин навсозӣ кунед.
          1. Арзиши ҳисобро афзоиш диҳед ва онро ба массиви баромади нигоҳ доред.
          2. Агар тафтиш кунед j аст индекси ҷорӣ аз 0 бузургтар аст ва инчунин аломати ҷории сатр "I" аст, пас, мешиканад.
  4. Натиҷаи баргаштан.
ҳамчунин нигаред
Тартиби дараҷаи зигзаги дарахти бинарӣ

Шарҳ

Бо назардошти сатр ва танҳо I ва D, аз мо хоҳиш карда мешавад, ки намунаеро, ки бо дода мешавад, чоп кунем данд. Ин ҷо I ба афзоиш ишора мекунад, ки мо бояд шумораи камтаринро тартиб диҳем ё ташкил диҳем, ки пайдарпаии додашударо асоснок кунад. Фарз мекунем, ки агар гӯем DI, ки дар он D маънои кам кардани шумораи ҳадди ақалро дорад, ки 2 пас аз он ҳамчун 21 шумораи камтаринро ташкил диҳад. рақамҳоро такрор кардан мумкин нест, рақам танҳо рақамҳои аз 1-9-ро дар бар гирифта метавонад. Пас аз он, "ман" ҳаст, мо бояд шумораи ками афзояндаро ташкил диҳем. Азбаски 21 аллакай вуҷуд дорад. Мо мақсад дорем, ки шумораи афзояндаро ташкил диҳем. Ҳамин тариқ пас аз 1 3 илова карда мешавад, зеро 2 аллакай истифода мешавад ва пас аз он 3 ягона рақаме мебошад, ки онро ҳамроҳ кардан мумкин аст.

Бо ҳамаи ин мафҳумҳо ва ғояҳо, аз мо хоҳиш карда мешавад, ки шумораи камтаринро, ки шартҳои додашударо риоя ва қонеъ мекунад, чоп намоем. Мо массиви баромадро истифода мебарем, ки дар он ҳамаи мо натиҷаи худро дар он массиви аломатҳо нигоҳ медорем. Мо барои тасдиқ ва тасдиқи маълумот якчанд шарт гузоштем. Агар мо дарозии сатрро аз 9 ё калонтар ёбем, пас мо -1-ро бармегардонем, зеро ба мо қатъиян истифодаи 1-9 рақам фармон дода шудааст ва ҳеҷ рақам такрор намешавад.

Сатреро, ки мо ҳамчун вуруд гирифтаем, гузаред. Агар индекси ҷорӣ ба дарозии сатр ё аломати ҷорӣ ба "I" баробар бошад. Пас танҳо мо минбаъд идома медиҳем. Пас аз он, аз арзиши қаблӣ то ба арзиши ҷории (i) гузаштанро оғоз кунед, то -1 мерасад. Дар дохили ин ҳалқа мо афзоиш додани арзиши ҳисоб ва нигоҳ доштан дар массиви баромади индекси j + 1-ро идома медиҳем. Пас санҷед, ки оё арзиши j аз ё бузургтар аст ва инчунин агар аломати ҳозира "I" бошад. Агар рост бошад, пас ҳалқаро кандан ва барои аломатҳои бештар идома додан.

ҳамчунин нигаред
Табдили зигзаг

рамз  

Коди C ++ барои ташаккули рақами минималӣ аз пайдарпаии додашуда

#include<iostream>

using namespace std;

string getMinimumNumberSeq(string str)
{
    int n = str.length();

    if (n >= 9)
        return "-1";

    string output(n+1, ' ');

    int count = 1;

    for (int i = 0; i <= n; i++)
    {
        if (i == n || str[i] == 'I')
        {
            for (int j = i - 1 ; j >= -1 ; j--)
            {
                output[j + 1] = '0' + count++;
                if(j >= 0 && str[j] == 'I')
                    break;
            }
        }
    }
    return output;
}
int main()
{
    string inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID"};

    for (string input : inputs)
    {
        cout << getMinimumNumberSeq(input) << "\n";
    }
    return 0;
}
21354
132
123
213
32145
13254
1325476

Рамзи Java барои ташаккули рақами минималӣ аз пайдарпаии додашуда

class minimumNumberID
{
    static String getMinimumNumberSeq(String str)
    {
        int n = str.length();

        if (n >= 9)
            return "-1";

        char output[] = new char[n + 1];

        int count = 1;

        for (int i = 0; i <= n; i++)
        {
            if (i == n || str.charAt(i) == 'I')
            {
                for (int j = i - 1; j >= -1; j--)
                {
                    output[j + 1] = (char) ((int) '0' + count++);
                    if (j >= 0 && str.charAt(j) == 'I')
                        break;
                }
            }
        }
        return new String(output);
    }
    public static void main(String[] args)
    {
        String inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID" };

        for(String input : inputs)
        {
            System.out.println(getMinimumNumberSeq(input));
        }
    }
}
21354
132
123
213
32145
13254
1325476

Таҳлили мураккабӣ  

Мураккабии вақт

О (Н) ки дар "N" дарозии сатри пурсишҳо мебошад. Аввал санҷед, ки мо ба дохили ҳалқаи лона ворид мешавем, танҳо дар сурате, ки мо ба охир расидаем ё индекси ҳозира ман I бошад. Ва ҳалқаи лона ба самти ақиб мегузарад ва мо аз ҳалқа берун мешавем, агар дучор оям. Пас мо гуфта метавонем ки мо ба ҳалқаи лона ворид мешавем, вақте ки бо I дучор меоем ва бо индексҳое кор мекунем, ки дар онҳо D захира шудааст. Азбаски ҳар як нишондиҳанда метавонад ман ё D дошта бошад, мо аз болои ҳар як аломат танҳо якто мегузарем. Ҳамин тариқ, мураккабии вақт хатӣ аст.

ҳамчунин нигаред
Муқаддима дарахти сурх-сиёҳ

Мураккабии фазо

О (Н), зеро мо барои нигаҳдории натиҷа массиви аломатҳои баромадие сохтем. Мураккабии фазо барои масъала низ хаттӣ аст.