Java | LeetCode

Задача: 641. Design Circular Deque Сложность: medium Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае. Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

👨‍💻 Алгоритм: 1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди. 2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры. 3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди. 😎 Решение:

public class MyCircularDeque {
    private int[] deque;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public MyCircularDeque(int k) {
        this.capacity = k;
        this.deque = new int[k];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    public boolean insertFront(int value) {
        if (isFull()) return false;
        front = (front - 1 + capacity) % capacity;
        deque[front] = value;
        size++;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) return false;
        deque[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) return false;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return true;
    }

    public int getFront() {
        if (isEmpty()) return -1;
        return deque[front];
    }

    public int getRear() {
        if (isEmpty()) return -1;
        return deque[(rear - 1 + capacity) % capacity];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Скидка на гели Ariel и Tide! Скидка 30% на гели для стирки Ariel и Tide по промокоду STIRKA30 Купить #реклама market.yandex.ru О рекламодателе

Задача: 164. Maximum Gap Сложность: easy Дан массив целых чисел nums. Верните максимальную разницу между двумя последовательными элементами в его отсортированной форме. Если массив содержит менее двух элементов, верните 0. Необходимо написать алгоритм, который работает за линейное время и использует линейное дополнительное пространство. Пример:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

👨‍💻 Алгоритм: 1⃣Инициализация: Определите минимальное и максимальное значения в массиве для расчета возможного максимального интервала (разрыва) между элементами в идеально распределенном массиве. Вычислите размер ведра (bucket size), необходимый для размещения всех элементов массива так, чтобы если массив был равномерно распределен, каждый ведер должен содержать хотя бы один элемент. Размер ведра = (max_value - min_value) / (количество элементов - 1). 2⃣Размещение элементов в ведрах: Создайте ведра для хранения минимальных и максимальных значений каждого ведра. Используйте формулу для распределения каждого элемента в соответствующем ведре на основе его значения. Игнорируйте пустые ведра при расчете максимального интервала. 3⃣Вычисление максимального интервала: Пройдите через ведра и вычислите максимальный интервал, сравнивая минимальное значение текущего непустого ведра с максимальным значением предыдущего непустого ведра. Максимальный интервал будет наибольшей разницей между "минимальными" и "максимальными" значениями последовательных непустых ведер. 😎 Решение:

public class Solution {
    public int maximumGap(int[] nums) {
        if (
            nums == null || nums.length < 2
        ) return 0; 
        Arrays.sort(nums);

        int maxGap = 0;

        for (int i = 0; i < nums.length - 1; i++) maxGap = Math.max(
            nums[i + 1] - nums[i],
            maxGap
        );

        return maxGap;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Нужны 7 желающих для работы с искусственным интеллектом. Работа из дома. График свободный. Пришло задание — изучили — выполнили — получили свои деньги. Деньги вы получаете в зависимости от сложности задания. Например: За задание могут платить 500-10.000 рублей. В зависимости от сложности. 500 рублей — это около 5-30 минут. 10 000 руб. это 5-6 часов. Работа может быть разной: Оживить фото, создать видео, реставрировать старое фото и т.д. 💰 В среднем новичок получает до 150.000 руб в месяц. А опытный может и 300-500т. Мы обучим вас сами: — 3 дня уроков по 30 минут — Домашки с проверкой ⚡ Набор заканчивается завтра. Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ neuromachina.ru О рекламодателе

Задача: 996. Number of Squareful Arrays Сложность: hard Массив является квадратным, если сумма каждой пары соседних элементов является совершенным квадратом. Если задан целочисленный массив nums, верните количество перестановок nums, которые являются квадратными. Две перестановки perm1 и perm2 различны, если существует некоторый индекс i такой, что perm1[i] != perm2[i]. Пример:

Input: nums = [1,17,8]
Output: 2

👨‍💻 Алгоритм: 1⃣Генерация перестановок: Сгенерируйте все возможные перестановки массива nums. Для каждой перестановки проверьте, является ли она квадратной. 2⃣Проверка квадратности: Для каждой перестановки проверьте, является ли сумма каждой пары соседних элементов совершенным квадратом. Для этого используйте функцию для проверки, является ли число совершенным квадратом. 3⃣Подсчет квадратных перестановок: Подсчитайте количество перестановок, которые являются квадратными, и верните это значение. 😎 Решение:

import java.util.*;

public class Solution {
    public int numSquarefulPerms(int[] nums) {
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        Set<List<Integer>> result = new HashSet<>();
        List<Integer> path = new ArrayList<>();
        backtrack(nums, used, path, result);
        return result.size();
    }
    
    private void backtrack(int[] nums, boolean[] used, List<Integer> path, Set<List<Integer>> result) {
        if (path.size() == nums.length) {
            if (isSquareful(path)) {
                result.add(new ArrayList<>(path));
            }
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
            path.add(nums[i]);
            used[i] = true;
            backtrack(nums, used, path, result);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
    
    private boolean isSquareful(List<Integer> perm) {
        for (int i = 0; i < perm.size() - 1; i++) {
            int sum = perm.get(i) + perm.get(i + 1);
            int root = (int) Math.sqrt(sum);
            if (root * root != sum) return false;
        }
        return true;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Spring Framework: проверь уровень знаний и начни учиться Spring курс ждёт тебя - сначала пройди тест и проверь свой уровень знаний! Узнать больше #реклама 16+ otus.ru О рекламодателе

Kafka на практике: продюсеры, консьюмеры, Docker Хотите увидеть, как реально работает Kafka? 3 августа в 20:00 — вебинар с живыми примерами кода. Поднимем кластер в Docker, создадим топики, напишем продюсеров на Python/Java, настроим консьюмеров с consumer groups. Разберем партиционирование, оффсеты и гарантии доставки. Для backend-разработчиков, DevOps и всех, кто любит практику. Узнать больше #реклама 16+ otus.ru О рекламодателе

Задача: 1165. Single-Row Keyboard Сложность: easy Есть специальная клавиатура, на которой все клавиши расположены в один ряд. Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|. Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем. Пример:

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.

👨‍💻 Алгоритм: 1⃣Клавиатура содержит уникальные строчные английские буквы, поэтому мы можем сопоставить её с массивом размера 26. Создадим массив размера 26, назовём его keyIndices. Сохраните индекс каждой буквы в этом массиве, проходя по строке keyboard. Инициализируйте переменную result значением 0, которая будет хранить сумму всех расстояний. Объявите переменную prev, которая будет хранить индекс предыдущей клавиши. Поскольку начальная позиция равна 0, инициализируйте её значением 0. 2⃣Проходите по строке word буква за буквой. Для каждой буквы c добавьте ∣prev−indexOf(c)∣ к result. Обновите prev до индекса c. 3⃣Повторите шаги 6 и 7 для всех букв. В конце прохода result будет содержать итоговое время, необходимое для набора слова. 😎 Решение:

class Solution {
    public int calculateTime(String keyboard, String word) {
        int[] keyIndices = new int[26];
        for (int i = 0; i < keyboard.length(); i++) {
            keyIndices[keyboard.charAt(i) - 'a'] = i;
        }
        
        int prev = 0;
        int result = 0;
        
        for (char c : word.toCharArray()) {
            int index = keyIndices[c - 'a'];
            result += Math.abs(prev - index);
            prev = index;
        }
        
        return result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

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

Получи грант до 1,35 млн руб. на обучение в магистратуре Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! — 4 офлайн программы по востребованным направлениям ИТ — 2 онлайн-программы: машинное обучение и продуктовый менеджмент — 550 грантов до 75% — Вечерние занятия и учеба по выходным — удобно совмещать с работой — Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса — Возможность стажировок и трудоустройства в ведущих компаниях — Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Зарегистрироваться #реклама 16+ cu.ru О рекламодателе

Задача: 339. Nested List Weight Sum Сложность: medium Вам дан вложенный список целых чисел nestedList. Каждый элемент либо целое число, либо список, элементы которого также могут быть целыми числами или другими списками. Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину. Верните сумму каждого целого числа в nestedList, умноженного на его глубину. Пример:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

👨‍💻 Алгоритм: 1⃣ Инициализация и вызов рекурсивной функции: Создайте основную функцию, которая принимает вложенный список и вызывает вспомогательную рекурсивную функцию с начальной глубиной 1. 2⃣ Рекурсивное исследование списка: В вспомогательной функции пройдите по каждому элементу списка. Если элемент является целым числом, добавьте его значение, умноженное на текущую глубину, к общей сумме. Если элемент является списком, вызовите вспомогательную функцию рекурсивно с увеличенной глубиной. 3⃣ Возврат результата: Возвращайте общую сумму на каждом уровне рекурсии. Основная функция возвращает итоговую сумму. 😎 Решение:

class Solution {

    public int depthSum(List<NestedInteger> nestedList) {
        return dfs(nestedList, 1);
    }

    private int dfs(List<NestedInteger> list, int depth) {
        int total = 0;
        for (NestedInteger nested : list) {
            if (nested.isInteger()) {
                total += nested.getInteger() * depth;
            } else {
                total += dfs(nested.getList(), depth + 1);
            }
        }
        return total;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Услуги дата-центра в Москве Размещение и аренда серверного оборудования в дата-центре. 👍 4 современных дата-центра в Москве. 👍 Лицензированный оператор связи. 👍 Индивидуальные конфигурации выделенных серверов под задачи клиента. 👍 Круглосуточная техническая поддержка в Телеграм, без ботов. Узнать цену #реклама 16+ itsoft.ru О рекламодателе

И вы знаете Поэтому просто ещё раз обозначим, что промокод NETSIL скинет 5000 рублей при бронировании жилья на Яндекс Путешествиях. Забронировать #реклама travel.yandex.ru О рекламодателе

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

Задача: 256. Paint House Сложность: medium Есть ряд из n домов, где каждый дом можно покрасить в один из трёх цветов: красный, синий или зелёный. Стоимость покраски каждого дома в определённый цвет разная. Необходимо покрасить все дома так, чтобы никакие два соседних дома не были окрашены в один и тот же цвет. Стоимость покраски каждого дома в определённый цвет представлена в виде матрицы стоимости n x 3. Например, costs[0][0] — это стоимость покраски дома 0 в красный цвет; costs[1][2] — это стоимость покраски дома 1 в зелёный цвет и так далее... Верните минимальную стоимость покраски всех домов. Пример:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

👨‍💻 Алгоритм: 1⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2]. 2⃣Для каждого дома i от 1 до n-1 обновите значения массива dp: dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]) 3⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]). 😎 Решение:

class Solution {
    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n][3];
        dp[0] = costs[0].clone();
        
        for (int i = 1; i < n; i++) {
            dp[i][0] = costs[i][0] + Math.min(dp[i-1][1], dp[i-1][2]);
            dp[i][1] = costs[i][1] + Math.min(dp[i-1][0], dp[i-1][2]);
            dp[i][2] = costs[i][2] + Math.min(dp[i-1][0], dp[i-1][1]);
        }
        
        return Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2]));
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Получи грант до 1,35 млн руб. на обучение в магистратуре Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! — 4 офлайн программы по востребованным направлениям ИТ — 2 онлайн-программы: машинное обучение и продуктовый менеджмент — 550 грантов до 75% — Вечерние занятия и учеба по выходным — удобно совмещать с работой — Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса — Возможность стажировок и трудоустройства в ведущих компаниях — Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Зарегистрироваться #реклама 16+ cu.ru О рекламодателе

Задача: 713. Subarray Product Less Than K Сложность: medium Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k. Пример:

Input: nums = [10,5,2,6], k = 100
Output: 8

👨‍💻 Алгоритм: 1⃣Инициализируйте переменные для отслеживания текущего произведения и количества допустимых подмассивов. Используйте два указателя для границ подмассива. 2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k. 3⃣Подсчитайте количество подмассивов с текущим правым указателем, добавив к общему количеству допустимых подмассивов разницу между правым и левым указателями. 😎 Решение:

public class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int product = 1, count = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
            while (product >= k) {
                product /= nums[left];
                left++;
            }
            count += right - left + 1;
        }
        return count;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

malloc - устройство памяти в системном программировании Поймёте, как устроено динамическое выделение памяти в системных программах Зарегистрироваться #реклама 16+ otus.ru О рекламодателе

Задача: 263. Ugly Number Сложность: easy Уродливое число — это положительное целое число, простые множители которого ограничены числами 2, 3 и 5. Дано целое число n, верните true, если n является уродливым числом. Пример:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

👨‍💻 Алгоритм: 1⃣Если данное целое число n неположительное, верните false, так как неположительное число не может быть уродливым. 2⃣Определите функцию keepDividingWhenDivisible, которая принимает два аргумента: делимое и делитель. Эта функция будет делить делимое на делитель до тех пор, пока оно делится без остатка. Функция возвращает измененное делимое. Последовательно примените эту функцию к n с делителями 2, 3 и 5. 3⃣Если после всех делений n равно 1, верните true, иначе верните false. 😎 Решение:

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        for (int factor : new int[] {2, 3, 5}) {
            n = keepDividingWhenDivisible(n, factor);
        }
        return n == 1;
    }

    private int keepDividingWhenDivisible(int dividend, int divisor) {
        while (dividend % divisor == 0) {
            dividend /= divisor;
        }
        return dividend;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Освой многопоточность в Java: вебинар с от Otus! Хочешь писать быстрый Java код? Приходи на открытый урок: разберём основы многопоточности - узнаешь, как ускорить приложения! Узнать больше #реклама 16+ otus.ru О рекламодателе