Available now! Telegram Research 2025 — the year's key insights 
Java | LeetCode
Open in Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+icUwivvbGOkwNWRi Вопросы собесов t.me/+7ESm0VKXC4tjYzky Вакансии t.me/+4pspF5nDjgM4MjQy
Show more6 654
Subscribers
+124 hours
-107 days
-4930 days
Posts Archive
6 654
#medium
Задача: 221. Maximal Square
Дана бинарная матрица размером m x n, заполненная 0 и 1. Найдите наибольший квадрат, содержащий только 1, и верните его площадь.
Пример:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4👨💻 Алгоритм: 1️⃣ Инициализировать 1D массив dp с нулями, чтобы хранить промежуточные результаты для каждого столбца, а также переменные maxsqlen для максимальной длины квадрата и prev для предыдущего значения. 2️⃣ Пройти по каждому элементу матрицы. Если текущий элемент равен '1', обновить dp[j] по формуле dp[j]=min(dp[j−1],prev,dp[j])+1 и обновить maxsqlen. Если текущий элемент равен '0', установить dp[j] в 0. Обновить prev на значение dp[j] перед его изменением. 3️⃣ По завершении пройти по всем строкам и столбцам, вернуть квадрат maxsqlen как площадь наибольшего квадрата. 😎 Решение:
public class Solution {
public int maximalSquare(char[][] matrix) {
int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
int[] dp = new int[cols + 1];
int maxsqlen = 0, prev = 0;
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
int temp = dp[j];
if (matrix[i - 1][j - 1] == '1') {
dp[j] = Math.min(Math.min(dp[j - 1], prev), dp[j]) + 1;
maxsqlen = Math.max(maxsqlen, dp[j]);
} else {
dp[j] = 0;
}
prev = temp;
}
}
return maxsqlen * maxsqlen;
}
}6 654
😮 Добавлена новая база слитых курсов на 800ГБ:
Python:
https://t.me/+QPSH2IcGu4w5ODky
Frontend и Web:
https://t.me/+MiJVQSyUlDNjODky
Программирование:
https://t.me/+opj2LZT23ddiZDli
Графика и дизайн:
https://t.me/+vrZ8dhdUEXM3YmQy
6 654
#hard
Задача: 220. Contains Duplicate III
Вам дан массив целых чисел nums и два целых числа indexDiff и valueDiff.
Найдите пару индексов (i, j) таких, что:
i != j,
abs(i - j) <= indexDiff,
abs(nums[i] - nums[j]) <= valueDiff.
Верните true, если такая пара существует, или false в противном случае.
Пример:
Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0 Output: true Explanation: We can choose (i, j) = (0, 3). We satisfy the three conditions: i != j --> 0 != 3 abs(i - j) <= indexDiff --> abs(0 - 3) <= 3 abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0👨💻 Алгоритм: 1️⃣ Инициализация и вычисление корзин: Рассчитать ширину корзины w = t + 1. Инициализировать пустой хэш-таблицей buckets. Определить функцию getID, которая возвращает идентификатор корзины для элемента x и ширины корзины w. 2️⃣ Итерация и проверка корзин: Перебрать все элементы массива nums. Для каждого элемента nums[i]: Определить его корзину с помощью getID. Проверить, есть ли в текущей корзине элемент. Если есть, вернуть true. Проверить соседние корзины на наличие "почти дубликатов". Если есть, вернуть true. Если текущая корзина пуста и в соседних корзинах нет "почти дубликатов", добавить текущий элемент в соответствующую корзину. Если текущий индекс превышает k, удалить элемент из корзины, которая вышла за пределы окна. 3️⃣ Завершение: Если ни одна пара "почти дубликатов" не найдена, вернуть false. 😎 Решение:
class Solution {
private long getID(long x, long w) {
return Math.floorDiv(x, w);
}
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (t < 0) return false;
Map<Long, Long> buckets = new HashMap<>();
long w = (long) t + 1;
for (int i = 0; i < nums.length; ++i) {
long bucket = getID(nums[i], w);
if (buckets.containsKey(bucket)) return true;
if (
buckets.containsKey(bucket - 1) &&
Math.abs(nums[i] - buckets.get(bucket - 1)) < w
) return true;
if (
buckets.containsKey(bucket + 1) &&
Math.abs(nums[i] - buckets.get(bucket + 1)) < w
) return true;
buckets.put(bucket, (long) nums[i]);
if (i >= k) buckets.remove(getID(nums[i - k], w));
}
return false;
}
}6 654
⚡ Когда говорят, что Java слишком простой язык, на сцену выходит канал Java Learning
Здесь легко научиться:
▪️ Разрабатывать высоконагруженные серверные приложения
▪️ Управлять сложными базами данных
▪️ Организовывать эффективную многопоточную обработку данных
▪️ Проходить технические собеседования в ведущие IT-компании
Самый необычный канал про Java, подписывайся – @Java_per_month
6 654
#hard
Задача: 315. Count of Smaller Numbers After Self
Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].
Пример:
Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.👨💻 Алгоритм: 1️⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4. 2️⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия: Смещайте число на num + offset. Запросите количество элементов в дереве отрезков, которые меньше текущего числа. Обновите счетчик текущего числа в дереве отрезков. 3️⃣Верните результат. 😎 Решение:
class Solution {
public List<Integer> countSmaller(int[] nums) {
int offset = 10000;
int size = 2 * 10000 + 1;
int[] tree = new int[size * 2];
List<Integer> result = new ArrayList<Integer>();
for (int i = nums.length - 1; i >= 0; i--) {
int smaller_count = query(0, nums[i] + offset, tree, size);
result.add(smaller_count);
update(nums[i] + offset, 1, tree, size);
}
Collections.reverse(result);
return result;
}
private void update(int index, int value, int[] tree, int size) {
index += size;
tree[index] += value;
while (index > 1) {
index /= 2;
tree[index] = tree[index * 2] + tree[index * 2 + 1];
}
}
private int query(int left, int right, int[] tree, int size) {
int result = 0;
left += size;
right += size;
while (left < right) {
if (left % 2 == 1) {
result += tree[left];
left++;
}
left /= 2;
if (right % 2 == 1) {
right--;
result += tree[right];
}
right /= 2;
}
return result;
}
}6 654
#medium
Задача: 314. Binary Tree Vertical Order Traversal
Дан корень бинарного дерева, верните вертикальный порядок обхода значений его узлов (т.е. сверху вниз, столбец за столбцом).
Если два узла находятся в одной строке и столбце, порядок должен быть слева направо.
Пример:
Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]]👨💻 Алгоритм: 1️⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов. 2️⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь. 3️⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам. 😎 Решение:
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> output = new ArrayList<>();
if (root == null) {
return output;
}
Map<Integer, ArrayList<Integer>> columnTable = new HashMap<>();
Queue<Pair<TreeNode, Integer>> queue = new ArrayDeque<>();
int column = 0;
queue.offer(new Pair<>(root, column));
while (!queue.isEmpty()) {
Pair<TreeNode, Integer> p = queue.poll();
root = p.getKey();
column = p.getValue();
if (root != null) {
if (!columnTable.containsKey(column)) {
columnTable.put(column, new ArrayList<Integer>());
}
columnTable.get(column).add(root.val);
queue.offer(new Pair<>(root.left, column - 1));
queue.offer(new Pair<>(root.right, column + 1));
}
}
List<Integer> sortedKeys = new ArrayList<>(columnTable.keySet());
Collections.sort(sortedKeys);
for (int k : sortedKeys) {
output.add(columnTable.get(k));
}
return output;
}
}6 654
#easy
Задача: 219. Contains Duplicate II
Дан массив целых чисел nums и целое число k. Верните true, если в массиве существуют два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k.
Пример:
Input: nums = [1,2,3,1,2,3], k = 2 Output: false👨💻 Алгоритм: 1️⃣ Создайте пустое множество set. 2️⃣ Пройдитесь по массиву nums: Если текущий элемент уже есть в множестве, верните true. Добавьте текущий элемент в множество. Если размер множества больше k, удалите элемент, который был добавлен k шагов назад. 3️⃣ Если не найдены дублирующиеся элементы на расстоянии k или менее, верните false. 😎 Решение:
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; ++i) {
if (set.contains(nums[i])) return true;
set.add(nums[i]);
if (set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}6 654
#medium
Задача: 276. Paint Fence
Вы красите забор из n столбцов, используя k различных цветов. Вы должны красить столбы, следуя этим правилам:
Каждый столб должен быть окрашен в один цвет.
Не может быть трех или более подряд идущих столбцов одного цвета.
Учитывая два целых числа n и k, верните количество способов покрасить забор.
Пример:
Input: n = 3, k = 2 Output: 6 Explanation: All the possibilities are shown. Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.👨💻 Алгоритм: 1️⃣Инициализация и определение вспомогательной функции: Определить хеш-таблицу memo, где memo[i] представляет количество способов покрасить i столбцов. Определить функцию totalWays, которая будет определять количество способов покрасить i столбцов. 2️⃣Реализация базы и проверка кэша: В функции totalWays проверить базовые случаи: вернуть k, если i == 1, и вернуть k * k, если i == 2. Проверить, рассчитан ли аргумент i и сохранен ли в memo. Если да, вернуть memo[i]. 3️⃣Расчет с использованием рекуррентного соотношения: В противном случае использовать рекуррентное соотношение для вычисления memo[i], сохранить результат в memo[i] и вернуть его. Вызвать и вернуть totalWays(n). 😎 Решение:
class Solution {
public int numWays(int n, int k) {
if (n == 1) return k;
int twoPostsBack = k;
int onePostBack = k * k;
for (int i = 3; i <= n; i++) {
int curr = (k - 1) * (onePostBack + twoPostsBack);
twoPostsBack = onePostBack;
onePostBack = curr;
}
return onePostBack;
}
}6 654
+5
Разработчик Java, ты тут? 😎
Хочешь построить карьеру в IT? Для Java-разработчиков запускаем бесплатный онлайн-интенсив в Открытых школах Т1. Прокачай скилы и, если повезет, попади в штат Холдинга Т1 — крупнейшей ИТ-компании по выручке в России по версии RAEX и CNews Analytics 2023.
Зачем участвовать?
🔵 Бесплатное обучение в гибком формате: по вечерам, онлайн, из любого города РФ.
🔵 Уникальный рыночный опыт. Проекты Т1 ежегодно побеждают в ИТ-конкурсах: Global CIO, Национальной банковской премии и др. Тебя обучит и поддержит команда профессионалов.
🔵 Возможность влиять на развитие ключевых отраслей экономики: в портфеле Т1 800+ высокотехнологичных проектов и 70+ продуктов и услуг на современном техстеке для крупнейших компаний и госсектора.
🔵 Карьерный рост и поддержка. Уникальный карьерный фаст-трек для выпускников Открытых школ помогает молодым специалистам прокачаться до уровня мидла в Т1 за 1,5 года.
Успей подать заявку до 11 октября!
Реклама. ООО «Т1» ИНН: 7720484492. Erid: 2SDnjd2oUin6 654
#hard
Задача: 218. The Skyline Problem
Горизонт города — это внешний контур силуэта, образованного всеми зданиями в этом городе, когда они видны издалека. Учитывая расположения и высоты всех зданий, верните горизонт, образованный этими зданиями в совокупности.
Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]:
lefti — это координата x левого края i-го здания.
righti — это координата x правого края i-го здания.
heighti — это высота i-го здания.
Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0.
Пример:
Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]] Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]] Explanation: Figure A shows the buildings of the input. Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.👨💻 Алгоритм: 1️⃣ Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights. 2️⃣ Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex). 3️⃣ Пройдитесь по обновленным высотам и добавьте все позиции, где высота меняется, в answer в качестве ключевых точек горизонта. Верните answer как результат. 😎 Решение:
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
SortedSet<Integer> edgeSet = new TreeSet<Integer>();
for (int[] building : buildings) {
int left = building[0], right = building[1];
edgeSet.add(left);
edgeSet.add(right);
}
List<Integer> edges = new ArrayList<Integer>(edgeSet);
Map<Integer, Integer> edgeIndexMap = new HashMap<>();
for (int i = 0; i < edges.size(); ++i) {
edgeIndexMap.put(edges.get(i), i);
}
int[] heights = new int[edges.size()];
for (int[] building : buildings) {
int left = building[0], right = building[1], height = building[2];
int leftIndex = edgeIndexMap.get(left), rightIndex = edgeIndexMap.get(right);
for (int idx = leftIndex; idx < rightIndex; ++idx) {
heights[idx] = Math.max(heights[idx], height);
}
}
List<List<Integer>> answer = new ArrayList<>();
for (int i = 0; i < heights.length; ++i) {
int currHeight = heights[i], currPos = edges.get(i);
if (answer.isEmpty() || answer.get(answer.size() - 1).get(1) != currHeight) {
answer.add(Arrays.asList(currPos, currHeight));
}
}
return answer;
}
}6 654
#medium
Задача: 275. H-Index II
Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.
Пример:
Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.👨💻 Алгоритм: 1️⃣Найти середину массива: Определить средний элемент массива, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n]. 2️⃣Сравнить количество статей с цитированиями больше или равными citations[mid]: Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть. Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n]. Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1]. 3️⃣Возвращение результата: Продолжать процесс, пока не будет найден h-индекс. Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid]. 😎 Решение:
public class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (citations[mid] == n - mid) {
return n - mid;
} else if (citations[mid] < n - mid) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return n - left;
}
}6 654
#easy
Задача: 217. Contains Duplicate
Дан массив целых чисел nums. Верните true, если любое значение появляется в массиве хотя бы дважды, и верните false, если каждый элемент уникален.
Пример:
Input: nums = [1,2,3,4] Output: false👨💻 Алгоритм: 1️⃣ Отсортируйте массив nums по возрастанию. 2️⃣ Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим. 3️⃣ Если любое число совпадает с следующим, верните true. Если цикл завершится без совпадений, верните false. 😎 Решение:
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; ++i) {
if (nums[i] == nums[i + 1]) return true;
}
return false;
}6 654
#medium
Задача: 274. H-Index
Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Пример:
Input: citations = [3,0,6,1,5] Output: 3 Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.👨💻 Алгоритм: 1️⃣Отсортировать массив цитирований по убыванию: Отсортировать массив citations в порядке убывания, чтобы наибольшее количество цитирований было в начале массива. 2️⃣Найти наибольшее значение i, для которого citations[i] > i: Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i. Это значение будет индексом, при котором количество цитирований статьи больше индекса. 3️⃣Рассчитать h-индекс: h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге. 😎 Решение:
public class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int[] papers = new int[n + 1];
for (int c : citations)
papers[Math.min(n, c)]++;
int k = n;
for (int s = papers[n]; k > s; s += papers[k])
k--;
return k;
}
}6 654
#medium
Задача: 216. Combination Sum III
Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:
Используются только числа от 1 до 9.
Каждое число используется не более одного раза.
Верните список всех возможных допустимых комбинаций. Список не должен содержать одинаковые комбинации, и комбинации могут возвращаться в любом порядке.
Пример:
Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations.👨💻 Алгоритм: 1️⃣ Инициализация и запуск рекурсивной функции: Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов. Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов. Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов. 2️⃣ Рекурсивная обработка: В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов. Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки. Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата. 3️⃣ Возвращение результатов: По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций. 😎 Решение:
class Solution {
protected void backtrack(
int remain,
int k,
LinkedList<Integer> comb,
int next_start,
List<List<Integer>> results
) {
if (remain == 0 && comb.size() == k) {
results.add(new ArrayList<Integer>(comb));
return;
} else if (remain < 0 || comb.size() == k) {
return;
}
for (int i = next_start; i < 9; ++i) {
comb.add(i + 1);
this.backtrack(remain - i - 1, k, comb, i + 1, results);
comb.removeLast();
}
}
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> results = new ArrayList<List<Integer>>();
LinkedList<Integer> comb = new LinkedList<Integer>();
this.backtrack(n, k, comb, 0, results);
return results;
}
}6 654
#medium
Задача: 215. Kth Largest Element in an Array
Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.
Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент.
Пример:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4👨💻 Алгоритм: 1️⃣ Отсортируйте массив в порядке убывания: Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее. 2️⃣ Найдите k-й по величине элемент: После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0). 3️⃣ Верните результат: Возвратите найденное значение как результат. 😎 Решение:
class Solution {
public String shortestPalindrome(String s) {
int n = s.length();
String rev = new StringBuilder(s).reverse().toString();
for (int i = 0; i < n; i++) {
if (s.substring(0, n - i).equals(rev.substring(i))) {
return rev.substring(0, i) + s;
}
}
return "";
}
}6 654
#hard
Задача: 273. Integer to English Words
Преобразуйте неотрицательное целое число num в его словесное представление на английском языке.
Пример:
Input: num = 123 Output: "One Hundred Twenty Three"👨💻 Алгоритм: 1️⃣Обработка чисел до 20 и кратных 10 до 90: Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90. Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление. 2️⃣Обработка сотен, тысяч, миллионов и миллиардов: Разделить число на группы по три цифры (единицы, тысячи, миллионы, миллиарды). Для каждой группы сформировать словесное представление с использованием рекурсивной функции для чисел от 1 до 999. 3️⃣Формирование окончательного результата: Собрать словесное представление всех групп, добавив соответствующие суффиксы (тысячи, миллионы, миллиарды). Соединить все части в одну строку, удалив лишние пробелы. 😎 Решение:
class Solution {
private final String[] belowTwenty = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private final String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
private final String[] thousands = {"", "Thousand", "Million", "Billion"};
public String numberToWords(int num) {
if (num == 0) return "Zero";
int i = 0;
String result = "";
while (num > 0) {
if (num % 1000 != 0) {
result = helper(num % 1000) + thousands[i] + " " + result;
}
num /= 1000;
i++;
}
return result.trim();
}
private String helper(int num) {
if (num == 0) return "";
else if (num < 20) return belowTwenty[num] + " ";
else if (num < 100) return tens[num / 10] + " " + helper(num % 10);
else return belowTwenty[num / 100] + " Hundred " + helper(num % 100);
}
}6 654
Тестовое собеседование на Middle Java-разработчика завтра
Уже завтра, 25 сентября в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Java-разработчика.
Как это будет:
1. Мария Ядерцова ведущий Java-разработчик в МТС Диджитал и ex. Сбербанк-Технологии будет задавать реальные вопросы и задачи разработчику-добровольцу
2. Мария будет комментировать каждый ответ респондента, чтобы дать понять чего от вас ожидает собеседующий на интервью
3. В конце можно будет задать любой вопрос Марии
Что узнаешь на прямом эфире от ШОРТКАТ:
· Чего ждут от кандидатов на Middle позиции в Java-разработке
· Какие вопросы задают на интервью и зачем
· Как подготовиться к собесу, чтобы получить оффер
Это бесплатно? Бесплатно
Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_sh_bot
Реклама. ООО "ШОРТКАТ", ИНН: 9731139396, erid: 2VtzqwV17Za
6 654
#hard
Задача: 214. Shortest Palindrome
Дана строка s. Вы можете преобразовать s в палиндром, добавив символы в начало строки.
Верните самый короткий палиндром, который можно получить, выполняя это преобразование.
Пример:
Input: s = "aacecaaa" Output: "aaacecaaa"👨💻 Алгоритм: 1️⃣ Создание обратной строки: Создайте обратную строку rev от исходной строки s, чтобы использовать её для сравнения. 2️⃣ Итерация для поиска наибольшего палиндрома: Перебирайте индекс i от 0 до size(s) - 1. Для каждой итерации проверяйте, равна ли подстрока s от начала до n - i подстроке rev от i до конца строки. Если условие выполняется, это означает, что подстрока s от начала до n - i является палиндромом, так как rev является обратной строкой s. 3️⃣ Возврат результата: Как только найден наибольший палиндром, возвращайте строку, состоящую из обратной подстроки rev от начала до i + исходная строка s. 😎 Решение:
class Solution {
public String shortestPalindrome(String s) {
int n = s.length();
String rev = new StringBuilder(s).reverse().toString();
for (int i = 0; i < n; i++) {
if (s.substring(0, n - i).equals(rev.substring(i))) return (
rev.substring(0, i) + s
);
}
return "";
}
}6 654
#hard
Задача: 272. Closest Binary Search Tree Value II
Дано корень бинарного дерева поиска, целевое значение и целое число k. Верните k значений в дереве, которые ближе всего к целевому значению. Вы можете вернуть ответ в любом порядке.
Гарантируется, что в дереве есть только один уникальный набор из k значений, которые ближе всего к целевому значению.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286, k = 2 Output: [4,3]👨💻 Алгоритм: 1️⃣Выполнить обход дерева в глубину (DFS) и собрать все значения в массив: Пройти по дереву в глубину, добавляя каждое значение узла в массив. 2️⃣Отсортировать массив по расстоянию от целевого значения: Использовать пользовательский компаратор, чтобы отсортировать массив по абсолютному значению разности между элементом массива и целевым значением. 3️⃣Вернуть первые k значений из отсортированного массива: Извлечь первые k элементов из отсортированного массива и вернуть их. 😎 Решение:
class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
List<Integer> arr = new ArrayList<>();
dfs(root, arr);
arr.sort((o1, o2) -> Math.abs(o1 - target) <= Math.abs(o2 - target) ? -1 : 1);
return arr.subList(0, k);
}
private void dfs(TreeNode node, List<Integer> arr) {
if (node == null) {
return;
}
arr.add(node.val);
dfs(node.left, arr);
dfs(node.right, arr);
}
}6 654
#easy
Задача: 270. Closest Binary Search Tree Value
Дано корень бинарного дерева поиска и целевое значение. Верните значение в дереве, которое ближе всего к целевому. Если существует несколько ответов, выведите наименьшее.
Пример:
Input: root = [4,2,5,1,3], target = 3.714286 Output: 4👨💻 Алгоритм: 1️⃣Построить массив с помощью inorder обхода: Выполнить inorder обход дерева и собрать элементы в отсортированный массив. 2️⃣Найти ближайший элемент: Пройти по массиву и определить элемент, наиболее близкий к целевому значению. 3️⃣Выбрать наименьший из ближайших элементов: Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них. 😎 Решение:
class Solution {
public int closestValue(TreeNode root, double target) {
int closest = root.val;
while (root != null) {
if (Math.abs(root.val - target) < Math.abs(closest - target)) {
closest = root.val;
} else if (Math.abs(root.val - target) == Math.abs(closest - target)) {
closest = Math.min(root.val, closest);
}
root = target < root.val ? root.left : root.right;
}
return closest;
}
}