🟢Easy
203. Remove Linked List Elements

Company: 🔍📱📱

📝Дан cвязный список и целое число val, удалите из списка все узлы, имеющие значение равное val

💡: добавьте вспомогательный узел перед началом списка

#leetcode203 | #easy #linkedlist

🟢Easy
160. Intersection of Two Linked Lists

Company: 🚖📱🏢

📝Даны два связных списка A и B, вернуть узел, в котором они пересекаются. Если такого узла нет, вернуть null

Попробуйте написать решение, используя O(1) памяти

💡: попробуйте выровнять A и B по длине переходом указателя на противоположный список

#leetcode160 | #easy #linkedlist

➡️ Стартуем тему бинарного поиска

Представь, что кто-то загадал число от 1 до 100, и ты пытаешься его угадать, задавая вопросы: "твоё число больше этого?" или "меньше?".

Самый быстрый способ это сделать — каждый раз отбрасывать половину возможных вариантов. Для этого нужно начать с середины диапазона — с числа 50.

Спрашиваешь: "Твоё число больше 50?":
▫Если да — значит, всё, что меньше или равно 50, можно забыть. Теперь ты ищешь только в диапазоне от 51 до 100.
▫Если нет — значит, загаданное число находится где-то между 1 и 49.

Теперь снова берёшь середину нового диапазона — например, 75, и повторяешь. С каждым вопросом ты уменьшаешь количество возможных вариантов в два раза и быстро приближаешься к загаданному числу.

Это и есть бинарный поиск — на каждом шаге ты делишь оставшийся диапазон пополам и выбираешь нужную половину в зависимости от условия. Важно помнить, что такой подход работает только с отсортированными данными, без этого алгоритм не сможет правильно сузить область поиска.

Пример кода бинарного поиска заданного числа target в массиве (задача):

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return -1;
    }
}

📎Обратите внимание, что для вычисления mid используется l + (r - l) / 2, вместо привычного (l + r) / 2. Это нужно для того, чтобы избежать переполнения int при больших значениях l и r.

#binarysearch

🟢Easy
35. Search Insert Position

Company: 📱🏢🚖

📝Дан отсортированный массив различных целых чисел и значение target. Верните индекс вставки target в массив.

Вам необходимо написать алгоритм со сложностью O(logn) по времени

💡: определите какой указатель бинарного поиска будет указывать на нужную позицию после цикла

#leetcode35 | #easy #binarysearch

🟢Easy
69. Sqrt(x)

Company: 📱📱📱

📝Дано неотрицательное целое число x, вернуть квадратный корень x, округленного вниз до ближайшего целого числа.

Не допускается использование встроенных функций

💡: ищите ответ в диапазоне от 2 до x / 2

#leetcode69 | #easy #binarysearch

🟢Easy
1539. Kth Missing Positive Number

Company: 🏢📱📱

📝Дан отсортированный массив arr натуральных чисел и целое число k.

Верните k-ое пропущенное число в этом массиве

💡: сравните исходный массив с массивом без отсутствующих чисел, чтобы понять, как передвигать указатели

#leetcode1539 | #easy #binarysearch

🟢Easy
101. Symmetric Tree

Company: 📕🔍📱

📝Дано двоичное дерево.

Верните true, если оно является зеркальным отражением самого себя, то есть симметричным относительно своего центра

💡: рекурсивно проверяйте каждый узел, сравнивая поддеревья с противоположных сторон

#leetcode101 | #easy #binarytree

🟢Easy
404. Sum of Left Leaves

Company: 🚔📱❤️

📝Дано двоичного дерево, вернуть сумму всех левых листьев.

Лист — это узел без потомков. Левый лист — это лист, который является левым потомком другого узла

💡: в рекурсивную функцию добавьте "флаг" левого узла

#leetcode404 | #easy #binarytree

🟢Easy
270. Closest Binary Search Tree Value

Company: 🏢📱📱

📝Дано двоичное дерево поиска (BST) и значение target.

Верните значение в BST, которое ближе всего к target. Если есть несколько ответов, верните наименьший

💡: пользуясь свойством BST, найдите для target ближайшие границы сверху и снизу

#leetcode270 | #easy #binarytree

🟢Easy
1046. Last Stone Weight

Company: 🏢📱🚔

📝Вам дан массив целых чисел stones, где stones[i] — вес камня.

На каждом ходу мы выбираем два самых тяжелых камня (x и y, x <= y) и разбиваем их друг о друга:

➖если x == y, то оба камня разрушены
➖если x != y, то камень веса x разрушается, а камень веса y имеет новый вес y - x
➖в конце игры остается максимум один камень

Верните вес последнего оставшегося камня. Если камней не осталось, верните 0

💡: настройте приоритет очереди и смоделируйте процесс игры

#leetcode1046 | #easy #priorityqueue

🟢Easy
703. Kth Largest Element in a Stream

Company: 🏢📱📕

📝Реализуйте класс KthLargest, который поддерживает поток ввода чисел и непрерывно возвращает k-ый наибольший элемент после загрузки нового числа

💡: поддерживайте очередь размером k

#leetcode703 | #easy #priorityqueue

🟢Easy
3318. Find X-Sum of All K-Long Subarrays I

Company: 🔍

📝Дан целочисленный массив nums и два целых числа k и x. Верните массив answer длины n - k + 1, где answer[i] — X-сумма подмассива nums[i..i + k - 1].

X-сумма вычисляется следующим образом:
➖посчитайте частоту всех элементов в подмассиве
➖вычислите сумму только x самых частых элементов. Если два элемента имеют одинаковую частоту, элемент с большим значением считается более частым

При этом, если подмассив содержит менее x различных элементов, его X-сумма равна сумме подмассива

💡: настройте компаратор очереди на сравнение частот элементов из HashMap

#leetcode3318 | #easy #priorityqueue

🟢Easy
1971. Find if Path Exists in Graph

Company: 🔍📱📱

📝Дан граф с n вершинами, где каждая вершина помечена от 0 до n-1.

Ребра графа представлены двумерным массивом целых чисел edges, где edges[i] обозначает двунаправленное ребро между вершинами. Каждая пара вершин соединена не более чем одним ребром, и ни одна вершина не имеет ребра, ведущего в себя.

Верните true, если существует допустимый путь от вершины source к вершине destination

💡: используйте Map для удобного представления графа

#leetcode1971 | #easy #graphs

🟢Easy
1791. Find Center of Star Graph

Company: 🔍📱📕

📝Дан неориентированный звёздчатый граф, состоящий из n узлов, помеченных от 1 до n. Верните центр заданного звёздного графа.

Граф представлен двумерным массивом целых чисел edges, где edges[i] указывает на ребро между вершинами.

Ограничения:

3 <= n <= 10^5
edges.length == n - 1

💡: используйте главную особенность центра графа

#leetcode1791 | #easy #graphs