Java | LeetCode

Задача: 567. Permutation in String Сложность: medium Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае. Другими словами, верните true, если одна из перестановок s1 является подстрокой s2. Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

👨‍💻 Алгоритм: 1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2. 2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1. 3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false. 😎 Решение:

public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int s1Len = s1.length(), s2Len = s2.length();
        if (s1Len > s2Len) return false;

        int[] s1Count = new int[26];
        int[] s2Count = new int[26];
        
        for (int i = 0; i < s1Len; i++) {
            s1Count[s1.charAt(i) - 'a']++;
            s2Count[s2.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < s2Len - s1Len; i++) {
            if (Arrays.equals(s1Count, s2Count)) return true;
            s2Count[s2.charAt(i) - 'a']--;
            s2Count[s2.charAt(i + s1Len) - 'a']++;
        }
        
        return Arrays.equals(s1Count, s2Count);
    }
}

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

Гайд по эффективным онлайн-встречам для отделов закупок Как специалистам по закупкам и тендерам экономить время на онлайн-совещаниях, сократить время на подготовку ТЗ и ускорить цикл закупок? Гайд МТС Линк — чек-листы, кейсы и подходы для упрощения коммуникации закупщиков с внутренними заказчиками и подрядчиками с помощью онлайн-встреч. ✅ В гайде: - Как создать постоянную ссылку на синки с коллегами или поставщиками и подключаться в 2 клика; - Как ускорить сбор требований без долгих переписок и конфликтов с юр.отделом; - Как обсуждать ТЗ и сразу фиксировать договоренности с помощью ИИ; - Как вести переговоры с подрядчиками и оперативно согласовать ключевые этапы сделки; - Как отслеживать выполнение условий контракта. Бонус внутри: 5 способов не выгореть от бесконечных синков. ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 206. Reverse Linked List Сложность: easy Дан односвязный список, разверните этот список и верните развернутый список. Пример:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

👨‍💻 Алгоритм: 1⃣Инициализируйте две переменные: prev как nullptr и curr как head списка. Эти переменные будут использоваться для отслеживания предыдущего и текущего узлов в процессе разворота списка. 2⃣Пройдитесь по списку с помощью цикла: Сохраните ссылку на следующий узел curr в переменную nextTemp. Измените ссылку next текущего узла curr на prev, чтобы развернуть направление ссылки. Переместите prev на текущий узел curr и переместите curr на следующий узел nextTemp. 3⃣После завершения цикла верните prev как новую голову развернутого списка. 😎 Решение:

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

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

Задача: 1025. Divisor Game Сложность: easy Алиса и Боб играют в игру по очереди, причем Алиса начинает первой. Изначально на доске мелом написано число n. В свой ход каждый игрок делает ход, состоящий из: выбора любого x при 0 < x < n и n % x == 0. Замены числа n на доске на n - x. Также, если игрок не может сделать ход, он проигрывает игру. Возвращается true тогда и только тогда, когда Алиса выигрывает игру, предполагая, что оба игрока играют оптимально. Пример:

Input: n = 2
Output: true

👨‍💻 Алгоритм: 1⃣Определение выигрыша: Заметим, что если число n четное, Алиса всегда выигрывает, потому что она может уменьшить n на 1, и оставить Боба с нечетным числом. Если число n нечетное, Алиса всегда проигрывает, потому что Боб может уменьшить n на 1, и оставить Алису с четным числом. 2⃣Проверка четности числа: Проверяем, четное ли число n. Если n четное, возвращаем true, если нечетное, возвращаем false. 3⃣Возврат результата: Возвращаем результат в зависимости от четности числа n. 😎 Решение:

public class Solution {
    public boolean divisorGame(int n) {
        return n % 2 == 0;
    }
}

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

DBCV: low-code мультиагентная платформа Новинка! Заработай на цифровизации! Визуальный конструктор, ИИ агенты, трехуровневый API, приложения для любых платформ, python для супер-гибкости. Попробовать #реклама 16+ dbcv.ru О рекламодателе

Задача: 1512. Number of Good Pairs Сложность: easy Дан массив целых чисел nums, верните количество хороших пар. Пара (i, j) называется хорошей, если nums[i] == nums[j] и i < j. Пример:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

👨‍💻 Алгоритм: 1⃣Инициализируйте переменную ans значением 0. 2⃣Итерируйте i от 0 до nums.length: Итерируйте j от i + 1 до nums.length: Если nums[i] == nums[j], увеличьте ans на 1. 3⃣Верните ans. 😎 Решение:

class Solution {
    public int numIdenticalPairs(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный курс по искусственному интеллекту! Мы подготовили для тебя 5 занятий по теме «Разработка нейро-сотрудников на GPT». Пройди регистрацию для получения полного бесплатного доступа к курсу. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 470. Implement Rand10() Using Rand7() Сложность: medium Дано API rand7(), которое генерирует случайное целое число в диапазоне [1, 7]. Напишите функцию rand10(), которая генерирует случайное целое число в диапазоне [1, 10]. Вы можете вызывать только API rand7(), и не должны вызывать другие API. Пожалуйста, не используйте встроенные в язык функции для генерации случайных чисел. Каждый тестовый случай будет содержать один внутренний аргумент n, который указывает количество вызовов вашей реализованной функции rand10() во время тестирования. Обратите внимание, что это не аргумент, передаваемый в rand10(). Пример:

Input: n = 1
Output: [2]

👨‍💻 Алгоритм: 1⃣Предустановите 49 возможных результатов в виде таблицы 7×7, получая индекс idx = (row - 1) * 7 + col, где rowи col— два вызова rand7(). 2⃣Повторяем генерацию, пока не обретаем значения в аспекте [1, 40], т.к. 40 включены на 10 без остатка и расширяют диапазон. 3⃣Возвращаем 1 + (idx - 1) % 10, чтобы преобразовать индекс в диапазон [1, 10]. 😎 Решение:

class Solution {
    public int rand10() {
        int row, col, idx;
        do {
            row = rand7();
            col = rand7();
            idx = col + (row - 1) * 7;
        } while (idx > 40);
        return 1 + (idx - 1) % 10;
    }
}

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

Пассивный доход от недвижимости с вложениями от 10 000 ₽ ЗПИФ Сбера позволяет инвестировать в коммерческую недвижимость без крупных вложений. Вход — от 10 000 ₽. Управление осуществляют эксперты. Оформить паи можно онлайн в СберБанк Онлайн. Узнать больше Финансовые услуги оказывает: ПАО Сбербанк. #реклама 16+ sberbank.com О рекламодателе

Задача: 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix Сложность: hard Дана бинарная матрица mat размером m x n. За один шаг вы можете выбрать одну ячейку и перевернуть её и всех её четырех соседей, если они существуют (Перевернуть означает изменить 1 на 0 и 0 на 1). Пара ячеек называется соседями, если они имеют общую границу. Верните минимальное количество шагов, необходимых для преобразования матрицы mat в нулевую матрицу или -1, если это невозможно. Бинарная матрица - это матрица, в которой все ячейки равны 0 или 1. Нулевая матрица - это матрица, в которой все ячейки равны 0. Пример:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

👨‍💻 Алгоритм: 1⃣Переберите все возможные варианты решений для первой строки матрицы. Каждое решение представляется массивом, где каждый элемент равен 0 или 1, указывая, перевернут ли соответствующий элемент в первой строке. Инициализируйте два бинарных массива для каждой строки: lastState[], содержащий значения предыдущей строки, и changed[], представляющий, были ли значения в текущей строке перевернуты при работе с предыдущей строкой. 2⃣Для каждой строки в матрице используйте следующий шаг для вычисления состояния, инициализированного как changed: Для каждой позиции j в диапазоне [0, n - 1] текущей строки измените значение state[j] соответственно, если lastState[j] равно 1. Переверните state[j], state[j - 1] и state[j + 1], если они существуют. Увеличьте счетчик переворотов на 1. Значения, которые будут перевернуты в следующей строке, точно равны lastState, а решение для следующей строки точно равно массиву state. Поэтому установите changed = lastState и lastState = state, затем переходите к следующей строке. 3⃣После обработки всех строк проверьте, содержит ли lastState все нули, чтобы определить, является ли это допустимым решением. Верните минимальное количество переворотов для всех допустимых решений. 😎 Решение:

class Solution {
    private int better(int x, int y) {
        return x < 0 || (y >= 0 && y < x) ? y : x;
    }

    private int dfs(int[][] mat, List<Integer> operations) {
        if (operations.size() == mat[0].length) {
            int[] changed = new int[mat[0].length];
            int[] lastState = operations.stream().mapToInt(i -> i).toArray();
            int maybe = 0;
            for (int[] row : mat) {
                int[] state = changed.clone();
                for (int j = 0; j < row.length; ++j) {
                    state[j] ^= row[j];
                    if (lastState[j] == 1) {
                        state[j] ^= 1;
                        if (j > 0) {
                            state[j - 1] ^= 1;
                        }
                        if (j + 1 < row.length) {
                            state[j + 1] ^= 1;
                        }
                        ++maybe;
                    }
                }
                changed = lastState;
                lastState = state;
            }
            for (int x : lastState) {
                if (x != 0) {
                    return -1;
                }
            }
            return maybe;
        }
        operations.add(0);
        int maybe1 = dfs(mat, operations);
        operations.set(operations.size() - 1, 1);
        int maybe2 = dfs(mat, operations);
        operations.remove(operations.size() - 1);
        return better(maybe1, maybe2);
    }

    public int minFlips(int[][] mat) {
        List<Integer> operations = new ArrayList<>();
        return dfs(mat, operations);
    }
}

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

🔍 Завтра тестовое собеседование с Java-разработчиком 2 июля(уже завтра!) в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Java-разработчика. Как это будет: 📂 Сергей Чамкин, старший разработчик из Uzum, ex-WildBerries, будет задавать реальные вопросы и задачи разработчику-добровольцу 📂 Cергей будет комментировать каждый ответ респондента, чтобы дать понять чего от вас ожидает собеседующий на интервью 📂 В конце можно будет задать любой вопрос Сергею Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для Java-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы. Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_sh_bot Реклама. ООО "ШОРТКАТ", ИНН: 9731139396, erid: 2VtzqxTSGHm

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

Задача: 1673. Find the Most Competitive Subsequence Сложность: medium Дан целочисленный массив nums и положительное целое число k. Верните наиболее конкурентоспособную подпоследовательность массива nums размера k. Подпоследовательность массива — это результирующая последовательность, полученная путем удаления некоторых (возможно, нуля) элементов из массива. Мы определяем, что подпоследовательность a более конкурентоспособна, чем подпоследовательность b (одинаковой длины), если в первой позиции, где они различаются, подпоследовательность a имеет число меньше, чем соответствующее число в b. Например, [1,3,4] более конкурентоспособна, чем [1,3,5], потому что первая позиция, где они различаются, это последнее число, и 4 меньше, чем 5. Пример:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

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

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        Deque<Integer> queue = new ArrayDeque<Integer>();
        int additionalCount = nums.length - k;
        for (int i = 0; i < nums.length; i++) {
            while (!queue.isEmpty() && queue.peekLast() > nums[i] && additionalCount > 0) {
                queue.pollLast();
                additionalCount--;
            }
            queue.addLast(nums[i]);
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = queue.pollFirst();
        }
        return result;
    }
}

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

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

Задача: 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts Сложность: medium Дан прямоугольный торт размером h x w и два массива целых чисел horizontalCuts и verticalCuts, где: horizontalCuts[i] — это расстояние от верхнего края прямоугольного торта до i-го горизонтального разреза, verticalCuts[j] — это расстояние от левого края прямоугольного торта до j-го вертикального разреза. Верните максимальную площадь кусочка торта после разрезания в каждом горизонтальном и вертикальном положении, указанном в массивах horizontalCuts и verticalCuts. Так как ответ может быть очень большим числом, верните его по модулю 10^9 + 7. Пример:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts.
 After you cut the cake, the green piece of cake has the maximum area.

👨‍💻 Алгоритм: 1⃣Отсортируйте массивы horizontalCuts и verticalCuts в порядке возрастания. Найдите максимальную высоту, учитывая верхний и нижний края торта, и пройдитесь по массиву horizontalCuts, чтобы найти максимальное расстояние между соседними разрезами. 2⃣Найдите максимальную ширину, учитывая левый и правый края торта, и пройдитесь по массиву verticalCuts, чтобы найти максимальное расстояние между соседними разрезами. 3⃣Верните произведение максимальной высоты и максимальной ширины, взятое по модулю 10^9+7. 😎 Решение:

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        int n = horizontalCuts.length;
        int m = verticalCuts.length;
        
        long maxHeight = Math.max(horizontalCuts[0], h - horizontalCuts[n - 1]);
        for (int i = 1; i < n; i++) {
            maxHeight = Math.max(maxHeight, horizontalCuts[i] - horizontalCuts[i - 1]);
        }
        
        long maxWidth = Math.max(verticalCuts[0], w - verticalCuts[m - 1]);
        for (int i = 1; i < m; i++){
            maxWidth = Math.max(maxWidth, verticalCuts[i] - verticalCuts[i - 1]);
        }

        return (int) ((maxWidth * maxHeight) % (1000000007));
    }
}

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

Запчасти к станкам Пневматика, фрезы, двигатели, контроллеры - все для производства и станков Узнать больше #реклама darxton.ru О рекламодателе

Задача: 434. Number of Segments in a String Сложность: easy Дана строка s, верните количество сегментов в строке. Сегмент определяется как непрерывная последовательность символов, отличных от пробелов. Пример:

Input: s = "Hello, my name is John"
Output: 5
Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]

👨‍💻 Алгоритм: 1⃣Инициализируйте счетчик сегментов segment_count равным 0. 2⃣Итеративно пройдитесь по строке s. Для каждого индекса i проверьте, начинается ли на этом индексе сегмент: Если символ s[i] не является пробелом, и (либо это первый символ строки, либо предыдущий символ s[i-1] является пробелом), увеличьте segment_count. 3⃣Верните segment_count. 😎 Решение:

public class Solution {
    public int countSegments(String s) {
        int segmentCount = 0;

        for (int i = 0; i < s.length(); i++) {
            if ((i == 0 || s.charAt(i-1) == ' ') && s.charAt(i) != ' ') {
                segmentCount++;
            }
        }

        return segmentCount;
    }
}

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка для вас и 3-х ваших близких 30 дней бесплатно. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте сейчас❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 1272. Remove Interval Сложность: medium Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше. Пример:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

👨‍💻 Алгоритм: 1⃣Итерируйтесь по каждому интервалу в списке intervals. 2⃣Для каждого интервала, проверяйте пересечения с toBeRemoved и обновляйте список результатов. 3⃣Добавляйте непересекающиеся части текущего интервала в результат. 😎 Решение:

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<int[]> removeInterval(int[][] intervals, int[] toBeRemoved) {
        List<int[]> result = new ArrayList<>();
        for (int[] interval : intervals) {
            if (interval[0] < toBeRemoved[0]) {
                result.add(new int[]{interval[0], Math.min(interval[1], toBeRemoved[0])});
            }
            if (interval[1] > toBeRemoved[1]) {
                result.add(new int[]{Math.max(interval[0], toBeRemoved[1]), interval[1]});
            }
        }
        return result;
    }
}

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

Зарабатывайте на установках Яндекс Браузера Партнёрская программа для сервисных центров, магазинов компьютерной техники, сайтов для скачивания файлов и авторов статей. Вы можете предлагать его своим клиентам и аудитории — и зарабатывать на новых установках. Выплаты до 500₽ за каждую установку Яндекс Браузера. Подать заявку #реклама 0+ partner.browser.yandex.ru О рекламодателе