Лучшие решения для задач Microsoft на собеседовании. Минимальные шаги, чтобы сделать сваи одинаковой высоты.

Описание:

Алекса дается n стопок одинаковой или неравной высоты. За один шаг Alexa может удалить любое количество коробок из стопки, имеющей максимальную высоту, и попытаться сделать ее равной той, которая чуть меньше максимальной высоты стопки. Определите минимальное количество ступенек, необходимых для того, чтобы все сваи были равны по высоте.

Пример 1:

Input: piles = [5, 2, 1]
Output: 3
Explanation:
Step 1: reducing 5 -> 2 [2, 2, 1]
Step 2: reducing 2 -> 1 [2, 1, 1]
Step 3: reducing 2 -> 1 [1, 1, 1]
So final number of steps required is 3.

Решение:

Давайте визуализируем груды, давайте использовать A вместо ящиков

5: AAAAA

2: AA

1: A

На первом этапе мы сокращаем 5: AAAAA до 2: AA.

2: AA

1: A

На втором этапе мы разрезаем первые струны 2: AA на 1: A.

1: A

1: AA

1: A

На третьем этапе мы разрезаем первые струны 2: AA на 1: A.

1: A

Если у нас будет две стопки одинаковой длины, например:

5: AAAAA

1: A

На первом этапе мы сокращаем первые 5: AAAAA до 1: A:

1: A

5: AAAAA

1: A

На втором этапе мы сокращаем вторые 5: AAAAA до 1: A:

1: A

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

Код C ++:

int solution(vector<int> v) {
    int v_size = v.size();
    if(v_size < 2) { return 0; }
    std::sort(v.begin(), v.end());
    int sum = 0;
    for (int i = 1; i < v_size; ++i) {
        if (v[v_size - i - 1] != v[v_size - i]) {
            sum += i;
        }
    }
    return sum;
}

Сложность этого решения составляет O (N * Log (N)), где N - длина строки, но я считаю, что есть решение с линейной сложностью, которое я просто не могу хорошо обработать во всех угловых случаях.

Репозиторий с полной версией проекта вы можете найти здесь: https://github.com/jolly-fellow/microsoft/tree/master/min_steps_to_make_piles_equal_height

Вернуться к оглавлению.

Лучшие решения для задач Microsoft на собеседовании. Минимальные шаги, чтобы сделать сваи одинаковой высоты.