Блог

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

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

Заданный массив flowers состоит из чисел от 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.

В соответствии с формулировками задачи:

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

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

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

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

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

• День 1: в слоте 1 распустится цветок.
• День 2: в слоте 3 распустится цветок.
• День 3: во втором слоте распустится цветок

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

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

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

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

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

Вам нужно найти подмассив, содержащий k цветов без остатка между 2 цветками blossom.

 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] amp;amp; 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;
    }
  

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

 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 amp;amp; flower - lower - 1 == k ||
                higher != null amp;amp; higher - flower - 1 == k)
            return day;
    }
    return -1;
}
  

}