Рубрики

Форма минимального числа из заданной последовательности

Учитывая шаблон, содержащий только я и D. Я для увеличения и D для уменьшения. Разработайте алгоритм для печати минимального числа, следующего за этим шаблоном. Цифры от 1 до 9 и цифры не могут повторяться.

Примеры:

   Input: D        Output: 21
   Input: I        Output: 12
   Input: DD       Output: 321
   Input: II       Output: 123
   Input: DIDI     Output: 21435
   Input: IIDDD    Output: 126543
   Input: DDIDDIID Output: 321654798 

Источник: Amazon Интервью Вопрос

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Ниже приведены некоторые важные наблюдения

Поскольку цифры не могут повторяться, на выходе может быть не более 9 цифр.

Также количество цифр в выходных данных на один больше, чем количество символов во входных данных. Обратите внимание, что первый символ ввода соответствует двум цифрам на выходе.

Идея состоит в том, чтобы перебрать массив ввода и отследить последнюю напечатанную цифру и максимальную напечатанную цифру. Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для вывода минимального числа, которое можно сформировать
// из заданной последовательности Is и Ds
#include <iostream>

using namespace std;

  
// Печатает минимальное число, которое можно сформировать из
// вводим последовательность I и D

void PrintMinNumberForPattern(string arr)

{

    // Инициализируем current_max (чтобы убедиться, что

    // мы не используем повторяющийся символ

    int curr_max = 0;

  

    // Инициализируем last_entry (Сохраняет трек для

    // последняя напечатанная цифра)

    int last_entry = 0;

  

    int j;

  

    // перебирать входной массив

    for (int i=0; i<arr.length(); i++)

    {

        // Инициализируем noOfNextD, чтобы получить количество

        // следующие D доступны

        int noOfNextD = 0;

  

        switch(arr[i])

        {

        case 'I':

            // Если буква 'I'

  

            // Рассчитать количество следующих подряд D

            // доступный

            j = i+1;

            while (arr[j] == 'D' && j < arr.length())

            {

                noOfNextD++;

                j++;

            }

                

            if (i==0)

            {

                curr_max = noOfNextD + 2;

  

                // Если «I» - первая буква, печать увеличивается

                // последовательность из 1

                cout << " " << ++last_entry;

                cout << " " << curr_max;

  

                // Устанавливаем максимальную цифру

                last_entry = curr_max;

            }

            else

            {

                // Если не первая буква

  

                // Получить следующую цифру для печати

                curr_max = curr_max + noOfNextD + 1;

  

                // Распечатать цифру для I

                last_entry = curr_max;

                cout << " " << last_entry;

            }

  

            // Для всей следующей последовательной печати 'D'

            // уменьшенная последовательность

            for (int k=0; k<noOfNextD; k++)

            {

                cout << " " << --last_entry;

                i++;

            }

            break;

  

        // Если буква 'D'

        case 'D':

            if (i == 0)

            {

                // Если 'D' - первая буква в последовательности

                // Находим количество следующих D доступных

                j = i+1;

                while (arr[j] == 'D' && j < arr.length())

                {

                    noOfNextD++;

                    j++;

                }

  

                // Рассчитать первую цифру для печати на основе

                // количество последовательных D

                curr_max = noOfNextD + 2;

  

                // печатать дважды в первый раз

                cout << " " << curr_max << " " << curr_max - 1;

  

                // Сохранить последнюю запись

                last_entry = curr_max - 1;

            }

            else

            {

                // Если текущее 'D' не первая буква

  

                // Decrement last_entry

                cout << " " << last_entry - 1;

                last_entry--;

            }

            break;

        }

    }

    cout << endl;

}

  
// Программа драйвера для тестирования выше

int main()

{

    PrintMinNumberForPattern("IDID");

    PrintMinNumberForPattern("I");

    PrintMinNumberForPattern("DD");

    PrintMinNumberForPattern("II");

    PrintMinNumberForPattern("DIDI");

    PrintMinNumberForPattern("IIDDD");

    PrintMinNumberForPattern("DDIDDIID");

    return 0;

}

Джава

// Java-программа для печати минимального числа, которое может быть сформировано
// из заданной последовательности Is и Ds

class GFG 

{

      

    // Печатает минимальное число, которое можно сформировать из

    // вводим последовательность I и D

    static void PrintMinNumberForPattern(String arr) 

    {

        // Инициализируем current_max (чтобы убедиться, что

        // мы не используем повторяющийся символ

        int curr_max = 0;

  

        // Инициализируем last_entry (Сохраняет трек для

        // последняя напечатанная цифра)

        int last_entry = 0;

  

        int j;

  

        // перебирать входной массив

        for (int i = 0; i < arr.length(); i++) 

        {

            // Инициализируем noOfNextD, чтобы получить количество

            // следующие D доступны

            int noOfNextD = 0;

  

            switch (arr.charAt(i))

            {

                case 'I':

                    // Если буква 'I'

  

                    // Рассчитать количество следующих подряд D

                    // доступный

                    j = i + 1;

                    while (j < arr.length() && arr.charAt(j) == 'D'

                    {

                        noOfNextD++;

                        j++;

                    }

  

                    if (i == 0

                    {

                        curr_max = noOfNextD + 2;

  

                        // Если «I» - первая буква, печать увеличивается

                        // последовательность из 1

                        System.out.print(" " + ++last_entry);

                        System.out.print(" " + curr_max);

  

                        // Устанавливаем максимальную цифру

                        last_entry = curr_max;

                    

                    else 

                    {

                        // Если не первая буква

  

                        // Получить следующую цифру для печати

                        curr_max = curr_max + noOfNextD + 1;

  

                        // Распечатать цифру для I

                        last_entry = curr_max;

                        System.out.print(" " + last_entry);

                    }

  

                    // Для всей следующей последовательной печати 'D'

                    // уменьшенная последовательность

                    for (int k = 0; k < noOfNextD; k++)

                    {

                        System.out.print(" " + --last_entry);

                        i++;

                    }

                    break;

  

                // Если буква 'D'

                case 'D':

                    if (i == 0)

                    {

                        // Если 'D' - первая буква в последовательности

                        // Находим количество следующих D доступных

                        j = i + 1;

                        while (j < arr.length()&&arr.charAt(j) == 'D'

                        {

                            noOfNextD++;

                            j++;

                        }

  

                        // Рассчитать первую цифру для печати на основе

                        // количество последовательных D

                        curr_max = noOfNextD + 2;

  

                        // печатать дважды в первый раз

                        System.out.print(" " + curr_max + " " + (curr_max - 1));

  

                        // Сохранить последнюю запись

                        last_entry = curr_max - 1;

                    

                    else

                    {

                        // Если текущее 'D' не первая буква

  

                        // Decrement last_entry

                        System.out.print(" " + (last_entry - 1));

                        last_entry--;

                    }

                    break;

            }

        }

        System.out.println();

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        PrintMinNumberForPattern("IDID");

        PrintMinNumberForPattern("I");

        PrintMinNumberForPattern("DD");

        PrintMinNumberForPattern("II");

        PrintMinNumberForPattern("DIDI");

        PrintMinNumberForPattern("IIDDD");

        PrintMinNumberForPattern("DDIDDIID");

    }

}

  
// Этот код предоставлен Принчи Сингхом

python3

# Python3 программа для вывода минимального числа, которое
# может быть сформирован из заданной последовательности Is и Ds

  
# Печатает минимальное число, которое можно сформировать из
# последовательность ввода I и D

def PrintMinNumberForPattern(arr):

  

    # Инициализировать current_max (чтобы убедиться, что

    # мы не используем повторяющиеся символы

    curr_max = 0

  

    # Initialize last_entry (Отслеживает

    # последняя напечатанная цифра)

    last_entry = 0

    i = 0

  

    # Итерировать по входному массиву

    while i < len(arr):

  

        # Инициализировать noOfNextD, чтобы получить количество

        # следующие D доступны

        noOfNextD = 0

        if arr[i] == "I":

  

            # Если буква «Я»

  

            # Рассчитать количество следующих подряд D

            # доступный

            j = i + 1

            while j < len(arr) and arr[j] == "D":

                noOfNextD += 1

                j += 1

            if i == 0:

                curr_max = noOfNextD + 2

                last_entry += 1

  

                # Если «I» - первая буква, печать увеличивается

                # последовательность от 1

                print("", last_entry, end = "")

                print("", curr_max, end = "")

  

                # Установить максимальную достигнутую цифру

                last_entry = curr_max

            else:

  

                # Если не первая буква

  

                # Получить следующую цифру для печати

                curr_max += noOfNextD + 1

  

                # Печать цифры для I

                last_entry = curr_max

                print("", last_entry, end = "")

  

            # Для всей следующей печати 'D'

            # уменьшенная последовательность

            for k in range(noOfNextD):

                last_entry -= 1

                print("", last_entry, end = "")

                i += 1

  

        # Если буква 'D'

        elif arr[i] == "D":

            if i == 0:

  

                # Если «D» - первая буква в последовательности

                # Найти количество доступных следующих D

                j = i + 1

                while j < len(arr) and arr[j] == "D":

                    noOfNextD += 1

                    j += 1

  

                # Рассчитать первую цифру для печати на основе

                # количество последовательных D

                curr_max = noOfNextD + 2

  

                # Печатайте дважды в первый раз

                print("", curr_max, curr_max - 1, end = "")

  

                # Сохранить последнюю запись

                last_entry = curr_max - 1

            else:

  

                # Если текущее 'D' не первая буква

  

                # Decrement last_entry

                print("", last_entry - 1, end = "")

                last_entry -= 1

        i += 1

    print()

  
# Код драйвера

if __name__ == "__main__":

    PrintMinNumberForPattern("IDID")

    PrintMinNumberForPattern("I")

    PrintMinNumberForPattern("DD")

    PrintMinNumberForPattern("II")

    PrintMinNumberForPattern("DIDI")

    PrintMinNumberForPattern("IIDDD")

    PrintMinNumberForPattern("DDIDDIID")

  
# Этот код предоставлен
# sanjeev2552

C #

// C # программа для вывода минимального числа, которое можно сформировать
// из заданной последовательности Is и Ds

using System;

      

class GFG 

{

      

    // Печатает минимальное число, которое можно сформировать из

    // вводим последовательность I и D

    static void PrintMinNumberForPattern(String arr) 

    {

        // Инициализируем current_max (чтобы убедиться, что

        // мы не используем повторяющийся символ

        int curr_max = 0;

  

        // Инициализируем last_entry (Сохраняет трек для

        // последняя напечатанная цифра)

        int last_entry = 0;

  

        int j;

  

        // перебирать входной массив

        for (int i = 0; i < arr.Length; i++) 

        {

            // Инициализируем noOfNextD, чтобы получить количество

            // следующие D доступны

            int noOfNextD = 0;

  

            switch (arr[i])

            {

                case 'I':

                    // Если буква 'I'

  

                    // Рассчитать количество следующих подряд D

                    // доступный

                    j = i + 1;

                    while (j < arr.Length && arr[j] == 'D'

                    {

                        noOfNextD++;

                        j++;

                    }

  

                    if (i == 0) 

                    {

                        curr_max = noOfNextD + 2;

  

                        // Если «I» - первая буква, печать увеличивается

                        // последовательность из 1

                        Console.Write(" " + ++last_entry);

                        Console.Write(" " + curr_max);

  

                        // Устанавливаем максимальную цифру

                        last_entry = curr_max;

                    

                    else

                    {

                        // Если не первая буква

  

                        // Получить следующую цифру для печати

                        curr_max = curr_max + noOfNextD + 1;

  

                        // Распечатать цифру для I

                        last_entry = curr_max;

                        Console.Write(" " + last_entry);

                    }

  

                    // Для всей следующей последовательной печати 'D'

                    // уменьшенная последовательность

                    for (int k = 0; k < noOfNextD; k++)

                    {

                        Console.Write(" " + --last_entry);

                        i++;

                    }

                    break;

  

                // Если буква 'D'

                case 'D':

                    if (i == 0)

                    {

                        // Если 'D' - первая буква в последовательности

                        // Находим количество следующих D доступных

                        j = i + 1;

                        while (j < arr.Length&&arr[j] == 'D'

                        {

                            noOfNextD++;

                            j++;

                        }

  

                        // Рассчитать первую цифру для печати на основе

                        // количество последовательных D

                        curr_max = noOfNextD + 2;

  

                        // печатать дважды в первый раз

                        Console.Write(" " + curr_max + " " + (curr_max - 1));

  

                        // Сохранить последнюю запись

                        last_entry = curr_max - 1;

                    

                    else

                    {

                        // Если текущее 'D' не первая буква

  

                        // Decrement last_entry

                        Console.Write(" " + (last_entry - 1));

                        last_entry--;

                    }

                    break;

            }

        }

        Console.WriteLine();

    }

  

    // Код драйвера

    public static void Main(String[] args) 

    {

        PrintMinNumberForPattern("IDID");

        PrintMinNumberForPattern("I");

        PrintMinNumberForPattern("DD");

        PrintMinNumberForPattern("II");

        PrintMinNumberForPattern("DIDI");

        PrintMinNumberForPattern("IIDDD");

        PrintMinNumberForPattern("DDIDDIID");

    }

}

  
// Этот код предоставлен Принчи Сингхом

PHP

<?php
// PHP программа для печати минимум
// число, которое можно сформировать
// из заданной последовательности
// Есть и Ds

  
// Печатает минимальное количество
// который может быть сформирован из
// вводим последовательность I и D

function PrintMinNumberForPattern($arr)

{

    // Инициализируем current_max

    // (чтобы убедиться, что

    // мы не используем повтор

    // персонаж

    $curr_max = 0;

  

    // Инициализируем last_entry

    // (Отслеживает

    // последняя напечатанная цифра)

    $last_entry = 0;

  

    $j;

  

    // перебирать

    // входной массив

    for ($i = 0; $i < strlen($arr); $i++)

    {

        // Инициализируем noOfNextD

        // чтобы получить количество

        // следующие D доступны

        $noOfNextD = 0;

  

        switch($arr[$i])

        {

        case 'I':

            // Если буква 'I'

  

            // Рассчитать количество

            // следующие подряд D

            // доступный

            $j = $i + 1;

            while ($arr[$j] == 'D' && 

                   $j < strlen($arr))

            {

                $noOfNextD++;

                $j++;

            }

              

            if ($i == 0)

            {

                $curr_max = $noOfNextD + 2;

  

                // Если «I» это первая буква,

                // печать увеличивается

                // последовательность из 1

                echo " " , ++$last_entry;

                echo " " , $curr_max;

  

                // Установить макс

                // достигнута цифра

                $last_entry = $curr_max;

            }

            else

            {

                // Если не первая буква

  

                // Получить следующую цифру

                // печатать

                $curr_max = $curr_max

                            $noOfNextD + 1;

  

                // Распечатать цифру для I

                $last_entry = $curr_max;

                echo " " , $last_entry;

            }

  

            // Для всех следующих подряд 'D'

            // вывести уменьшенную последовательность

            for ($k = 0; $k < $noOfNextD; $k++)

            {

                echo " " , --$last_entry;

                $i++;

            }

            break;

  

        // Если буква 'D'

        case 'D':

            if ($i == 0)

            {

                // Если 'D' это первая буква

                // по порядку. Найти номер

                // из следующих D доступны

                $j = $i+1;

                while (($arr[$j] == 'D') && 

                       ($j < strlen($arr)))

                {

                    $noOfNextD++;

                    $j++;

                }

  

                // Рассчитать первую цифру

                // для печати на основе

                // количество последовательных D

                $curr_max = $noOfNextD + 2;

  

                // Печатать дважды для

                // первый раз

                echo " " , $curr_max

                     " " ,$curr_max - 1;

  

                // Сохранить последнюю запись

                $last_entry = $curr_max - 1;

            }

            else

            {

                // Если текущий 'D'

                // не первая буква

  

                // Decrement last_entry

                echo " " , $last_entry - 1;

                $last_entry--;

            }

            break;

        }

    }

      

echo "\n";

}

  
// Код драйвера

PrintMinNumberForPattern("IDID");

PrintMinNumberForPattern("I");

PrintMinNumberForPattern("DD");

PrintMinNumberForPattern("II");

PrintMinNumberForPattern("DIDI");

PrintMinNumberForPattern("IIDDD");

PrintMinNumberForPattern("DDIDDIID");

  
// Этот код предоставлен aj_36
?>

Выход:

 1 3 2 5 4
 1 2
 3 2 1
 1 2 3
 2 1 4 3 5
 1 2 6 5 4 3
 3 2 1 6 5 4 7 9 8

Это решение предложено Swapnil Trambake.

Альтернативное решение:
Давайте рассмотрим несколько фактов в случае минимального числа:

  • Цифры не могут повторяться, поэтому на выходе может быть не более 9 цифр.
  • Чтобы сформировать минимальное число, в каждом индексе выходных данных нас интересует минимальное число, которое может быть помещено в этот индекс.

Идея состоит в том, чтобы перебрать весь входной массив, отслеживая минимальное число (1-9), которое может быть размещено в этой позиции вывода.

Сложная часть, конечно, происходит, когда «D» встречается с индексом, отличным от 0. В таком случае мы должны отслеживать ближайший «I» слева от «D» и увеличивать каждое число в выходном векторе на 1 между «Я» и «D».

Мы рассмотрим базовый случай следующим образом:

  • Если первым символом ввода является «I», то мы добавляем 1 и 2 в выходной вектор и минимальное доступное число устанавливается равным 3. Индекс самого последнего «I» устанавливается равным 1.
  • Если первым символом ввода является 'D', то мы добавляем 2 и 1 в выходной вектор, и минимальное доступное число устанавливается равным 3, а индекс самого последнего 'I' устанавливается равным 0.

Теперь мы перебираем входную строку от индекса 1 до его конца и:

  • Если отсканированный символ имеет значение «I», минимальное значение, которое еще не использовалось, добавляется к выходному вектору. Мы увеличиваем значение минимального нет. доступно, и индекс самого последнего 'I' также обновляется.
  • Если отсканированный символ равен «D» в индексе i входного массива, мы добавляем i-й элемент из выходного вектора в выходной и отслеживаем ближайший «I» слева от «D» и увеличиваем каждое число в выходном векторе на 1. между «я» и «D».

Ниже приводится программа для того же:

C ++

// C ++ программа для вывода минимального числа, которое можно сформировать
// из заданной последовательности Is и Ds
#include<bits/stdc++.h>

using namespace std;

  

void printLeast(string arr)

{

    // min_avail представляет минимальное число, которое

    // все еще доступно для вставки в выходной вектор.

    // pos_of_I отслеживает самый последний индекс

    // где 'I' было найдено с выходным вектором

    int min_avail = 1, pos_of_I = 0;

  

    // вектор для хранения вывода

    vector<int>v;

  

    // покрываем базовые случаи

    if (arr[0]=='I')

    {

        v.push_back(1);

        v.push_back(2);

        min_avail = 3;

        pos_of_I = 1;

    }

    else

    {

        v.push_back(2);

        v.push_back(1);

        min_avail = 3;

        pos_of_I = 0;

    }

  

    // Пересечь остаток ввода

    for (int i=1; i<arr.length(); i++)

    {

        if (arr[i]=='I')

        {

            v.push_back(min_avail);

            min_avail++;

            pos_of_I = i+1;

        }

        else

        {

            v.push_back(v[i]);

            for (int j=pos_of_I; j<=i; j++)

                v[j]++;

  

            min_avail++;

        }

    }

  

    // напечатать номер

    for (int i=0; i<v.size(); i++)

        cout << v[i] << " ";

    cout << endl;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    printLeast("IDID");

    printLeast("I");

    printLeast("DD");

    printLeast("II");

    printLeast("DIDI");

    printLeast("IIDDD");

    printLeast("DDIDDIID");

    return 0;

}

Джава

// Java-программа для печати минимального числа, которое может быть сформировано
// из заданной последовательности Is и Ds

import java.io.*;

import java.util.*;

public class GFG {

  

       static void printLeast(String arr)

       {

              // min_avail представляет минимальное число, которое

              // все еще доступно для вставки в выходной вектор.

              // pos_of_I отслеживает самый последний индекс

              // где 'I' было найдено с выходным вектором

              int min_avail = 1, pos_of_I = 0

  

              // вектор для хранения вывода

              ArrayList<Integer> al = new ArrayList<>();

                

              // покрываем базовые случаи

              if (arr.charAt(0) == 'I'

              

                  al.add(1); 

                  al.add(2); 

                  min_avail = 3

                  pos_of_I = 1

              

  

              else

              {

                  al.add(2);

                  al.add(1);

                  min_avail = 3

                  pos_of_I = 0

              }

  

              // Пересечь остаток ввода

              for (int i = 1; i < arr.length(); i++)

              {

                   if (arr.charAt(i) == 'I')

                   {

                       al.add(min_avail);

                       min_avail++;

                       pos_of_I = i + 1;

                   }

                   else

                   {

                       al.add(al.get(i));

                       for (int j = pos_of_I; j <= i; j++)

                            al.set(j, al.get(j) + 1);

  

                       min_avail++;

                   }

              }

  

              // напечатать номер

              for (int i = 0; i < al.size(); i++)

                   System.out.print(al.get(i) + " ");

              System.out.println();

       }

  

  

       // Код драйвера

       public static void main(String args[])

       {

              printLeast("IDID"); 

              printLeast("I"); 

              printLeast("DD"); 

              printLeast("II"); 

              printLeast("DIDI"); 

              printLeast("IIDDD"); 

              printLeast("DDIDDIID"); 

       }

}
// Этот код предоставлен rachana soma

C #

// C # программа для вывода минимального числа, которое можно сформировать
// из заданной последовательности Is и Ds

using System;

using System.Collections.Generic; 

  

class GFG 

{

      

static void printLeast(String arr)

{

    // min_avail представляет минимальное число, которое

    // все еще доступно для вставки в выходной вектор.

    // pos_of_I отслеживает самый последний индекс

    // где 'I' было найдено с выходным вектором

    int min_avail = 1, pos_of_I = 0; 

  

    // вектор для хранения вывода

    List<int> al = new List<int>();

          

    // покрываем базовые случаи

    if (arr[0] == 'I'

    

        al.Add(1); 

        al.Add(2); 

        min_avail = 3; 

        pos_of_I = 1; 

    

  

    else

    {

        al.Add(2);

        al.Add(1);

        min_avail = 3; 

        pos_of_I = 0; 

    }

  

    // Пересечь остаток ввода

    for (int i = 1; i < arr.Length; i++)

    {

        if (arr[i] == 'I')

        {

            al.Add(min_avail);

            min_avail++;

            pos_of_I = i + 1;

        }

        else

        {

            al.Add(al[i]);

            for (int j = pos_of_I; j <= i; j++)

                al[j] = al[j] + 1;

  

            min_avail++;

        }

    }

  

    // напечатать номер

    for (int i = 0; i < al.Count; i++)

        Console.Write(al[i] + " ");

    Console.WriteLine();

}

  

  
// Код драйвера

public static void Main(String []args)

{

    printLeast("IDID"); 

    printLeast("I"); 

    printLeast("DD"); 

    printLeast("II"); 

    printLeast("DIDI"); 

    printLeast("IIDDD"); 

    printLeast("DDIDDIID"); 

}
}

  
// Этот код предоставлен Rajput-Ji


Выход:

1 3 2 5 4 
1 2 
3 2 1 
1 2 3 
2 1 4 3 5 
1 2 6 5 4 3 
3 2 1 6 5 4 7 9 8 

Это решение предложено Ашутошем Кумаром .

Способ 3
Мы можем, что когда мы встречаемся с I, мы получаем числа в возрастающем порядке, но если мы сталкиваемся с 'D', мы хотим иметь числа в убывающем порядке. Длина выходной строки всегда на единицу больше входной строки. Так что цикл от 0 до длины жала. Мы должны брать числа от 1 до 9, поэтому мы всегда помещаем (i + 1) в наш стек. Затем мы проверяем, что является результирующим символом по указанному индексу. Итак, будет два случая:
Случай 1: Если мы встретили I или мы находимся на последнем символе входной строки, извлекаем его из стека и добавляем его в конец выходной строки, пока стек не опустеет.
Случай 2: если мы столкнулись с D, то мы хотим, чтобы числа в порядке убывания. Поэтому мы просто помещаем (i + 1) в наш стек.

C ++

// C ++ программа для вывода минимального числа, которое можно сформировать
// из заданной последовательности Is и Ds
#include <bits/stdc++.h>

using namespace std;

  
// Функция для декодирования заданной последовательности для построения
// минимальное число без повторяющихся цифр

void PrintMinNumberForPattern(string seq)

{

    // результат сохраняем строку вывода

    string result;

  

    // создаем пустой стек целых чисел

    stack<int> stk;

  

    // запускаем n + 1 раз, где n - длина входной последовательности

    for (int i = 0; i <= seq.length(); i++)

    {

        // вставляем число i + 1 в стек

        stk.push(i + 1);

  

        // если все символы входной последовательности

        // обработан или текущий символ 'I'

        // (увеличивается)

        if (i == seq.length() || seq[i] == 'I')

        {

            // запустить до тех пор, пока стек не станет пустым

            while (!stk.empty())

            {

                // удаляем верхний элемент из стека и

                // добавить его в решение

                result += to_string(stk.top());

                result += " ";

                stk.pop();

            }

        }

    }

  

    cout << result << endl;

}

  
// основная функция

int main()

{

    PrintMinNumberForPattern("IDID");

    PrintMinNumberForPattern("I");

    PrintMinNumberForPattern("DD");

    PrintMinNumberForPattern("II");

    PrintMinNumberForPattern("DIDI");

    PrintMinNumberForPattern("IIDDD");

    PrintMinNumberForPattern("DDIDDIID");

    return 0;

}

Джава

import java.util.Stack;

  
// Java-программа для печати минимального числа, которое может быть сформировано
// из заданной последовательности Is и Ds

class GFG {

  
// Функция для декодирования заданной последовательности для построения
// минимальное число без повторяющихся цифр

    static void PrintMinNumberForPattern(String seq) {

        // результат сохраняем строку вывода

        String result = "";

  

        // создаем пустой стек целых чисел

        Stack<Integer> stk = new Stack<Integer>();

  

        // запускаем n + 1 раз, где n - длина входной последовательности

        for (int i = 0; i <= seq.length(); i++) {

            // вставляем число i + 1 в стек

            stk.push(i + 1);

  

            // если все символы входной последовательности

            // обработан или текущий символ 'I'

            // (увеличивается)

            if (i == seq.length() || seq.charAt(i) == 'I') {

                // запустить до тех пор, пока стек не станет пустым

                while (!stk.empty()) {

                    // удаляем верхний элемент из стека и

                    // добавить его в решение

                    result += String.valueOf(stk.peek());

                    result += " ";

                    stk.pop();

                }

            }

        }

  

        System.out.println(result);

    }

  
// основная функция

    public static void main(String[] args) {

        PrintMinNumberForPattern("IDID");

        PrintMinNumberForPattern("I");

        PrintMinNumberForPattern("DD");

        PrintMinNumberForPattern("II");

        PrintMinNumberForPattern("DIDI");

        PrintMinNumberForPattern("IIDDD");

        PrintMinNumberForPattern("DDIDDIID");

    }

}
// Этот код предоставлен PrinciRaj1992

C #

// C # программа для вывода минимального числа, которое можно сформировать
// из заданной последовательности Is и Ds

using System;

using System.Collections;

public class GFG {

   
// Функция для декодирования заданной последовательности для построения
// минимальное число без повторяющихся цифр

    static void PrintMinNumberForPattern(String seq) {

        // результат сохраняем строку вывода

        String result = "";

   

        // создаем пустой стек целых чисел

        Stack stk = new Stack();

   

        // запускаем n + 1 раз, где n - длина входной последовательности

        for (int i = 0; i <= seq.Length; i++) {

            // вставляем число i + 1 в стек

            stk.Push(i + 1);

   

            // если все символы входной последовательности

            // обработан или текущий символ 'I'

            // (увеличивается)

            if (i == seq.Length || seq[i] == 'I') {

                // запустить до тех пор, пока стек не станет пустым

                while (stk.Count!=0) {

                    // удаляем верхний элемент из стека и

                    // добавить его в решение

                    result += String.Join("",stk.Peek());

                    result += " ";

                    stk.Pop();

                }

            }

        }

   

        Console.WriteLine(result);

    }

   
// основная функция

    public static void Main() {

        PrintMinNumberForPattern("IDID");

        PrintMinNumberForPattern("I");

        PrintMinNumberForPattern("DD");

        PrintMinNumberForPattern("II");

        PrintMinNumberForPattern("DIDI");

        PrintMinNumberForPattern("IIDDD");

        PrintMinNumberForPattern("DDIDDIID");

    }

}
// Этот код предоставлен 29AjayKumar


Выход:

1 3 2 5 4 
1 2 
3 2 1 
1 2 3 
2 1 4 3 5 
1 2 6 5 4 3 
3 2 1 6 5 4 7 9 8 

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Этот метод предоставлен Roshni Agarwal .

Метод 4 (с использованием двух указателей)
наблюдение

  1. Поскольку мы должны найти минимальное число без повторяющихся цифр, максимальная длина вывода может быть 9 (используя каждые 1-9 цифр один раз)
  2. Длина вывода будет ровно на единицу больше длины ввода.
  3. Идея состоит в том, чтобы перебрать строку и сделать следующее, если текущий символ равен «I» или строка заканчивается.
    1. Присвойте счет в порядке возрастания для каждого элемента от текущего -1 до следующего левого индекса «I» (или начальный индекс достигнут).
    2. Увеличьте счет на 1.
Input  :  IDID
Output : 13254

Input  :  I
Output : 12

Input  :  DD
Output : 321

Input  :  II
Output : 123

Input  :  DIDI
Output : 21435

Input  :  IIDDD
Output : 126543

Input  :  DDIDDIID
Output : 321654798

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа вышеуказанного подхода
#include <bits/stdc++.h> 

using namespace std; 

    
// Возвращает минимальное число из данной последовательности без повторяющихся цифр
string getMinNumberForPattern(string seq) 

    int n = seq.length();

  

    if (n >= 9)

        return "-1";

  

    string result(n+1, ' '); 

  

    int count = 1;  

  

    // Цикл выполняется для каждого входного символа, а также

    // еще один раз для присвоения ранга оставшимся символам

    for (int i = 0; i <= n; i++) 

    

        if (i == n || seq[i] == 'I')

        {

            for (int j = i - 1 ; j >= -1 ; j--)

            {

                result[j + 1] = '0' + count++;

                if(j >= 0 && seq[j] == 'I')

                    break;

            }

        }

    }

    return result;

}

    
// основная функция

int main() 

{

    string inputs[] = {"IDID", "I", "DD", "II", "DIDI", "IIDDD", "DDIDDIID"};

  

    for (string input : inputs)

    {

        cout << getMinNumberForPattern(input) << "\n";

    }

    return 0; 

}

Джава

// Java-программа вышеуказанного подхода

import java.io.IOException;

  

public class Test

{

    // Возвращает минимальное число из данной последовательности без повторяющихся цифр

    static String getMinNumberForPattern(String seq)

    {

        int n = seq.length();

  

        if (n >= 9)

            return "-1";

  

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

  

        int count = 1;

  

        // Цикл выполняется для каждого входного символа, а также

        // одно дополнительное время для присвоения ранга каждому оставшемуся персонажу

        for (int i = 0; i <= n; i++)

        {

            if (i == n || seq.charAt(i) == 'I')

            {

                for (int j = i - 1; j >= -1; j--)

                {

                    result[j + 1] = (char) ((int) '0' + count++);

                    if (j >= 0 && seq.charAt(j) == 'I')

                        break;

                }

            }

        }

        return new String(result);

    }

      

    public static void main(String[] args) throws IOException

    {

        String inputs[] = { "IDID", "I", "DD", "II", "DIDI", "IIDDD", "DDIDDIID" };

  

        for(String input : inputs)

        {

            System.out.println(getMinNumberForPattern(input));

        }

    }

}

python3

# Python3 программа вышеуказанного подхода

      
# Возвращает минимальное число из
# заданная последовательность без повторяющихся цифр

def getMinNumberForPattern(seq):

    n = len(seq) 

  

    if (n >= 9):

        return "-1"

  

    result = [None] * (n + 1

  

    count = 1

  

    # Цикл выполняется для каждого входного символа

    # а также одно дополнительное время для

    # присвоение ранга оставшимся персонажам

    for i in range(n + 1):

        if (i == n or seq[i] == 'I'):

            for j in range(i - 1, -2, -1):

                result[j + 1] = int('0' + str(count))

                count += 1

                if(j >= 0 and seq[j] == 'I'): 

                    break

    return result

      
Код водителя

if __name__ == '__main__':

    inputs = ["IDID", "I", "DD", "II"

              "DIDI", "IIDDD", "DDIDDIID"]

    for Input in inputs:

        print(*(getMinNumberForPattern(Input)))

  
# Этот код предоставлен PranchalK

C #

// C # программа вышеуказанного подхода

using System; 

class GFG

      
// Возвращает минимальное количество сделанное из заданного
// последовательность без повторяющихся цифр

static String getMinNumberForPattern(String seq) 

    int n = seq.Length; 

  

    if (n >= 9) 

        return "-1"

  

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

  

    int count = 1; 

  

    // цикл выполняется для каждого входного символа

    // а также одно дополнительное время для

    // присваиваем ранг каждому оставшемуся персонажу

    for (int i = 0; i <= n; i++) 

    

        if (i == n || seq[i] == 'I'

        

            for (int j = i - 1; j >= -1; j--) 

            

                result[j + 1] = (char) ((int) '0' + count++); 

                if (j >= 0 && seq[j] == 'I'

                    break

            

        

    

    return new String(result); 

  
// Код драйвера

public static void Main()

    String []inputs = { "IDID", "I", "DD", "II"

                        "DIDI", "IIDDD", "DDIDDIID" }; 

  

    foreach(String input in inputs) 

    

        Console.WriteLine(getMinNumberForPattern(input)); 

    


  
// Этот код предоставлен Rajput-Ji


Выход:

13254
12
321
123
21435
126543
321654798

Сложность времени: O (N)
Вспомогательное пространство: O (1)

Это решение предложено Бриджем Десаи .

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Форма минимального числа из заданной последовательности

0.00 (0%) 0 votes