Java | LeetCode

Это открытие изменит всё... Сериал «Большая Фарма» По сюжету, ученые-медики изобрели лекарство, которое может вылечить любое заболевание, даже раковую опухоль. Но препарат, который может спасти мир, становится яблоком раздора для семьи одного из учёных. Старший сын решает помочь отцу с продвижением. Дочь уверена, что брату нужны только слава и деньги. А сам главный герой оказывается не готов к компромиссам, которых требует от него рынок большой фармы. Что победит: жадность или совесть? Узнайте в новом сериале «Большая Фарма» Узнать больше #реклама 18+ okko.tv О рекламодателе

Задача: 913. Cat and Mouse Сложность: hard В игру на неориентированном графе играют два игрока, Мышь и Кот, которые чередуются по очереди. Граф задан следующим образом: graph[a] - это список всех вершин b, таких, что ab является ребром графа. Мышь начинает в вершине 1 и идет первой, Кот начинает в вершине 2 и идет второй, а в вершине 0 находится дыра. Во время хода каждого игрока он должен пройти по одному ребру графа, которое встречает его местоположение.Например, если Мышь находится в узле 1, она должна добраться до любого узла графа[1]. Кроме того, Кошке запрещено добираться до Дыры (узел 0). Затем игра может закончиться тремя способами: если Кошка занимает тот же узел, что и Мышь, Кошка побеждает. Если Мышь достигает Дыры, Мышь побеждает. Если позиция повторяется (т.е, игроки находятся в той же позиции, что и в предыдущий ход, и сейчас очередь того же игрока двигаться), то игра считается ничейной. Учитывая граф и предполагая, что оба игрока играют оптимально, верните 1, если в игре победила мышь, 2, если в игре победила кошка, или 0, если в игре ничья. Пример:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0

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

import java.util.*;

public class Solution {
    public int catMouseGame(int[][] graph) {
        int n = graph.length;
        final int DRAW = 0, MOUSE = 1, CAT = 2;
        int[][][] dp = new int[n][n][2];
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 1; i < n; i++) {
            dp[0][i][0] = MOUSE;
            dp[0][i][1] = MOUSE;
            dp[i][i][0] = CAT;
            dp[i][i][1] = CAT;
            queue.offer(new int[]{0, i, 0, MOUSE});
            queue.offer(new int[]{0, i, 1, MOUSE});
            queue.offer(new int[]{i, i, 0, CAT});
            queue.offer(new int[]{i, i, 1, CAT});
        }

        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int mouse = state[0], cat = state[1], turn = state[2], winner = state[3];
            for (int[] parent : parents(graph, mouse, cat, turn)) {
                int m = parent[0], c = parent[1], t = parent[2];
                if (dp[m][c][t] == DRAW) {
                    if ((t == 0 && winner == MOUSE) || (t == 1 && winner == CAT)) {
                        dp[m][c][t] = winner;
                        queue.offer(new int[]{m, c, t, winner});
                    } else {
                        int degrees = 0;
                        for (int[] p : parents(graph, m, c, t)) degrees++;
                        if (degrees == 0) {
                            dp[m][c][t] = winner;
                            queue.offer(new int[]{m, c, t, winner});
                        }
                    }
                }
            }
        }

        return dp[1][2][0];
    }

    private List<int[]> parents(int[][] graph, int mouse, int cat, int turn) {
        List<int[]> res = new ArrayList<>();
        if (turn == 1) {
            for (int m : graph[mouse]) {
                res.add(new int[]{m, cat, 0});
            }
        } else {
            for (int c : graph[cat]) {
                if (c > 0) res.add(new int[]{mouse, c, 1});
            }
        }
        return res;
    }
}

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

🔴 Тестовый собес с Java-разработчиком уже завтра!  [+ разбор 50 сложных вопросов в подарок ] 19 августа (уже завтра!) в 19:00 по мск приходи онлайн, чтобы посмотреть на настоящее интервью на Middle Java-разработчика! Собеседование проведёт Сергей Чамкин - старший разработчик из Uzum, ex-WildBerries Как это будет: 📂 Сергей задаст разработчику-добровольцу вопросы и задачи, которые могут спросить на реальном собесе 📂 После каждого ответа респондента ты услышишь подробный комментарий от ментора и поймёшь, чего на самом деле ожидает собеседующий на интервью 📂 В конце сможешь задать любой вопрос Сергею и получить на него развёрнутый ответ Эфир проходит в рамках менторской программы от ШОРТКАТ для Java-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы Но ты можешь посмотреть его бесплатно 🔥 Только завтра, в прямом эфире! 🎁 Подарок для всех, кто зарегается на веб — файл с ОТВЕТАМИ НА 50 СЛОЖНЫХ ВОПРОСОВ с Java-собеседований 🔥 Жми на кнопку, чтобы попасть на эфир и забрать подарок ↓ @shortcut_sh_bot    Реклама. О рекламодателе.

Домашняя школа для 1-11 классов. Онлайн-школа бесплатно! ✅Выдаем аттестат гос. образца! ✨Есть государственная лицензия и аккредитация! ✅Зачисление и обучение в школе полностью онлайн. Узнайте в мессенджере TELEGRAM, доступна ли вам льгота на бесплатное онлайн-обучение с 1 по 11 класс. Узнать больше #реклама 16+ s.salebot.pro О рекламодателе

Задача: 1249. Minimum Remove to Make Valid Parentheses Сложность: medium Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка. Пример:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

👨‍💻 Алгоритм: 1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления. 2⃣После первого прохода, все оставшиеся в стеке открывающие скобки пометьте для удаления. 3⃣Создайте новую строку, удалив все помеченные скобки. 😎 Решение:

public class Solution {
    public String minRemoveToMakeValid(String s) {
        StringBuilder sb = new StringBuilder(s);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) == '(') {
                stack.push(i);
            } else if (sb.charAt(i) == ')') {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    sb.setCharAt(i, '*');
                }
            }
        }
        while (!stack.isEmpty()) {
            sb.setCharAt(stack.pop(), '*');
        }
        return sb.toString().replaceAll("\\*", "");
    }
}

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

Задача: 867. Transpose Matrix Сложность: easy Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу. Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами. Пример:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

👨‍💻 Алгоритм: 1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк. 2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c]. 3⃣Верните матрицу ans. 😎 Решение:

class Solution {
    public int[][] transpose(int[][] A) {
        int R = A.length, C = A[0].length;
        int[][] ans = new int[C][R];
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c)
                ans[c][r] = A[r][c];
        return ans;
    }
}

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

Переходи в скоростной режим карьеры ⚡Учись у тех, кто прошел путь от джуна до топа. В Мини-СЕО ты попадешь в команду топ-менеджера Т-Банка и сможешь: — исследовать экосистемы и находить наиболее перспективные точки роста; — развивать сегмент автолюбителей в Т-Банке; — заниматься региональной экспансией банка; — вести стратегический план развития 3P, развивать AI-продукты; — участвовать в создании B2B-маркетплейса; — разрабатывать эффективные методологии. Программа длится шесть месяцев и подойдет студентам и выпускникам, которые уже умеют в математику и аналитику. Подай заявку до 25 сентября! Зарегистрироваться #реклама 16+ t-miniceo.ru О рекламодателе

Задача: 650. 2 Keys Keyboard Сложность: medium На экране блокнота есть только один символ 'A'. Для каждого шага можно выполнить одну из двух операций над этим блокнотом: Copy All: скопировать все символы, присутствующие на экране (частичное копирование не допускается). Paste: Вы можете вставить символы, которые были скопированы в прошлый раз. Учитывая целое число n, верните минимальное количество операций, чтобы символ 'A' появился на экране ровно n раз. Пример:

Input: n = 3
Output: 3

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

public class Solution {
    public int minSteps(int n) {
        if (n == 1) return 0;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j <= i / 2; j++) {
                if (i % j == 0) {
                    dp[i] = Math.min(dp[i], dp[j] + i / j);
                }
            }
        }
        return dp[n];
    }
}

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

Задача: 520. Detect Capital Сложность: easy Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий: Все буквы в этом слове заглавные, как "USA". Все буквы в этом слове строчные, как "leetcode". Только первая буква в этом слове заглавная, как "Google". Дана строка word. Верните true, если использование заглавных букв в ней правильное. Пример:

Input: word = "USA"
Output: true

👨‍💻 Алгоритм: 1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы". 2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные. 3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*. 😎 Решение:

import java.util.regex.*;

class Solution {
    public boolean detectCapitalUse(String word) {
        String pattern = "[A-Z]*|.[a-z]*";
        return Pattern.matches(pattern, word);
    }
}

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

Нужно увеличить продажи на Wildberries? Поднимайте в ТОП ИИ-ассистент для управления бизнесом на Wildberries. SEO, аналитика, автоматизация, реклама и финансы — всё в одной платформе ilai. - SEO оптимизация Wildberries - Аудит, анализ и сравнение с конкурентами - ИИ ассистент с автоматизацией - Рекламные инструменты и биддер - Финансовый контроль и аналитика - Автообработка отзывов и вопросов Перейти на сайт #реклама 16+ ilai.io О рекламодателе

Задача: 856. Score of Parentheses Сложность: medium Дана строка s, состоящая из сбалансированных скобок, верните счёт строки. Счёт сбалансированной строки скобок основывается на следующих правилах: "()" имеет счёт 1. AB имеет счёт A + B, где A и B — сбалансированные строки скобок. (A) имеет счёт 2 * A, где A — сбалансированная строка скобок. Пример:

Input: s = "()"
Output: 1

👨‍💻 Алгоритм: 1⃣Назовём сбалансированную строку примитивной, если её нельзя разделить на две непустые сбалансированные строки. 2⃣Отслеживая баланс (количество открывающих скобок минус количество закрывающих скобок), мы можем разделить строку S на примитивные подстроки S = P_1 + P_2 + ... + P_n. Тогда, по определению, score(S) = score(P_1) + score(P_2) + ... + score(P_n). 3⃣Для каждой примитивной подстроки (S[i], S[i+1], ..., S[k]), если длина строки равна 2, то её счёт равен 1. В противном случае, счёт равен удвоенному счёту подстроки (S[i+1], S[i+2], ..., S[k-1]). 😎 Решение:

class Solution {
    public int scoreOfParentheses(String S) {
        return F(S, 0, S.length());
    }

    public int F(String S, int i, int j) {
        int ans = 0, bal = 0;

        for (int k = i; k < j; ++k) {
            bal += S.charAt(k) == '(' ? 1 : -1;
            if (bal == 0) {
                if (k - i == 1) ans++;
                else ans += 2 * F(S, i + 1, k);
                i = k + 1;
            }
        }

        return ans;
    }
}

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

Бесплатный курс по дизайну в FIGMA от Yudaev School Онлайн-программа с наставником и чатом. Внимание! 80% практики. ✅По результату обучения у вас будет портфолио из нескольких работ. ✅Сертификат о прохождении курса. ✅Возможность пройти полное обучение и получить карьерное сопровождение! Учитесь дизайну у профессионалов в Yudaev Shool. Переходи по кнопки: "Подробнее" и начинай свое обучение. Доступ 0 руб. Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 186. Reverse Words in a String II Сложность: medium Дан массив символов s, переверните порядок слов. Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены одним пробелом. Ваш код должен решать задачу на месте, то есть без выделения дополнительного пространства. Пример:

Input: s = ["a"]
Output: ["a"]

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

class Solution {
    public void reverse(char[] s, int left, int right) {
        while (left < right) {
            char tmp = s[left];
            s[left++] = s[right];
            s[right--] = tmp;
        }
    }

    public void reverseEachWord(char[] s) {
        int n = s.length;
        int start = 0, end = 0;

        while (start < n) {
            while (end < n && s[end] != ' ') ++end;
            reverse(s, start, end - 1);            start = end + 1;
            ++end;
        }
    }

    public void reverseWords(char[] s) {
        reverse(s, 0, s.length - 1);
        reverseEachWord(s);
    }
}

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

Услуги коммерческого дата-центра в Москве Размещение серверного оборудования в дата-центре. ✅ Услуги предоставляются в 4 дата-центрах в Москве. ✅ Географическое резервирование. ✅ Высокая отказоустойчивость. ✅ Гибкость при выборе площадки для размещения оборудования. Узнать цену #реклама itsoft.ru О рекламодателе

Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves Сложность: medium Вам дан массив целых чисел nums. За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение. Верните минимальную разницу между наибольшим и наименьшим значением в массиве nums после выполнения не более трех ходов. Пример:

Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.

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

class Solution {
    public int minDifference(int[] nums) {
        int numsSize = nums.length;
        
        if (numsSize <= 4) return 0;
        
        Arrays.sort(nums);
        
        int minDiff = Integer.MAX_VALUE;
        
        for (int left = 0, right = numsSize - 4; left < 4; left++, right++) {
            minDiff = Math.min(minDiff, nums[right] - nums[left]);
        }
        
        return minDiff;
    }
}

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

Подготовка к вступительным экзаменам в ШАД 120+ поступивших в ШАД. Преподаватели МГУ. Гарантия результата. Вы поступите в ШАД, магистратуру или мы зачислим Вас на следующий поток бесплатно Узнать больше #реклама 16+ shadhelper.com О рекламодателе

Задача: 599. Minimum Index Sum of Two Lists Сложность: easy Даны два массива строк list1 и list2, необходимо найти общие строки с наименьшей суммой индексов. Общая строка - это строка, которая появляется и в list1, и в list2. Общая строка с наименьшей суммой индексов - это общая строка, такая, что если она появилась в list1[i] и list2[j], то i + j должно быть минимальным значением среди всех других общих строк. Верните все общие строки с наименьшей суммой индексов. Верните ответ в любом порядке. Пример:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".

👨‍💻 Алгоритм: 1⃣Для каждой строки из list1, сравниваем её с каждой строкой из list2, обходя весь список list2. Используем хэш-таблицу map, которая содержит элементы в виде (сумма: список строк). Здесь сумма относится к сумме индексов совпадающих элементов, а список строк соответствует списку совпадающих строк, чья сумма индексов равна этой сумме. 2⃣Во время сравнений, когда находится совпадение строки на i-м индексе из list1 и j-м индексе из list2, создаём запись в map, соответствующую сумме i + j, если такая запись ещё не существует. Если запись с этой суммой уже существует, добавляем текущую строку в список строк, соответствующих сумме i + j. 3⃣В конце обходим ключи в map и находим список строк, соответствующих ключу с минимальной суммой. 😎 Решение:

import java.util.*;

public class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        HashMap<Integer, List<String>> map = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            for (int j = 0; j < list2.length; j++) {
                if (list1[i].equals(list2[j])) {
                    if (!map.containsKey(i + j)) {
                        map.put(i + j, new ArrayList<>());
                    }
                    map.get(i + j).add(list1[i]);
                }
            }
        }
        int minIndexSum = Integer.MAX_VALUE;
        for (int key : map.keySet()) {
            minIndexSum = Math.min(minIndexSum, key);
        }
        return map.get(minIndexSum).toArray(new String[0]);
    }
}

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

Скидки до 50% на духовые шкафы Kuppersberg Духовые шкафы Kuppersberg со скидками на Яндекс Маркете! Узнать больше #реклама market.yandex.ru О рекламодателе

Задача: 827. Making A Large Island Сложность: hard Вам дан n x n бинарный матрица grid. Вам разрешено изменить не более одного 0 на 1. Верните размер самого большого острова в grid после выполнения этой операции. Остров — это группа 1, соединенных в 4 направлениях. Пример:

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.

👨‍💻 Алгоритм: 1⃣Пройдите по матрице и пометьте каждую группу, используя уникальный индекс, и запомните её размер. 2⃣Для каждого 0 в матрице проверьте соседние группы и вычислите потенциальный размер острова, если изменить этот 0 на 1. 3⃣Возвращайте максимальный размер острова, учитывая как уже существующие острова, так и потенциальные, образованные после изменения 0 на 1. 😎 Решение:

class Solution {
    int[] dr = new int[]{-1, 0, 1, 0};
    int[] dc = new int[]{0, -1, 0, 1};
    int[][] grid;
    int N;

    public int largestIsland(int[][] grid) {
        this.grid = grid;
        N = grid.length;

        int index = 2;
        int[] area = new int[N*N + 2];
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c)
                if (grid[r][c] == 1)
                    area[index] = dfs(r, c, index++);

        int ans = 0;
        for (int x: area) ans = Math.max(ans, x);
        for (int r = 0; r < N; ++r)
            for (int c = 0; c < N; ++c)
                if (grid[r][c] == 0) {
                    Set<Integer> seen = new HashSet();
                    for (Integer move: neighbors(r, c))
                        if (grid[move / N][move % N] > 1)
                            seen.add(grid[move / N][move % N]);

                    int bns = 1;
                    for (int i: seen) bns += area[i];
                    ans = Math.max(ans, bns);
                }

        return ans;
    }

    public int dfs(int r, int c, int index) {
        int ans = 1;
        grid[r][c] = index;
        for (Integer move: neighbors(r, c)) {
            if (grid[move / N][move % N] == 1) {
                grid[move / N][move % N] = index;
                ans += dfs(move / N, move % N, index);
            }
        }

        return ans;
    }

    public List<Integer> neighbors(int r, int c) {
        List<Integer> ans = new ArrayList();
        for (int k = 0; k < 4; ++k) {
            int nr = r + dr[k];
            int nc = c + dc[k];
            if (0 <= nr && nr < N && 0 <= nc && nc < N)
                ans.add(nr * N + nc);
        }

        return ans;
    }

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

Начните пользоваться Kaspersky Premium бесплатно 30 дней Kaspersky Premium бесплатно: – защита от вирусов и взломов – безопасность платежей и данных – блокировка спам-звонков – и ещё больше возможностей Попробуйте! Узнать больше #реклама 16+ kaspersky.ru О рекламодателе