Java | LeetCode
Ir al canal en Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Mostrar más
Red:6 517
Suscriptores
-324 horas
-197 días
-5030 días
Archivo de publicaciones
6 517
Задача: 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);
}
}6 517
Задача: 108. Convert Sorted Array to Binary Search Tree
Сложность: easy
Дан массив целых чисел nums, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте двоичное дерево поиска.
Пример:
Input: nums = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] Explanation: [0,-10,5,null,-3,null,9] is also accepted:👨💻 Алгоритм: 1⃣Инициализация функции помощника: Реализуйте функцию помощника helper(left, right), которая строит двоичное дерево поиска (BST) из элементов массива nums между индексами left и right. Если left > right, это означает, что элементов для построения поддерева нет, возвращаем None. 2⃣Выбор корня и разделение массива: Выберите элемент в середине для корня: p = (left + right) // 2. Инициализируйте корень: root = TreeNode(nums[p]). 3⃣Рекурсивное построение поддеревьев: Рекурсивно стройте левое поддерево: root.left = helper(left, p - 1). Рекурсивно стройте правое поддерево: root.right = helper(p + 1, right). В качестве результата возвращайте helper(0, len(nums) - 1), начиная с корня дерева. 😎 Решение:
class Solution {
int[] nums;
public TreeNode helper(int left, int right) {
if (left > right) return null;
int p = (left + right) / 2;
TreeNode root = new TreeNode(nums[p]);
root.left = helper(left, p - 1);
root.right = helper(p + 1, right);
return root;
}
public TreeNode sortedArrayToBST(int[] nums) {
this.nums = nums;
return helper(0, nums.length - 1);
}
}6 517
Запустите рекламу в телеграм-каналах с Яндекс Директом
Перфоманс-реклама теперь в телеграм-каналах ⚡
Яндекс Директ знает, как привлечь целевую аудиторию 💰👌
Попробовать
#реклама
yandex.ru
О рекламодателе
6 517
Задача: 255. Verify Preorder Sequence in Binary Search Tree
Сложность: medium
Дан массив уникальных целых чисел preorder. Верните true, если это правильная последовательность обхода в порядке предварительного (preorder) обхода для бинарного дерева поиска.
Пример:
Input: preorder = [5,2,1,3,6] Output: true👨💻 Алгоритм: 1⃣Объявите целое число minLimit с маленьким значением, например, минус бесконечность, и стек. 2⃣Итерируйте по массиву preorder. Для каждого num: Очистите стек. Пока верх стека меньше num, извлекайте из стека и обновляйте minLimit. Если num <= minLimit, верните false. Добавьте num в стек. 3⃣Верните true, если удалось пройти весь массив. 😎 Решение:
import java.util.Stack;
class Solution {
public boolean verifyPreorder(int[] preorder) {
int minLimit = Integer.MIN_VALUE;
Stack<Integer> stack = new Stack<>();
for (int num: preorder) {
while (!stack.isEmpty() && stack.peek() < num) {
minLimit = stack.pop();
}
if (num <= minLimit) {
return false;
}
stack.push(num);
}
return true;
}
}6 517
Задача: 1137. N-th Tribonacci Number
Сложность: easy
Трибоначчи последовательность Tn определяется следующим образом:
T0 = 0, T1 = 1, T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 для n >= 0.
Дано n, вернуть значение Tn.
Пример:
Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4👨💻 Алгоритм: 1⃣Если n < 3, вернуть значение n-го терма, как указано в описании задачи. 2⃣Инициализировать a, b и c как базовые случаи. Установить a = 0, b = 1, c = 1. 3⃣Для следующих n - 2 шагов обновлять a, b, c следующим образом: a = b, b = c, c = a + b + c. Вернуть c. 😎 Решение:
class Solution {
public int tribonacci(int n) {
if (n < 3) {
return n > 0 ? 1 : 0;
}
int a = 0, b = 1, c = 1;
for (int i = 0; i < n - 2; ++i) {
int tmp = a + b + c;
a = b;
b = c;
c = tmp;
}
return c;
}
}6 517
Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition
Сложность: medium
Вам дан массив целых чисел
nums и целое число target.
Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)class Solution {
public static int binarySearchRightmost(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
public int numSubseq(int[] nums, int target) {
int n = nums.length;
int mod = 1_000_000_007;
Arrays.sort(nums);
int[] power = new int[n];
power[0] = 1;
for (int i = 1; i < n; ++i) {
power[i] = (power[i - 1] * 2) % mod;
}
int answer = 0;
for (int left = 0; left < n; left++) {
int right = binarySearchRightmost(nums, target - nums[left]) - 1;
if (right >= left) {
answer += power[right - left];
answer %= mod;
}
}
return answer;
}
}6 517
👨👨👨👨👨👨👨👨👨👨
Каналы с Junior IT вакансиями
и стажировками
Подписывайся и забирай свой оффер 🤘
1. Стажировки и вакансии по России и миру
2. IT вакансии по СНГ
3. IT стажировки по СНГ
4. ИИ-ассистент для автооткликов
5. DIGITAL и IT стажировки и вакансии
6. IT стажировки в топовых компаниях мира
7. Удалённые IT вакансии и стажировки
8. Python вакансии и стажировки
9. БИГТЕХ вакансии и стажировки
10. Design вакансии и стажировки
11. QA вакансии и стажировки
12. Junior вакансии и стажировки
13. Frontend вакансии и вопросы собесов
14. Вакансии и стажировки для аналитиков
15. Вакансии в русских стартапах за границей
16. Вакансии и стажировки для DevOps
17. Вакансии, которых нет на ХХ.РУ
6 517
Задача: 1276. Number of Burgers with No Waste of Ingredients
Сложность: medium
Даны два целых числа tomatoSlices и cheeseSlices. Ингредиенты разных бургеров таковы: Jumbo Burger: 4 ломтика помидора и 1 ломтик сыра. Small Burger: 2 ломтика помидора и 1 ломтик сыра. Верните [total_jumbo, total_small] так, чтобы количество оставшихся tomatoSlices было равно 0, а количество оставшихся cheeseSlices было равно 0. Если невозможно сделать так, чтобы оставшиеся tomatoSlices и cheeseSlices были равны 0, верните [].
Пример:
Input: tomatoSlices = 16, cheeseSlices = 7 Output: [1,6]👨💻 Алгоритм: 1⃣Проверьте, возможно ли решить задачу, убедившись, что tomatoSlices четно и находится в допустимых пределах. 2⃣Решите систему уравнений: 4J + 2S = tomatoSlices J + S = cheeseSlices 3⃣Если решение существует, верните его, иначе верните пустой список. 😎 Решение:
public class Solution {
public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
if (tomatoSlices % 2 != 0 || tomatoSlices < 2 * cheeseSlices || tomatoSlices > 4 * cheeseSlices) {
return new ArrayList<>();
}
int total_jumbo = (tomatoSlices - 2 * cheeseSlices) / 2;
int total_small = cheeseSlices - total_jumbo;
return Arrays.asList(total_jumbo, total_small);
}
}6 517
Старт продаж санаторно-курортного комплекса в Крыму!
❤️Оазиз круглогодичного оздоровления и отдыха в Крыму в апартаментах премиум-класса!
Инвестируйте в комплекс, соединяющий в себе оздоровление и отдых 5* и получайте пассивный доход на сдаче от 2.5 млн рублей в год!
Мощная инфраструктура:
- Первая береговая линия с собственным пляжем площадью 30 ГА!
- Вход в море всегда пологий
-Spa центр и круглогодичный бассейн
-Панорамный ресторан на 16 этаже
- Собственный санаторий на территории:
✨Включает в себя популярные программы оздоровления с применением местных лечебных факторов, таких как широко известные Сакские грязи
А также: физиотерапия, массаж и многое другое!
🏠90% номеров с видом на морскую акваторию и горы Крыма!
📱Получите презентацию комплекса + инвестиционную стратегию от брокера!
Получить предложение
#реклама 16+
mrqz.me
О рекламодателе
6 517
Задача: 152. Maximum Product Subarray
Сложность: medium
Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение.
Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.
Пример:
Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.👨💻 Алгоритм: 1⃣Инициализация: Если массив nums пуст, возвращаем 0, так как нет элементов для обработки. Инициализируем переменную result первым элементом массива, чтобы иметь начальную точку сравнения для нахождения максимального произведения. 2⃣Перебор элементов: Используем вложенные циклы для обработки всех возможных подмассивов: Внешний цикл i начинается с начала массива и определяет начальную точку каждого подмассива. Внутренний цикл j начинается с индекса i и идет до конца массива, последовательно умножая элементы и расширяя рассматриваемый подмассив. 3⃣Вычисление произведения и обновление результата: Для каждой итерации внутреннего цикла умножаем текущий элемент nums[j] на аккумулирующую переменную accu и проверяем, не стало ли текущее произведение больше максимального найденного до этого. Обновляем переменную result, если текущее произведение accu превышает текущее максимальное значение result. 😎 Решение:
class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 0) return 0;
int result = nums[0];
for (int i = 0; i < nums.length; i++) {
int accu = 1;
for (int j = i; j < nums.length; j++) {
accu *= nums[j];
result = Math.max(result, accu);
}
}
return result;
}
}6 517
Задача: 157. Read N Characters Given Read4
Сложность: easy
Предположим, что у вас есть файл, и вы можете читать файл только с помощью данного метода read4. Реализуйте метод для чтения n символов.
Метод read4:
API read4 читает четыре последовательных символа из файла, затем записывает эти символы в массив буфера buf4.
Возвращаемое значение — количество фактически прочитанных символов.
Обратите внимание, что у read4 есть собственный указатель файла, аналогично FILE *fp в C.
Определение read4:
Параметр: char[] buf4
Возвращает: int
buf4[] — это назначение, а не источник. Результаты из read4 будут скопированы в buf4[].
Метод read:
Используя метод read4, реализуйте метод read, который читает n символов из файла и сохраняет их в массиве буфера buf. Учтите, что вы не можете напрямую манипулировать файлом.
Возвращаемое значение — количество фактически прочитанных символов.
Определение read:
Параметры: char[] buf, int n
Возвращает: int
buf[] — это назначение, а не источник. Вам нужно будет записать результаты в buf[].
Примечание:
Учтите, что вы не можете напрямую манипулировать файлом. Файл доступен только для чтения с помощью read4, но не для read.
Функция read будет вызываться только один раз для каждого тестового случая.
Вы можете предполагать, что массив буфера назначения, buf, гарантированно имеет достаточно места для хранения n символов.
Пример:
Input: file = "abc", n = 4 Output: 3 Explanation: After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3. Note that "abc" is the file's content, not buf. buf is the destination buffer that you will have to write the results to.👨💻 Алгоритм: 1⃣Инициализация и подготовка: Инициализируйте переменные: copiedChars = 0 для подсчета скопированных символов и readChars = 4 для подсчета прочитанных символов из файла. Начальное значение readChars установлено в 4, что позволяет использовать условие readChars != 4 в качестве маркера конца файла (EOF). Создайте внутренний буфер из 4 символов: buf4. 2⃣Чтение и копирование символов: Пока количество скопированных символов меньше N (copiedChars < n) и еще есть символы в файле (readChars == 4): Прочитайте символы из файла во внутренний буфер buf4 с помощью метода read4(buf4). Копируйте символы из внутреннего буфера buf4 в основной буфер buf по одному. Увеличивайте copiedChars после каждого скопированного символа. 3⃣Завершение процесса: Если количество скопированных символов достигло N (copiedChars == n), прервите процесс копирования. Верните copiedChars как результат функции, указывающий на количество успешно скопированных символов в основной буфер buf. 😎 Решение:
public class Solution extends Reader4 {
public int read(char[] buf, int n) {
int copiedChars = 0, readChars = 4;
char[] buf4 = new char[4];
while (copiedChars < n && readChars == 4) {
readChars = read4(buf4);
for (int i = 0; i < readChars; ++i) {
if (copiedChars == n) return copiedChars;
buf[copiedChars] = buf4[i];
++copiedChars;
}
}
return copiedChars;
}
}6 517
Задача: 565. Array Nesting
Сложность: medium
Дан массив целых чисел nums длиной n, где nums является перестановкой чисел в диапазоне [0, n - 1].
Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила:
Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k.
Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее.
Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат.
Верните длину самого длинного множества s[k].
Пример:
Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation:
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}
👨💻 Алгоритм:
1⃣Создайте массив для отслеживания посещенных элементов.
2⃣Для каждого элемента в nums, если он не посещен, начните формирование множества s[k], последовательно переходя по элементам, пока не встретится уже посещенный элемент.
3⃣Обновите максимальную длину найденного множества.
😎 Решение:
public class Solution {
public int arrayNesting(int[] nums) {
boolean[] visited = new boolean[nums.length];
int maxLength = 0;
for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
int start = i;
int count = 0;
while (!visited[start]) {
visited[start] = true;
start = nums[start];
count++;
}
maxLength = Math.max(maxLength, count);
}
}
return maxLength;
}
}6 517
Задача: 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
Сложность: hard
Вам даны три целых числа n, m и k. Рассмотрим следующий алгоритм для нахождения максимального элемента в массиве положительных целых чисел:
maximum_value = -1
maximum_index = -1
search_cost = 0
n = arr.length
for (i = 0; i < n; i++){
if (maximum_value < arr[i]){
maximum_value = arr[i]
maximum_index = i
search_cost = search_cost + 1
}
}
return maximum_index
Вам необходимо построить массив arr, который имеет следующие свойства:
arr содержит ровно n целых чисел.
1 <= arr[i] <= m, где (0 <= i < n).
После применения указанного алгоритма к arr, значение search_cost равно k.
Верните количество способов построить массив arr с учетом указанных условий. Так как ответ может быть очень большим, ответ должен быть вычислен по модулю 10^9 + 7.
Пример:
Input: n = 2, m = 3, k = 1 Output: 6 Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]👨💻 Алгоритм: 1⃣Инициализация и базовые случаи: Инициализируем 3D массив dp размером [n+1][m+1][k+1]. Устанавливаем базовые случаи: dp[n][...][0] = 1. 2⃣Итерация и обновление массива dp: Проходим в обратном порядке по индексам i от n-1 до 0, по maxSoFar от m до 0 и по remain от 0 до k. Для каждого из этих значений обновляем dp массив, используя предыдущие результаты для вычисления текущих значений. 3⃣Возврат результата: Возвращаем значение dp[0][0][k], которое является решением исходной задачи. 😎 Решение:
class Solution {
public int numOfArrays(int n, int m, int k) {
int[][][] dp = new int[n + 1][m + 1][k + 1];
int MOD = (int) 1e9 + 7;
for (int num = 0; num < dp[0].length; num++) {
dp[n][num][0] = 1;
}
for (int i = n - 1; i >= 0; i--) {
for (int maxSoFar = m; maxSoFar >= 0; maxSoFar--) {
for (int remain = 0; remain <= k; remain++) {
int ans = 0;
for (int num = 1; num <= maxSoFar; num++) {
ans = (ans + dp[i + 1][maxSoFar][remain]) % MOD;
}
if (remain > 0) {
for (int num = maxSoFar + 1; num <= m; num++) {
ans = (ans + dp[i + 1][num][remain - 1]) % MOD;
}
}
dp[i][maxSoFar][remain] = ans;
}
}
}
return dp[0][0][k];
}
}6 517
Открой мощь новых MSI с GeForce RTX 50
Серия NVIDIA GeForce RTX 50 в ноутбуках MSI — это квантовый скачок в мире мощности. Игры на максималках, 3D-рендер без ожиданий, монтаж видео в реальном времени и искусственный интеллект, работающий с небывалой скоростью. Эта техника создана не просто для задач — она их уничтожает. Будь в центре производительности нового поколения. MSI с RTX 50 — когда ты не хочешь ждать, а действуешь.
Узнать больше
#реклама
msi.gm
О рекламодателе
6 517
Задача: 297. Serialize and Deserialize Binary Tree
Сложность: hard
Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по сетевому соединению для последующего восстановления в той же или другой компьютерной среде.
Разработайте алгоритм для сериализации и десериализации бинарного дерева. Нет ограничений на то, как ваш алгоритм сериализации/десериализации должен работать. Вам нужно просто гарантировать, что бинарное дерево может быть сериализовано в строку, и эта строка может быть десериализована в исходную структуру дерева.
Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы.
Пример:
Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5]👨💻 Алгоритм: 1⃣Сериализация дерева: Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree. Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None". 2⃣Пример: Начните с корня, узел 1, строка сериализации становится "1,". Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,". Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None"). Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,"). 3⃣Десериализация строки: Разделите строку на список значений. Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой. 😎 Решение:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Codec {
private void rserialize(TreeNode root, StringBuilder str) {
if (root == null) {
str.append("null,");
} else {
str.append(root.val).append(",");
rserialize(root.left, str);
rserialize(root.right, str);
}
}
public String serialize(TreeNode root) {
StringBuilder str = new StringBuilder();
rserialize(root, str);
return str.toString();
}
private TreeNode rdeserialize(LinkedList<String> data) {
if (data.get(0).equals("null")) {
data.remove(0);
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(data.remove(0)));
root.left = rdeserialize(data);
root.right = rdeserialize(data);
return root;
}6 517
REKONFA Live
6 ноября приглашаем всех, кто имеет отношение к маркетингу и рекламным технологиям, обсудить рынок, тренды, вызовы и их решения.
С докладами на актуальные темы выступят лидеры индустрии и медийные спикеры.
Принять участие можно офлайн и онлайн. Мероприятие бесплатное, нужно только зарегистрироваться.
Зарегистрироваться
#реклама 16+
ya.rekonfa.ru
О рекламодателе
6 517
Задача: 734. Sentence Similarity
Сложность: easy
Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].
Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства не является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c не обязательно похожи.
Пример:
Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]] Output: true👨💻 Алгоритм: 1⃣Проверьте, равны ли длины предложений sentence1 и sentence2. Если нет, верните false. 2⃣Создайте словарь для хранения всех пар похожих слов. 3⃣Проверьте каждую пару слов из предложений sentence1 и sentence2 на схожесть, используя словарь и правило, что слово всегда похоже на само себя. 😎 Решение:
import java.util.*;
public class Solution {
public boolean areSentencesSimilar(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
if (sentence1.length != sentence2.length) {
return false;
}
Map<String, Set<String>> similar = new HashMap<>();
for (List<String> pair : similarPairs) {
String x = pair.get(0);
String y = pair.get(1);
similar.computeIfAbsent(x, k -> new HashSet<>()).add(y);
similar.computeIfAbsent(y, k -> new HashSet<>()).add(x);
}
for (int i = 0; i < sentence1.length; i++) {
String w1 = sentence1[i];
String w2 = sentence2[i];
if (!w1.equals(w2) && (!similar.containsKey(w1) || !similar.get(w1).contains(w2))) {
return false;
}
}
return true;
}
}6 517
Задача: 998. Maximum Binary Tree II
Сложность: medium
Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).
Пример:
Input: root = [5,2,4,null,1], val = 3 Output: [5,2,4,null,1,null,3]👨💻 Алгоритм: 1⃣Поиск места вставки: Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком. 2⃣Вставка нового узла: Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки. 3⃣Создание нового дерева: После вставки нового узла убедитесь, что дерево сохраняет свои свойства максимального дерева. 😎 Решение:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
if (root == null || val > root.val) {
TreeNode newNode = new TreeNode(val);
newNode.left = root;
return newNode;
}
root.right = insertIntoMaxTree(root.right, val);
return root;
}
}6 517
Задача: 118. Pascal's Triangle
Сложность: easy
Дано целое число numRows. Верните первые numRows строк треугольника Паскаля.
В треугольнике Паскаля каждое число является суммой двух чисел, непосредственно расположенных над ним, как показано:
Пример:
Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]👨💻 Алгоритм: 1⃣Инициализируем список triangle, в который добавим первую строку [1]. 2⃣Для каждой новой строки берём предыдущую строку и создаём новую, начиная и заканчивая единицей. Все промежуточные элементы считаем как сумму двух элементов сверху: prevRow[j - 1] + prevRow[j]. 3⃣Добавляем полученную строку в треугольник. Повторяем процесс, пока не соберём все numRows. 😎 Решение:
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<List<Integer>>();
triangle.add(new ArrayList<>());
triangle.get(0).add(1);
for (int rowNum = 1; rowNum < numRows; rowNum++) {
List<Integer> row = new ArrayList<>();
List<Integer> prevRow = triangle.get(rowNum - 1);
row.add(1);
for (int j = 1; j < rowNum; j++) {
row.add(prevRow.get(j - 1) + prevRow.get(j));
}
row.add(1);
triangle.add(row);
}
return triangle;
}
}6 517
Задача: 405. Convert a Number to Hexadecimal
Сложность: easy
Если задано целое число num, верните строку, представляющую его шестнадцатеричное представление. Для отрицательных целых чисел используется метод дополнения до двух. Все буквы в строке ответа должны быть строчными, и в ответе не должно быть никаких ведущих нулей, кроме самого нуля. Примечание: Вам не разрешается использовать какие-либо встроенные библиотечные методы для непосредственного решения этой задачи.
Пример:
Input: num = 26 Output: "1a"👨💻 Алгоритм: 1⃣Определите, является ли число отрицательным. Если да, преобразуйте его в положительное число с помощью метода дополнения до двух. Для этого прибавьте к числу 2^32 и используйте битовую операцию И с маской 0xFFFFFFFF. 2⃣Создайте строку с шестнадцатеричными символами. Последовательно делите число на 16 и добавляйте соответствующий символ к результату, пока число не станет равным нулю. 3⃣Переверните строку результата и удалите ведущие нули, если они есть. Если строка пустая, верните "0". 😎 Решение:
public class Solution {
public String toHex(int num) {
if (num == 0) return "0";
char[] hexChars = "0123456789abcdef".toCharArray();
long n = num;
if (num < 0) n += 1L << 32;
StringBuilder result = new StringBuilder();
while (n > 0) {
result.append(hexChars[(int)(n % 16)]);
n /= 16;
}
return result.reverse().toString();
}
}