Java | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Show more
6 373
Subscribers
No data24 hours
-187 days
-7830 days
Posts Archive
6 373
#easy
Задача: 375. Guess Number Higher or Lower II
Мы играем в угадайку. Правила игры следующие:
Я загадываю число между 1 и n.
Вы угадываете число.
Если вы угадаете правильное число, вы выигрываете игру.
Если вы угадаете неправильное число, я скажу вам, загаданное число больше или меньше, и вы продолжите угадывать.
Каждый раз, когда вы угадываете неправильное число x, вы платите x долларов. Если у вас закончились деньги, вы проигрываете игру.
Дано число n. Верните минимальную сумму денег, необходимую для гарантированной победы независимо от того, какое число я загадаю.
Пример:
Input: n = 1 Output: 0 Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.👨💻 Алгоритм: 1⃣В методе "грубой силы" для чисел в диапазоне (i, j) выбираем каждое число от i до j в качестве опорного и находим максимальную стоимость из его левых и правых сегментов. Если выбрать число из диапазона (i, (i + j) / 2) как опорное, правый сегмент будет длиннее левого, что приведет к большему максимальному затратам из правого сегмента. 2⃣Наша цель - уменьшить большие затраты, приходящиеся на правый сегмент. Поэтому целесообразно выбирать опорное число из диапазона ((i + j) / 2, j). В этом случае затраты на оба сегмента будут ближе друг к другу, что минимизирует общую стоимость. 3⃣Вместо перебора от i до j, итерируем от (i + j) / 2 до j, находя минимально возможные затраты аналогично методу грубой силы. 😎 Решение:
public class Solution {
public int calculate(int low, int high) {
if (low >= high)
return 0;
int minres = Integer.MAX_VALUE;
for (int i = low; i <= high; i++) {
int res = i + Math.max(calculate(i + 1, high), calculate(low, i - 1));
minres = Math.min(res, minres);
}
return minres;
}
public int getMoneyAmount(int n) {
return calculate(1, n);
}
}6 373
#Medium
Задача: 477. Total Hamming Distance
Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются.
Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.
Пример:
Input: nums = [4,14,2] Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). The answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.👨💻 Алгоритм: 1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие. 2⃣Для каждой пары элементов используем XOR, чтобы получить битовую разницу, и подсчитываем количество битов, равных 1, чтобы определить Хэммингово расстояние между парой. 3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний. 😎 Решение:
public class Solution {
public int totalHammingDistance(int[] nums) {
int ans = 0;
if (nums.length == 0) {
return ans;
}
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
ans += Integer.bitCount(nums[i] ^ nums[j]);
}
}
return ans;
}
}6 373
#easy
Задача: 374. Guess Number Higher or Lower
Мы играем в игру "Угадай число". Правила игры следующие:
Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал.
Каждый раз, когда вы угадываете неправильно, я говорю вам, загаданное число больше или меньше вашего предположения.
Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов:
-1: Ваше предположение больше загаданного числа (т.е. num > pick).
1: Ваше предположение меньше загаданного числа (т.е. num < pick).
0: Ваше предположение равно загаданному числу (т.е. num == pick).
Верните загаданное число.
Пример:
Input: n = 10, pick = 6 Output: 6👨💻 Алгоритм: 1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess. 2⃣Если функция guess возвращает -1, это означает, что загаданное число меньше предположенного. Продолжаем бинарный поиск в диапазоне чисел, меньших данного. 3⃣Если функция guess возвращает 1, это означает, что загаданное число больше предположенного. Продолжаем бинарный поиск в диапазоне чисел, больших данного. 😎 Решение:
public class Solution extends GuessGame {
public int guessNumber(int n) {
int low = 1;
int high = n;
while (low <= high) {
int mid = low + (high - low) / 2;
int res = guess(mid);
if (res == 0)
return mid;
else if (res < 0)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
}6 373
#medium
Задача: 374. Guess Number Higher or Lower
Мы играем в игру "Угадай число". Правила игры следующие:
Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал.
Каждый раз, когда вы угадываете неправильно, я говорю вам, загаданное число больше или меньше вашего предположения.
Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов:
-1: Ваше предположение больше загаданного числа (т.е. num > pick).
1: Ваше предположение меньше загаданного числа (т.е. num < pick).
0: Ваше предположение равно загаданному числу (т.е. num == pick).
Верните загаданное число.
Пример:
Input: n = 10, pick = 6 Output: 6👨💻 Алгоритм: 1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess. 2⃣Если функция guess возвращает -1, это означает, что загаданное число меньше предположенного. Продолжаем бинарный поиск в диапазоне чисел, меньших данного. 3⃣Если функция guess возвращает 1, это означает, что загаданное число больше предположенного. Продолжаем бинарный поиск в диапазоне чисел, больших данного. 😎 Решение:
public class Solution extends GuessGame {
public int guessNumber(int n) {
int low = 1;
int high = n;
while (low <= high) {
int mid = low + (high - low) / 2;
int res = guess(mid);
if (res == 0)
return mid;
else if (res < 0)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
}6 373
#medium
Задача: 462. Minimum Moves to Equal Array Elements II
Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными.
В одном ходе вы можете увеличить или уменьшить элемент массива на 1.
Тестовые случаи составлены так, что ответ поместится в 32-битное целое число.
Пример:
Input: nums = [1,2,3] Output: 2 Explanation: Only two moves are needed (remember each move increments or decrements one element): [1,2,3] => [2,2,3] => [2,2,2]👨💻 Алгоритм: 1⃣Найти минимальный и максимальный элементы в массиве. Пусть k будет числом, к которому должны быть приведены все элементы массива. 2⃣Перебирать значения k в диапазоне между минимальным и максимальным элементами, вычисляя количество ходов, необходимых для каждого k. 3⃣Определить минимальное количество ходов среди всех возможных k, что и будет конечным результатом. 😎 Решение:
public class Solution {
public int minMoves2(int[] nums) {
long ans = Long.MAX_VALUE;
int minval = Integer.MAX_VALUE;
int maxval = Integer.MIN_VALUE;
for (int num : nums) {
minval = Math.min(minval, num);
maxval = Math.max(maxval, num);
}
for (int i = minval; i <= maxval; i++) {
long sum = 0;
for (int num : nums) {
sum += Math.abs(num - i);
}
ans = Math.min(ans, sum);
}
return (int) ans;
}
}6 373
#medium
Задача: 333. Largest BST Subtree
Дан корень бинарного дерева, найдите самое большое поддерево, которое также является деревом бинарного поиска (BST), где "самое большое" означает поддерево с наибольшим количеством узлов.
Дерево бинарного поиска (BST) — это дерево, в котором все узлы соблюдают следующие свойства:
Значения в левом поддереве меньше значения их родительского (корневого) узла.
Значения в правом поддереве больше значения их родительского (корневого) узла.
Примечание: Поддерево должно включать всех своих потомков.
Пример:
Input: root = [10,5,15,1,8,null,7] Output: 3 Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.👨💻 Алгоритм: 1⃣Пост-упорядоченный обход дерева: Обходите каждую ноду дерева в пост-упорядоченном порядке (left-right-root). Это позволит гарантировать, что обе поддеревья ноды уже проверены на соответствие критериям BST перед проверкой самой ноды. 2⃣Проверка условий BST для каждой ноды: Для каждой ноды определите минимальное и максимальное значения в её левом и правом поддеревьях. Проверьте, удовлетворяет ли текущее поддерево условиям BST: - значение текущей ноды должно быть больше максимального значения в левом поддереве. - значение текущей ноды должно быть меньше минимального значения в правом поддереве. Если условия выполняются, вычислите размер текущего поддерева как сумму размеров левого и правого поддеревьев плюс 1 (для текущей ноды). 3⃣Возврат максимального размера BST: Если текущее поддерево не является BST, верните максимальный размер BST из его левого или правого поддерева. В конце рекурсивного обхода верните максимальный размер BST в дереве. 😎 Решение:
class NodeValue {
public int maxNode, minNode, maxSize;
NodeValue(int minNode, int maxNode, int maxSize) {
this.maxNode = maxNode;
this.minNode = minNode;
this.maxSize = maxSize;
}
};
class Solution {
public NodeValue largestBSTSubtreeHelper(TreeNode root) {
if (root == null) {
return new NodeValue(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
}
NodeValue left = largestBSTSubtreeHelper(root.left);
NodeValue right = largestBSTSubtreeHelper(root.right);
if (left.maxNode < root.val && root.val < right.minNode) {
return new NodeValue(Math.min(root.val, left.minNode), Math.max(root.val, right.maxNode),
left.maxSize + right.maxSize + 1);
}
return new NodeValue(Integer.MIN_VALUE, Integer.MAX_VALUE,
Math.max(left.maxSize, right.maxSize));
}
public int largestBSTSubtree(TreeNode root) {
return largestBSTSubtreeHelper(root).maxSize;
}
}6 373
#medium
Задача: 373. Find K Pairs with Smallest Sums
Вам даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k.
Определим пару (u, v), которая состоит из одного элемента из первого массива и одного элемента из второго массива.
Верните k пар (u1, v1), (u2, v2), ..., (uk, vk) с наименьшими суммами.
Пример:
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Output: [[1,2],[1,4],[1,6]] Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]👨💻 Алгоритм: 1⃣Создайте две целочисленные переменные m и n, инициализируйте их размерами массивов nums1 и nums2 соответственно. Создайте список ans для хранения пар с наименьшими суммами, которые будут возвращены в качестве ответа. Создайте множество visited для отслеживания просмотренных пар. 2⃣Инициализируйте минимальную кучу minHeap, которая содержит тройки целых чисел: сумму пары, индекс первого элемента пары в nums1 и индекс второго элемента пары в nums2. Вставьте в minHeap первую пару из обоих массивов, т.е. nums1[0] + nums2[0], 0, 0, и добавьте пару (0, 0) в visited. 3⃣Повторяйте до получения k пар и пока minHeap не пуст: Извлеките верхний элемент из minHeap и установите i = top[1] и j = top[2]. Добавьте пару (nums1[i], nums2[j]) в ans. Если i + 1 < m и пары (i + 1, j) нет в visited, добавьте новую пару nums1[i + 1] + nums2[j], i + 1, j в minHeap. Если j + 1 < n и пары (i, j + 1) нет в visited, добавьте новую пару nums1[i] + nums2[j + 1], i, j + 1 в minHeap. Верните ans. 😎 Решение:
import java.util.*;
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
int m = nums1.length, n = nums2.length;
List<List<Integer>> ans = new ArrayList<>();
Set<Pair<Integer, Integer>> visited = new HashSet<>();
PriorityQueue<Triple> minHeap = new PriorityQueue<>(Comparator.comparingInt(t -> t.sum));
minHeap.add(new Triple(nums1[0] + nums2[0], 0, 0));
visited.add(new Pair<>(0, 0));
while (k-- > 0 && !minHeap.isEmpty()) {
Triple top = minHeap.poll();
int i = top.i, j = top.j;
ans.add(Arrays.asList(nums1[i], nums2[j]));
if (i + 1 < m && !visited.contains(new Pair<>(i + 1, j))) {
minHeap.add(new Triple(nums1[i + 1] + nums2[j], i + 1, j));
visited.add(new Pair<>(i + 1, j));
}
if (j + 1 < n && !visited.contains(new Pair<>(i, j + 1))) {
minHeap.add(new Triple(nums1[i] + nums2[j + 1], i, j + 1));
visited.add(new Pair<>(i, j + 1));
}
}
return ans;
}
class Triple {
int sum, i, j;
Triple(int sum, int i, int j) {
this.sum = sum;
this.i = i;
this.j = j;
}
}
}6 373
#hard
Задача: 332. Reconstruct Itinerary
Вам дан список авиабилетов, где tickets[i] = [fromi, toi] представляют собой аэропорты отправления и прибытия одного рейса. Восстановите маршрут в порядке следования и верните его.
Все билеты принадлежат человеку, который вылетает из "JFK", поэтому маршрут должен начинаться с "JFK". Если существует несколько возможных маршрутов, вы должны вернуть маршрут, который имеет наименьший лексикографический порядок при чтении как одна строка.
Например, маршрут ["JFK", "LGA"] имеет меньший лексикографический порядок, чем ["JFK", "LGB"].
Вы можете предположить, что все билеты формируют хотя бы один действительный маршрут. Вы должны использовать все билеты один раз и только один раз.
Пример:
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"]👨💻 Алгоритм: 1⃣Построение графа и сортировка: Создайте граф flightMap, где ключи - это аэропорты отправления, а значения - это списки аэропортов прибытия. Пройдите по всем билетам и заполните flightMap соответствующими значениями. Отсортируйте списки аэропортов прибытия в лексикографическом порядке. 2⃣Пост-упорядоченный обход (DFS): Создайте функцию DFS, которая будет рекурсивно проходить по всем ребрам (рейсам), начиная с аэропорта "JFK". Во время обхода удаляйте использованные рейсы из графа, чтобы не проходить по ним повторно. 3⃣Формирование маршрута: По мере завершения обхода добавляйте текущий аэропорт в начало списка результата. После завершения DFS верните сформированный маршрут. 😎 Решение:
class Solution {
HashMap<String, LinkedList<String>> flightMap = new HashMap<>();
LinkedList<String> result = null;
public List<String> findItinerary(List<List<String>> tickets) {
for(List<String> ticket : tickets) {
String origin = ticket.get(0);
String dest = ticket.get(1);
if (this.flightMap.containsKey(origin)) {
LinkedList<String> destList = this.flightMap.get(origin);
destList.add(dest);
} else {
LinkedList<String> destList = new LinkedList<String>();
destList.add(dest);
this.flightMap.put(origin, destList);
}
}
this.flightMap.forEach((key, value) -> Collections.sort(value));
this.result = new LinkedList<String>();
this.DFS("JFK");
return this.result;
}
protected void DFS(String origin) {
if (this.flightMap.containsKey(origin)) {
LinkedList<String> destList = this.flightMap.get(origin);
while (!destList.isEmpty()) {
String dest = destList.pollFirst();
DFS(dest);
}
}
this.result.offerFirst(origin);
}
}6 373
#medium
Задача: 372. Super Pow
Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.
Пример:
Input: a = 2, b = [3] Output: 8👨💻 Алгоритм: 1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди. 2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337. 3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337. 😎 Решение:
public class Solution {
public int getSum(int a, int b) {
int x = Math.abs(a), y = Math.abs(b);
if (x < y) return getSum(b, a);
int sign = a > 0 ? 1 : -1;
if (a * b >= 0) {
while (y != 0) {
int carry = (x & y) << 1;
x ^= y;
y = carry;
}
} else {
while (y != 0) {
int borrow = ((~x) & y) << 1;
x ^= y;
y = borrow;
}
}
return x * sign;
}
}6 373
#easy
Задача: 461. Hamming Distance
Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны.
Даны два целых числа x и y, верните расстояние Хэмминга между ними.
Пример:
Input: x = 3, y = 1 Output: 1👨💻 Алгоритм: 1⃣Во-первых, стоит упомянуть, что в большинстве (или, по крайней мере, во многих) языков программирования есть встроенные функции для подсчета битов, установленных в 1. Если вам нужно решить такую задачу в реальном проекте, то лучше использовать эти функции, чем изобретать велосипед. 2⃣Однако, поскольку это задача на LeetCode, использование встроенных функций можно сравнить с "реализацией LinkedList с использованием LinkedList". Поэтому рассмотрим также несколько интересных ручных алгоритмов для подсчета битов. 3⃣Пошаговый подсчет битов: Выполните побитовое XOR между x и y. Инициализируйте счетчик bitCount = 0. Пока число не равно нулю: Если текущий бит равен 1, увеличьте bitCount. Сдвиньте число вправо на один бит. Возвращайте bitCount. 😎 Решение:
class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
}6 373
#medium
Задача: 371. Sum of Two Integers
Даны два целых числа a и b. Вернуть сумму этих двух чисел, не используя операторы + и -.
Пример:
Input: a = 1, b = 2 Output: 3👨💻 Алгоритм: 1⃣Упростите задачу до двух случаев: сумма или вычитание двух положительных целых чисел: x ± y, где x > y. Запомните знак результата. 2⃣Если нужно вычислить сумму: Пока перенос не равен нулю (y != 0): Текущий ответ без переноса равен XOR x и y: answer = x ^ y. Текущий перенос равен сдвинутому влево AND x и y: carry = (x & y) << 1. Подготовьтесь к следующему циклу: x = answer, y = carry. Верните x * sign. 3⃣Если нужно вычислить разность: Пока заимствование не равно нулю (y != 0): Текущий ответ без заимствования равен XOR x и y: answer = x ^ y. Текущее заимствование равно сдвинутому влево AND НЕ x и y: borrow = ((~x) & y) << 1. Подготовьтесь к следующему циклу: x = answer, y = borrow. Верните x * sign. 😎 Решение:
public class Solution {
public int getSum(int a, int b) {
int x = Math.abs(a), y = Math.abs(b);
if (x < y) return getSum(b, a);
int sign = a > 0 ? 1 : -1;
if (a * b >= 0) {
while (y != 0) {
int carry = (x & y) << 1;
x ^= y;
y = carry;
}
} else {
while (y != 0) {
int borrow = ((~x) & y) << 1;
x ^= y;
y = borrow;
}
}
return x * sign;
}
}Input: a = 1, b = 2 Output: 3👨💻 Алгоритм: 1⃣Упростите задачу до двух случаев: сумма или вычитание двух положительных целых чисел: x ± y, где x > y. Запомните знак результата. 2⃣Если нужно вычислить сумму: Пока перенос не равен нулю (y != 0): Текущий ответ без переноса равен XOR x и y: answer = x ^ y. Текущий перенос равен сдвинутому влево AND x и y: carry = (x & y) << 1. Подготовьтесь к следующему циклу: x = answer, y = carry. Верните x * sign. 3⃣Если нужно вычислить разность: Пока заимствование не равно нулю (y != 0): Текущий ответ без заимствования равен XOR x и y: answer = x ^ y. Текущее заимствование равно сдвинутому влево AND НЕ x и y: borrow = ((~x) & y) << 1. Подготовьтесь к следующему циклу: x = answer, y = borrow. Верните x * sign. 😎 Решение:
public class Solution {
public int getSum(int a, int b) {
int x = Math.abs(a), y = Math.abs(b);
if (x < y) return getSum(b, a);
int sign = a > 0 ? 1 : -1;
if (a * b >= 0) {
while (y != 0) {
int carry = (x & y) << 1;
x ^= y;
y = carry;
}
} else {
while (y != 0) {
int borrow = ((~x) & y) << 1;
x ^= y;
y = borrow;
}
}
return x * sign;
}
}6 373
#medium
Задача: 370. Range Addition
Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci].
У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci.
Верните arr после применения всех обновлений.
Пример:
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] Output: [-2,0,3,5,3]👨💻 Алгоритм: 1⃣Для каждого обновления (start, end, val) выполните две операции: Увеличьте значение в позиции start на val: arr[start] = arr[start] + val. Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val. 2⃣Примените конечное преобразование: вычислите кумулятивную сумму всего массива (с индексами, начиная с 0). 3⃣Верните обновленный массив arr. 😎 Решение:
public int[] getModifiedArray(int length, int[][] updates) {
int[] result = new int[length];
for (int[] update : updates) {
int start = update[0], end = update[1], val = update[2];
result[start] += val;
if (end + 1 < length) {
result[end + 1] -= val;
}
}
for (int i = 1; i < length; i++) {
result[i] += result[i - 1];
}
return result;
}6 373
#hard
Задача: 460. LFU Cache
Спроектируйте и реализуйте структуру данных для кеша с наименьшим количеством использования (Least Frequently Used, LFU).
Реализуйте класс LFUCache:
LFUCache(int capacity): Инициализирует объект с указанной вместимостью структуры данных.
int get(int key): Возвращает значение ключа, если ключ существует в кеше. В противном случае возвращает -1.
void put(int key, int value): Обновляет значение ключа, если он уже присутствует, или вставляет ключ, если его еще нет. Когда кеш достигает своей вместимости, он должен аннулировать и удалить ключ, используемый наименее часто, перед вставкой нового элемента. В этой задаче, если имеется несколько ключей с одинаковой частотой использования, аннулируется наименее недавно использованный ключ.
Чтобы определить наименее часто используемый ключ, для каждого ключа в кеше поддерживается счетчик использования. Ключ с наименьшим счетчиком использования является наименее часто используемым ключом.
Когда ключ впервые вставляется в кеш, его счетчик использования устанавливается на 1 (из-за операции put). Счетчик использования для ключа в кеше увеличивается при вызове операции get или put для этого ключа.
Функции get и put должны иметь среднюю временную сложность O(1).
Пример:
Input ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, 3, null, -1, 3, 4]👨💻 Алгоритм: 1⃣insert(int key, int frequency, int value): Вставить пару частота-значение в cache с заданным ключом. Получить LinkedHashSet, соответствующий данной частоте (по умолчанию пустой Set), и вставить в него ключ. 2⃣int get(int key): Если ключа нет в кеше, вернуть -1. Получить частоту и значение из кеша. Удалить ключ из LinkedHashSet, связанного с частотой. Если minf == frequency и LinkedHashSet пуст, увеличить minf на 1 и удалить запись частоты из frequencies. Вызвать insert(key, frequency + 1, value). Вернуть значение. 3⃣void put(int key, int value): Если capacity <= 0, выйти. Если ключ существует, обновить значение и вызвать get(key). Если размер кеша равен capacity, удалить первый элемент из LinkedHashSet, связанного с minf, и из кеша. Установить minf в 1. Вызвать insert(key, 1, value). 😎 Решение:
import java.util.*;
class LFUCache {
private Map<Integer, LinkedHashSet<int[]>> frequencies;
private Map<Integer, int[]> cache;
private int capacity;
private int minf;
public LFUCache(int capacity) {
this.capacity = capacity;
this.minf = 0;
this.cache = new HashMap<>();
this.frequencies = new HashMap<>();
}
private void insert(int key, int frequency, int value) {
frequencies.computeIfAbsent(frequency, k -> new LinkedHashSet<>()).add(new int[]{key, value});
cache.put(key, new int[]{frequency, value});
}
public int get(int key) {
if (!cache.containsKey(key)) return -1;
int[] entry = cache.get(key);
int frequency = entry[0];
int value = entry[1];
frequencies.get(frequency).remove(entry);
if (frequencies.get(frequency).isEmpty()) {
frequencies.remove(frequency);
if (minf == frequency) minf++;
}
insert(key, frequency + 1, value);
return value;
}
public void put(int key, int value) {
if (capacity <= 0) return;
if (cache.containsKey(key)) {
cache.get(key)[1] = value;
get(key);
return;
}
if (cache.size() == capacity) {
int[] leastUsed = frequencies.get(minf).iterator().next();
frequencies.get(minf).remove(leastUsed);
if (frequencies.get(minf).isEmpty()) frequencies.remove(minf);
cache.remove(leastUsed[0]);
}
minf = 1;
insert(key, 1, value);
}
}6 373
GitHub теперь в Telegram!
Более 7000+ репозиториев с исходным кодом нейросетей, ботов, сайтов и других интересных проектов для разработчиков:
Всё разбито по #хештегам. Подписывайтесь: @GitHub
6 373
#easy
Задача: 234. Palindrome Linked List
Дан головной элемент односвязного списка. Верните true, если список является палиндромом, и false в противном случае.
Пример:
Input: head = [1,2,2,1] Output: true👨💻 Алгоритм: 1⃣Копирование односвязного списка в массив: Итеративно пройдите по односвязному списку, добавляя каждое значение в массив. Для этого используйте переменную currentNode, указывающую на текущий узел. На каждой итерации добавляйте currentNode.val в массив и обновляйте currentNode, чтобы он указывал на currentNode.next. Остановите цикл, когда currentNode укажет на null. 2⃣Проверка массива на палиндром: Используйте метод с двумя указателями для проверки массива на палиндром. Разместите один указатель в начале массива, а другой в конце. На каждом шаге проверяйте, равны ли значения, на которые указывают указатели, и перемещайте указатели к центру, пока они не встретятся. 3⃣Сравнение значений: Помните, что необходимо сравнивать значения узлов, а не сами узлы. Используйте node_1.val == node_2.val для сравнения значений узлов. Сравнение узлов как объектов node_1 == node_2 не даст ожидаемого результата. 😎 Решение:
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<>();
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
}6 373
#hard
Задача: 233. Number of Digit One
Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n.
Пример:
Input: n = 13 Output: 6👨💻 Алгоритм: 1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n. 2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10). 3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i. 😎 Решение:
public class Solution {
public int countDigitOne(int n) {
int countr = 0;
for (long i = 1; i <= n; i *= 10) {
long divider = i * 10;
countr += (n / divider) * i + Math.min(Math.max(n % divider - i + 1, 0), i);
}
return countr;
}
}6 373
Тестовое собеседование на Middle Java-разработчика завтра
Заходи завтра, 30 октября в 19:00 по мск, на открытое онлайн-собеседование от ШОРТКАТ, чтобы узнать:
— Чего ждут от кандидатов на Middle позиции в Java-разработке
— Какие вопросы задают на интервью и зачем
— Как подготовиться к собесу, чтобы получить оффер
Интервью проведёт Илья Аров — ведущий разработчик программного обеспечения в T1, ВТБ ID
Чтобы записаться на эфир, переходи в бот → @shortcut_sh_bot
Реклама. ООО "ШОРТКАТ", ИНН: 9731139396, erid: 2Vtzquwunwn
6 373
#medium
Задача: 331. Verify Preorder Serialization of a Binary Tree
Один из способов сериализации бинарного дерева — использование обхода в порядке предварительного прохода (preorder traversal). Когда мы встречаем ненулевой узел, мы записываем значение узла. Если это нулевой узел, мы записываем его с использованием специального значения, такого как '#'.
Дана строка, содержащая значения, разделенные запятыми, представляющие предварительный обход дерева (preorder). Верните true, если это правильная сериализация предварительного обхода бинарного дерева.
Гарантируется, что каждое значение в строке, разделенное запятыми, должно быть либо целым числом, либо символом '#', представляющим нулевой указатель.
Вы можете предположить, что формат ввода всегда действителен.
Например, он никогда не может содержать две последовательные запятые, такие как "1,,3".
Примечание: Вам не разрешено восстанавливать дерево.
Пример:
Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#" Output: true👨💻 Алгоритм: 1⃣Инициализация и разбор строки: Инициализируйте переменную slots значением 1, представляющую количество доступных слотов. Разделите строку по запятым, чтобы получить массив элементов. 2⃣Итерация по элементам и проверка: Перебирайте каждый элемент массива. Для каждого элемента уменьшайте количество слотов на 1. Если количество слотов становится отрицательным, верните false, так как это означает неправильную сериализацию. Если элемент не равен '#', увеличьте количество слотов на 2, так как непустой узел создает два новых слота. 3⃣Проверка завершения: После итерации по всем элементам проверьте, равно ли количество слотов 0. Если да, верните true, в противном случае false. 😎 Решение:
class Solution {
public boolean isValidSerialization(String preorder) {
int slots = 1;
for(String node : preorder.split(",")) {
--slots;
if (slots < 0) return false;
if (!node.equals("#")) slots += 2;
}
return slots == 0;
}
}6 373
#easy
Задача: 476. Number Complement
Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении.
Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение.
Пример:
Input: num = 5 Output: 2 Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.👨💻 Алгоритм: 1⃣Вычислите длину в битах входного числа: l=⌊log 2 (num)⌋+1. 2⃣Постройте битовую маску из 1-битов длины l: bitmask=(1≪l)−1. 3⃣Верните результат операции XOR числа и битовой маски: num⊕bitmask num⊕bitmask. 😎 Решение:
class Solution {
public int findComplement(int num) {
int bitmask = num;
bitmask |= (bitmask >> 1);
bitmask |= (bitmask >> 2);
bitmask |= (bitmask >> 4);
bitmask |= (bitmask >> 8);
bitmask |= (bitmask >> 16);
return bitmask ^ num;
}
}6 373
VPN в России — умер. Роскомнадзор инвестирует 60 000 000 000 рублей на новую систему блокировки.
Youtube полностью заблокируют зимой. Google сворачивает ВСЕ свои сервисы. А Windows и Apple ждут удобного момента.Изоляция ждёт всех, кто не заботится о своей свободе и кибербезопасности. Чтобы такого не было с вами — читайте канал IT ВЕДОМСТВО. Это главный техноканал Телеграма, где постят инсайдейрскую информацию, лайфхаки, гайды по обходу блокировок без VPN, фишки для айтишников - все самое полезное там. Подписывайтесь, чтобы не потерять: https://t.me/+wVax9n-CeFRmNzgy
