Разбор задачи про замену 0 и максимальную последовательность 1
Эту задачу можно эффективно решить за линейное время и константную память. Мне известно как минимум 3 таких решения. Но приведу, на мой взгляд, наиболее элегантное и понятное из них.
Идея решения состоит в том, чтобы обходить исходный список и сохранять индекс предыдущего 0, который мы встретили. Так мы можем легко узнать общее количество 1 между текущим и предыдущим 0 для каждого последующего 0.
Временная сложность приведенного на скриншоте выше решения составляет O(n) и не требует дополнительной памяти.
Какую задачу хотите, чтобы я разобрал следующей? Присылайте в комментарии или л. с.)
#задачиссобеседований
Эту задачу можно эффективно решить за линейное время и константную память. Мне известно как минимум 3 таких решения. Но приведу, на мой взгляд, наиболее элегантное и понятное из них.
Идея решения состоит в том, чтобы обходить исходный список и сохранять индекс предыдущего 0, который мы встретили. Так мы можем легко узнать общее количество 1 между текущим и предыдущим 0 для каждого последующего 0.
Временная сложность приведенного на скриншоте выше решения составляет O(n) и не требует дополнительной памяти.
Какую задачу хотите, чтобы я разобрал следующей? Присылайте в комментарии или л. с.)
#задачиссобеседований