Java | LeetCode

Задача: 499. The Maze III Сложность: hard В лабиринте есть мячик с пустыми пространствами (0) и стенами (1). Мячик может катиться вверх, вниз, влево или вправо, пока не столкнется со стеной, затем выбрать новое направление. В лабиринте также есть отверстие, куда мячик упадет, если закатится в него. Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо). Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно). Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны. Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

👨‍💻 Алгоритм: 1⃣Инициализация и вспомогательные функции Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной. 2⃣Запуск алгоритма Дейкстры Инициализируйте очередь с начальной позицией мяча, где элементы с меньшим расстоянием имеют высокий приоритет, а при равных расстояниях выбирайте минимальную строку пути. Создайте структуру seen для отслеживания посещенных узлов. 3⃣Поиск кратчайшего пути Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible". 😎 Решение:

class State {
    int row, col, dist;
    String path;
    State(int r, int c, int d, String p) { row = r; col = c; dist = d; path = p; }
}

class Solution {
    int[][] directions = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    String[] textDirections = {"l", "u", "r", "d"};
    int m, n;

    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        m = maze.length; n = maze[0].length;
        PriorityQueue<State> heap = new PriorityQueue<>((a, b) -> a.dist == b.dist ? a.path.compareTo(b.path) : a.dist - b.dist);
        boolean[][] seen = new boolean[m][n];
        heap.add(new State(ball[0], ball[1], 0, ""));
        
        while (!heap.isEmpty()) {
            State curr = heap.remove();
            if (seen[curr.row][curr.col]) continue;
            if (curr.row == hole[0] && curr.col == hole[1]) return curr.path;
            seen[curr.row][curr.col] = true;
            
            for (State nextState : getNeighbors(curr.row, curr.col, maze, hole)) {
                heap.add(new State(nextState.row, nextState.col, curr.dist + nextState.dist, curr.path + nextState.path));
            }
        }
        return "impossible";
    }
    
    private List<State> getNeighbors(int row, int col, int[][] maze, int[] hole) {
        List<State> neighbors = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            int dy = directions[i][0], dx = directions[i][1], dist = 0, currRow = row, currCol = col;
            String direction = textDirections[i];
            while (valid(currRow + dy, currCol + dx, maze)) {
                currRow += dy; currCol += dx; dist++;
                if (currRow == hole[0] && currCol == hole[1]) break;
            }
            neighbors.add(new State(currRow, currCol, dist, direction));
        }
        return neighbors;
    }
    
    private boolean valid(int row, int col, int[][] maze) {
        return row >= 0 && row < m && col >= 0 && col < n && maze[row][col] == 0;
    }
}

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

Купить новый EXEED RX по спец. цене в Москве! Особые условия на покупку EXEED RX. Выгодный Трейд-Ин + Подарки. Узнайте VIP-цену! Узнать цену #реклама rolfexeed-msk.ru О рекламодателе

Задача: 972. Equal Rational Numbers Сложность: hard Даны две строки s и t, каждая из которых представляет собой неотрицательное рациональное число. Вернуть true тогда и только тогда, когда они представляют одно и то же число. Строки могут использовать скобки для обозначения повторяющейся части рационального числа. Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов: <ЦелаяЧасть> Например, 12, 0 и 123. <ЦелаяЧасть><.><НеповторяющаясяЧасть> Например, 0.5, 1., 2.12 и 123.0001. <ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)> Например, 0.1(6), 1.(9), 123.00(1212). Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например: 1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66). Пример:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

👨‍💻 Алгоритм: 1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина. 2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии. 3⃣Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения. 😎 Решение:

class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
}

class Solution {
    Map<Integer, Employee> emap;
    
    public int getImportance(List<Employee> employees, int queryid) {
        emap = new HashMap<>();
        for (Employee e : employees) {
            emap.put(e.id, e);
        }
        return dfs(queryid);
    }
    
    public int dfs(int eid) {
        Employee employee = emap.get(eid);
        int ans = employee.importance;
        for (Integer subid : employee.subordinates) {
            ans += dfs(subid);
        }
        return ans;
    }
}

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

Data и ML для бизнеса. Большая конференция Яндекса Для продактов, владельцев бизнеса и менеджеров Data/IT-проектов: о применении генеративных моделей, LLM-агентов, чат-ботов и речевой аналитики. Зарегистрироваться #реклама 16+ yandex.cloud О рекламодателе Реклама на Яндексе

Задача: 309. Best Time to Buy and Sell Stock with Cooldown Сложность: medium Дан массив prices, где prices[i] — цена данной акции в i-й день. Найдите максимальную прибыль, которую можно получить. Вы можете совершить любое количество транзакций (т. е. купить и продать одну акцию несколько раз) с следующими ограничениями: После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать). Пример:

Input: prices = [1]
Output: 0

👨‍💻 Алгоритм: 1⃣Инициализация состояний Используйте три состояния для отслеживания максимальной прибыли: hold: максимальная прибыль на данный день, если у вас есть акция. sold: максимальная прибыль на данный день, если вы продали акцию. cooldown: максимальная прибыль на данный день, если вы находитесь в периоде ожидания после продажи. 2⃣Обновление состояний Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день. 3⃣Определение максимальной прибыли В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли. 😎 Решение:

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        
        int hold = -prices[0];
        int sold = 0;
        int cooldown = 0;
        
        for (int i = 1; i < prices.length; i++) {
            int newHold = Math.max(hold, cooldown - prices[i]);
            int newSold = hold + prices[i];
            int newCooldown = Math.max(cooldown, sold);
            
            hold = newHold;
            sold = newSold;
            cooldown = newCooldown;
        }
        
        return Math.max(sold, cooldown);
    }
}

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

Виртуальный сервер в аренду в Турции или России. Отказоустойчивый виртуальный облачный сервер на базе виртуализации VMWARE по модели подписки. - Бесплатная миграция инфраструктуры в Турцию - Размещайте ресурсы в Турции или России и оплачивайте в рублях, турицких лирах или евро. - Храните резервные копии данных за рубежом для минимизации рисков - Продолжайте использовать импортное ПО, скачивайте обновления и патчи, общайтесь с техподдержкой - Доступность сервиса — от 99,982% SLA - Дата центры Tier III в России и Турции - Почасовой биллинг и постоплата Подключите услугу сегодня со скидкой 50% на инфраструктуру. Подать заявку #реклама cloud4y.ru О рекламодателе

Задача: 109. Convert Sorted List to Binary Search Tree Сложность: medium Дана голова односвязного списка, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте бинарное дерево поиска. Пример:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

👨‍💻 Алгоритм: 1⃣Поскольку нам дан односвязный список, а не массив, у нас нет прямого доступа к элементам списка по индексам. Нам нужно определить средний элемент односвязного списка. Мы можем использовать подход с двумя указателями для нахождения среднего элемента списка. В основном, у нас есть два указателя: slow_ptr и fast_ptr. slow_ptr перемещается на один узел за раз, тогда как fast_ptr перемещается на два узла за раз. К тому времени, как fast_ptr достигнет конца списка, slow_ptr окажется в середине списка. Для списка с четным количеством элементов любой из двух средних элементов может стать корнем BST. 2⃣Как только мы находим средний элемент списка, мы отсоединяем часть списка слева от среднего элемента. Мы делаем это, сохраняя prev_ptr, который указывает на узел перед slow_ptr, т.е. prev_ptr.next = slow_ptr. Для отсоединения левой части мы просто делаем prev_ptr.next = None. 3⃣Для создания сбалансированного по высоте BST нам нужно передать только голову связанного списка в функцию, которая преобразует его в BST. Таким образом, мы рекурсивно работаем с левой половиной списка, передавая оригинальную голову списка, и с правой половиной, передавая slow_ptr.next в качестве головы. 😎 Решение:

class Solution {
    private ListNode findMiddleElement(ListNode head) {
        ListNode prevPtr = null;
        ListNode slowPtr = head;
        ListNode fastPtr = head;

        while (fastPtr != null && fastPtr.next != null) {
            prevPtr = slowPtr;
            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }

        if (prevPtr != null) {
            prevPtr.next = null;
        }

        return slowPtr;
    }

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode mid = this.findMiddleElement(head);
        TreeNode node = new TreeNode(mid.val);

        if (head == mid) {
            return node;
        }

        node.left = this.sortedListToBST(head);
        node.right = this.sortedListToBST(mid.next);
        return node;
    }
}

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

Задача: 140. Break II Сложность: hard Дана строка s и словарь строк wordDict. Добавьте пробелы в строку s, чтобы построить предложение, в котором каждое слово является допустимым словом из словаря. Верните все такие возможные предложения в любом порядке. Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении. Пример:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

👨‍💻 Алгоритм: 1⃣Инициализация и начальный вызов: Преобразуйте массив wordDict в множество wordSet для эффективного поиска. Инициализируйте пустой массив results для хранения допустимых предложений. Инициализируйте пустую строку currentSentence для отслеживания конструируемого предложения. Вызовите функцию backtrack с исходной строкой s, множеством wordSet, текущим предложением currentSentence, массивом результатов results и начальным индексом, установленным в 0 — начало входной строки. Верните results после завершения работы backtrack. 2⃣Функция backtrack: Базовый случай: Если startIndex равен длине строки, добавьте currentSentence в results и вернитесь, так как это означает, что currentSentence представляет собой допустимое предложение. Итерация по возможным значениям endIndex от startIndex + 1 до конца строки. 3⃣Обработка и рекурсия: Извлеките подстроку word от startIndex до endIndex - 1. Если word найдено в wordSet: Сохраните текущее значение currentSentence в originalSentence. Добавьте word к currentSentence (с пробелом, если это необходимо). Рекурсивно вызовите backtrack с обновленным currentSentence и endIndex. Сбросьте currentSentence к его исходному значению (originalSentence) для отката и попробуйте следующий endIndex. Вернитесь из функции backtrack. 😎 Решение:

class Solution {

    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        List<String> results = new ArrayList<>();
        backtrack(s, wordSet, new StringBuilder(), results, 0);
        return results;
    }

    private void backtrack(
        String s,
        Set<String> wordSet,
        StringBuilder currentSentence,
        List<String> results,
        int startIndex
    ) {
        if (startIndex == s.length()) {
            results.add(currentSentence.toString().trim());
            return;
        }

        for (int endIndex = startIndex + 1; endIndex <= s.length(); endIndex++) {
            String word = s.substring(startIndex, endIndex);
            if (wordSet.contains(word)) {
                int currentLength = currentSentence.length();
                currentSentence.append(word).append(" ");
                backtrack(s, wordSet, currentSentence, results, endIndex);
                currentSentence.setLength(currentLength);
            }
        }
    }
}

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 1463. Cherry Pickup II Сложность: hard Дана матрица grid размером rows x cols, представляющая поле с вишнями, где grid[i][j] обозначает количество вишен, которые можно собрать с клетки (i, j). У вас есть два робота, которые могут собирать вишни: Робот №1 находится в левом верхнем углу (0, 0), а Робот №2 находится в правом верхнем углу (0, cols - 1). Верните максимальное количество собранных вишен с помощью обоих роботов, следуя приведённым ниже правилам: Из клетки (i, j) роботы могут перемещаться в клетку (i + 1, j - 1), (i + 1, j) или (i + 1, j + 1). Когда любой робот проходит через клетку, он подбирает все вишни, и клетка становится пустой. Когда оба робота находятся в одной клетке, только один из них собирает вишни. Оба робота не могут выходить за пределы матрицы в любой момент времени. Оба робота должны достичь нижней строки в матрице grid. Пример:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

👨‍💻 Алгоритм: 1⃣Определите трехмерный массив dp, где dp[row][col1][col2] представляет максимальное количество вишен, которые можно собрать, если робот 1 находится в (row, col1), а робот 2 находится в (row, col2). 2⃣Итеративно заполните dp, начиная с нижней строки, вычисляя для каждой клетки максимальное количество вишен, которое можно собрать с учетом возможных перемещений роботов. 3⃣Верните dp[0][0][n-1], что представляет максимальное количество вишен, которое можно собрать, начиная с верхнего левого и верхнего правого углов. 😎 Решение:

class Solution {

    public int cherryPickup(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int dp[][][] = new int[m][n][n];

        for (int row = m - 1; row >= 0; row--) {
            for (int col1 = 0; col1 < n; col1++) {
                for (int col2 = 0; col2 < n; col2++) {
                    int result = 0;
                    result += grid[row][col1];
                    if (col1 != col2) {
                        result += grid[row][col2];
                    }
                    if (row != m - 1) {
                        int max = 0;
                        for (int newCol1 = col1 - 1; newCol1 <= col1 + 1; newCol1++) {
                            for (int newCol2 = col2 - 1; newCol2 <= col2 + 1; newCol2++) {
                                if (newCol1 >= 0 && newCol1 < n && newCol2 >= 0 && newCol2 < n) {
                                    max = Math.max(max, dp[row + 1][newCol1][newCol2]);
                                }
                            }
                        }
                        result += max;
                    }
                    dp[row][col1][col2] = result;
                }
            }
        }
        return dp[0][0][n - 1];
    }
}

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

Задача: 218. The Skyline Problem Сложность: hard Горизонт города — это внешний контур силуэта, образованного всеми зданиями в этом городе, когда они видны издалека. Учитывая расположения и высоты всех зданий, верните горизонт, образованный этими зданиями в совокупности. Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]: lefti — это координата x левого края i-го здания. righti — это координата x правого края i-го здания. heighti — это высота i-го здания. Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0. Пример:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

👨‍💻 Алгоритм: 1⃣Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights. 2⃣Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex). 3⃣Пройдитесь по обновленным высотам и добавьте все позиции, где высота меняется, в answer в качестве ключевых точек горизонта. Верните answer как результат. 😎 Решение:

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        SortedSet<Integer> edgeSet = new TreeSet<Integer>();
        for (int[] building : buildings) {
            int left = building[0], right = building[1];
            edgeSet.add(left);
            edgeSet.add(right);
        }
        List<Integer> edges = new ArrayList<Integer>(edgeSet);
        
        Map<Integer, Integer> edgeIndexMap = new HashMap<>();
        for (int i = 0; i < edges.size(); ++i) {
            edgeIndexMap.put(edges.get(i), i);
        }

        int[] heights = new int[edges.size()];

        for (int[] building : buildings) {
            int left = building[0], right = building[1], height = building[2];
            int leftIndex = edgeIndexMap.get(left), rightIndex = edgeIndexMap.get(right);
            
            for (int idx = leftIndex; idx < rightIndex; ++idx) {
                heights[idx] = Math.max(heights[idx], height);
            }
        }
        
        List<List<Integer>> answer = new ArrayList<>();

        for (int i = 0; i < heights.length; ++i) {
            int currHeight = heights[i], currPos = edges.get(i);

            if (answer.isEmpty() || answer.get(answer.size() - 1).get(1) != currHeight) {
                answer.add(Arrays.asList(currPos, currHeight));
            }
        }
        return answer;
    }
}

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 733. Flood Fill Сложность: easy Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки. Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

👨‍💻 Алгоритм: 1⃣Получите цвет начального пикселя. 2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет. 3⃣Обновите изображение и верните его. 😎 Решение:

public class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) {
            return image;
        }
        
        dfs(image, sr, sc, originalColor, color);
        return image;
    }
    
    private void dfs(int[][] image, int x, int y, int originalColor, int newColor) {
        if (x < 0 || x >= image.length || y < 0 || y >= image[0].length || image[x][y] != originalColor) {
            return;
        }
        image[x][y] = newColor;
        dfs(image, x + 1, y, originalColor, newColor);
        dfs(image, x - 1, y, originalColor, newColor);
        dfs(image, x, y + 1, originalColor, newColor);
        dfs(image, x, y - 1, originalColor, newColor);
    }
}

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

Задача: 373. Find K Pairs with Smallest Sums Сложность: medium Вам даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k. Определим пару (u, v), которая состоит из одного элемента из первого массива и одного элемента из второго массива. Верните k пар (u1, v1), (u2, v2), ..., (uk, vk) с наименьшими суммами. Пример:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

👨‍💻 Алгоритм: 1⃣Создайте две целочисленные переменные m и n, инициализируйте их размерами массивов nums1 и nums2 соответственно. Создайте список ans для хранения пар с наименьшими суммами, которые будут возвращены в качестве ответа. Создайте множество visited для отслеживания просмотренных пар. 2⃣Инициализируйте минимальную кучу minHeap, которая содержит тройки целых чисел: сумму пары, индекс первого элемента пары в nums1 и индекс второго элемента пары в nums2. Вставьте в minHeap первую пару из обоих массивов, т.е. nums1[0] + nums2[0], 0, 0, и добавьте пару (0, 0) в visited. 3⃣Повторяйте до получения k пар и пока minHeap не пуст: Извлеките верхний элемент из minHeap и установите i = top[1] и j = top[2]. Добавьте пару (nums1[i], nums2[j]) в ans. Если i + 1 < m и пары (i + 1, j) нет в visited, добавьте новую пару nums1[i + 1] + nums2[j], i + 1, j в minHeap. Если j + 1 < n и пары (i, j + 1) нет в visited, добавьте новую пару nums1[i] + nums2[j + 1], i, j + 1 в minHeap. Верните ans. 😎 Решение:

import java.util.*;

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        List<List<Integer>> ans = new ArrayList<>();
        Set<Pair<Integer, Integer>> visited = new HashSet<>();
        PriorityQueue<Triple> minHeap = new PriorityQueue<>(Comparator.comparingInt(t -> t.sum));
        minHeap.add(new Triple(nums1[0] + nums2[0], 0, 0));
        visited.add(new Pair<>(0, 0));

        while (k-- > 0 && !minHeap.isEmpty()) {
            Triple top = minHeap.poll();
            int i = top.i, j = top.j;
            ans.add(Arrays.asList(nums1[i], nums2[j]));

            if (i + 1 < m && !visited.contains(new Pair<>(i + 1, j))) {
                minHeap.add(new Triple(nums1[i + 1] + nums2[j], i + 1, j));
                visited.add(new Pair<>(i + 1, j));
            }

            if (j + 1 < n && !visited.contains(new Pair<>(i, j + 1))) {
                minHeap.add(new Triple(nums1[i] + nums2[j + 1], i, j + 1));
                visited.add(new Pair<>(i, j + 1));
            }
        }

        return ans;
    }

    class Triple {
        int sum, i, j;
        Triple(int sum, int i, int j) {
            this.sum = sum;
            this.i = i;
            this.j = j;
        }
    }
}

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

Задача: 230. Kth Smallest Element in a BST Сложность: medium Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве. Пример:

Input: root = [3,1,4,null,2], k = 1
Output: 1

👨‍💻 Алгоритм: 1⃣Инициализация стека и обход в глубину: Инициализируйте стек для хранения узлов дерева. Начните обход дерева в глубину, начиная с корня, и перемещайтесь влево, добавляя каждый узел в стек, пока не достигнете самого левого узла. 2⃣Извлечение узлов и проверка: Когда достигнете самого левого узла, извлеките узел из стека и уменьшите значение k на 1. Если k становится равным нулю, верните значение текущего узла, так как это и есть k-ое по величине значение. 3⃣Переход к правому поддереву: Если k не равен нулю, переместитесь к правому поддереву текущего узла и продолжайте обход, повторяя шаги 1 и 2, пока не найдете k-ое по величине значение. 😎 Решение:

class Solution {
  public int kthSmallest(TreeNode root, int k) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    
    while (true) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      if (--k == 0) return root.val;
      root = root.right;
    }
  }
}

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

Битрикс24 дропнул новую фичу — онлайн-доски Теперь к вашему рабочему мессенджеру, видеозвонкам и таскам добавился еще один маст-хэв инструмент. Все это бесплатно и в одном комплекте. Офисные стикеры, берегитесь.😊 Узнать больше #реклама 16+ bitrix24.ru О рекламодателе

Задача: 1347. Minimum Number of Steps to Make Two Strings Anagram Сложность: medium Даны две строки одинаковой длины s и t. За один шаг вы можете выбрать любой символ строки t и заменить его другим символом. Вернуть минимальное количество шагов, чтобы сделать t анаграммой строки s. Анаграмма строки — это строка, которая содержит те же символы в другом (или том же) порядке. Пример:

Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

👨‍💻 Алгоритм: 1⃣Вычислить разницу частот символов в строках t и s, сохраняя результаты в массиве count. 2⃣Подсчитать количество символов, которые нужно заменить в t, добавляя в ans только положительные значения из массива count. 3⃣Вернуть ans как минимальное количество шагов для превращения t в анаграмму строки s. 😎 Решение:

class Solution {
    public int minSteps(String s, String t) {
        int[] count = new int[26];
        
        for (int i = 0; i < s.length(); i++) {
            count[t.charAt(i) - 'a']++;
            count[s.charAt(i) - 'a']--;
        }

        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += Math.max(0, count[i]);
        }

        return ans;
    }
}

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

Ищу желающих перейти в сферу IT без долгого обучения ⚡ Обучим бесплатно — от вас потребуется всего несколько часов в день. Мы помогаем IT-компаниям находить квалифицированных тестировщиков. Профессия тестировщика — отличный способ сменить сферу и начать зарабатывать стабильно. 👌 Подходит тем, кто не боится работать и хочет достойный доход. Сначала проведу вводное бесплатное занятие, где расскажу: — что такое тестирование и зачем оно нужно; — где искать клиентов; — как пройти практику и попасть в крутую IT-команду. ✅ Что нужно будет делать: — проверять приложения и программы; — находить баги; — получать за это деньги. 💰 Доход — от 70 000 ₽ в месяц и выше Подходит даже без технической подготовки. 👍 Для регистрации на бесплатный урок переходите на сайт. Перейти на сайт #реклама 16+ site.purrweb-academy.ru О рекламодателе

Задача: 681. Next Closest Time Сложность: medium Дано время, представленное в формате "ЧЧ:ММ". Сформируйте ближайшее следующее время, используя текущие цифры. Количество раз, которое можно использовать цифру, не ограничено. Можно предположить, что заданная строка всегда корректна. Например, "01:34", "12:09" являются корректными. "1:34", "12:9" являются некорректными. Пример:

Input: time = "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.
It is not 19:33, because this occurs 23 hours and 59 minutes later.

👨‍💻 Алгоритм: 1⃣Симулируйте ход часов, увеличивая время на одну минуту. Каждый раз, когда время увеличивается, если все цифры допустимы, верните текущее время. 2⃣Представьте время как целое число t в диапазоне 0 <= t < 24 * 60. Тогда часы равны t / 60, минуты равны t % 60. 3⃣Найдите каждую цифру часов и минут: часы / 10, часы % 10 и т.д. 😎 Решение:

class Solution {
    public String nextClosestTime(String time) {
        int cur = 60 * Integer.parseInt(time.substring(0, 2));
        cur += Integer.parseInt(time.substring(3));
        Set<Integer> allowed = new HashSet<>();
        for (char c : time.toCharArray()) {
            if (c != ':') {
                allowed.add(c - '0');
            }
        }

        while (true) {
            cur = (cur + 1) % (24 * 60);
            int[] digits = new int[]{cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10};
            search:
            {
                for (int d : digits) {
                    if (!allowed.contains(d)) {
                        break search;
                    }
                }
                return String.format("%02d:%02d", cur / 60, cur % 60);
            }
        }
    }
}

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