Разбор типичных ошибок и антипаттернов в алгоритмических задачах.
Разбор типичных ошибок и антипаттернов в алгоритмических задачах. Учитесь на чужих ошибках!
# Неправильно
while left < right:
if condition:
pass # Забыли двигать указатель!
# Правильно
while left < right:
if condition:
left += 1
else:
right -= 1# Для поиска элемента: left <= right
# Для поиска пика/минимума: left < right# Неправильно
for right in range(len(s)):
expand()
while not valid():
shrink()
# Забыли: result = max(result, right - left + 1)
# Правильно
for right in range(len(s)):
expand()
while not valid():
shrink()
result = max(result, right - left + 1)# Порядок: Expand → Shrink → Update# В языках с фиксированными int:
mid = (left + right) // 2 # Может переполниться!
# Правильно:
mid = left + (right - left) // 2# Неправильно
while left < right:
mid = (left + right) // 2
if condition(mid):
left = mid # Зацикливание!
# Правильно
while left < right:
mid = left + (right - left) // 2
if condition(mid):
left = mid + 1
else:
right = mid# Неправильно — цикл в графе
def dfs(node):
process(node)
for neighbor in node.neighbors:
dfs(neighbor)
# Правильно
def dfs(node, visited):
if node in visited:
return
visited.add(node)
...# Неправильно
path.append(node)
dfs(node)
# Забыли path.pop()!
# Правильно
path.append(node)
dfs(node)
path.pop()# Для 1D DP: слева направо
# Для 2D DP: зависит от формулы# Coin Change: dp[0] = 0, остальные = inf
# Edit Distance: dp[i][0] = i, dp[0][j] = j# Неправильно — используем обновлённые значения
for i in range(n):
dp[i] = dp[i-1] + dp[i] # dp[i-1] уже обновлено!
# Правильно — итерация справа налево для 1D оптимизации
for i in range(n-1, -1, -1):
dp[i] = dp[i-1] + dp[i]# Неправильно
result.append(path) # Все элементы result ссылаются на один список!
# Правильно
result.append(path[:]) # Копия списка# После сортировки:
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue # Пропускаем дубликаты на этом уровне# Python имеет только min-heap
# Для max-heap используйте отрицание:
heapq.heappush(heap, -value)
max_val = -heapq.heappop(heap)# Неправильно — heap не обновляется
heap[0] = new_value # Нарушает свойство кучи!
# Правильно
heapq.heapreplace(heap, new_value)# Greedy требует доказательства!
# Проверяйте на контрпримерах# Interval Scheduling: сортировать по окончанию
intervals.sort(key=lambda x: x[1])
# Не по началу!# Неправильно — O(n) find
def find(self, x):
if self.parent[x] != x:
return self.find(self.parent[x])
return self.parent[x]
# Правильно — O(α(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]# Сначала сделайте правильно, потом оптимизируйте# Всегда проверяйте:
# - Пустой ввод
# - Один элемент
# - Максимальный размер
# - Отрицательные числа
# - Нули# Пишите тесты на:
# - Пример из условия
# - Граничные случаи
# - Минимальный ввод
# - Максимальный вводТипичные ошибки:
Запоминайте и избегайте!
Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.