Java | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:6 506
Subscribers
-424 hours
-217 days
-5730 days
Posts Archive
6 507
👍Научитесь писать проверки для своего проекта, правильно подсвечивать в IDE и репортить найденные инциденты!
На бесплатном уроке онлайн-курса «Android Developer. Professional» — «Android Lint»: регистрация
Что будет на вебинаре?
- Подробно рассмотрим API Android Lint и PSI/UAST деревья
- Научимся реализовывать свои Detector'ы
- Научимся тестировать реализованные Detector'ы
Каким слушателям вебинар будет полезен?
- Инженерам, которые интересуются статическим анализом, хотят автоматизировать поиск codesmell'ов, проверку кодстайла, проверку принятых в проекте регламентов.
🔥После вебинара вы сможете продолжить обучение на курсе по спеццене, в том числе, в рассрочку.
erid: LjN8JxFQ7
6 507
2024 все.. а ты еще не разработчик?
нет опыта, идей и времени, высокая конкуренция. Оставь эти отговорки в 2024! И читай здесь, что нужно для успешной карьеры 👇
- актуальные навыки в 2025. Быстрее адаптируешься к запросам рынка, выше твоя зп 😉
- идеи для проектов, современные инструменты разработки (Jira, GitHub, Miro)
- успешное прохождение интервью
Не понимаешь, как это реализовать? Тогда приходи на мощный 3-х дневный интенсив «Пошаговый гайд к работе Java Dev в 2025» от FAANG SCHOOL. И у тебя полностью перевернется представление о том, как сейчас выглядит рынок IT!
Получишь полный план от изучения базы программирования и создания проекта до оффера!
- какие навыки изучить в первую очередь
- как выбирать актуальные идеи для проекта
- ошибки, из-за которых 80% проектов оказываются провальными
- как преодолеть фильтры HR без накрутки опыта
⬇️ Пока ты думаешь, кто-то получает твой оффер! Переходи, забирай подарок и узнай, как даже джуну создать проект, способный обеспечить для него пассивный доход!
6 507
#Medium
Задача: 478. Generate Random Point in a Circle
Дан радиус и положение центра окружности, реализуйте функцию randPoint, которая генерирует равномерно случайную точку внутри окружности.
Реализуйте класс Solution:
- Solution(double radius, double x_center, double y_center) инициализирует объект с радиусом окружности radius и положением центра (x_center, y_center).
- randPoint() возвращает случайную точку внутри окружности. Точка на окружности считается находящейся внутри окружности. Ответ возвращается в виде массива [x, y].
Пример:
Input ["Solution", "randPoint", "randPoint", "randPoint"] [[1.0, 0.0, 0.0], [], [], []] Output [null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]] Explanation Solution solution = new Solution(1.0, 0.0, 0.0); solution.randPoint(); // return [-0.02493, -0.38077] solution.randPoint(); // return [0.82314, 0.38945] solution.randPoint(); // return [0.36572, 0.17248]👨💻 Алгоритм: 1⃣ Генерируем равномерно случайные точки в квадрате S с длиной стороны 2R. 2⃣ Сохраняем все точки, которые находятся на расстоянии не более R от центра, и отклоняем все, которые дальше этого расстояния. 3⃣ Повторяем процесс до получения нужного количества точек, учитывая, что примерно 78.5% от всех сгенерированных точек будут приемлемыми, и ожидаемое число попыток до получения приемлемой точки составляет примерно 1.274 раза. 😎 Решение:
class Solution {
double rad, xc, yc;
public Solution(double radius, double x_center, double y_center) {
rad = radius;
xc = x_center;
yc = y_center;
}
public double[] randPoint() {
double x0 = xc - rad;
double y0 = yc - rad;
while (true) {
double xg = x0 + Math.random() * rad * 2;
double yg = y0 + Math.random() * rad * 2;
if (Math.sqrt(Math.pow((xg - xc), 2) + Math.pow((yg - yc), 2)) <= rad) {
return new double[]{xg, yg};
}
}
}
}6 507
#Hard
Задача: 480. Sliding Window Median
Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.
Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.
Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.
Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.
Пример:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3 Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000] Explanation: Window position Median --------------- ----- [1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6👨💻 Алгоритм: 1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента. 2⃣ Отсортируйте окно, чтобы найти медианы. Вместо того чтобы каждый раз копировать и сортировать k последовательных элементов из входных данных, вставляйте и удаляйте по одному элементу при каждом сдвиге окна. 3⃣ Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления. 😎 Решение:
import java.util.*;
public class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
List<Double> medians = new ArrayList<>();
for (int i = 0; i + k <= nums.length; i++) {
int[] window = Arrays.copyOfRange(nums, i, i + k);
Arrays.sort(window);
if (k % 2 == 1) {
medians.add((double) window[k / 2]);
} else {
medians.add((window[k / 2 - 1] + window[k / 2]) / 2.0);
}
}
double[] result = new double[medians.size()];
for (int i = 0; i < medians.size(); i++) {
result[i] = medians.get(i);
}
return result;
}
}6 507
👍Научитесь писать проверки для своего проекта, правильно подсвечивать в IDE и репортить найденные инциденты!
На бесплатном уроке онлайн-курса «Android Developer. Professional» — «Android Lint»: регистрация
Что будет на вебинаре?
- Подробно рассмотрим API Android Lint и PSI/UAST деревья
- Научимся реализовывать свои Detector'ы
- Научимся тестировать реализованные Detector'ы
Каким слушателям вебинар будет полезен?
- Инженерам, которые интересуются статическим анализом, хотят автоматизировать поиск codesmell'ов, проверку кодстайла, проверку принятых в проекте регламентов.
🔥После вебинара вы сможете продолжить обучение на курсе по спеццене, в том числе, в рассрочку.
erid: LjN8JxFQ7
6 507
#Easy
Задача: 482. License Key Formatting
Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k.
Мы хотим переформатировать строку s так, чтобы каждая группа содержала ровно k символов, за исключением первой группы, которая может быть короче k, но все же должна содержать хотя бы один символ. Кроме того, между двумя группами должно быть вставлено тире, и все строчные буквы следует преобразовать в прописные.
Верните переформатированный лицензионный ключ.
Пример:
Input: s = "5F3Z-2e-9-w", k = 4 Output: "5F3Z-2E9W" Explanation: The string s has been split into two parts, each part has 4 characters. Note that the two extra dashes are not needed and can be removed.👨💻 Алгоритм: 1⃣Инициализация Установите count в 0 для подсчета символов в текущей группе. Установите ans в пустую строку для хранения конечного результата. 2⃣Итерация по входной строке в обратном порядке Пропускайте символы '-'. Если текущий символ не '-', добавьте его в ans и увеличьте count на 1. Если count достигает k, добавьте '-' в ans и сбросьте count. 3⃣Завершение Проверьте, есть ли в конце строки ans тире, и удалите его, если оно есть. Переверните строку ans и верните её. 😎 Решение:
class Solution {
public String licenseKeyFormatting(String s, int k) {
int count = 0;
StringBuilder ans = new StringBuilder();
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) != '-') {
ans.append(Character.toUpperCase(s.charAt(i)));
count++;
if (count == k) {
ans.append('-');
count = 0;
}
}
}
if (ans.length() > 0 && ans.charAt(ans.length() - 1) == '-') {
ans.deleteCharAt(ans.length() - 1);
}
return ans.reverse().toString();
}
}6 507
#easy
Задача: 589. N-ary Tree Preorder Traversal
Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода.
Сериализация ввода N-арного дерева представлена в их обходе уровнями. Каждая группа детей разделена значением null (См. примеры).
Пример:
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]👨💻 Алгоритм: 1⃣Инициализация Создайте два списка: stack для хранения узлов и output для хранения значений узлов в порядке обхода. Добавьте корневой узел в stack. 2⃣Итеративный обход Пока stack не пуст, извлекайте узел из stack и добавляйте его значение в output. Разверните список дочерних узлов текущего узла и добавьте их в stack. 3⃣Возврат результата Верните список output как результат. 😎 Решение:
class Solution {
public List<Integer> preorder(Node root) {
LinkedList<Node> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
Node node = stack.pollLast();
output.add(node.val);
Collections.reverse(node.children);
for (Node item : node.children) {
stack.add(item);
}
}
return output;
}
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
}
}6 507
#easy
Задача: 326. Power of Three
Дано целое число n. Верните true, если оно является степенью тройки, иначе верните false.
Целое число n является степенью тройки, если существует целое число x такое, что n == 3^x.
Пример:
Input: n = 27 Output: true Explanation: 27 = 3^3👨💻 Алгоритм: 1⃣Проверка начального значения Если n меньше или равно нулю, вернуть false, так как степени тройки всегда положительны. 2⃣Цикл деления на 3 Пока n делится на 3 без остатка, делите n на 3. Повторяйте этот процесс до тех пор, пока n делится на 3. 3⃣Проверка конечного значения Если после всех делений значение n стало равно 1, значит исходное число является степенью тройки, вернуть true. В противном случае вернуть false. 😎 Решение:
public class Solution {
public boolean isPowerOfThree(int n) {
if (n <= 0) return false;
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}
}6 507
#medium
Задача: 325. Maximum Size Subarray Sum Equals k
Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0.
Пример:
Input: nums = [1,-1,5,-2,3], k = 3 Output: 4 Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.👨💻 Алгоритм: 1⃣Инициализация переменных Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов. 2⃣Итерация по массиву На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i. 3⃣Возврат результата Верните значение longestSubarray. 😎 Решение:
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int maxSubArrayLen(int[] nums, int k) {
int prefixSum = 0;
int longestSubarray = 0;
Map<Integer, Integer> indices = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
prefixSum += nums[i];
if (prefixSum == k) {
longestSubarray = i + 1;
}
if (indices.containsKey(prefixSum - k)) {
longestSubarray = Math.max(longestSubarray, i - indices.get(prefixSum - k));
}
if (!indices.containsKey(prefixSum)) {
indices.put(prefixSum, i);
}
}
return longestSubarray;
}
}6 507
#hard
Задача: 407. Trapping Rain Water II
Задав целочисленную матрицу heightMap размером m x n, представляющую высоту каждой ячейки на двумерной карте рельефа, верните объем воды, который она может задержать после дождя.
Пример:
Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] Output: 4👨💻 Алгоритм: 1⃣Используйте приоритетную очередь для хранения всех ячеек по периметру матрицы. 2⃣Постепенно извлекайте ячейки из очереди, рассматривая их соседей. Если соседняя ячейка ниже текущей, добавьте разницу в высоте к общему объему воды и обновите её высоту. 3⃣Повторите процесс, пока все ячейки не будут обработаны. 😎 Решение:
import java.util.PriorityQueue;
public class Solution {
public int trapRainWater(int[][] heightMap) {
if (heightMap.length == 0 || heightMap[0].length == 0) return 0;
int m = heightMap.length, n = heightMap[0].length;
boolean[][] visited = new boolean[m][n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < m; i++) {
for (int j : new int[]{0, n-1}) {
pq.offer(new int[]{heightMap[i][j], i, j});
visited[i][j] = true;
}
}
for (int j = 0; j < n; j++) {
for (int i : new int[]{0, m-1}) {
pq.offer(new int[]{heightMap[i][j], i, j});
visited[i][j] = true;
}
}
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int water = 0;
while (!pq.isEmpty()) {
int[] cell = pq.poll();
for (int[] dir : directions) {
int nx = cell[1] + dir[0], ny = cell[2] + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
visited[nx][ny] = true;
water += Math.max(0, cell[0] - heightMap[nx][ny]);
pq.offer(new int[]{Math.max(cell[0], heightMap[nx][ny]), nx, ny});
}
}
}
return water;
}
}6 507
#medium
Задача: 323. Number of Connected Components in an Undirected Graph
У вас есть граф из n узлов. Вам дано целое число n и массив edges, где edges[i] = [ai, bi] указывает на наличие ребра между ai и bi в графе.
Верните количество связных компонентов в графе.
Пример:
Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2👨💻 Алгоритм: 1⃣Создание списка смежности Создайте список смежности, такой что adj[v] содержит все смежные вершины вершины v. 2⃣Инициализация посещенных узлов Инициализируйте хэш-карту или массив visited для отслеживания посещенных вершин. 3⃣Подсчет компонентов Определите счетчик и инициализируйте его нулем. Итерируйте по каждой вершине в edges, и если вершина еще не была посещена, начните DFS с этой вершины. Добавляйте каждую вершину, посещенную во время DFS, в visited. Каждый раз, когда начинается новый DFS, увеличивайте счетчик на один. В конце, счетчик будет содержать количество связных компонентов в неориентированном графе. 😎 Решение:
public class Solution {
public int countComponents(int n, int[][] edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, adj, visited);
count++;
}
}
return count;
}
private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
Stack<Integer> stack = new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
int current = stack.pop();
if (!visited[current]) {
visited[current] = true;
for (int neighbor : adj.get(current)) {
if (!visited[neighbor]) stack.push(neighbor);
}
}
}
}
}6 507
📶 С 1 декабря для граждан РФ открыт доступ к платным материалам по программированию
Вот отсортированные базы с тонной материала(книги, курсы, ресурсы и гайды). Выбирай своё направление:
👩💻 Frontend 👩💻 PHP
⚙️ Backend 👩💻 Моб. Dev
📱 GitHub 👩💻 GameDev
🤓 Всё айти 👩💻 DevOps
👩💻 Python 🖥 Data Science
👩💻 Java 🐞 Тестирование
👩💻 C# 🤔 Хакинг & ИБ
👩💻 С/С++ 📱 Маркетинг
🖥 SQL 🖥 Дизайн
👩💻 Golang 👣 Rust
Скачивать ничего не нужно — все выложили в Telegram с доступом по ссылке
6 507
#medium
Задача: 406. Queue Reconstruction by Height
Вам дан массив людей, people, которые являются атрибутами некоторых людей в очереди (не обязательно по порядку). Каждый people[i] = [hi, ki] представляет собой человека ростом hi, перед которым стоят ровно ki других людей, чей рост больше или равен hi. Реконструируйте и верните очередь, представленную входным массивом people. Возвращаемая очередь должна быть отформатирована как массив queue, где queue[j] = [hj, kj] - это атрибуты j-го человека в очереди (queue[0] - человек, находящийся в начале очереди).
Пример:
Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]👨💻 Алгоритм: 1⃣Отсортируйте массив people по убыванию роста hi. Если два человека имеют одинаковый рост, отсортируйте их по возрастанию значения ki. 2⃣Создайте пустой список для результата. Вставляйте каждого человека из отсортированного массива в список на позицию, соответствующую значению ki. 3⃣Верните список результата. 😎 Решение:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
List<int[]> result = new ArrayList<>();
for (int[] person : people) {
result.add(person[1], person);
}
return result.toArray(new int[result.size()][]);
}
}6 507
#medium
Задача: 322. Coin Change
Дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.
Верните минимальное количество монет, необходимых для составления этой суммы. Если эту сумму невозможно составить с помощью комбинации монет, верните -1.
Вы можете предположить, что у вас есть неограниченное количество монет каждого типа.
Пример:
Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1👨💻 Алгоритм: 1⃣Инициализация и вызов функции backtracking Инициализируйте переменные для хранения минимального количества монет и вызовите функцию backtracking с начальными параметрами. 2⃣Функция backtracking Внутри функции backtracking для каждой монеты из массива coins: Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет. 3⃣Возврат результата Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1. 😎 Решение:
public class Solution {
public int coinChange(int[] coins, int amount) {
return coinChange(0, coins, amount);
}
private int coinChange(int idxCoin, int[] coins, int amount) {
if (amount == 0) return 0;
if (idxCoin < coins.length && amount > 0) {
int maxVal = amount / coins[idxCoin];
int minCost = Integer.MAX_VALUE;
for (int x = 0; x <= maxVal; x++) {
if (amount >= x * coins[idxCoin]) {
int res = coinChange(idxCoin + 1, coins, amount - x * coins[idxCoin]);
if (res != -1)
minCost = Math.min(minCost, res + x);
}
}
return (minCost == Integer.MAX_VALUE) ? -1 : minCost;
}
return -1;
}
}6 507
Забирай пошаговую roadmap по JAVA
FAANG School в течение 24 часов отдают бесплатно свою библиотеку знаний. Вы можете получить доступ:
– Redis - 5 улучшений для твоего пет-проекта
– Пошаговая RoadMap по Java
– Мануал по Docker. Основные команды и концепции
– Микросервисы. Вопросы с собеседований
– Шпаргалка с горячими клавишами JetBrains IDE. Ускоришь работу в 10 раз
– Desk setup. Подборка аксессуаров для комфортной работы
– Шпаргалка по Kafka
– Инструкция по работе с Git
– Подробный гайд, как найти работу в IT без опыта
– Подборка платформ с вакансиями для java-разработчиков
Последнее пополнение - Шпаргалка по Spring, в которой подробно разобрали, что такое паттерн Наблюдатель, и как его реализовать в Java. А также познакомитесь с событиями и научитесь работать с ними в Spring Boot!
Библиотека знаний обновляется постоянно, но бесплатный доступ длится всего сутки. Чтобы получить полезные материалы, переходи по ссылке и жми на оранжевую кнопку.
6 507
#easy
Задача: 543. Diameter of Binary Tree
Учитывая корень бинарного дерева, вернуть длину диаметра дерева.
Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.
Длина пути между двумя узлами представлена числом ребер между ними.
Пример:
Input: root = [1,2] Output: 1👨💻 Алгоритм: 1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS. 2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1. 3⃣Вызвать longestPath с root. 😎 Решение:
class Solution {
private int diameter;
public int diameterOfBinaryTree(TreeNode root) {
diameter = 0;
longestPath(root);
return diameter;
}
private int longestPath(TreeNode node) {
if (node == null) return 0;
int leftPath = longestPath(node.left);
int rightPath = longestPath(node.right);
diameter = Math.max(diameter, leftPath + rightPath);
return Math.max(leftPath, rightPath) + 1;
}
}6 507
#easy
Задача: 405. Convert a Number to Hexadecimal
Если задано целое число 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();
}
}6 507
#medium
Задача: 320. Generalized Abbreviation
Обобщенная аббревиатура слова может быть построена путем замены любых неперекрывающихся и несмежных подстрок на их соответствующие длины.
Например, "abcde" можно сократить следующим образом:
"a3e" ("bcd" заменено на "3")
"1bcd1" ("a" и "e" заменены на "1")
"5" ("abcde" заменено на "5")
"abcde" (без замены подстрок)
Однако следующие аббревиатуры недействительны:
"23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные.
"22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются.
Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке.
Пример:
Input: word = "a" Output: ["1","a"]👨💻 Алгоритм: 1⃣Создание битовых масок Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур. 2⃣Генерация аббревиатур Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик. 3⃣Перебор всех комбинаций Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1. 😎 Решение:
public class Solution {
public List<String> generateAbbreviations(String word) {
List<String> ans = new ArrayList<>();
for (int x = 0; x < (1 << word.length()); ++x)
ans.add(abbr(word, x));
return ans;
}
private String abbr(String word, int x) {
StringBuilder builder = new StringBuilder();
int k = 0, n = word.length();
for (int i = 0; i < n; ++i, x >>= 1) {
if ((x & 1) == 0) {
if (k != 0) {
builder.append(k);
k = 0;
}
builder.append(word.charAt(i));
} else {
++k;
}
}
if (k != 0) builder.append(k);
return builder.toString();
}
}6 507
#medium
Задача: 319. Bulb Switcher
Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку.
На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку.
Верните количество лампочек, которые будут включены после n раундов.
Пример:
Input: n = 3 Output: 1 Explanation: At first, the three bulbs are [off, off, off]. After the first round, the three bulbs are [on, on, on]. After the second round, the three bulbs are [on, off, on]. After the third round, the three bulbs are [on, off, off]. So you should return 1 because there is only one bulb is on. Explanation: The two words can be "abcw", "xtfn".👨💻 Алгоритм: 1⃣Инициализация Лампочка остается включенной, если она переключалась нечетное количество раз. Лампочка будет переключаться на каждом делителе её номера. 2⃣Определение состояния лампочки Лампочка останется включенной только в том случае, если у нее нечетное количество делителей, что возможно только для квадратных чисел. 3⃣Подсчет включенных лампочек Количество лампочек, которые будут включены после n раундов. 😎 Решение:
class Solution {
public int bulbSwitch(int n) {
return (int) Math.sqrt(n);
}
}6 507
#medium
Задача: 318. Maximum Product of Word Lengths
Дан массив строк
words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0.
Пример:
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"] Output: 16 Explanation: The two words can be "abcw", "xtfn".👨💻 Алгоритм: 1⃣Предварительная обработка масок и длин Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens. 2⃣Сравнение слов и проверка общих букв Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd. 3⃣Возврат результата Верните максимальное значение произведения maxProd. 😎 Решение:
class Solution {
public int maxProduct(String[] words) {
int n = words.length;
int[] masks = new int[n];
int[] lens = new int[n];
for (int i = 0; i < n; i++) {
int bitmask = 0;
for (char ch : words[i].toCharArray()) {
bitmask |= 1 << (ch - 'a');
}
masks[i] = bitmask;
lens[i] = words[i].length();
}
int maxVal = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((masks[i] & masks[j]) == 0) {
maxVal = Math.max(maxVal, lens[i] * lens[j]);
}
}
}
return maxVal;
}
}