Java | LeetCode

Задача: 214. Shortest Palindrome Сложность: hard Дана строка s. Вы можете преобразовать s в палиндром, добавив символы в начало строки. Верните самый короткий палиндром, который можно получить, выполняя это преобразование. Пример:

    
        Input: s = "aacecaaa"
Output: "aaacecaaa"{}
    

👨‍💻 Алгоритм: 1⃣Создание обратной строки: Создайте обратную строку rev от исходной строки s, чтобы использовать её для сравнения. 2⃣Итерация для поиска наибольшего палиндрома: Перебирайте индекс i от 0 до size(s) - 1. Для каждой итерации проверяйте, равна ли подстрока s от начала до n - i подстроке rev от i до конца строки. Если условие выполняется, это означает, что подстрока s от начала до n - i является палиндромом, так как rev является обратной строкой s. 3⃣Возврат результата: Как только найден наибольший палиндром, возвращайте строку, состоящую из обратной подстроки rev от начала до i + исходная строка s. 😎 Решение:

    
        class Solution {
    public String shortestPalindrome(String s) {
        int n = s.length();
        String rev = new StringBuilder(s).reverse().toString();
        for (int i = 0; i < n; i++) {
            if (s.substring(0, n - i).equals(rev.substring(i))) return (
                rev.substring(0, i) + s
            );
        }
        return "";
    }
}{}
    

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

Задача: 995. Minimum Number of K Consecutive Bit Flips Сложность: hard Дан бинарный массив nums и целое число k. Операция переворота k-бит заключается в выборе подмассива длиной k из nums и одновременном изменении каждого 0 в подмассиве на 1 и каждого 1 в подмассиве на 0. Верните минимальное количество k-битных переворотов, необходимых для того, чтобы в массиве не осталось 0. Если это невозможно, верните -1. Подмассив - это непрерывная часть массива. Пример:

    
        Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].{}
    

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

    
        public class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        int flip = 0;
        int flips = 0;
        int[] flipQueue = new int[n];
        
        for (int i = 0; i < n; i++) {
            if (i >= k) {
                flip ^= flipQueue[i - k];
            }
            if (nums[i] == flip) {
                if (i + k > n) return -1;
                flips++;
                flip ^= 1;
                flipQueue[i] = 1;
            }
        }
        return flips;
    }
}{}
    

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

Как frontend-разработчику получить оффер в Big Tech? Платят как джуну, а спрашивают как с лида 🙄 Зарплата не растёт, задачи скучные. Пробуешь откликаться, но на резюме клюют только ноунейм компании, а на собесах валят на алгоритмах? При этом вокруг кто-то постоянно получает офферы в Яндекс или VK... Стабильность с маленькой зп, или дестрой рынка и выход на максимальную? Синяя или красная таблетка, Нео?! 👾

Меня зовут Тихон, привет! Я — действующий Frontend-разработчик и ментор.

Помогаю устроиться на хорошие позиции в Big Tech и сопровождаю на испытательном сроке. В своем канале: 👉Разбираю самые популярные и каверзные вопросы на собесах 👉Рассказываю как пройти фильтр HR 👉Борюсь с убеждениями, которые мешают развиваться 👉Делюсь лайфхаками, например как аккуратно “пинговать” рекрутеров Регулярно публикую полезные материалы: ▪️60 вопросов, которые точно помогут тебе на собеседовании. ▪️Подборка из 100+ каналов с вакансиями для разработчиков ▪️10 задротских вопросов про JavaScript, после которых ты усомнишься, что вообще знаешь JS. Часть 1 ▪️Чек лист проверки своего резюме Подписывайся, нас уже 4500 🤓: ссылка Реклама, erid 2W5zFJsgVhi: ИП Галактионов Тихон Витальевич, ИНН 771618975809

Задача: 186. Reverse Words in a String II Сложность: medium Дан массив символов s, переверните порядок слов. Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены одним пробелом. Ваш код должен решать задачу на месте, то есть без выделения дополнительного пространства. Пример:

    
        Input: s = ["a"]
Output: ["a"]{}
    

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

    
        class Solution {
    public void reverse(char[] s, int left, int right) {
        while (left < right) {
            char tmp = s[left];
            s[left++] = s[right];
            s[right--] = tmp;
        }
    }

    public void reverseEachWord(char[] s) {
        int n = s.length;
        int start = 0, end = 0;

        while (start < n) {
            while (end < n && s[end] != ' ') ++end;
            reverse(s, start, end - 1);            start = end + 1;
            ++end;
        }
    }

    public void reverseWords(char[] s) {
        reverse(s, 0, s.length - 1);
        reverseEachWord(s);
    }
}{}
    

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

Cтажировки и вакансии для JAVA разработчиков. - Вакансии которых нет на джоб-агрегаторах - Только прямые контакты HR в Telegram 👉 @jobs_java 🤖 ML & DS 👩‍💻 DevOps 👨‍✈️ ИБ & OSINT 👣 Go 👩‍💻 Mobile 👩‍💻 C# 👩‍💻 Node.js 👩‍💻 Python 🔎 QA 👩‍💻 Java 👩‍💻 UX/UI 👩‍💻 Frontend 🖼️ PHP 📋 Analyst 💼 1C 🖥 SQL 👩‍💻 IT HR Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.

Задача: 1051. Height Checker Сложность: easy Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i]. Пример:

    
        Input: heights = [1,1,4,2,1,3]
Output: 3{}
    

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

    
        import java.util.Arrays;

public class Solution {
    public int heightChecker(int[] heights) {
        int[] expected = heights.clone();
        Arrays.sort(expected);
        int count = 0;
        for (int i = 0; i < heights.length; i++) {
            if (heights[i] != expected[i]) {
                count += 1;
            }
        }
        return count;
    }
}{}
    

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

Java.hasChosen(you) 🥶😟 Почему Java всё ещё №1 в автотестах? Стас Васенков, основатель школы автотестировщиков @qa_guru, расскажет про свой мэтч с Java. Чем его зацепил этот язык и куда привёл. И куда Java может привести вас. Приходите на открытый эфир ➡ 27 января ➡ 13:00 (МСК) Что будет: — неочевидные карьерные сценарии — внутрянка: какой стек ждут, когда ищут автоматизатора — кому Java уже не поможет 🐹 Не откладываем в TODO ➡ webinar.join();

Задача: 920. Number of Music Playlists Сложность: hard В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Пример:

    
        Input: n = 3, goal = 3, k = 1
Output: 6{}
    

👨‍💻 Алгоритм: 1⃣Создать двумерный массив dp, где dp[i][j] представляет количество возможных плейлистов длины i, содержащих j различных песен. 2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями. Заполнить массив dp, используя два случая: Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1) Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0) 3⃣Ответ находится в dp[goal][n]. 😎 Решение:

    
        class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        final int MOD = 1_000_000_007;
        long[][] dp = new long[goal + 1][n + 1];
        dp[0][0] = 1;

        for (int i = 1; i <= goal; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD;
                if (j > k) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j] * (j - k) % MOD) % MOD;
                }
            }
        }

        return (int) dp[goal][n];
    }
}{}
    

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

Задача: 664. Strange Printer Сложность: hard Существует странный принтер с двумя особыми свойствами: Принтер может печатать последовательность одного и того же символа за раз. На каждом шагу принтер может печатать новые символы, начиная и заканчивая в любом месте, при этом покрывая уже существующие символы. Дана строка s. Верните минимальное количество ходов, необходимых для её печати. Пример:

    
        Input: s = "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".{}
    

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

    
        public class Solution {
    public int strangePrinter(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        
        for (int length = 1; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = (i == j) ? 1 : dp[i][j - 1] + 1;
                for (int k = i; k < j; k++) {
                    if (s.charAt(k) == s.charAt(j)) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + (k + 1 <= j - 1 ? dp[k + 1][j - 1] : 0));
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
}{}
    

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

Задача: 189. Rotate Array Сложность: medium Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число. Пример:

    
        Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]{}
    

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

    
        class Solution {
    public void rotate(int[] nums, int k) {
        int[] a = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            a[(i + k) % nums.length] = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = a[i];
        }
    }
}{}
    

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