Берілген қатардан минималды санды құрыңыз


Күрделілік дәрежесі орта
Жиі кіреді Акколит Amazon Фанатика Голдман Сакс Ақпараттық шеті Snapchat
Array үйме String

«Берілген дәйектіліктен минималды санды құру» мәселесінде сізге бірнеше өрнек берілгендігі айтылған Мен және D тек. Мағынасы 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 немесе жолдың ағымдағы таңбасы «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 -дан үлкен немесе тең 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

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

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

O (N) қайда «N» - сұраным жолының ұзындығы. Алдымен кірістірілген цикл ішіне кіретіндігімізді тексеріңіз, егер біз оның соңына жеткенде немесе ағымдағы индекс I болса. Ал кірістірілген цикл кері бағытта жүреді, ал егер I кездессе, біз циклден шығамыз. біз I кездескенде кірістірілген циклге кіріп, оларда D сақталған индекстермен жұмыс жасаймыз. Әр индексте I немесе D болуы мүмкін болғандықтан, біз әр таңбадан тек біреуін өтеміз. Осылайша уақыттың күрделілігі сызықтық болып табылады.

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

O (N), өйткені біз нәтижені сақтау үшін шығыс таңбалар жиымын құрдық. Мәселе үшін кеңістіктің күрделілігі де сызықтық болып табылады.