Задача интервью с массивом целых чисел, представляющих блочные башни, необходимо создать ступенчатый шаблон за минимальное количество ходов

Получил эту проблему:

Имея массив целых чисел «башни», представляющий высоту некоторых блочных башен (в количестве блоков), необходимо написать код Python, чтобы расположить башни в виде восходящей или нисходящей ступенчатой ​​​​шаблоны. Это означает, что высота каждой башни должна отличаться от высоты соседей ровно на 1, а вся последовательность должна быть строго возрастающей или убывающей. Чтобы изменить башни, вы можете сделать несколько ходов, добавляя только один блок на вершину любой башни. Ваша задача — найти минимальное количество ходов, необходимое для последовательного увеличения или уменьшения башен, в зависимости от того, какая последовательность требует меньшего количества ходов.

Пример: ввод towers=[1,4,3,2] вывод 4. Означает «нам нужно добавить 4 блока к вершине 1-й башни, чтобы получить последовательно более короткий массив [5,4,3,2]»

Пример 2: ввод towers=[5,7,9,4,11] вывод 9. Означает «добавить 2 блока на вершину 1-й башни, + добавить 1 блок на вершину 2-й, + добавить 6 блоков на вершину 4-й башни», 9 = 2 + 1 + 6, чтобы получить окончательный массив [7,8,9,10,11]».

Не нашел как решить, подскажите.

Похоже, вы просите нас написать этот код для вас. Это не совсем цель этого сайта. Мы бы предпочли, чтобы вы написали его сами, с небольшой помощью. Итак, имея это в виду, каков ваш КОНКРЕТНЫЙ вопрос программирования в связи с этой проблемой?

John Gordon 12.02.2023 20:14

Не совсем, для меня все равно уже поздно :) Но хотелось бы обсудить или понять, как это сделать. И это было бы полезно для кого-то в будущем

lugger1 12.02.2023 20:17
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
0
2
127
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Оригинальное решение

Возьмите башни = [5,7,9,4,11]. рассмотрим опорную диагональ [0,1,2,3,4]. Различия [5,6,7,1,7]. Таким образом, мы должны переместить опорную диагональ вверх на 7. Она становится [7,8,9,10,11]. Затем он касается линии горизонта сверху, и разница с башнями составляет [2,1,0,6,0]. И 2 + 1 + 0 + 6 + 0 равно 9. Или вместо того, чтобы корректировать 5 разностей на 7, просто измените их сумму на 5 * 7.

Для [1,4,3,2] то же самое, но нам нужна нисходящая ссылка [0,-1,-2,-3]. Для каждого входа мы пробуем как по возрастанию, так и по убыванию, и находим лучший.

for towers in [1,4,3,2], [5,7,9,4,11]:
    print(min(
        max(d)*len(d) - sum(d)
        for m in [-1,1]
        for d in [[t-m*i for i, t in enumerate(towers)]]
    ))

Вывод (Попробуйте онлайн!):

4
9

Наверное проще

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

for towers in [1,4,3,2], [5,7,9,4,11]:
    print(min(
        sum(r-t for r, t in enumerate(ts, start=up))
        for ts in [towers, towers[::-1]]
        for up in [max(t-r for r, t in enumerate(ts))]
    ))

Решение с постоянным пространством

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

towers = [5,7,9,4,11]
ref = total = 0
for i, tow in enumerate(towers):
    if tow > ref:
        total += i * (tow - ref)
        ref = tow
    total += ref - tow
    ref += 1
print(total)

Попробуйте онлайн!

Может ли одна из башен быть нулевой? Что, если башни [0, 8, 2, 0, 9]? Просто любопытно.

Daniel Hao 12.02.2023 21:52

@DanielHao Да, почему бы и нет? Мое первое решение может обрабатывать даже отрицательные башни. (Мое только что добавленное второе решение предполагает неотрицательность, хотя при необходимости это можно решить.)

Kelly Bundy 12.02.2023 22:02

@ kelly-bundy Быстрый вопрос: как работает эта конструкция с 2 элементами «для» в первом решении и с 3 элементами «для»? Это не обычные циклы, верно?

lugger1 13.02.2023 18:41

@lugger1 Это выражение генератора с несколькими предложениями for.

Kelly Bundy 13.02.2023 18:43

А, точно, точно...

lugger1 13.02.2023 18:46

Другие вопросы по теме