Տրված հաջորդականությունից կազմեք նվազագույն թիվը


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Ակոլիտ Amazon Ֆանատիկա Goldman Sachs-ը Info Edge Snapchat
Դասավորություն Գրապահոց String

«Տրված հաջորդականությունից նվազագույն թիվը կազմիր» խնդրում նշվում է, որ քեզ տրված է որոշակի ձև Ես եմ և Դ միայն Իմաստը 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 չափի char զանգված և հաշվարկի արժեքը դնել 1:
  3. Սկսեք զանգվածը տարածել 0-ից n (ներառյալ):
    1. Ստուգեք i հավասար է n կամ լարի ներկայիս նիշը հավասար է «ես» -ին, եթե այդ դեպքում ճիշտ է
      1. Անցեք զանգվածը նախորդ արժեքից մինչև -1:
        1. Թարմացրեք ելքային զանգվածի արժեքները `կատարելով հետևյալ քայլերը:
          1. Բարձրացրեք հաշվարկի արժեքը և պահեք այն ելքային զանգվածում:
          2. Ստուգեք j ներկայիս ինդեքսն ավելի մեծ է, քան 0-ը, և նաև տողի ներկայիս բնութագիրը «Ես» է, ապա ՝ կոտրել:
  4. Վերադարձի արդյունք:

բացատրություն

Հաշվի առնելով միայն I և D տողերը, մեզ խնդրում են տպել օրինակը, որը կարող է կազմվել տրվածով լարային. Այստեղ I վերաբերում է այն մեծացմանը, որը մենք պետք է կազմենք կամ կազմենք նվազագույն թիվ, որը կարող է արդարացնել տվյալ հաջորդականությունը: Ենթադրենք, եթե մենք ասում ենք DI, Որտեղ D նշանակում է նվազագույն քանակի նվազեցում այնպես, որ 2-ին հաջորդում է 21-ը `որպես նվազագույն թիվ: թվանշանները չեն կարող կրկնվել, համարը կարող է պարունակել միայն 1-9 թվանշանները: Դրանից հետո «ես» կա, մենք պետք է կազմենք նվազագույն քանակի ավելացում: Քանի որ 21-ն արդեն այնտեղ է: Մենք նպատակ ունենք ավելի ու ավելի շատ թվեր կազմել: Այսպիսով 1-ին հաջորդում է 3-ը, քանի որ 2-ն արդեն օգտագործվում է, և դրանից հետո 3-ը միակ համարն է, որը կարող է միացվել:

Այս բոլոր հասկացությունների և գաղափարների հետ միասին մեզ խնդրում են տպել այդ նվազագույն թիվը, որը հետևում և բավարարում է տվյալ պայմանները: Մենք պատրաստվում ենք օգտագործել ելքային զանգվածը, որում բոլորս մեր ելքը պահում ենք այդ նիշերի զանգվածում: Մենք որոշ պայմաններ առաջադրեցինք տվյալների վավերացման և ստուգման համար: Եթե ​​տողի երկարությունը գտնենք 9.-ից մեծ կամ հավասար, ապա արդյունքում մենք կվերադարձնենք -1, քանի որ խստորեն պատվիրված է օգտագործել 1-9 թվանշանը և ոչ մի թվանշան չի կարող կրկնվել:

Անցեք այն լարը, որը մենք ստացել ենք որպես մուտք: Եթե ​​ընթացիկ ինդեքսը հավասար է լարի երկարությանը կամ ընթացիկ նիշը հավասար է «ես» -ին: Հետո միայն մենք հետագայում ենք առաջ գնում: Դրանից հետո սկսեք անցնել ընթացիկ արժեքին նախորդող (i) արժեքից, մինչև հասնել -1-ի: Այս օղակի ներսում մենք շարունակում ենք ավելացնել հաշվարկի արժեքը և պահպանել ելքային զանգվածը j + 1 ինդեքսում: Դրանից հետո ստուգեք ՝ արդյոք արժեքը j ավելի մեծ է կամ հավասար է դրան 0 և նաև, եթե ներկայիս նիշը «ես» է: Եթե ​​ճիշտ է, ապա կոտրեք օղակը և հետագա գործողությունները շարունակեք ավելի շատ նիշերի համար:

Կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ) որտեղ «Ն» հարցման տողի երկարությունն է: Նախ ստուգեք, որ մենք ներս ենք մտնում հանգուցյալ օղակի մեջ, միայն այն դեպքում, եթե մենք հասել ենք ավարտին կամ եթե ներկայիս ցուցանիշը I է: Եվ տեղադրված հանգույցն ընթանում է հետընթաց ուղղությամբ, և եթե մենք բախվենք I. մենք դուրս ենք գալիս օղակից: Այսպիսով, մենք կարող ենք ասել որ մենք մտնում ենք տեղադրված հանգույց, երբ բախվում ենք I- ի հետ և աշխատում ենք ինդեքսների վրա, որոնք իրենց մոտ պահում են D: Քանի որ յուրաքանչյուր ինդեքս կարող է ունենալ I կամ D. Մենք անցնում ենք յուրաքանչյուր նիշի վրա միայն մեկը: Այսպիսով, ժամանակի բարդությունը գծային է:

Տիեզերական բարդություն

ՎՐԱ), քանի որ մենք ստեղծել ենք ելքային բնույթի զանգված ՝ արդյունքը պահելու համար: Խնդրի տիեզերական բարդությունը նույնպես գծային է: