Как анализировать алгоритм k пустых слотов?

В Leet Code есть алгоритм, который называется K Empty Slots. Я не понимаю ограничений. Я пытался найти лучшее объяснение вопроса, но не могу его найти. Это выглядит следующим образом:

Есть сад с N слотами. В каждом слоте есть цветок. N цветов расцветут один за другим через N дней. Каждый день будет распускаться ровно один цветок, и с тех пор он будет находиться в состоянии цветения.

Дан массив цветов, состоящий из чисел от 1 до N. Каждое число в массиве представляет собой место, где цветок раскроется в этот день.

Например, flowers[i] = x означает, что уникальный цветок, распустившийся в день i, будет в позиции x, где i и x будут находиться в диапазоне от 1 до N.

Также задано целое число k, нужно вывести, в какой день существуют два цветка в состоянии цветения, а также количество цветов между ними равно k и эти цветы не цветут.

Если такого дня нет, выведите -1.

Пример 1:

Вход:

цветы: [1,3,2]

k: 1

Выход: 2

Пояснение: На второй день распустились первый и третий цветок.

Пример 2:

Вход:

цветы: [1,2,3]

k: 1

Выход: -1

Примечание:

Данный массив будет находиться в диапазоне [1, 20000].

Я хочу решить это сам. Я хочу знать, есть ли более простое объяснение проблемы. Я не понимаю ввод k. Я не понимаю, почему первый пример вернул 2, а второй пример вернул -1.


algorithm data-structures array-algorithms
person Kelli    schedule 10.03.2019    source источник
comment
Для данного k вам нужно найти ближайший день, в который распускаются два цветка, а между ними k цветков, не распустившихся.   -  person Dillon Davis    schedule 10.03.2019

Ответы (3)


arrow_upward
1
arrow_downward

Согласно условиям задачи:

1) Есть сад с N слотами. В каждом слоте есть цветок. N цветов расцветут один за другим через N дней. Каждый день будет цвести ровно один цветок, и с тех пор он будет находиться в состоянии цветения

По сути, это говорит о том, что существует массив размера N, представляющий собой слоты, в которых цветы будут распускаться по одному в каждый день. Таким образом, размер массива скажет вам количество цветов.

2) Данный массив цветов состоит из чисел от 1 до N. Каждое число в массиве представляет собой место, где цветок раскроется в этот день.

arr[i] сообщит вам слот, в котором будет цвести цветок, а i (индекс) сообщит вам день, в который цветок будет цвести в этот день. Например:

[1,3,2] здесь говорит, что

  • День 1: цветок расцветает в слоте 1.
  • День 2: цветок расцветет в слоте 3.
  • День 3: цветок расцветет в слоте 2.

3) Также задано целое число k, вам нужно вывести, в какой день существуют два цветка в статусе цветения, а также количество цветов между ними равно k и эти цветы не цветут.

Из этого утверждения мы понимаем, что мы должны вывести тот день, когда два цветущих цветка находятся в таких слотах, что слоты между ними должны быть пустыми, а количество слотов между ними равно k. Если такого слота нет, вернуть -1.

Для первого примера. [1,3,2] здесь, как объяснено выше, в день 2 цветок будет цвести в слоте 3, а в день 1 цветок распустился в слоте 1, поэтому количество свободных слотов во второй день равно 1 (равно k) между ними. Следовательно, выходной день 2.

Во втором примере мы видим, что цветы находятся в последовательных слотах, поэтому между любыми из них нет нераспустившихся цветочных слотов, поэтому выход равен -1.

Надеюсь это поможет!

person Mrigank    schedule 10.03.2019

arrow_upward
1
arrow_downward

Вам нужно найти подмассив, содержащий k нераспустившихся цветов между двумя цветущими цветами.

public int kEmptySlots(int[] flowers, int k) {
        int[] days = new int[flowers.length];
        for (int i = 0; i < days.length; i++) {
            days[flowers[i] - 1] = i + 1;
        }
        int left = 0;
        int right = k + 1;
        int res = Integer.MAX_VALUE;
        for (int i = 1; right < days.length; i++) {
            // current days[i] is valid, continue scanning
            if (days[i] > days[left] && days[i] > days[right]) {
                continue;
            }
           // reach boundary of sliding window, since previous number are all valid, record result  
            if (i == right) {
                res = Math.min(res, Math.max(days[left],days[right]));
            }
            // not valid, move the sliding window
            left = i;
            right = left + k + 1;
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
person user3151077    schedule 30.01.2020

arrow_upward
1
arrow_downward

Оптимальным решением может быть:

class Solution {
public int kEmptySlots(int[] flowers, int k) {
    TreeSet<Integer> active = new TreeSet();
    int day = 0;
    for (int flower: flowers) {
        day++;
        active.add(flower);
        Integer lower = active.lower(flower)
        Integer higher = active.higher(flower);
        if (lower != null && flower - lower - 1 == k ||
                higher != null && higher - flower - 1 == k)
            return day;
    }
    return -1;
}

}

person Supriya Mishra    schedule 25.06.2021