Улучшить алгоритм Python

Question

Улучшить алгоритм Python

Рейтинг: -1Ответов: 2Опубликовано: 14.08.2023

Помогите, пожалуйста, улучшить код по алгоритмической задаче на python.

Требования задачи коротко: дан массив длиной n. В массиве встречаются встречаются точки между которыми нужно рассчитать расстояние. В условии задачи это нули. Если кратко, то есть набор чисел: 4, 5, 0, 3, 2, 0, а должно на выходе быть 2, 1, 0, 1, 1, 0.

Преподаватель сказал сделать решение путем срезов. Создаем массив нулей и двигаясь по нему вперед увеличиваем значение 0, 1, 2, 3, 4, 5 и т.д. потом доходим до нуля и вспоминаем, какой индекс был у прежнего нуля (его стоит хранить) и делаем обратный срез, т.е. перезаписываем данные. После этого вновь меняем индекс нуля и двигаемся дальше.

Мой код:

def distance(count, list):
    result = [0] * count
    point = None
    for index, value in enumerate(list):
        if value == '0':
            if point is None:
                point = index
                if index == 0:
                    continue
                else:
                    result[:index] = result[(index - 1)::-1]
            else:
                middle = (len(result[point:index])) // 2
                result[(index - middle):index] = result[(point + middle):point:-1]
                point = index
        else:
            result[index] = (index + 1) if point is None else (result[index - 1] + 1)

    return result

Проблема в том, что у меня есть отдельное условие, что делать есть ноль встречается первым. Если его не поставить, вполне ожидаемо в результате список добавит себе в конец нулей на длину списка, ведь я обращаюсь к предыдущему индексу от нуля. Преподаватель пишет, что если чуть изменить строку result[:index] = result[(index - 1)::-1] то от условия можно будет избавиться. Я совсем не понимаю как.

python алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 0

Не то, чтобы совсем избавиться от условия, но без отдельных ветвей:

def distance(lst):
    result = [0] * len(lst)
    point = None
    for index, value in enumerate(lst):
        if value == 0:
            if point is None:
                point = index
                result[:index] = result[(index-int(index>0))::-1]
            else:
                middle = (len(result[point:index])) // 2
                result[(index - middle):index] = result[(point + middle):point:-1]
                point = index
        else:
            #result[index] = (index + 1) if point is None else (result[index - 1] + 1)
            result[index] = result[index - 1] + 1
    return result

Answer 2

▲ 0

Выделить нули в отдельный список. Нарисовать спуск в начале списка до первого нуля. Нарисовать горки между нулями. Нарисовать подъём в конце списка после последнего нуля. Всё на срезах, только один if:

def distance(n, lst):
    assert n == len(lst)

    zeros = [i for i, v in enumerate(lst) if v == '0']

    result = [None] * n

    def up(i, j):
        result[i:j] = range(0, j - i)

    def down(i, j):
        result[i:j] = range(j - i, 0, -1)

    # спуск до первого нуля
    down(0, zeros[0])

    it = iter(zeros)
    next(it)
    for i, j in zip(zeros, it):
        # горка между нулями
        k = (j + i + 1) // 2
        up(i, k)
        down(k, j)

    # подъём после последнего нуля
    up(zeros[-1], n)

    return result

Если функцию переделать в генератор, не надо будет хранить даже результат:

def distance(n, lst):
    assert n == len(lst)

    zeros = [i for i, v in enumerate(lst) if v == '0']

    def up(i, j):
        return range(0, j - i)

    def down(i, j):
        return range(j - i, 0, -1)

    yield from down(0, zeros[0])

    it = iter(zeros)
    next(it)
    for i, j in zip(zeros, it):
        k = (j + i + 1) // 2
        yield from up(i, k)
        yield from down(k, j)

    yield from up(zeros[-1], n)

Улучшить алгоритм Python

Ответы