Java | LeetCode

Бесплатное IT-образование в 2024 Отобрали для вас полезные телеграм-каналы, которые помогут освоить программирование и другие IT-направления Выбирайте нужное и подписывайтесь: 👩‍💻 Python: @PythonPortal 📱 GitHub: @git_developer 👩‍💻 Frontend: @FrontendPortal 🤓 Книги айти: @portalToIT 👩‍💻 Java: @Java_Iibrary 👩‍💻 C#: @KodBlog 👩‍💻 С/С++: @Cpportal ⚙️ Backend: @BackendPortal 🐞 Тестирование: @QAPortal 👩‍💻 DevOps: @loose_code 🖥 Базы Данных & SQL: @SQL 👩‍💻 Golang: @juniorGolang 👩‍💻 PHP: @PHPortal 👩‍💻 Моб. разработка: @MobDev 👩‍💻 Разработка игр: @GameDevgx 🖥 Data Science: @DataSciencegx 🤔 Хакинг & ИБ: @cybersecinform 📱 Маркетинг: @MarketingPortal 🖥 Дизайн: @PortalToDesign ➡️ Сохраняйте себе, чтобы не потерять

#medium Задача: 337. House Robber III Вор снова нашел себе новое место для краж. В этом районе есть только один вход, который называется корнем. Кроме корня, каждый дом имеет только один родительский дом. После осмотра, умный вор понял, что все дома в этом месте образуют бинарное дерево. Полиция будет автоматически уведомлена, если два дома, напрямую связанные между собой, будут ограблены в одну ночь. Дано корневое дерево бинарного дерева, верните максимальную сумму денег, которую вор может украсть, не уведомляя полицию. Пример:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

👨‍💻 Алгоритм: 1⃣Инициализация и базовый случай: Создайте вспомогательную функцию helper, которая принимает узел в качестве входных данных и возвращает массив из двух элементов, где первый элемент представляет максимальную сумму денег, которую можно украсть, если не грабить этот узел, а второй элемент - если грабить этот узел. Базовый случай для вспомогательной функции - узел null, и в этом случае функция возвращает массив из двух нулей [0, 0]. 2⃣Рекурсивное исследование дерева: В функции helper вызывайте её рекурсивно для левого и правого поддеревьев текущего узла. Если грабить текущий узел, то нельзя грабить его потомков, поэтому сумма будет равна значению текущего узла плюс максимальные суммы для случаев, когда потомки не грабятся. Если не грабить текущий узел, то можно свободно выбирать, грабить потомков или нет, поэтому сумма будет равна максимальной сумме из двух вариантов для каждого потомка. 3⃣Возврат результата: В основной функции rob вызовите helper для корня дерева и верните максимальное значение из двух элементов массива, возвращенного функцией helper. 😎 Решение:

class Solution {
    public int[] helper(TreeNode node) {
        if (node == null) {
            return new int[] { 0, 0 };
        }
        int left[] = helper(node.left);
        int right[] = helper(node.right);
        int rob = node.val + left[1] + right[1];
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return new int[] { rob, notRob };
    }

    public int rob(TreeNode root) {
        int[] answer = helper(root);
        return Math.max(answer[0], answer[1]);
    }
}

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

#medium Задача: 465. Optimal Account Balancing Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi. Верните минимальное количество транзакций, необходимых для урегулирования долгов. Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

👨‍💻 Алгоритм: 1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека. 2⃣Собрать все ненулевые чистые балансы в массив balance_list. 3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]: Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1. Если cur = n, вернуть 0. В противном случае установить cost на большое значение, например, inf. Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0, Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur]. Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1). Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат). Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации. Вернуть cost, когда итерация завершена. Вернуть dfs(0). 😎 Решение:

import java.util.*;

public class Solution {
    private List<Integer> creditList;
    
    public int minTransfers(int[][] transactions) {
        Map<Integer, Integer> creditMap = new HashMap<>();
        for (int[] t : transactions) {
            creditMap.put(t[0], creditMap.getOrDefault(t[0], 0) + t[2]);
            creditMap.put(t[1], creditMap.getOrDefault(t[1], 0) - t[2]);
        }
        
        creditList = new ArrayList<>();
        for (int amount : creditMap.values()) {
            if (amount != 0) {
                creditList.add(amount);
            }
        }
        
        int n = creditList.size();
        return dfs(0, n);
    }
    
    private int dfs(int cur, int n) {
        while (cur < n && creditList.get(cur) == 0) {
            cur++;
        }
    
        if (cur == n) {
            return 0;
        }
        
        int cost = Integer.MAX_VALUE;
        for (int nxt = cur + 1; nxt < n; nxt++) {
            if (creditList.get(nxt) * creditList.get(cur) < 0) {
                creditList.set(nxt, creditList.get(nxt) + creditList.get(cur));
                cost = Math.min(cost, 1 + dfs(cur + 1, n));
                creditList.set(nxt, creditList.get(nxt) - creditList.get(cur));
            }
        }
        
        return cost;
    }
}

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

Курс по Java: с нуля до middle за 6 месяцев с гарантией трудоустройства Образовательный проект EdMe начинает набор на курс Java-разработки для начинающих. Программа основана на менторстве и подходит для начинающих программистов и тех, кто хочет освоить Java с нуля. От вас нужно лишь желание учиться и готовность уделять от 15 часов в неделю на занятия. 🔹 Получение профессии: 6 месяцев до зарплаты от 140.000 руб. 🔹 Гарантия трудоустройства: 98,9% выпускников получают оффер за 34 дня. 🔹 Оплата после трудоустройства: 20% от зарплаты в течение 18 месяцев. 🔹 После обучения 86% выпускников выбирают работу онлайн. Обучение проходит онлайн: 40% самостоятельная работа, 30% — взаимодействие с ментором, 30% — в группе. Такой подход развивает быстрее обычных курсов, ментор проведёт вас по короткому пути. Он объяснит, что нужно учить и как это делать, а также чего не делать, чтобы быстрее освоить нужные навыки и достичь заветной цели – получить оффер в IT. Программа курса: ▫️ Java Core, List, JDBC, Hibernate, Spring (Core, MVC, Security), Spring Boot, Git ▫️ Работа над проектами ▫️ Подготовка к собеседованиям 🗓 Старт обучения: ноябрь 2024. Чтобы начать учиться нужно оставить заявку на сайте EdMe. Отбор включает несложное тестовое задание, которое под силу выполнить человеку без опыта, и собеседование.

#hard Задача: 336. Palindrome Pairs Вам дан массив уникальных строк words, индексируемый с 0. Пара палиндромов — это пара целых чисел (i, j), таких что: 0 <= i, j < words.length, i != j, и words[i] + words[j] (конкатенация двух строк) является палиндромом. Верните массив всех пар палиндромов из слов. Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words). Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

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

class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {

        List<List<Integer>> pairs = new ArrayList<>();

        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if (i == j) continue;
                String combined = words[i].concat(words[j]);
                String reversed = new StringBuilder(combined).reverse().toString();
                if (combined.equals(reversed)) {
                    pairs.add(Arrays.asList(i, j));
                }
            }   
        }

        return pairs;
    }
}

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

#medium Задача: 377. Combination Sum IV Дан массив различных целых чисел nums и целое число target. Верните количество возможных комбинаций, которые в сумме дают target. Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число. Пример:

Input: nums = [9], target = 3
Output: 0

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

class Solution {
    private HashMap<Integer, Integer> memo;

    public int combinationSum4(int[] nums, int target) {
        memo = new HashMap<>();
        return combs(nums, target);
    }

    private int combs(int[] nums, int remain) {
        if (remain == 0)
            return 1;
        if (memo.containsKey(remain))
            return memo.get(remain);

        int result = 0;
        for (int num : nums) {
            if (remain - num >= 0)
                result += combs(nums, remain - num);
        }
        memo.put(remain, result);
        return result;
    }
}

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

Начните свою карьеру Java-разработчика с Hexlet! Хотите стать профессионалом в Java? Пройдите обучение и за 10 месяцев освоите все ключевые навыки, от основ до продвинутого уровня. 🎁 🎃 Бонусы к Черной пятнице! Вас ждет специальное предложение - скидка до 81 000 ₽. на обучение и второй курс в подарок! Вас ждут сотни практических упражнений, реальные проекты для портфолио и поддержка опытных менторов. Освойте язык крупного бизнеса и финансовых технологий и научитесь разрабатывать веб-приложения на фреймворке Spring. А во время обучения вы также поучаствуете в Карьерном треке! Пройдите 5 бесплатных уроков и откройте для себя увлекательный процесс обучения. Поймите, насколько интересен и перспективен этот путь, и получите уникальную возможность продолжить обучение на полном курсе со скидкой!

#easy Задача: 463. Island Perimeter Дан массив размером row x col, представляющий карту, где grid[i][j] = 1 обозначает сушу, а grid[i][j] = 0 обозначает воду. Клетки сетки соединены горизонтально/вертикально (не по диагонали). Сетка полностью окружена водой, и на ней находится ровно один остров (т.е. одна или более соединённых ячеек суши). У острова нет "озёр", то есть вода внутри не соединена с водой вокруг острова. Одна ячейка - это квадрат со стороной 1. Сетка прямоугольная, ширина и высота не превышают 100. Определите периметр острова. Пример:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

👨‍💻 Алгоритм: 1⃣Пройти через каждую ячейку сетки и, когда вы находитесь в ячейке с значением 1 (ячейка суши), проверить окружающие (СВЕРХУ, СПРАВА, СНИЗУ, СЛЕВА) ячейки. 2⃣Ячейка суши без каких-либо окружающих ячеек суши будет иметь периметр 4. Вычесть 1 за каждую окружающую ячейку суши. 3⃣Когда вы находитесь в ячейке с значением 0 (ячейка воды), ничего не делать. Просто перейти к следующей ячейке. 😎 Решение:

public class Solution {
    public int islandPerimeter(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        int result = 0;
        
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    int up = (r == 0) ? 0 : grid[r-1][c];
                    int left = (c == 0) ? 0 : grid[r][c-1];
                    int down = (r == rows-1) ? 0 : grid[r+1][c];
                    int right = (c == cols-1) ? 0 : grid[r][c+1];
                    
                    result += 4 - (up + left + right + down);
                }
            }
        }
        
        return result;
    }
}

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

#medium Задача: 376. Wiggle Subsequence Колеблющаяся последовательность — это последовательность, в которой разности между последовательными числами строго чередуются между положительными и отрицательными. Первая разность (если она существует) может быть как положительной, так и отрицательной. Последовательность с одним элементом и последовательность с двумя неравными элементами тривиально являются колеблющимися последовательностями. Например, [1, 7, 4, 9, 2, 5] — это колеблющаяся последовательность, потому что разности (6, -3, 5, -7, 3) чередуются между положительными и отрицательными. В отличие от нее, [1, 4, 7, 2, 5] и [1, 7, 4, 5, 5] не являются колеблющимися последовательностями. Первая не является, потому что первые две разности положительные, а вторая не является, потому что последняя разность равна нулю. Подпоследовательность получается путем удаления некоторых элементов (возможно, нуля) из исходной последовательности с сохранением оставшихся элементов в их первоначальном порядке. Дан целочисленный массив nums, верните длину самой длинной колеблющейся подпоследовательности из nums. Пример:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

👨‍💻 Алгоритм: 1⃣Для понимания этого подхода создайте два массива для динамического программирования, названных up и down. Эти массивы будут хранить длины наибольших колеблющихся подпоследовательностей, заканчивающихся соответственно восходящим или нисходящим колебанием. 2⃣up[i] относится к длине самой длинной колеблющейся подпоследовательности на данный момент, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся восходящим колебанием. Аналогично, down[i] относится к длине самой длинной колеблющейся подпоследовательности, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся нисходящим колебанием. 3⃣up[i] обновляется каждый раз, когда мы находим восходящее колебание, заканчивающееся на i-м элементе. Чтобы найти up[i], необходимо учесть максимальное значение всех предыдущих подпоследовательностей, заканчивающихся нисходящим колебанием, т.е. down[j], для каждого j<i и nums[i]>nums[j]. Аналогично, down[i] обновляется при нахождении нисходящего колебания. 😎 Решение:

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2)
            return nums.length;
        int[] up = new int[nums.length];
        int[] down = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            for(int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    up[i] = Math.max(up[i],down[j] + 1);
                } else if (nums[i] < nums[j]) {
                    down[i] = Math.max(down[i],up[j] + 1);
                }
            }
        }
        return 1 + Math.max(down[nums.length - 1], up[nums.length - 1]);
    }
}

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

Забирай пошаговую roadmap по JAVA FAANG School в течение 24 часов отдают бесплатно свою библиотеку знаний. Вы можете получить доступ: – Redis - 5 улучшений для твоего пет-проекта – Пошаговая RoadMap по Java – Мануал по Docker. Основные команды и концепции – Микросервисы. Вопросы с собеседований – Шпаргалка с горячими клавишами JetBrains IDE. Ускоришь работу в 10 раз – Desk setup. Подборка аксессуаров для комфортной работы – Шпаргалка по Kafka – Инструкция по работе с Git – Подробный гайд, как найти работу в IT без опыта – Подборка платформ с вакансиями для java-разработчиков Последнее пополнение - Шпаргалка по Spring, в которой подробно разобрали, что такое паттерн Наблюдатель, и как его реализовать в Java. А также познакомитесь с событиями и научитесь работать с ними в Spring Boot! Библиотека знаний обновляется постоянно, но бесплатный доступ длится всего сутки. Чтобы получить полезные материалы, переходи по ссылке и жми на оранжевую кнопку.

#medium Задача: 334. Increasing Triplet Subsequence Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false. Пример:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте две переменные first_num и second_num и установите их значение на максимальное целое значение (Integer.MAX_VALUE или аналогичный максимум для выбранного языка программирования). Эти переменные будут хранить минимальные значения, необходимые для проверки существования возрастающей тройки. 2⃣Итерация по массиву: Пройдите по каждому элементу массива nums. Для каждого элемента выполните следующие проверки: - если текущий элемент меньше или равен first_num, обновите first_num текущим элементом. - иначе, если текущий элемент меньше или равен second_num, обновите second_num текущим элементом. - иначе, если текущий элемент больше second_num, это означает, что найдена возрастающая тройка, поэтому верните true. 3⃣Возврат результата: Если после завершения итерации по массиву не была найдена возрастающая тройка, верните false. 😎 Решение:

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first_num = Integer.MAX_VALUE;
        int second_num = Integer.MAX_VALUE;
        for (int n: nums) {
            if (n <= first_num) {
                first_num = n;
            } else if (n <= second_num) {
                second_num = n;
            } else {
                return true;
            }
        }
        return false;
    }
}

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

#easy Задача: 375. Guess Number Higher or Lower II Мы играем в угадайку. Правила игры следующие: Я загадываю число между 1 и n. Вы угадываете число. Если вы угадаете правильное число, вы выигрываете игру. Если вы угадаете неправильное число, я скажу вам, загаданное число больше или меньше, и вы продолжите угадывать. Каждый раз, когда вы угадываете неправильное число x, вы платите x долларов. Если у вас закончились деньги, вы проигрываете игру. Дано число n. Верните минимальную сумму денег, необходимую для гарантированной победы независимо от того, какое число я загадаю. Пример:

Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

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

public class Solution {
    public int calculate(int low, int high) {
        if (low >= high)
            return 0;
        int minres = Integer.MAX_VALUE;
        for (int i = low; i <= high; i++) {
            int res = i + Math.max(calculate(i + 1, high), calculate(low, i - 1));
            minres = Math.min(res, minres);
        }
        return minres;
    }

    public int getMoneyAmount(int n) {
        return calculate(1, n);
    }
}

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

#Medium Задача: 477. Total Hamming Distance Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются. Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums. Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

public class Solution {
    public int totalHammingDistance(int[] nums) {
        int ans = 0;
        
        if (nums.length == 0) {
            return ans;
        }
        
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                ans += Integer.bitCount(nums[i] ^ nums[j]);
            }
        }
        
        return ans;
    }
}

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

#easy Задача: 374. Guess Number Higher or Lower Мы играем в игру "Угадай число". Правила игры следующие: Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал. Каждый раз, когда вы угадываете неправильно, я говорю вам, загаданное число больше или меньше вашего предположения. Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов: -1: Ваше предположение больше загаданного числа (т.е. num > pick). 1: Ваше предположение меньше загаданного числа (т.е. num < pick). 0: Ваше предположение равно загаданному числу (т.е. num == pick). Верните загаданное число. Пример:

Input: n = 10, pick = 6
Output: 6

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

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int res = guess(mid);
            if (res == 0)
                return mid;
            else if (res < 0)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
}

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

#medium Задача: 374. Guess Number Higher or Lower Мы играем в игру "Угадай число". Правила игры следующие: Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал. Каждый раз, когда вы угадываете неправильно, я говорю вам, загаданное число больше или меньше вашего предположения. Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов: -1: Ваше предположение больше загаданного числа (т.е. num > pick). 1: Ваше предположение меньше загаданного числа (т.е. num < pick). 0: Ваше предположение равно загаданному числу (т.е. num == pick). Верните загаданное число. Пример:

Input: n = 10, pick = 6
Output: 6

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

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int res = guess(mid);
            if (res == 0)
                return mid;
            else if (res < 0)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
}

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

#medium Задача: 462. Minimum Moves to Equal Array Elements II Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными. В одном ходе вы можете увеличить или уменьшить элемент массива на 1. Тестовые случаи составлены так, что ответ поместится в 32-битное целое число. Пример:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

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

public class Solution {
    public int minMoves2(int[] nums) {
        long ans = Long.MAX_VALUE;
        int minval = Integer.MAX_VALUE;
        int maxval = Integer.MIN_VALUE;
        for (int num : nums) {
            minval = Math.min(minval, num);
            maxval = Math.max(maxval, num);
        }
        for (int i = minval; i <= maxval; i++) {
            long sum = 0;
            for (int num : nums) {
                sum += Math.abs(num - i);
            }
            ans = Math.min(ans, sum);
        }
        return (int) ans;
    }
}

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

#medium Задача: 333. Largest BST Subtree Дан корень бинарного дерева, найдите самое большое поддерево, которое также является деревом бинарного поиска (BST), где "самое большое" означает поддерево с наибольшим количеством узлов. Дерево бинарного поиска (BST) — это дерево, в котором все узлы соблюдают следующие свойства: Значения в левом поддереве меньше значения их родительского (корневого) узла. Значения в правом поддереве больше значения их родительского (корневого) узла. Примечание: Поддерево должно включать всех своих потомков. Пример:

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

👨‍💻 Алгоритм: 1⃣Пост-упорядоченный обход дерева: Обходите каждую ноду дерева в пост-упорядоченном порядке (left-right-root). Это позволит гарантировать, что обе поддеревья ноды уже проверены на соответствие критериям BST перед проверкой самой ноды. 2⃣Проверка условий BST для каждой ноды: Для каждой ноды определите минимальное и максимальное значения в её левом и правом поддеревьях. Проверьте, удовлетворяет ли текущее поддерево условиям BST: - значение текущей ноды должно быть больше максимального значения в левом поддереве. - значение текущей ноды должно быть меньше минимального значения в правом поддереве. Если условия выполняются, вычислите размер текущего поддерева как сумму размеров левого и правого поддеревьев плюс 1 (для текущей ноды). 3⃣Возврат максимального размера BST: Если текущее поддерево не является BST, верните максимальный размер BST из его левого или правого поддерева. В конце рекурсивного обхода верните максимальный размер BST в дереве. 😎 Решение:

class NodeValue {
    public int maxNode, minNode, maxSize;
    
    NodeValue(int minNode, int maxNode, int maxSize) {
        this.maxNode = maxNode;
        this.minNode = minNode;
        this.maxSize = maxSize;
    }
};

class Solution {
    public NodeValue largestBSTSubtreeHelper(TreeNode root) {
        if (root == null) {
            return new NodeValue(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
        }
        
        NodeValue left = largestBSTSubtreeHelper(root.left);
        NodeValue right = largestBSTSubtreeHelper(root.right);
        
        if (left.maxNode < root.val && root.val < right.minNode) {
            return new NodeValue(Math.min(root.val, left.minNode), Math.max(root.val, right.maxNode), 
                                left.maxSize + right.maxSize + 1);
        }
        
        return new NodeValue(Integer.MIN_VALUE, Integer.MAX_VALUE, 
                            Math.max(left.maxSize, right.maxSize));
    }
    
    public int largestBSTSubtree(TreeNode root) {
        return largestBSTSubtreeHelper(root).maxSize;
    }
}

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

#medium Задача: 373. Find K Pairs with Smallest Sums Вам даны два целочисленных массива 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;
        }
    }
}

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

#hard Задача: 332. Reconstruct Itinerary Вам дан список авиабилетов, где tickets[i] = [fromi, toi] представляют собой аэропорты отправления и прибытия одного рейса. Восстановите маршрут в порядке следования и верните его. Все билеты принадлежат человеку, который вылетает из "JFK", поэтому маршрут должен начинаться с "JFK". Если существует несколько возможных маршрутов, вы должны вернуть маршрут, который имеет наименьший лексикографический порядок при чтении как одна строка. Например, маршрут ["JFK", "LGA"] имеет меньший лексикографический порядок, чем ["JFK", "LGB"]. Вы можете предположить, что все билеты формируют хотя бы один действительный маршрут. Вы должны использовать все билеты один раз и только один раз. Пример:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

👨‍💻 Алгоритм: 1⃣Построение графа и сортировка: Создайте граф flightMap, где ключи - это аэропорты отправления, а значения - это списки аэропортов прибытия. Пройдите по всем билетам и заполните flightMap соответствующими значениями. Отсортируйте списки аэропортов прибытия в лексикографическом порядке. 2⃣Пост-упорядоченный обход (DFS): Создайте функцию DFS, которая будет рекурсивно проходить по всем ребрам (рейсам), начиная с аэропорта "JFK". Во время обхода удаляйте использованные рейсы из графа, чтобы не проходить по ним повторно. 3⃣Формирование маршрута: По мере завершения обхода добавляйте текущий аэропорт в начало списка результата. После завершения DFS верните сформированный маршрут. 😎 Решение:

class Solution {
  HashMap<String, LinkedList<String>> flightMap = new HashMap<>();
  LinkedList<String> result = null;

  public List<String> findItinerary(List<List<String>> tickets) {
    for(List<String> ticket : tickets) {
      String origin = ticket.get(0);
      String dest = ticket.get(1);
      if (this.flightMap.containsKey(origin)) {
        LinkedList<String> destList = this.flightMap.get(origin);
        destList.add(dest);
      } else {
        LinkedList<String> destList = new LinkedList<String>();
        destList.add(dest);
        this.flightMap.put(origin, destList);
      }
    }

    this.flightMap.forEach((key, value) -> Collections.sort(value));

    this.result = new LinkedList<String>();
    this.DFS("JFK");
    return this.result;
  }

  protected void DFS(String origin) {
    if (this.flightMap.containsKey(origin)) {
      LinkedList<String> destList = this.flightMap.get(origin);
      while (!destList.isEmpty()) {
        String dest = destList.pollFirst();
        DFS(dest);
      }
    }
    this.result.offerFirst(origin);
  }
}

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

#medium Задача: 372. Super Pow Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива. Пример:

Input: a = 2, b = [3]
Output: 8

👨‍💻 Алгоритм: 1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди. 2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337. 3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337. 😎 Решение:

public class Solution {
    public int getSum(int a, int b) {
        int x = Math.abs(a), y = Math.abs(b);
        if (x < y) return getSum(b, a);
        int sign = a > 0 ? 1 : -1;

        if (a * b >= 0) {
            while (y != 0) {
                int carry = (x & y) << 1;
                x ^= y;
                y = carry;
            }
        } else {
            while (y != 0) {
                int borrow = ((~x) & y) << 1;
                x ^= y;
                y = borrow;
            }
        }
        return x * sign;
    }
}

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