Это первая часть серии практических задач по программированию на Python, моего подхода к ним и уроков, извлеченных из них. Идеи основаны на принципах практики кодирования интервью, изложенных Паркером на https://www.interviewcake.com/.
Первая проблема:
Шаблон жадного алгоритма, электронная почта №2, пример шаблона №2
https://www.interviewcake.com/question/python/stock-price
Приведенный пример:
stock_prices = [10, 7, 5, 8, 11, 9] get_max_profit(stock_prices) # Returns 6 (buying for $5 and selling for $11)
Эта примерная задача предназначена для алгоритмического шаблона «Жадный», поэтому нам нужно отслеживать лучший ответ «на данный момент».
Я чувствовал, что мне нужно знать индексы списка, чтобы сравнивать их, поэтому я использовал enumerate. Мне нужно было сравнить каждый элемент с элементами, которые появятся позже, и найти лучший номер. Я знал, что мне нужно сравнивать только предметы, которые идут ПОСЛЕ каждого предмета, потому что вы должны сначала купить, а ПОТОМ продать. Каждый индекс списка представляет собой цену акции в данную минуту.
Это решение, которое я придумал, и для меня это своего рода стиль решения проблем, когда дело доходит до такого рода проблем (сравнение элементов в списке), я почти всегда буду использовать вложенный цикл for. Даже большинство ответов StackOverflow для сравнений списков Python, на которые я смотрел, использовали их. Когда я закончил это решение, я пошел, чтобы ответить на вопрос, но когда они упомянули, что это можно сделать без вложенных циклов for, я действительно попал в петлю. Я понятия не имел, как справиться с этим по-другому. Что я узнал от Паркера, так это то, что вложенные циклы for не являются наиболее эффективным решением, потому что они занимают время O (n2) вместо времени O (n). Потратив немного времени, пытаясь понять это, я, наконец, сдался и взглянул на его решение:
Разница между нашими решениями заключается в том, что, поскольку мое решение выполняет цикл по списку, а затем снова выполняет цикл по списку ДЛЯ КАЖДОГО ЭЛЕМЕНТА в списке, реализация моего решения займет экспоненциально больше времени, чем его решение, которое просто проходит по списку один раз. Мое решение подходит для относительно небольших списков, но становится проблематичным по мере их увеличения.
Урок здесь заключается в том, что если немного больше подумать о проблеме и понять, какие переменные следует отслеживать, мы можем сэкономить много времени на вычисления при работе с большими списками. В этом случае я знал, что мне нужно отслеживать максимальную прибыль по мере продвижения, и я мог бы избежать повторного просмотра списка дважды, просто отслеживая самую низкую цену, которую я видел до сих пор, и проверяя, не вычитается ли она. от текущей цены даст мне новую максимальную прибыль. В следующий раз, когда я столкнусь с такой проблемой, я определенно подумаю немного о том, какие переменные я могу отслеживать, чтобы поддерживать время обработки на уровне O(n), и просто пройдусь по списку один раз.
Если у вас есть какие-либо мысли или отзывы, пожалуйста, не стесняйтесь оставлять комментарии! Я делаю это, чтобы учиться и расти, поэтому, если у вас есть идеи, дайте мне знать!
Следующая статья: ПП №2
