Java | LeetCode

🚨 60 минут до финала Через час мы закроем краудфандинг easyoffer 2.0 Это последний шанс вписаться в самые выгодные условия. 👉 https://planeta.ru/campaigns/easyoffer

Теперь AI сам создает сайты ИИшка в Битрикс24 берёт на себя весь процесс: структура, дизайн, контент — всё создаётся автоматически. Сделайте один запрос AI-помощнику, и через 30 секунд он создаст свой вариант полностью работающего сайта. Узнать больше #реклама sites-24.bitrix24.ru О рекламодателе

Финальный отсчёт: 3 часа до конца краудфандинга easyoffer 2.0! Это не просто скидка. Это шанс поддержать проект, который поможет и вам и тысячам айтишников готовиться к собеседованиям быстрее, эффективнее и увереннее. За последние недели: 💥 Нас поддержали уже больше 1450 человек; 🔥 Вместе собрали больше 4,5 млн. рублей на запуск проекта; Но сейчас важнее другое. ⏳ Через 3 часа всё закончится. – Больше не будет подписки за 3 200 руб. на целый год! – Не будет шанса первыми воспользоваться EasyOffer 2.0 на бета-тестировании Если вы: + Планируете менять работу в этом или следующем году; + Хотите иметь под рукой 40,000+ вопросов собеседований с разборами, видео-ответами и тренажёрами; + Хотите зафиксировать лучшую цену на целый год… (потом будет в 12 раз дороже) 👉 Тогда просто переходите и поддержите нас сейчас: https://planeta.ru/campaigns/easyoffer 📢 Три часа — и всё. Не откладывайте на потом. Спасибо всем, кто уже с нами! 💙

Задача: №26. Remove Duplicates from Sorted Array Сложность: easy Дан целочисленный массив nums, отсортированный в неубывающем порядке. Удалите дубликаты *на месте*, чтобы каждый уникальный элемент встречался только один раз. Порядок должен сохраняться, и нужно вернуть количество уникальных элементов k. Пример:

Input: nums = [1,1,2] Output: 2 (nums = [1,2,_])

👨‍💻 Алгоритм: 1⃣Если длина массива ≤ 1 — вернуть её как результат, дубликатов нет. 2⃣Используем два указателя: - left — указывает на последний уникальный элемент; - right — проходит по массиву, сравнивая текущий элемент с nums[left]. 3⃣Если найден уникальный элемент — перемещаем его на позицию left + 1, увеличиваем оба указателя. 😎 Решение:

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n <= 1) return n;

        int left = 0;
        int right = 1;

        while (right < n) {
            if (nums[right] != nums[left]) {
                nums[left + 1] = nums[right];
                left++;
            }
            right++;
        }

        return left + 1;
    }
}

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

⏳ Такого больше не будет! Всего пара часов и больше не будет возможности получить: 🚀 PRO подписку к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование 👉 Поддержать: https://planeta.ru/campaigns/easyoffer

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

Задача: 94. Binary Tree Inorder Traversal Сложность: easy Дан корень бинарного дерева. Верните обход значений его узлов в симметричном порядке. Пример:

Input: root = [1,null,2,3]
Output: [1,3,2]

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

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    public void helper(TreeNode root, List<Integer> res) {
        if (root != null) {
            helper(root.left, res);
            res.add(root.val);
            helper(root.right, res);
        }
    }
}

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

⚡️ Linux теперь в Telegram! Ребята сделали крутейший канал про Linux, где на простых картинках и понятном языке обучают работе с этой ОС, делятся полезными фишками и инструментами Подписывайтесь: @linuxos_tg

🚨 Последний шанс! Сегодня — последний день краудфандинга. Через несколько часов всё закроется, и больше невозможно будет поучаствовать. Если ты хотел, но откладывал — СЕЙЧАС самое время. Займёт 2 минуты, но изменит твой подход к собеседованиям надолго. Поддержи easyoffer 2.0 и получи: 🚀 PRO подписка к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование PRO подписка к easyoffer 2.0: ✅ Доступ к списку вопросов, которые задаются на собеседованиях + вероятность встречи этих вопросов + их фильтрация по грейдам, типам интервью, компаниям ✅ Доступ к лучшим ответам на вопросы ✅ Список самых частых задач, которые задаются на собеседовании + их фильтрация по грейдам и компаниям ✅ Доступ к лучшим ответам на задачи ✅ Список тестовых заданий компаний + лучшее решение ✅ Доступ к тренажеру "Проработка вопросов", который позволит очень быстро подготовиться к самым частым вопросам ✅ Доступ к тренажеру "Реальное собеседование", который позволит тренироваться проходить собеседование в конкретную компанию До конца кампании — остались часы. Поддержать: https://planeta.ru/campaigns/easyoffer 📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ

Ищешь высокооплачиваемые проекты? Попробуй SkillStaff SkillStaff — это платформа для ИТ-специалистов, менеджеров и креаторов, которым мало одного оклада. Здесь можно найти клиентов, выполнять их проекты и увеличивать свой доход. - Проекты с гибким графиком: part time, full time, удаленка и гибрид - Ставка за час работы — та, что ты сам выбрал - Клиенты — ведущие бренды, проверенные с юридической точки зрения при регистрации на платформе - Оплата поступает ежемесячно на расчетный счет исполнителя - Удобный личный кабинет и функционал, автоматизирующий документооборот Все, что нужно для работы — иметь статус самозанятого или ИП, а платформа поможет со всеми нюансами. Регистрируйся прямо сейчас Зарегистрироваться #реклама 16+ skillstaff.ru О рекламодателе

Задача: 138. Copy List with Random Pointer Сложность: medium Дан связный список длиной n, в котором каждый узел содержит дополнительный случайный указатель (random pointer), который может указывать на любой узел в списке или быть равным null. Создайте глубокую копию списка. Глубокая копия должна состоять из ровно n совершенно новых узлов, где каждый новый узел имеет значение, равное значению соответствующего оригинального узла. Указатели next и random новых узлов должны указывать на новые узлы в скопированном списке таким образом, чтобы указатели в оригинальном и скопированном списке представляли одно и то же состояние списка. Ни один из указателей в новом списке не должен указывать на узлы в оригинальном списке. Например, если в оригинальном списке есть два узла X и Y, где X.random --> Y, то для соответствующих узлов x и y в скопированном списке, x.random должен указывать на y. Верните голову скопированного связного списка. Связный список представлен во входных/выходных данных как список из n узлов. Каждый узел представлен парой [val, random_index], где: val: целое число, представляющее Node.val random_index: индекс узла (в диапазоне от 0 до n-1), на который указывает случайный указатель, или null, если он не указывает ни на какой узел. Вашему коду будет дана только голова оригинального связного списка. Пример:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

👨‍💻 Алгоритм: 1⃣Инициализация и начало обхода: Начните обход графа со стартового узла (head). Создайте словарь visited_dictionary для отслеживания посещенных и клонированных узлов. 2⃣Проверка и клонирование узлов: Для каждого текущего узла (current_node) проверьте, есть ли уже клонированная копия в visited_dictionary. Если клонированная копия существует, используйте ссылку на этот клонированный узел. Если клонированной копии нет, создайте новый узел (cloned_node_for_current_node), инициализируйте его и добавьте в visited_dictionary, где ключом будет current_node, а значением — созданный клон. 3⃣Рекурсивные вызовы для обработки связей: Сделайте два рекурсивных вызова для каждого узла: один используя указатель random, другой — указатель next. Эти вызовы отражают обработку "детей" текущего узла в терминах графа, где детьми являются узлы, на которые указывают указатели random и next. 😎 Решение:

public class Solution {
    HashMap<Node, Node> visitedHash = new HashMap<Node, Node>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        if (this.visitedHash.containsKey(head)) {
            return this.visitedHash.get(head);
        }

        Node node = new Node(head.val, null, null);
        this.visitedHash.put(head, node);

        node.next = this.copyRandomList(head.next);
        node.random = this.copyRandomList(head.random);

        return node;
    }
}

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

Завтра последний день! Краудфандинг заканчивается уже завтра, и второй попытки не будет. 👉 Поддержи easyoffer 2.0 и получи: 🚀 PRO подписка к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование 📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ

Задача: 147. Insertion Sort List Сложность: medium Дана голова односвязного списка. Отсортируйте список, используя сортировку вставками, и верните голову отсортированного списка. Шаги алгоритма сортировки вставками: 1. Сортировка вставками итеративно работает, потребляя один входной элемент за каждую итерацию и формируя отсортированный выходной список. 2. На каждой итерации сортировка вставками удаляет один элемент из входных данных, находит место, куда он принадлежит в отсортированном списке, и вставляет его туда. 3. Процесс повторяется до тех пор, пока не закончатся входные элементы. Пример:

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

👨‍💻 Алгоритм: 1⃣Создание вспомогательного узла (pseudo_head): В качестве первого шага создайте вспомогательный узел, который называется pseudo_head. Этот узел будет использоваться как указатель на начало результирующего списка. Этот узел облегчает доступ к результирующему списку, особенно когда необходимо вставить новый элемент в начало списка. Этот прием значительно упрощает логику работы с односвязным списком. 2⃣Механизм вставки узла: В односвязном списке каждый узел содержит только один указатель, который указывает на следующий узел. Чтобы вставить новый узел (например, B) перед определенным узлом (например, A), необходимо знать узел (например, C), который находится перед узлом A (т.е. C -> A). Имея ссылку на узел C, можно вставить новый узел так, чтобы получилось C -> B -> A. 3⃣Использование пары указателей для вставки: Используя пару указателей (prev и next), которые служат местом для вставки нового элемента между ними, вставьте новый элемент в список. Это делается путем установки prev -> new_node -> next. Этот метод позволяет точно и безопасно вставлять новые элементы в список, сохраняя при этом правильный порядок элементов без необходимости перемещения других узлов списка. 😎 Решение:

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode();
        ListNode curr = head;

        while (curr != null) {
            ListNode prev = dummy;

            while (prev.next != null && prev.next.val <= curr.val) {
                prev = prev.next;
            }

            ListNode next = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            curr = next;
        }

        return dummy.next;
    }
}

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

Высшее образование онлайн — поменяйте жизнь в 2025 году! ✅Набор в апреле: от 6700 ₽/мес.* Московский технологический институт предлагает: — Высшее образование в московском вузе без выезда на сессии — Полностью дистанционный онлайн-формат — Возможность обучаться дома, на работе, в путешествии — Диплом государственного образца — Более 60 направлений на выбор (IT, инженерные, экономические, педагогические, управленческие и другие) — 5 способов оплаты обучения — Поддержка персонального куратора: от поступления до получения диплома Узнать больше #реклама 16+ mti-vuz.ru О рекламодателе

Задача: 1129. Shortest Path with Alternating Colors Сложность: medium Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра. Вам даны два массива redEdges и blueEdges, где: redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj. Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует. Пример:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

👨‍💻 Алгоритм: 1⃣Создание структуры данных и инициализация: Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла. Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла. Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета. 2⃣Инициализация очереди и начальных условий: Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра). Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно. 3⃣Обработка очереди и обновление результата: Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра). Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь. 😎 Решение:

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        Map<Integer, List<List<Integer>>> adj = new HashMap<>();
        for (int[] redEdge : redEdges) {
            adj.computeIfAbsent(redEdge[0], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(redEdge[1], 0));
        }

        for (int[] blueEdge : blueEdges) {
            adj.computeIfAbsent(blueEdge[0], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(blueEdge[1], 1));
        }

        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        boolean[][] visit = new boolean[n][2];
        Queue<int[]> q = new LinkedList<>();

        q.offer(new int[] { 0, 0, -1 });
        answer[0] = 0;
        visit[0][1] = visit[0][0] = true;

        while (!q.isEmpty()) {
            int[] element = q.poll();
            int node = element[0], steps = element[1], prevColor = element[2];

            if (!adj.containsKey(node)) {
                continue;
            }

            for (List<Integer> nei : adj.get(node)) {
                int neighbor = nei.get(0);
                int color = nei.get(1);
                if (!visit[neighbor][color] && color != prevColor) {
                    if (answer[neighbor] == -1)
                        answer[neighbor] = 1 + steps;
                    visit[neighbor][color] = true;
                    q.offer(new int[] { neighbor, 1 + steps, color });
                }
            }
        }
        return answer;
    }
}

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

⏳ Осталось 3 дня! Финальный отсчёт пошёл — осталось всего 3 дня до окончания краудфандинга easyoffer 2.0 Сейчас можно получить максимум пользы за минимальные деньги. После окончания кампании цены вырастут и вознаграждения станут недоступны. 👉 Поддержи easyoffer 2.0 и получи: 🚀 PRO подписка к easyoffer 2.0 на 1 год по цене месячной подписки. Активировать подписку можно в любой момент, например, когда начнешь искать работу. ➕ Приглашение на закрытое бета-тестирование Поддержи проект сейчас, чтобы не забыть! 📌 Если не получается оплатить через карту РФ — напишите мне @kivaiko, и мы найдём удобный способ

Освойте профессию Системный аналитик с нуля за 7 месяцев Освойте высокооплачиваемую IT-профессию без программирования. Выдаём диплом, помогаем с трудоустройством. Excel, BPMN, UML, Python, SQL, API Преимущества обучения в Академии Eduson: 🎓 22 реальных бизнес-кейса 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать доход уже во время обучения! Получить скидку #реклама 16+ mrqz.me О рекламодателе

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

Input: s = "the sky is blue"
Output: "blue is sky the"

👨‍💻 Алгоритм: 1⃣Удаление лишних пробелов: Удалите начальные и конечные пробелы из строки s. Это делается для того, чтобы убрать пробелы в начале и в конце строки, которые могут исказить конечный результат. В коде это реализовано с помощью методов erase и find_first_not_of/find_last_not_of, которые удаляют пробелы до первого и после последнего непробельного символа. 2⃣Разделение строки на слова: Преобразуйте строку s в поток и используйте istringstream для чтения слов, разделенных пробелами. Каждое слово определяется как последовательность символов, не содержащая пробелов. Слова сохраняются в вектор words. Это делается с помощью copy, который копирует слова из потока в words с помощью istream_iterator. 3⃣Реверсирование и соединение слов: Переверните вектор слов и соедините их обратно в одну строку, разделяя слова одним пробелом. Для реверсирования используется функция reverse, а для соединения слов — ostringstream вместе с ostream_iterator. Слова объединяются таким образом, что между ними находится только один пробел, исключая лишние пробелы между словами. 😎 Решение:

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }
}

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

Профессия «Аналитик данных» - начни учиться бесплатно! Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python. Преимущества обучения в Академии Eduson: 🎓 можно начать учиться бесплатно, если не понравится — не платите 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Узнать больше #реклама 16+ eduson.academy О рекламодателе

Задача: 1074. Number of Submatrices That Sum to Target Сложность: hard Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению. Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2. Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'. Пример:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

👨‍💻 Алгоритм: 1⃣Инициализируйте результат: count = 0. Вычислите количество строк: r = len(matrix) и количество столбцов: c = len(matrix[0]). Вычислите двумерную префиксную сумму ps, выделив еще одну строку и еще один столбец для нулевых значений. 2⃣Итерируйте по строкам: r1 от 1 до r и r2 от r1 до r. Внутри этого двойного цикла фиксируйте левые и правые границы строк и инициализируйте хэш-таблицу для хранения префиксных сумм. Итерируйте по столбцам от 1 до c + 1, вычислите текущую префиксную сумму 1D curr_sum и увеличьте count на количество матриц, сумма которых равна target. 3⃣Добавьте текущую префиксную сумму 1D в хэш-таблицу. Когда все итерации завершены, верните count. 😎 Решение:

class Solution {
  public int numSubmatrixSumTarget(int[][] matrix, int target) {
    int r = matrix.length, c = matrix[0].length;

    int[][] ps = new int[r + 1][c + 1];
    for (int i = 1; i < r + 1; ++i) {
      for (int j = 1; j < c + 1; ++j) {
        ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + matrix[i - 1][j - 1];
      }
    }

    int count = 0, currSum;
    Map<Integer, Integer> h = new HashMap();
    for (int r1 = 1; r1 < r + 1; ++r1) {
      for (int r2 = r1; r2 < r + 1; ++r2) {
        h.clear();
        h.put(0, 1);
        for (int col = 1; col < c + 1; ++col) {
          currSum = ps[r2][col] - ps[r1 - 1][col];
          count += h.getOrDefault(currSum - target, 0);
          h.put(currSum, h.getOrDefault(currSum, 0) + 1);
        }
      }
    }

    return count;
  }
}

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