მინიმალური რაოდენობის ფორმა მოცემული თანმიმდევრობიდან


Რთული ტური საშუალო
ხშირად ეკითხებიან თანამოსაყრელი Amazon ფანატიკა Goldman Sachs ინფო ზღვარი Snapchat
Array დასტის სიმებიანი

პრობლემა "მოცემული თანმიმდევრობიდან შექმნა მინიმალური რიცხვი" აცხადებს, რომ თქვენ მოცემულია გარკვეული ნიმუში მე და მხოლოდ მნიშვნელობა 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 ან სიმების ამჟამინდელი სიმბოლო უდრის "მე" -ს, თუ ასეა მაშინ
      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 მეტია ან ტოლი 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

ჯავის კოდი მოცემული თანმიმდევრობიდან მინიმალური რაოდენობის შესაქმნელად

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

სირთულის ანალიზი

დროის სირთულე

O (N) სადაც "N" არის შეკითხვის სტრიქონის სიგრძე. პირველი შეამოწმეთ, რომ ჩასმული მარყუჟის შიგნით შევალთ, მხოლოდ იმ შემთხვევაში, თუ ბოლომდე მივაღწიეთ ან თუ ამჟამინდელი ინდექსია I. და ჩასმული მარყუჟი უკანა მიმართულებით გადის და მარყუჟიდან გამოვდივართ, თუ I გვხვდება. ასე რომ, ჩვენ შეგვიძლია ვთქვათ რომ ჩავდგათ მარყუჟში, როდესაც I- ს წავაწყდებით და ვმუშაობთ იმ ინდექსებზე, რომლებზეც D ინახება. მას შემდეგ, რაც თითოეულ ინდექსს შეიძლება ჰქონდეს I ან D. ჩვენ თითოეულ პერსონაჟს მხოლოდ ერთით ვაკვირდებით. ამრიგად, დროის სირთულე წრფივია.

სივრცის სირთულე

O (N), რადგან ჩვენ შევქმენით გამომავალი სიმბოლოების მასივი შედეგის შესანახად. სივრცის სირთულე პრობლემისთვის ასევე ხაზოვანია.