Flood fill в матрице
Дана матрица целых чисел matrix, где число обозначает цвет клетки. Также даны координаты стартовой клетки x, y и новый цвет new_color.
Перекрасьте всю 4-связную область стартовой клетки в new_color: можно ходить вверх, вниз, влево и вправо только по клеткам исходного цвета стартовой клетки.
Верните измененную матрицу.
Сигнатура
def flood_fill(matrix: list[list[int]], x: int, y: int, new_color: int) -> list[list[int]]:Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Нажмите «Запустить проверки» или Ctrl+Enter.
Показать разбор
Подсказки
- Исходный цвет
Сохраните цвет стартовой клетки до перекраски.
- Только стороны
Диагональные соседи не входят в 4-связную область.
Идея решения
Сохраняем исходный цвет стартовой клетки, затем запускаем DFS или BFS.
Клетку можно добавить в обход, если она внутри матрицы и ее цвет равен исходному. Чтобы не зациклиться, перекрашиваем клетку в момент добавления или поддерживаем visited.
Если матрица пустая, координаты вне границ или новый цвет совпадает со старым, можно сразу вернуть исходную матрицу.
Эталонный код
def flood_fill(matrix: list[list[int]], x: int, y: int, new_color: int) -> list[list[int]]:
if not matrix or not matrix[0]:
return matrix
height = len(matrix)
width = len(matrix[0])
if x < 0 or x >= height or y < 0 or y >= width:
return matrix
old_color = matrix[x][y]
if old_color == new_color:
return matrix
stack = [(x, y)]
matrix[x][y] = new_color
while stack:
row, col = stack.pop()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr = row + dr
nc = col + dc
if 0 <= nr < height and 0 <= nc < width and matrix[nr][nc] == old_color:
matrix[nr][nc] = new_color
stack.append((nr, nc))
return matrixТоп-3 зарплаты в каждом департаменте
Даны таблицы Employee и Department.
Найдите сотрудников, которые входят в top-3 уникальных зарплат внутри своего департамента. Если несколько сотрудников имеют одинаковую зарплату, все они должны попасть в результат, если эта зарплата входит в top-3 уникальных зарплат департамента.
Схема
CREATE TABLE Department (
id INTEGER PRIMARY KEY,
name TEXT NOT NULL
);
CREATE TABLE Employee (
id INTEGER PRIMARY KEY,
name TEXT NOT NULL,
salary INTEGER NOT NULL,
departmentId INTEGER NOT NULL,
FOREIGN KEY (departmentId) REFERENCES Department(id)
);Верните Department, Employee, Salary. Отсортируйте результат по Department ASC, Salary DESC, Employee ASC.
Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Нажмите «Запустить проверки» или Ctrl+Enter.
Показать разбор
Подсказки
- Top уникальных зарплат
Используйте DENSE_RANK(), а не ROW_NUMBER().
- Связь таблиц
Employee.departmentId ссылается на Department.id.
Идея решения
Здесь нужен не ROW_NUMBER, а DENSE_RANK: одинаковые зарплаты получают один и тот же ранг, а следующая уникальная зарплата получает следующий номер без пропусков.
После ранжирования оставляем salary_rank <= 3 и выводим только публичные колонки результата.
Эталонный код
WITH ranked AS (
SELECT
d.name AS Department,
e.name AS Employee,
e.salary AS Salary,
DENSE_RANK() OVER (
PARTITION BY e.departmentId
ORDER BY e.salary DESC
) AS salary_rank
FROM Employee e
INNER JOIN Department d
ON e.departmentId = d.id
)
SELECT
Department,
Employee,
Salary
FROM ranked
WHERE salary_rank <= 3
ORDER BY Department ASC, Salary DESC, Employee ASC;