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


Сложный уровень средний
Часто спрашивают в Акколит Амазонка Фанатики Goldman Sachs Info Edge Snapchat
массив Стек строка

Задача «Сформировать минимальное число из заданной последовательности» гласит, что вам дан некоторый шаблон Является и 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, если истина, верните -XNUMX.
  2. Объявите массив символов размера n + 1 и установите значение count равным 1.
  3. Начать обход массива от 0 до n (включительно).
    1. Проверить, если i равно n или текущий символ строки равен «I», если true, то
      1. Перейти по массиву от предыдущего значения до -1.
        1. Обновите значения выходного массива, выполнив следующие шаги.
          1. Увеличьте значение count и сохраните его в выходном массиве.
          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. Внутри этого цикла мы продолжаем увеличивать значение count и сохранять в выходной массив с индексом j + 1. Затем проверьте, имеет ли значение j Больше или равно 0 а также если текущий символ - «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. Итак, мы можем сказать что мы входим во вложенный цикл, когда встречаем I, и работаем с индексами, в которых хранится D. Поскольку каждый индекс может иметь либо I, либо D. Мы обходим каждый символ только по одному. Таким образом, временная сложность линейна.

Космическая сложность

НА), потому что мы создали массив выходных символов для хранения результата. Пространственная сложность задачи также линейна.