Java | LeetCode

Регистрируйся на ИТ-Пикник от Т-Банка 8 августа 8 августа — время отложить ноутбуки и встретиться офлайн на ИТ-Пикнике от Т-Банка в музее-заповеднике «Коломенское». Вот сколько всего запланировано: — научпоп-лекции; — мастер-классы; — дискуссии об ИИ и больших языковых моделях; — доклады о кибербезопасности; — примеры, как данные из логов становятся решениями; — много музыки. Бери с собой друзей, супругов и детей — каждый найдет себе что-то по душе. Узнать больше #реклама 16+ it-picnic.ru О рекламодателе

Задача: 256. Paint House Сложность: medium Есть ряд из n домов, где каждый дом можно покрасить в один из трёх цветов: красный, синий или зелёный. Стоимость покраски каждого дома в определённый цвет разная. Необходимо покрасить все дома так, чтобы никакие два соседних дома не были окрашены в один и тот же цвет. Стоимость покраски каждого дома в определённый цвет представлена в виде матрицы стоимости n x 3. Например, costs[0][0] — это стоимость покраски дома 0 в красный цвет; costs[1][2] — это стоимость покраски дома 1 в зелёный цвет и так далее... Верните минимальную стоимость покраски всех домов. Пример: Input: costs = [[17,2,17],[16,16,5],[14,3,19]] Output: 10 Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10. 👨‍💻 Алгоритм: 1⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2]. 2⃣Для каждого дома i от 1 до n-1 обновите значения массива dp: dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]) 3⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]). 😎 Решение: class Solution { public int minCost(int[][] costs) { int n = costs.length; int[][] dp = new int[n][3]; dp[0] = costs[0].clone(); for (int i = 1; i < n; i++) { dp[i][0] = costs[i][0] + Math.min(dp[i-1][1], dp[i-1][2]); dp[i][1] = costs[i][1] + Math.min(dp[i-1][0], dp[i-1][2]); dp[i][2] = costs[i][2] + Math.min(dp[i-1][0], dp[i-1][1]); } return Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2])); } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 713. Subarray Product Less Than K Сложность: medium Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k. Пример: Input: nums = [10,5,2,6], k = 100 Output: 8 👨‍💻 Алгоритм: 1⃣Инициализируйте переменные для отслеживания текущего произведения и количества допустимых подмассивов. Используйте два указателя для границ подмассива. 2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k. 3⃣Подсчитайте количество подмассивов с текущим правым указателем, добавив к общему количеству допустимых подмассивов разницу между правым и левым указателями. 😎 Решение: public class Solution { public int numSubarrayProductLessThanK(int[] nums, int k) { if (k <= 1) return 0; int product = 1, count = 0, left = 0; for (int right = 0; right < nums.length; right++) { product *= nums[right]; while (product >= k) { product /= nums[left]; left++; } count += right - left + 1; } return count; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 263. Ugly Number Сложность: easy Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5. Дано целое число n, верните true, если n является уродливым числом. Пример: Input: n = 6 Output: true Explanation: 6 = 2 × 3 👨‍💻 Алгоритм: 1⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым. 2⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5. 3⃣Если после всех делений n равно 1, верните true, иначе верните false. 😎 Решение: class Solution { public boolean isUgly(int n) { if (n <= 0) { return false; } for (int factor : new int[] {2, 3, 5}) { n = keepDividingWhenDivisible(n, factor); } return n == 1; } private int keepDividingWhenDivisible(int dividend, int divisor) { while (dividend % divisor == 0) { dividend /= divisor; } return dividend; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 462. Minimum Moves to Equal Array Elements II Сложность: medium Дан массив целых чисел 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; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1328. Break a Palindrome Сложность: medium Дана палиндромная строка из строчных английских букв palindrome. Замените ровно один символ на любую строчную английскую букву так, чтобы результирующая строка не была палиндромом и чтобы она была лексикографически наименьшей из возможных. Верните получившуюся строку. Если нет способа заменить символ, чтобы строка перестала быть палиндромом, верните пустую строку. Строка a лексикографически меньше строки b (одинаковой длины), если в первой позиции, где они отличаются, у строки a символ строго меньше соответствующего символа в строке b. Например, "abcc" лексикографически меньше "abcd", потому что первой различающейся позицией является четвертая, и 'c' меньше, чем 'd'. Пример: Input: palindrome = "abccba" Output: "aaccba" Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba". Of all the ways, "aaccba" is the lexicographically smallest. 👨‍💻 Алгоритм: 1⃣Если длина строки равна 1, верните пустую строку, так как невозможно создать непалиндромическую строку в этом случае. 2⃣Итерируйтесь по строке слева до середины строки: если символ не равен 'a', измените его на 'a' и верните строку. 3⃣Если вы прошли всю левую часть строки и все еще не получили непалиндромическую строку, это означает, что строка состоит только из 'a'. Следовательно, измените последний символ на 'b' и верните полученную строку. 😎 Решение: class Solution { public String breakPalindrome(String palindrome) { int length = palindrome.length(); if (length == 1) { return ""; } char[] palindromeArray = palindrome.toCharArray(); for (int i = 0; i < length / 2; i++) { if (palindromeArray[i] != 'a') { palindromeArray[i] = 'a'; return new String(palindromeArray); } } palindromeArray[length - 1] = 'b'; return new String(palindromeArray); } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 438. Find All Anagrams in a String Сложность: medium Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке. Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз. Пример: Input: s = "cbaebabacd", p = "abc" Output: [0,6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc". 👨‍💻 Алгоритм: 1⃣Построить эталонный счетчик pCount для строки p. 2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева. 3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список. 😎 Решение: class Solution { public List<Integer> findAnagrams(String s, String p) { int ns = s.length(), np = p.length(); if (ns < np) return new ArrayList<>(); Map<Character, Integer> pCount = new HashMap<>(); Map<Character, Integer> sCount = new HashMap<>(); for (char ch : p.toCharArray()) { pCount.put(ch, pCount.getOrDefault(ch, 0) + 1); } List<Integer> output = new ArrayList<>(); for (int i = 0; i < ns; ++i) { char ch = s.charAt(i); sCount.put(ch, sCount.getOrDefault(ch, 0) + 1); if (i >= np) { ch = s.charAt(i - np); if (sCount.get(ch) == 1) { sCount.remove(ch); } else { sCount.put(ch, sCount.get(ch) - 1); } } if (pCount.equals(sCount)) { output.add(i - np + 1); } } return output; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 989. Add to Array-Form of Integer Сложность: easy Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо. Например, для num = 1321, массивная форма - это [1, 3, 2, 1]. Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k. Пример: Input: num = [1,2,0,0], k = 34 Output: [1,2,3,4] Explanation: 1200 + 34 = 1234 👨‍💻 Алгоритм: 1⃣Инициализация переменных: Преобразуйте число k в массив его цифр и переверните оба массива (массив num и массив цифр k). Завести переменную carry для хранения переноса и инициализировать ее нулем. Создать пустой массив result для хранения результата. 2⃣Сложение массивов: Пройдите по элементам массивов num и цифр k, начиная с их конца, сложите соответствующие цифры вместе с переносом (carry). Если сумма больше 9, сохраните последнюю цифру в текущей позиции результата, а carry установите в 1. Если сумма меньше 10, установите carry в 0. Добавьте результат текущего сложения в массив result 3⃣Обработка оставшихся цифр и переноса: Если один из массивов закончился раньше, продолжайте сложение оставшихся цифр другого массива с переносом. Если после окончания всех сложений остается перенос (carry), добавьте его в начало массива result. Переверните массив result обратно и верните его. 😎 Решение: import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Solution { public List<Integer> addToArrayForm(int[] num, int k) { List<Integer> result = new ArrayList<>(); int n = num.length; for (int i = n - 1; i >= 0; i--) { k += num[i]; result.add(k % 10); k /= 10; } while (k > 0) { result.add(k % 10); k /= 10; } Collections.reverse(result); return result; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 916. Word Subsets Сложность: medium Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке. Пример: Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"] Output: ["facebook","google","leetcode"] 👨‍💻 Алгоритм: 1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2. 2⃣Проверить каждое слово из words1, если оно содержит не менее максимального количества каждой буквы, которая встречается в словах из words2. 3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию. 😎 Решение: import java.util.*; class Solution { public List<String> wordSubsets(String[] words1, String[] words2) { int[] maxCount = new int[26]; for (String word : words2) { int[] count = getCount(word); for (int i = 0; i < 26; i++) { maxCount[i] = Math.max(maxCount[i], count[i]); } } List<String> result = new ArrayList<>(); for (String word : words1) { int[] count = getCount(word); if (isUniversal(count, maxCount)) { result.add(word); } } return result; } private int[] getCount(String word) { int[] count = new int[26]; for (char c : word.toCharArray()) { count[c - 'a']++; } return count; } private boolean isUniversal(int[] count, int[] maxCount) { for (int i = 0; i < 26; i++) { if (count[i] < maxCount[i]) { return false; } } return true; } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 567. Permutation in String Сложность: medium Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае. Другими словами, верните true, если одна из перестановок s1 является подстрокой s2. Пример: Input: s1 = "ab", s2 = "eidbaooo" Output: true Explanation: s2 contains one permutation of s1 ("ba"). 👨‍💻 Алгоритм: 1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2. 2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1. 3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false. 😎 Решение: public class Solution { public boolean checkInclusion(String s1, String s2) { int s1Len = s1.length(), s2Len = s2.length(); if (s1Len > s2Len) return false; int[] s1Count = new int[26]; int[] s2Count = new int[26]; for (int i = 0; i < s1Len; i++) { s1Count[s1.charAt(i) - 'a']++; s2Count[s2.charAt(i) - 'a']++; } for (int i = 0; i < s2Len - s1Len; i++) { if (Arrays.equals(s1Count, s2Count)) return true; s2Count[s2.charAt(i) - 'a']--; s2Count[s2.charAt(i + s1Len) - 'a']++; } return Arrays.equals(s1Count, s2Count); } } Ставь 👍 и забирай 📚 Базу знаний