Java | LeetCode

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

Получи грант на обучение в Центральном университете Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе. Для школьников 10-х и 11-х классов, СПО. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 842. Split Array into Fibonacci Sequence Сложность: medium Вам дана строка цифр num, такая как "123456579". Мы можем разделить её на последовательность, похожую на Фибоначчи [123, 456, 579]. Формально, последовательность, похожая на Фибоначчи, это список f неотрицательных целых чисел, таких что: 0 <= f[i] < 2^31 (то есть каждое число помещается в 32-битный знаковый целый тип), f.length >= 3, и f[i] + f[i + 1] == f[i + 2] для всех 0 <= i < f.length - 2. Обратите внимание, что при разделении строки на части каждая часть не должна иметь лишних ведущих нулей, за исключением случая, если эта часть является числом 0. Верните любую последовательность, похожую на Фибоначчи, из строки num, или верните [] если это невозможно. Пример:

Input: num = "1101111"
Output: [11,0,11,11]
Explanation: The output [110, 1, 111] would also be accepted.

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

class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        int N = S.length();
        for (int i = 0; i < Math.min(10, N); ++i) {
            if (S.charAt(0) == '0' && i > 0) break;
            long a = Long.valueOf(S.substring(0, i+1));
            if (a >= Integer.MAX_VALUE) break;

            search: for (int j = i+1; j < Math.min(i+10, N); ++j) {
                if (S.charAt(i+1) == '0' && j > i+1) break;
                long b = Long.valueOf(S.substring(i+1, j+1));
                if (b >= Integer.MAX_VALUE) break;

                List<Integer> fib = new ArrayList();
                fib.add((int) a);
                fib.add((int) b);

                int k = j + 1;
                while (k < N) {
                    long nxt = fib.get(fib.size() - 2) + fib.get(fib.size() - 1);
                    String nxtS = String.valueOf(nxt);

                    if (nxt <= Integer.MAX_VALUE && S.substring(k).startsWith(nxtS)) {
                        k += nxtS.length();
                        fib.add((int) nxt);
                    }
                    else continue search;
                }
                if (fib.size() >= 3) return fib;
            }
        }

        return new ArrayList<Integer>();
    }
}

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

Онлайн-магистратура «DevOps-инженер облачных сервисов» День открытых дверей 26 марта в 19:00 мск | Онлайн Эксперты Яндекса и ИТМО расскажут об очной онлайн-магистратуре для карьеры в IT. Всё о поступлении и обучении, выступления экспертов, ответы на вопросы. Забронировать #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 1043. Partition Array for Maximum Sum Сложность: medium Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число. Пример:

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84

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

public class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n];
        
        for (int i = 0; i < n; i++) {
            int maxVal = 0;
            for (int j = 1; j <= k; j++) {
                if (i - j + 1 >= 0) {
                    maxVal = Math.max(maxVal, arr[i - j + 1]);
                    if (i - j >= 0) {
                        dp[i] = Math.max(dp[i], dp[i - j] + maxVal * j);
                    } else {
                        dp[i] = Math.max(dp[i], maxVal * j);
                    }
                }
            }
        }
        
        return dp[n - 1];
    }
}

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

Заработайте 3000Р за рекомендацию счёта для бизнеса Участвуйте в реферальной программе СберБизнеса и получите промокод на 3000 ₽ в Купер. Как это работает: ✅ Вы делитесь ссылкой на открытие счёта для бизнеса; ✅ Друг открывает счёт и пользуется им; ✅ Через 2 месяца вы получаете промокод на 3000 ₽ в Купер, а друг – 3000 ₽ на открытый счёт. Присоединяйтесь к реферальной программе СберБизнеса и зарабатывайте. Участвовать можно неограниченное количество раз. Узнать больше Финансовые услуги оказывает: ПАО Сбербанк. #реклама sberbank.com О рекламодателе

Задача: 1502. Can Make Arithmetic Progression From Sequence Сложность: easy Последовательность чисел называется арифметической прогрессией, если разница между любыми двумя последовательными элементами одинаковая. Дан массив чисел arr, верните true, если массив можно переставить так, чтобы он образовал арифметическую прогрессию. В противном случае верните false. Пример:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

👨‍💻 Алгоритм: 1⃣Отсортируйте массив arr. 2⃣Запишите разницу первой пары элементов: diff = arr[1] - arr[0]. 3⃣Итерируйтесь по отсортированному массиву начиная с i = 2, проверяя, равна ли разница каждой пары элементов значению diff. Если нет, верните False. Если итерация завершена без нахождения различий, верните True. 😎 Решение:

class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr);
        int diff = arr[1] - arr[0];
        
        for (int i = 2; i < arr.length; ++i) {
            if (arr[i] - arr[i - 1] != diff) {
                return false;
            }
        }
        
        return true;
    }
}

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

На easyoffer 2.0 появится: База тестовых заданий 🟠Тестовые задания для разных грейдов 🟠Фильтрация тестовых заданий по технологиям и компаниям Когда я только начинал учиться на программиста, я постоянно выдумывал себе задачи для практики и тратил на это много времени. Но только в момент поиска работы я столкнулся с тестовыми заданиями, и понял насколько круто они прокачивают навыки. Нужно было еще на этапе обучения пробовать их делать. Все компании стараются составить тестовое задание "под себя", это дает большой выбор в тематике задач и технологий. На easyoffer 2.0 вы сможете отфильтровать тестовые задания по навыкам/грейдам и найти те, что подходят лично вам для практики. В течение 1-2 дней я объявлю о краудфандинг кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки и смогут попасть на закрытое бета-тестирование. А первые 150 донатеров получать особо-выгодную цену и бонус. 🚀 Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Онлайн-интенсив для ИТ-специалистов в Открытых школах Т1 Открытые школы — это возможность за месяц прокачать свои навыки и получить оффер в ИТ-холдинг Т1. С тебя — год опыта работы в ИТ, с нас — бесплатный онлайн-интенсив и топовые преподаватели. Что ты получишь? ✅ Уникальный рыночный опыт. Наши проекты ежегодно получают награды на ИТ-конкурсах: Global CIO, Национальной банковской премии и др. ✅ Быстрый рост в ИТ при экспертной поддержке. ✅ Материалы от HR, которые помогут прокачать резюме и подготовиться к интервью в Т1. ✅ Поддержка опытных преподавателей и уникальный карьерный фаст-трек до мидла в Т1 для выпускников интенсива. ✅ Реальный шанс получить оффер в Т1. Подавай заявку до 11 апреля и приходи учиться! Старт ИТ-интенсива уже 14 апреля. Подать заявку #реклама 16+ t1.ru О рекламодателе

Задача: 423. Reconstruct Original Digits from English Сложность: medium Дана строка s, содержащая неупорядоченное английское представление цифр от 0 до 9, верните цифры в порядке возрастания. Пример:

Input: s = "owoztneoer"
Output: "012"

👨‍💻 Алгоритм: 1⃣Подсчитайте количество каждого символа в строке s с помощью хэш-таблицы или массива, чтобы определить количество каждого символа. 2⃣Используйте уникальные символы, присутствующие только в одном числе (например, 'z' для 0, 'w' для 2, 'u' для 4, 'x' для 6, 'g' для 8), чтобы определить количество этих цифр в строке. Затем определите количество остальных цифр, вычитая уже найденные цифры. 3⃣Соберите найденные цифры в строку в порядке возрастания и верните результат. 😎 Решение:

class Solution {
    public String originalDigits(String s) {
        int[] count = new char[26 + (int)'a'];
        for(char letter: s.toCharArray()) {
            count[letter]++;
        }

        int[] out = new int[10];
        out[0] = count['z'];
        out[2] = count['w'];
        out[4] = count['u'];
        out[6] = count['x'];
        out[8] = count['g'];
        out[3] = count['h'] - out[8];
        out[5] = count['f'] - out[4];
        out[7] = count['s'] - out[6];
        out[9] = count['i'] - out[5] - out[6] - out[8];
        out[1] = count['n'] - out[7] - 2 * out[9];

        StringBuilder output = new StringBuilder();
        for(int i = 0; i < 10; i++)
            for (int j = 0; j < out[i]; j++)
                output.append(i);
        return output.toString();
    }
}

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

Методичка: как сделать онлайн-встречи эффективнее Надоело ждать коллег, которые постоянно забывают о встречах, а отсутствие повестки и потерянные договоренности мешают нормально работать? Команда МТС Линк собрала на 37 страницах полезные материалы, чек-листы и кейсы, которые помогают компаниям проводить эффективные совещания в онлайне с помощью сервиса Встречи. Из методички узнаете: - Как создать постоянную ссылку и подключаться на встречи в 2 клика, - Как делать заметки и работать с файлами, не переживая за качество связи и безопасность данных. - Как облегчает жизнь ИИ, который расшифровывает созвоны в текст и автоматически отправляет расшифровку на почту. Еще в методичке описаны 7 способов оценки текущей эффективности ваших онлайн-встреч. Получить гайд можно бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 1482. Minimum Number of Days to Make m Bouquets Сложность: medium Вам дан массив целых чисел bloomDay, целое число m и целое число k. Вам нужно сделать m букетов. Для создания букета необходимо использовать k соседних цветов из сада. Сад состоит из n цветов, i-й цветок расцветет на bloomDay[i] и затем может быть использован ровно в одном букете. Верните минимальное количество дней, которое нужно подождать, чтобы можно было сделать m букетов из сада. Если сделать m букетов невозможно, верните -1. Пример:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

👨‍💻 Алгоритм: 1⃣Инициализация: Инициализируйте start как 0 и end как максимальное значение в массиве bloomDay. Введите вспомогательную функцию getNumOfBouquets для подсчета количества букетов, которые можно сделать на определенный день. 2⃣Поиск минимального числа дней: Выполняйте бинарный поиск, пока start меньше или равен end: - рассчитайте mid как среднее значение между start и end. - используйте getNumOfBouquets, чтобы определить, сколько букетов можно сделать на mid день. - если количество букетов больше или равно m, сохраните mid как возможное решение и переместите end влево. - иначе переместите start вправо. 3⃣Возвращение результата: Верните найденное минимальное количество дней или -1, если сделать m букетов невозможно. 😎 Решение:

class Solution {

    private int getNumOfBouquets(int[] bloomDay, int mid, int k) {
        int numOfBouquets = 0;
        int count = 0;

        for (int i = 0; i < bloomDay.length; i++) {
            if (bloomDay[i] <= mid) {
                count++;
            } else {
                count = 0;
            }

            if (count == k) {
                numOfBouquets++;
                count = 0;
            }
        }

        return numOfBouquets;
    }

    public int minDays(int[] bloomDay, int m, int k) {
        int start = 0;
        int end = 0;
        for (int day : bloomDay) {
            end = Math.max(end, day);
        }

        int minDays = -1;
        while (start <= end) {
            int mid = (start + end) / 2;

            if (getNumOfBouquets(bloomDay, mid, k) >= m) {
                minDays = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return minDays;
    }
}

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

Онлайн-магистратура «Управление IT-продуктами» от МФТИ День открытых дверей 2 апреля в 19:00 мск | Онлайн Эксперты Яндекса и МФТИ расскажут об очной онлайн-магистратуре для карьеры в IT. Всё о поступлении и обучении, выступления экспертов, ответы на вопросы. Записаться онлайн #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 916. Word Subsets Сложность: medium Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке. Пример:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

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

import java.util.*;

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        int[] maxCount = new int[26];
        for (String word : words2) {
            int[] count = getCount(word);
            for (int i = 0; i < 26; i++) {
                maxCount[i] = Math.max(maxCount[i], count[i]);
            }
        }

        List<String> result = new ArrayList<>();
        for (String word : words1) {
            int[] count = getCount(word);
            if (isUniversal(count, maxCount)) {
                result.add(word);
            }
        }
        
        return result;
    }

    private int[] getCount(String word) {
        int[] count = new int[26];
        for (char c : word.toCharArray()) {
            count[c - 'a']++;
        }
        return count;
    }

    private boolean isUniversal(int[] count, int[] maxCount) {
        for (int i = 0; i < 26; i++) {
            if (count[i] < maxCount[i]) {
                return false;
            }
        }
        return true;
    }
}

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

Стать бэкендером в Яндексе за несколько дней 12–17 апреля устраиваем Week Offer Backend: за несколько дней можно пройти технические секции и попасть в Яндекс. Для этого нужно зарегистрироваться и решить несколько задач в Контесте. Ищем классных бэкенд-разработчиков с опытом работы от 3 лет на C++, Python, Java/Kotlin или Go, готовых работать в офисном или гибридном режиме в России. Вы сможете выбрать одну из команд: Яндекс Пэй, Яндекс ID, Яндекс Плюс, Яндекс Сплит, Яндекс Сейвы, Яндекс 360. Можно пообщаться с нанимающими менеджерами и выбрать самый интересный проект. Если всё пройдёт хорошо, сразу же получите офер. Зарегистрироваться #реклама yandex.ru О рекламодателе

Задача: 859. Buddy Strings Сложность: easy Даны две строки s и goal. Верните true, если вы можете поменять местами две буквы в s так, чтобы результат был равен goal, в противном случае верните false. Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j]. Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad". Пример:

Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.

👨‍💻 Алгоритм: 1⃣Если количество символов в строках s и goal разное, возвращаем false. Если s == goal, используем хеш-таблицу или массив из 26 элементов для хранения частоты каждого символа в строке s. Если какой-либо символ встречается более одного раза, можно поменять местами две одинаковые буквы, возвращаем true. Иначе возвращаем false. 2⃣Иначе, если s != goal, инициализируем firstIndex и secondIndex значениями -1 для хранения индексов символов в строке s, которые отличаются от символов в строке goal на тех же индексах. Итерируем по каждому индексу i в строке s: если символы s[i] и goal[i] разные, сохраняем текущий индекс. Если firstIndex == -1, обновляем firstIndex = i. Если firstIndex != -1, но secondIndex == -1, обновляем secondIndex = i. Если оба индекса уже обновлены, возвращаем false. 3⃣Если обновлен только firstIndex, возвращаем false. Иначе, все символы обеих строк одинаковы, кроме двух индексов. Поэтому s[firstIndex] должен быть равен goal[secondIndex], и s[secondIndex] должен быть равен goal[firstIndex], чтобы строки стали равны после обмена. 😎 Решение:

class Solution {
    public boolean buddyStrings(String s, String goal) {
        if (s.length() != goal.length()) return false;
        if (s.equals(goal)) {
            int[] freq = new int[26];
            for (char ch : s.toCharArray()) {
                if (++freq[ch - 'a'] > 1) return true;
            }
            return false;
        }

        int firstIndex = -1, secondIndex = -1;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) != goal.charAt(i)) {
                if (firstIndex == -1) firstIndex = i;
                else if (secondIndex == -1) secondIndex = i;
                else return false;
            }
        }

        return secondIndex != -1 &&
               s.charAt(firstIndex) == goal.charAt(secondIndex) &&
               s.charAt(secondIndex) == goal.charAt(firstIndex);
    }
}

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

На easyoffer 2.0 появится: Тренажер "Реальное собеседование" 🟠 Сценарии вопросов из реального собеседования 🟠Возможность подготовиться к собеседованию в конкретную компанию 🟠Итоговая статистика (прошёл/не прошёл) Сценарий вопросов взят из реального собеседования. То есть вы тренируетесь на тех вопросах, которые действительно задавались в компании X. Уже в начале следующей недели стартует краудфандинг кампания, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки. Первые 150 донатеров получать особо-выгодную цену и бонус. Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

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

Задача: 961. N-Repeated Element in Size 2N Array Сложность: easy Вам дан целочисленный массив nums со следующими свойствами: nums.length == 2 * n. nums содержит n + 1 уникальных элементов. Ровно один элемент массива nums повторяется n раз. Верните элемент, который повторяется n раз. Пример:

Input: nums = [1,2,3,3]
Output: 3

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

class Solution {
    public int repeatedNTimes(int[] A) {
        for (int k = 1; k <= 3; ++k)
            for (int i = 0; i < A.length - k; ++i)
                if (A[i] == A[i+k])
                    return A[i];

        throw null;
    }
}

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

⚡️ Айтишник из «VISION» скупил курсы айти школ и выложил гигабайты материалов к себе Каждый найдет что-то по душе: 1202 ГБ — Python 1811 ГБ — Frontend 1100 ГБ — C / C++ / C# 804 ГБ — Java 411 ГБ — SQL & БД 309 ГБ — DevOps 998 ГБ — ИБ & Хакинг 773 ГБ — Kotlin / Swift 189 ГБ — PHP 201 ГБ — GoLang 170 ГБ — Rust 167 ГБ — QA / Тестирование 310 ГБ — 1C + Лицензии 495 ГБ — Машинное обучение 704 ГБ — Аналитика Данных 991 ГБ — Дизайн Материалы в закрепе, постоянно пополняются👆🏻