Вопрос:
Есть сетка m*n с мячом. Мяч изначально находится в позиции [start_row, start_column] . Вам разрешено перемещать мяч в одну из четырех соседних ячеек сетки (возможно, за пределы сетки, пересекая границу сетки). К мячу можно применить не более max_move ходов.
Дайте пять целых чисел m , n, max_move , start_row , start_column , верните количество путей для перемещения мяча за пределы сетки. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
Решение:
Для рекурсивного решения в базовом случае start_row или start_column будет либо m, либо n соответственно. В этом случае мы возвращаем 1path. Другим базовым случаем будет, когда max_move равно 0 . В этом случае мы возвращаем 0 путь.
В остальном мы добавляем пути движения всех четырех направлений и уменьшаем значение max_move на 1 для каждого отдельного движения. Затем мы возвращаем сумму всех четырех путей.
Вот реализация:
def find_paths(m: int, n: int, max_move: int, start_row: int, start_column: int) -> int:
if start_row == m or start_column == n or start_row < 0 or start_column < 0:
return 1
elif max_move == 0:
return 0
else:
paths = find_paths(m, n, max_move-1, start_row-1, start_column) + \
find_paths(m, n, max_move-1, start_row+1, start_column) + \
find_paths(m, n, max_move-1, start_row, start_column-1) + \
find_paths(m, n, max_move-1, start_row, start_column+1)
return paths
m, n, max_move, start_row, start_column = 2, 2, 2, 0, 0
print(find_paths(m, n, max_move, start_row, start_column)) # prints 6
m_1, n_1, max_move_1, start_row_1, start_column_1 = 1, 3, 3, 0, 1
print(find_paths(m_1, n_1, max_move_1, start_row_1, start_column_1)) # prints 12
Дерево рекурсии для m=2, n=2, start_row=0, start_column=0, max_move=2 выглядит так:
Сложность выполнения: O(4^n), где 4 — четыре направления, а n — max_move .
Пространственная сложность: O(n), где n — глубина рекурсии.
Теперь давайте перейдем к запомненной версии реализации. Мемоизация помогает устранить избыточность вычислений за счет сохранения кеша уже вычисленных параметров.
Мы используем start_row, start_column, max_move в качестве ключа кэша, поскольку именно эти параметры изменяются.
from typing import Dict, Tuple
from collections import defaultdict
def find_paths(m: int, n: int, max_move: int, start_row: int, start_column: int, memo: Dict[Tuple[int, int, int], int]) -> int:
if start_row == m or start_column == n or start_row < 0 or start_column < 0:
return 1
elif max_move == 0:
return 0
elif (start_row, start_column, max_move) in memo:
return memo[(start_row, start_column, max_move)]
else:
paths = find_paths(m, n, max_move-1, start_row-1, start_column, memo) + \
find_paths(m, n, max_move-1, start_row+1, start_column, memo) + \
find_paths(m, n, max_move-1, start_row, start_column-1, memo) + \
find_paths(m, n, max_move-1, start_row, start_column+1, memo)
memo[(start_row, start_column, max_move)] = paths
return memo[(start_row, start_column, max_move)]
memo = defaultdict(int)
m, n, max_move, start_row, start_column = 2, 2, 2, 0, 0
print(find_paths(m, n, max_move, start_row, start_column, memo)) # prints 6
memo_1 = defaultdict(int)
m_1, n_1, max_move_1, start_row_1, start_column_1 = 1, 3, 3, 0, 1
print(find_paths(m_1, n_1, max_move_1, start_row_1, start_column_1, memo_1)) # prints 12
Сложность выполнения: O(m*n*N), где m — размер строки, n — размер столбца, а N — максимальный ход.
Сложность пространства: O(m*n*N), где m — размер строки, n — размер столбца, а N — максимальный ход.
Теперь давайте займемся реализацией динамического программирования (DP). Две вещи, которые следует помнить для DP, — это распознавание подзадачи и использование решения подзадачи для построения решения целевых параметров.
Подпроблема заключается в том, что если значения координат x,y выходят за пределы размера сетки. В этом шаге мы добавим 1 к текущему местоположению, иначе мы добавим то, что у нас было из местоположения предыдущего хода, к текущему местоположению.
Вот реализация:
def find_paths(m: int, n: int, max_move: int, start_row: int, start_column: int) -> int:
dp = [[[0]*n for _ in range(m)] for _ in range(max_move+1)]
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for k in range(1, max_move+1):
for i in range(m):
for j in range(n):
for d_i, d_j in dirs:
n_i, n_j = d_i+i, d_j+j
if n_i < 0 or n_i >= m or n_j < 0 or n_j >= n:
dp[k][i][j] += 1
else:
dp[k][i][j] += dp[k-1][n_i][n_j]
return dp[max_move][start_row][start_column]
m, n, max_move, start_row, start_column = 2, 2, 2, 0, 0
print(find_paths(m, n, max_move, start_row, start_column)) # prints 6
m_1, n_1, max_move_1, start_row_1, start_column_1 = 1, 3, 3, 0, 1
print(find_paths(m_1, n_1, max_move_1, start_row_1, start_column_1)) # prints 12
Сложность выполнения: O(k*m*n), где k – максимально допустимое перемещение, m – размер строки, n – размер столбца.
Сложность пространства: O(k*m*n), где k – максимально допустимое количество ходов, m – размер строки, n – размер столбца.
Спасибо, что зашли так далеко! 🎈
Вопрос:
Двоичное дерево, вид справа
Учитывая root двоичного дерева, представьте, что вы стоите на правой стороне от него, верните значение видимых узлов, упорядоченных сверху вниз.
Это для отработки того, что задает вопрос.
Из схемы легко учесть только узел right. Что, если левое дерево глубже, чем правое? Поэтому нам нужно учитывать обе стороны дерева.
Вот реализация:
from typing import Optional, List
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def right_side_view(root: Optional[TreeNode]) -> List[int]:
if root is None:
return []
q = deque([root])
res = []
while q:
size = len(q)
last_node = None
for _ in range(size):
node = q.popleft()
last_node = node
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if last_node:
res.append(last_node.val)
return res
t1 = TreeNode(1)
t1.left = TreeNode(2)
t1.right = TreeNode(3)
t1.left.right = TreeNode(5)
t1.right.right = TreeNode(4)
print(right_side_view(t1)) # prints [1, 3, 4]
Сложность выполнения: O(n), где n — высота дерева.
Сложность пространства: O(2^n), где n — высота дерева.
Это все для этого поста. Поздравляем, вы узнали больше об алгоритмах! 🌻🙌
До следующего раза, ✨
Вдохновение:
Вы можете поддержать меня на Патреоне!
