Задача: 407. Trapping Rain Water II
Сложность: hard

Задав целочисленную матрицу heightMap размером m x n, представляющую высоту каждой ячейки на двумерной карте рельефа, верните объем воды, который она может задержать после дождя.

Пример:

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4

👨‍💻 Алгоритм:

1⃣Используйте приоритетную очередь для хранения всех ячеек по периметру матрицы.

2⃣Постепенно извлекайте ячейки из очереди, рассматривая их соседей. Если соседняя ячейка ниже текущей, добавьте разницу в высоте к общему объему воды и обновите её высоту.

3⃣Повторите процесс, пока все ячейки не будут обработаны.

😎 Решение:

import java.util.PriorityQueue;

public class Solution {
    public int trapRainWater(int[][] heightMap) {
        if (heightMap.length == 0 || heightMap[0].length == 0) return 0;
        int m = heightMap.length, n = heightMap[0].length;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < m; i++) {
            for (int j : new int[]{0, n-1}) {
                pq.offer(new int[]{heightMap[i][j], i, j});
                visited[i][j] = true;
            }
        }
        for (int j = 0; j < n; j++) {
            for (int i : new int[]{0, m-1}) {
                pq.offer(new int[]{heightMap[i][j], i, j});
                visited[i][j] = true;
            }
        }
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int water = 0;
        while (!pq.isEmpty()) {
            int[] cell = pq.poll();
            for (int[] dir : directions) {
                int nx = cell[1] + dir[0], ny = cell[2] + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    water += Math.max(0, cell[0] - heightMap[nx][ny]);
                    pq.offer(new int[]{Math.max(cell[0], heightMap[nx][ny]), nx, ny});
                }
            }
        }
        return water;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: №19. Remove Nth Node From End of List
Сложность: medium

Учитывая заголовок связанного списка, удалите n-й узел с конца списка и верните его заголовок.

Пример:

Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

👨‍💻 Алгоритм:

1⃣Создать фиктивный узел dummy, указывающий на head, чтобы удобно было обрабатывать крайние случаи (например, удаление головы).

2⃣Инициализировать два указателя fast и slow, оба на dummy. Сначала сдвинуть fast на n шагов вперёд.

3⃣Затем двигать оба указателя, пока fast.next не станет null. Теперь slow находится перед узлом, который нужно удалить.


😎 Решение:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;

        return dummy.next;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium

Даны 2 целых числа n и start. Ваша задача - вернуть любую перестановку p из (0,1,2.....,2^n -1) такую, что : p[0] = start p[i] и p[i+1] отличаются только одним битом в их двоичном представлении. p[0] и p[2^n -1] также должны отличаться только одним битом в их двоичном представлении.

Пример:

Input: n = 2, start = 3
Output: [3,2,0,1]

👨‍💻 Алгоритм:

1⃣Генерация Грей-кода:
Генерация Грей-кода для чисел от 0 до 2𝑛−1

2⃣Определение начальной позиции:
Находим индекс числа start в последовательности Грей-кода.

3⃣Построение перестановки:
Формируем перестановку, начиная с числа start и следуя по циклическому Грей-коду.

😎 Решение:

import java.util.*;

public class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        List<Integer> gray = grayCode(n);
        int startIndex = gray.indexOf(start);
        List<Integer> result = new ArrayList<>();
        result.addAll(gray.subList(startIndex, gray.size()));
        result.addAll(gray.subList(0, startIndex));
        return result;
    }

    private List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        int numElements = 1 << n;
        for (int i = 0; i < numElements; i++) {
            result.add(i ^ (i >> 1));
        }
        return result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний