Вопрос для интервью:
Вам дана сетка из нулей и единиц.Вы можете произвольно выбрать любую точку в этой сетке.Вы должны написать функцию, которая делает две вещи:
- Если вы выберете, например, координату (3,4), и она равна нулю, вам нужно перевернуть ее на единицу.Если это единица, вам нужно перевернуть ее в ноль.
- Вам нужно вернуть наибольшую непрерывную область с наибольшим количеством, т.е. те, которые должны быть как минимум связаны с другим.
Например,
[0,0,0,0]
[0,1,1,0]
[1,0,1,0]
У нас самый большой регион из трех.У нас есть еще одна область, в которой есть только одна (находится по координатам (2,0)).
Вам нужно найти алгоритм, который решит эту проблему, и вы будете вызывать эту функцию много раз.Вы должны убедиться, что ваше амортизированное время выполнения является наименьшим, которого вы можете достичь.
Мое решение, которое имеет временную сложность: O (num_row * num_col) каждый раз, когда вызывается эта функция:
def get_all_coordinates_of_ones(grid):
set_ones = set()
for i in range(len(grid[0])):
for j in range(len(grid)):
if grid[i][j]:
set_ones.add((i, j))
return set_ones
def get_largest_region(x, y, grid):
num_col = len(grid)
num_row = len(grid[0])
one_or_zero = grid[x][y]
if not grid[x][y]:
grid[x][y] = 1 - grid[x][y]
# get the coordinates of ones in the grid
# Worst Case O(num_col * num_row)
coordinates_ones = get_all_coordinates_of_ones(grid)
while coordinates_ones:
queue = collections.deque([coordinates_ones.pop()])
largest_one = float('-inf')
count_one = 1
visited = set()
while queue:
x, y = queue.popleft()
visited.add((x, y))
for new_x, new_y in ((x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y)):
if (0 <= new_x < num_row and 0 <= new_y < num_col):
if grid[new_x][new_y] == 1 and (new_x, new_y) not in visited:
count_one += 1
if (new_x, new_y) in coordinates_ones:-
coordinates_ones.remove((new_x, new_y))
queue.append((new_x, new_y))
largest_one = max(largest_one, count_one)
return largest_one
Мои предложенные модификации:
Использование Union Find по рангу.Обнаружена проблема.Объедините все те, которые находятся рядом друг с другом.Теперь, когда одна из координат перевернута, например, с нуля на одну, мне нужно будет удалить эту координату из области, к которой она подключена.
Вопросы:
- Какой самый быстрый алгоритм с точки зрения сложности времени?
- Использование Union Find с рангом влечет за собой удаление узла.Это способ улучшить сложность времени?Если да, есть ли реализация удаления узла в объединении поиска в Интернете?
------------------------ РЕДАКТИРОВАТЬ---------------------------------
Должны ли мы всегда вычитать один из степени из суммы (степень-1 каждой «вырезанной» вершины).Вот два примера: первый, где нам нужно вычесть один, и второй, где нам не нужно вычитать один:
Пример дерева выреза блока 1
Вырезвершина - это вершина B. Степень вершины B в дереве разрезов блоков равна 2.
Сумма (количество элементов каждой вершины «блока»): 2 (A, B) + 1 (B) + 3 (B,C, D) = 6
Сумма (степень каждой вершины среза): 1 (B)
Размер среза блока: 6 - 1 = 5, но должно быть 4 (A. B, C, D, E, F).Здесь нужно вычесть еще одну.
Пример дерева среза блока 2
Сумма (мощность каждой вершины блока): 3 (A, B, C) +1 (C) + 1 (D) + 3 (D, E, F) = 8
Сумма (степень каждой «вырезанной» вершины): 2 (C и D)
Блокразмер среза: 8 - 2 = 6, что (A. B, C, D, E, F).Здесь не нужно вычитать один.