главная новое лучшее написать

rust


3

Задача, что мы рассмотрим сегодня - 2948. Make Lexicographically Smallest Array by Swapping Elements

📝 Описание задачи:

Лексикографический порядок: Массив a меньше массива b, если на первой позиции i, где они различаются, a[i] < b[i].

💡 Идея:

Будем эксплуатировать следующие замечания:

🔍 Детали подхода:

  1. Сортировка индексов: На первом шаге создаём массив sorted_indices, заполняя его значениями [0, 1, ..., n-1]. Затем сортируем этот массив по значениям массива nums, чтобы определить относительный порядок элементов.

Читать дальше →

ответить
3

В очередной задаче для обзора - 802. Find Eventual Safe States нам предстоит найти вершины, не попадающие в циклы графа.

📋 Описание задачи

Нужно определить безопасные вершины в ориентированном графе.

💡 Идея

Задача решается с помощью обхода графа в глубину (DFS) и вектора состояний.
Каждому узлу присваивается одно из трёх состояний:

  1. Unseen (ещё не обработан);
  2. Processing (в процессе обработки; узлы, являющиеся частью цикла, остаются в этом состоянии и после обработки);
  3. Safe (безопасный).

🔍 Детальное описание подхода

Читать дальше →

ответить
3

В нашей новой задаче - 1765. Map of Highest Peak продолжим закреплять работу с семейством простых графовых алгоритмов.

📜 Описание задачи

Вам дана матрица isWater размером m×n, где:

Требуется назначить высоты каждой клетке таким образом, чтобы:

  1. Высота каждой клетки была неотрицательной.
  2. Высота любой клетки с водой была равна 0.
  3. Абсолютная разница высот у соседних клеток не превышала 1.
  4. Максимальная высота в назначенной карте была как можно больше.

💡 Идея

Мы используем поиск в ширину с несколькими источниками (multi-source BFS), начиная с клеток воды (высота 0).
На каждом шаге ближайшие клетки суши получают высоту на 1 больше текущей.
Этот метод гарантирует, что все клетки суши получают наилучшую из возможных высот, что приводит к максимизации самой высокой высоты в матрице.

🛠 Подробности подхода

  1. Инициализация:
    • Создаём очередь и добавляем в неё все клетки воды, помечая их высотой 0.

Читать дальше →

ответить
3

Сегодня в нашей задаче 2017. Grid Game требуется рассчитать оптимальную стратегию в игре с 2 участниками. И большая часть решения опять – "размышления на салфетке".

🖍️ Условие задачи

Дано: двумерный массив grid размером 2 x n, где grid[r][c] представляет количество очков в ячейке (r, c).

Цель первого робота: минимизировать максимальное количество очков, которые сможет собрать второй робот.

💡 Идея

Легко увидеть, что только две стратегии второго робота могут оказаться оптимальными:

  1. Право → Вниз: Сначала пройти весь верхний ряд, а затем спуститься вниз на последней колонке.
  2. Вниз → Право: Спуститься вниз сразу, а затем двигаться вправо вдоль нижнего ряда.

Читать дальше →

ответить
3

В следующей задаче - 2661. First Completely Painted Row or Column можно не симулировать в лоб, и за счёт этого сэкономить память при решении (хоть и не получится асимптотически лучше).

📋 Описание задачи

example-painting

Необходимо найти первый такой индекс i в массиве arr, при котором:

💡 Идея

Задачу можно переформулировать:

Читать дальше →

ответить
3

Следующая задача 407. Trapping Rain Water II даёт возможность потренировать пространственное воображение (по крайней мере на этапе выбора адекватного для её решения алгоритма).

📋 Описание задачи

Дана 3D-сетка, представляющая высоты ячеек. Необходимо вычислить объем воды, который можно удержать после дождя. Вода может заполнять только области, окруженные ячейками с большей высотой.

example-3d-grid

💡 Идея

Мы рассматриваем каждую ячейку как часть сетки, где вода может стекать только в соседние ячейки с меньшей или равной высотой. Используя структуру данных непересекающихся множеств (Disjoint-Set или Union-Find), мы группируем соединённые ячейки и отслеживаем их связь с границами, чтобы определить, какие ячейки могут удерживать воду.

🛠️ Детали подхода

  1. Представление и сортировка:
    • Преобразуем все ячейки в список, где каждая ячейка представлена своей высотой и координатами.
    • Сортируем ячейки по высоте в порядке возрастания.
  2. Структура объединения множеств:
    • Создаем дискретное множество для ячеек, добавляя виртуальный узел для границ сетки.

Читать дальше →

ответить

Страница 1 2 3