crush it easy

Задача Remove Element

Уровень: easy

Итак, задачка следующая: дан массив чисел nums и некоторое число val типа int. Нужно удалить все значения массива, которые равны числу val. А в качестве ответа возвращаем количество элементов, которые не равны val.

Пример:
Исходный массив nums: [1,4,1,8,9], число val: 1
Ответ: 3, массив на выходе [4,8,9,_,_]

Ограничения:
1. Длина массива от 1 до 200
2. Значения элементов массива от 0 до 50
3. Значения val от 0 до 20

Ссылочка на задачу, как всегда

Подход к решению:
Задаем текущий индекс равным 0 (он и есть число элементов, которые не равны значению val) .
Нам нужно последовательно обойти все числа массива, если текущий элемент массива не равен значению val, то на место nums[index] мы запишем текущее значение, а индекс увеличим на единицу. Для примера выше был

Итак, код:

public int removeElement(int[] nums, int val) {
    int index = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != val) {
            nums[index] = nums[i];
            index++;
        }
    }
    return index;
}

1. Инициализация переменной index, которая указывает, куда именно нужно записывать элементы, которые не равны val.
2. Проход по массиву: цикл for, который проходит по каждому элементу массива nums с использованием индекса i. На каждом шаге проверяется, равен ли текущий элемент nums[i] значению val.
3. Проверка каждого элемента: если nums[i] не равен val, это означает, что данный элемент нужно оставить в массиве.
— Присваивание значения: Алгоритм присваивает nums[index] = nums[i], копируя текущее значение nums[i] в позицию index. Этот шаг заменяет значение в позиции index текущим значением, которое не равно val.
—Сдвиг index: Затем увеличиваем index на 1, чтобы указать, где должен располагаться следующий элемент, который не равен val.
Если nums[i] равен val, то алгоритм просто пропускает его, не изменяя index и переходя к следующему элементу.
4. Возврат результата: после завершения цикла значение index указывает на количество элементов, не равных val. Это также количество элементов, которые мы оставили в начале массива.

Временная сложность: O(n), т.к. придется пройтись по всем элементам массива
Пространственная сложность: O(1), т.к. будет выделено ограниченное кол-во памяти под переменные index и i, которые не зависят от размера входного массива.

Нас тут почти 500 человек собралось, круто!

Поэтому хочу узнать, кто ты, мой читатель, чтобы понять какой контент интереснее :)

ниже небольшой опросик

А теперь еще анонс! - Boosty

Сделала себе бусти - https://boosty.to/crushiteasy

Написала там уже одну статью про мавен:)

Основная идея бусти - показывать там больше примеров реальных задач, проблем и повседневной рутины разработчика (то есть меня😄). Ну и релизить туда статьи раньше всего, конечно же.

Ссылка будет в описании профиля на будущее!

Принцип SOLID

Написала большую статью на Хабр про SOLID с примерами из жизни и разработки.

Читать здесь.

👉👉

Принцип KISS - Keep it simple, Stupid!

Немного из истории - принцип пошел из сферы самолетостроения. Кларенс Джонсон (первый, кто использовал выражение) дал своим ребятам набор инструментов и сказал, что с помощью этого набора механик среднего уровня должен уметь отремонтировать реактивный самолет в полевых условиях.

stupid, кстати, в его версии было без запятой, то есть это не значило, что механики глупы)

Итак, KISS - делай проще!

Пример из жизни:
Например, мне нужен срочно бенто-кейк (ситуация реально из жизни😄). Бенто-кейк - это тортик такой, маленький. И вот я могла бы пойти, купить сливочное масло, муку, сахар, какой-нибудь маскарпоне и тд. Потратить Х часов на готовку. И все бы ничего, но времени у меня нет, ресурсы ограничены. По принципу KISS я просто беру и нахожу в запрещенной соц.сети контору, где собственно на потоке делают эти тортики. Кидаю дизайн, который хочу (нашла на пинтерест, например), оплачиваю, в нужный день забираю. Конец.

Пример из разработки:
В голову приходит кейс, когда к нам пришел на спринт разработчик из соседней команды. Он, кстати, очень крутой разработчик! Но была у него штука, он очень любил усложнять местами😄
Вот ревьюю его код, смотрю вместо привычного ArrayList используется очередь. Да не просто очередь, а CircularFifoQueue.
И по коду было что-то вроде:
селектом мы вытащили лист, преобразовали в очередь, потом в сервисе достали очередь, преобразовали в лист😵‍💫

Из плюсов я тогда узнала про существование такого вида очереди😄
Но после ревью, согласились не усложнять, и оставить список☺️

В общем, плюсы от принципа

❗️

KISS - делай проще!

=> Код понятнее
=> Легче on-boarding новых разработчиков
=> Проще поддержка

Принцип DRY - Don`t repeat yourself

Решила написать про три ключевых принципа (SOLID, DRY, KISS), знания которых часто ожидают от разработчика на проектах.

Итак, DRY - "Не повторяйся!".

Пример из жизни:
Представьте, что вы стали вести блог, и каждый пост начинает с рассказа о себе "Меня зовут Х, мне 25 лет, занимаюсь тем-то тем-то, то-то". А потом вам стало 26 лет, и КАЖДЫЙ пост теперь придется исправлять, ведь информация стала неактуальной. А еще ваши читатели каждый раз должны читать одно и то же, зачем-то 🤷‍♂️

Пример из разработки:
На днях как раз делала подобную штуку. У меня проект с микросервисной архитектурой и на уровне каждого сервиса мы получали из секьюрити контекста данные о пользователе. Менялся этот код не часто, но дублирования было, ух. Вынесла все аккуратненько в стартер авторизации, зарегала сервисный слой в spring.factories, и все, теперь и код чище, и изменения по всем сервисам делать не придется в случае чего.

В общем, плюсы от принципа очевидны:

❗️DRY - "Не повторяйся!"
=>уменьшение дублирования
=> улучшение читаемости (все в одном месте)
=> упрощение поддержки и возможность переиспользования

Алгоритм Кадане

Сегодня решала задачу на алгоритм Кадане, главная идея которого - нахождение подмассива с максимальной суммой чисел в массиве.

Вот ссылка на задачу на leetcode.

Уровень, кстати, medium. Но, кажется, все довольно нативно.

Ограничения:
- Значения чисел в массиве: от -10^4 до + 10^5
- Длина массива: от 1 до 10^4

Ну, собственно, условие - найти подмассив с максимальной суммой чисел в массиве.

Идея алгоритма Кадане в том, чтобы поэтапно накапливать сумму элементов и динамически решать, продолжать ли текущий подмассив или начать новый.

Реализация:
1. Заводим две переменные под текущую сумму и под максмальную сумму, инициализируя их первым элементом массива, т.к. это минимально возможный подмассив.
2. Начинаем итерацию по массива со 2-ого элемента:
- Проверяем, продолжать ли текущий подмассив (добавив текущий элемент к currentSum), или начать новый подмассив с текущего элемента
- Если текущая сумма становится отрицательной, алгоритм фактически "сбрасывает" её и начинает новый подмассив с текущего элемента.
- Обновляем максимальную сумму
3. Возвращаем максимальную сумму.

Итак, код:

public int maxSubArray(int[] nums) {
    int currentSum = nums[0];
    int maxSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
        }
    return maxSum;
}

А если не хочется использовать Math.max, то можно через if-ы (только тут currentSum = 0 изначально, иначе сломается)

public int maxSubArray(int[] nums) {
    int currentSum = 0, maxSum = nums[0];
    for (int i = 0; i < nums.length; i++) {
        currentSum += nums[i];
        if (currentSum > maxSum) maxSum = currentSum;
        if (currentSum < 0) currentSum = 0;
    }
    return maxSum;
}

Временная сложность: О(n) - один раз проходимся по массиву
Пространственная сложность: O(1) - только память под константы.

Задача "16. 3Sum Closest"

Решила попробовать добавлять ссылку в заголовок, потестим удобство.

Итак, тут не было постов аж 2 недели, пора возвращаться в ритм.

Сегодня разобрала две medium задачи, в обеих из которых использовался метод двух указателей. Поделюсь той, что поинтереснее🙌

Уровень: medium

Условие следующее: дан массив чисел, размер массива n и целевое значение target. Требуется найти 3 таких числа в массиве, сумма которых ближе всего к целевому значению, и вернуть их сумму.
p.s. каждый входной набор данных имеет только одно решение

Итак, погнали алгоритм:
1. Сортируем массив
2. Берем какое-то базовое значение, чтобы было от чего оттолкнуться, пусть это будет сумма первых трех чисел.
3. Проходимся по каждому числу массива, сужая потенциально возможные суммы за счет метода двух указателей, и сравнивая с целевым значением.

Третий пункт сложноват для восприятия в одном предложении, согласна. Посмотрим на примере:
[-1,2,1,-4, 12, 5, 9, -3] - наш массив, 7 - target (целевое значение)

1. Сортируем [-4, -3, -1, 1, 2, 5, 9, 12]
2. Берем за базу сумму первых трех чисел: (-4) + (-3) + (-1) = -8
3. Заходим в цикл по нашему массиву, начиная с первого значения (-4), т.е. i = 0, присваивая значения указателей left = i + 1; right = nums.length - 1.
Для первого круга: left = 1; right = 7.
- Находим текущую сумму: -4 + (-3) + 12 = 5
- Если она равна целевому значению, ура, возвращаем ее, конец.
Иначе:
- Сравниваем по модулю разницы между таргетом и базовой суммой и между таргетом и текущей суммой. Если первый модуль больше, то заменяем базовую сумму на текущую: 7 - (-8) = 15, 7 - 5 =2. |15| > |2| => базовая сумма = 5.
- Двигаем границы: если базовая сумма меньше таргета => двигаем левый указатель, иначе правый. В нашем случае двигаем левый, теперь left = -1.
- Заново рассчитываем текущую сумму: -4 + (-1) + 12 = 7 - ура, это и был наш таргет, возвращаем.

Теперь код:

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int threeSumClosest = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.length - 2; i++) {
        int left = i + 1; 
        int right = nums.length - 1;

        while (left < right) {
            int currentThreeSum = nums[i] + nums[left] + nums[right];
            if (currentThreeSum == target) {
                return currentThreeSum;
            }
            if (Math.abs(target - currentThreeSum) < Math.abs (target - threeSumClosest)) {
                threeSumClosest = currentThreeSum;
            }
            if (currentThreeSum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return threeSumClosest;
}

Временная сложность: O(n^2), к сожалению лучше нельзя, т.к. нужно рассмотреть комбинации для трех чисел, а поэтому в худшем случае нам придется пройти по всем числам массива внешним циклом, что займет O(n), а внутренним двигать указатели, что также O(n). Ну, еще и сортировка O(n * log n), но общая все равно O(n^2), т.к. она доминирует

Пространственная сложность: O(1), т.к. тут только константы используем под память.

Задача "1351. Count Negative Numbers in a Sorted Matrix"

Уровень: easy

Не так часто сталкиваюсь с матрицами, поэтому захотела записать для себя задачку. Решение у нее элементарное - любимый бинарный поиск👉

Но сначала условие:
Дана матрица чисел размер m x n, отсортированная по убыванию в обоих разрезах: и по столбцам, и по строкам. Нужно подсчитать количество отрицательных чисел в матрице.

Пример матрицы:

5  4  2  1
3  2  1 -1
2 -1 -2 -3
1 -2 -3 -5

Ответ: 7 (количество отрицательных чисел)

Ограничения:
1.m - кол-во строк, n - кол-во столбцов (в коде я назову их rows, cols - так понятнее, на мой взгляд)
2. 1 <= n, m <= 100
3. -100 <= grid[i][j] <= 100

Ссылочка на задачу, как всегда

Итак, погнали алгоритм:
1. Для каждой строки применяем бинарный поиск, чтобы найти индекс первого отрицательного числа (кстати, про бинарный поиск писала статейку на хабре)
UPD:
- если первый элемент строки отрицательный, то все числа на этой строке и на следующих будут отрицательными, поэтому высчитываем кол-во отрицательных здесь и завершаем цикл.
- если последний элемент строки положительный, то можно пропустить всю строку, т.к. элементы слева будут тоже положительными
2. Все числа справа от найденного индекса также будут отрицательными, поэтому сразу добавляем их количество к общему счётчику.

Код:

public int countNegatives(int[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;
    int negatives = 0;

    for (int i = 0; i < rows; i++) {
        if (grid[i][0] < 0) {
            negatives += (rows - i) * cols;
            break;
        }

        if (grid[i][cols - 1] > 0) {
            continue;
        }

        int left = 0;
        int right = cols - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (grid[i][mid] < 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        negatives += cols - left;
    }
    return negatives;
}

Временная сложность: O(m x log n) - т.к. мы будем совершать двоичный поиск в каждой строке (их m штук), и скорость поиска в каждой строке будет O(log n)
Пространственная сложность: O(1) - т.к. выделяется константное кол-во памяти под переменные negatives, left, right, mid, cols, rows

Задача "1512. Number of Good Pairs"

Уровень: easy

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

Итак, легкая задачка: дан массив чисел nums, нужно вернуть кол-во пар равных элементов (nums[i] == nums[j]), где i < j.

Например, массив [5, 9, 2, 5, 2, 2]:
- Индексы равных пар: (0, 3), (2, 4), (2, 5), (4, 5)
- Ответ: 4

Ограничения:
1. Длина массива от 1 до 100
2. Числа в массиве от 1 до 100

Ссылочка на задачу, как всегда.

Существует два решения, которые приходят на ум (конечно, можно сделать больше решений, но остановимся на 2-ух).

Первый вариант: Хэш-таблица

Код:

public int numIdenticalPairs(int[] nums) {
    int goodPairs = 0;
    Map<Integer, Integer> map = new HashMap<>();
    for (int num: nums) {
        if (map.containsKey(num)) {
            goodPairs += map.get(num);
            map.put(num, map.get(num) + 1);
        } else {
            map.put(num, 1);
        }
    }
    return goodPairs;
}

Алгоритм:
1. Заводим хэш-таблицу map и переменную, где будет храниться ответ goodPairs
2. Проходимся по каждому элементу массива и проверяем, есть ли уже такой ключ (с текущим значением массива) в хэш-таблице:
- ключа нет - добавляем, записывая в ключ - значение массива, а в значение единицу (текущее кол-во повторений)
- ключ есть - получаем по ключу значение из хэш-таблицы (кол-во повторений), увеличиваем счетчик goodPairs, перезаписываем в хэш-таблицу значение массива с увеличенным на "1" кол-вом повторений.
3. Возвращаем результат goodPairs

Временная сложность: O(n) -т.к. пройдемся по каждому элементу массива один раз.
Пространственная сложность: O(n) - худший случай, если все элементы массива уникальны и придется выделить память под каждый элемент в хэш-таблице. O(1) - лучший случай, если все элементы равны.

Второй вариант: массив

Однако, в текущих ограничениях - значения от 0 до 100, мы можем выделить фиксированное значение памяти и улучшить пространственную сложность до O(1).

Код:

public int numIdenticalPairs(int[] nums) {
    int goodPairs = 0, 
    elements[] = new int[101];
    for (int num: nums) {
        goodPairs += elements[num]++;
    }
    return goodPairs;
}

1. Выделяем память под результат - goodPairs.
2. Создаем массив elements размером 101 для подсчета количества встреч каждого значения в массиве. Этот массив покрывает диапазон значений от 0 до 100 (подходит под наши ограничения)
3. Идем по каждому элементу массива nums, увеличивая счетчик goodPairs на текущее значение счетчика elements[num].
Это работает, потому что если элемент num уже встречался ранее, значит, он может образовать "хорошие пары" с каждым из предыдущих вхождений этого элемента.
4. Увеличиваем счётчик elements[num] на единицу, чтобы учесть текущее вхождение элемента.
5. Возвращаем результат

Важно: такой подход будет эффективен только на небольших отрезках чисел (как в этой задаче). Если ограничение станет, скажем в пределах значений int или long - массив сожрет много памяти, а это нам не нужно. Тогда будет эффективнее использовать хэш-таблицу.

Задача "Minimum Moves to Equal Array Elements"

Уровень: medium

Решаю задачки на массивы, делюсь интересной.
Условие следующее: дан массив целых чисел размером n, требуется вернуть минимальное количество шагов, необходимых для того, чтобы все элементы массива стали равны. За один шаг можно увеличить 'n - 1' элементов массива на 1.

Например, дан массив:
[3,1,4]
- шаг 1: [3,2,5] - увеличили 1-ый, и 2-ой элементы
- шаг 2: [4,3,5] - увеличили 0-ой, и 1-ый элементы
- шаг 3: [5,4,5] - увеличили 0-ой, и 1-ый элементы
- шаг 4: [6,5,5] - увеличили 0-ой, и 1-ый элементы
- шаг 5: [6,6,6] - увеличили 1-ый, и 2-ой элементы

Минимальное количество шагов, которое потребуется в данном случае, чтобы все элементы массивы стали равны - это 5.

Алгоритм: для того, чтобы решить задачу, нужно посмотреть на нее под другим углом. Увеличивать 'n-1' элементов массива на 1 это равносильно тому, что уменьшать на 1 один элемент массива. Другими словами, задача сводится к тому, чтобы привести все элементы массива к минимальному значению.

Проверим на том же массиве - [3,1,4]:
- шаг 1: [3,1,3] - уменьшаем 2-ой
- шаг 2: [3,1,2] - уменьшаем 2-ой
- шаг 3: [3,1,1] - уменьшаем 2-ой
- шаг 4: [2,1,1] - уменьшаем 0-ой
- шаг 5: [1,1,1] - - уменьшаем 0-ой
Ответ: 5

Значит, нам нужно выполнить следующие шаги в алгоритме:
1. Найти минимальное значение в массиве
2. Найти разницу между каждым элементом и минимальным значением
3. Суммировать все разницы - это и будет минимальное количество шагов, которое требуется для того, чтобы все элементы стали равны.

Итак, код:

public int minMoves(int[] nums) {
   int min = Integer.MAX_VALUE;
   for (int num: nums) {
    min = Math.min(num, min);
   } 
   int moves = 0;
   for (int num: nums) {
    moves += num - min;
   }
   return moves;
}

Временная сложность: O(n) т.к. O(n) - для нахождения минимального элемента в массиве и O(n) - для подсчета общего кол-ва шагов.
Пространственная сложность: O(1), т.к. требуется фиксированное количество памяти для хранения минимального значения массива и для количества шагов.

Задача "Sort Characters By Frequency"

Уровень: medium

Сегодня решала задачку с использованием не самой частой структуры данных - PriorityQueue. Думаю, стоит зафиксировать решение.

На вход получаем строку состоящую из английских букв (могут быть строчные и заглавные) и символов. Нужно вернуть строку эту же строку, но в отсортированном по убыванию порядке, исходя из того, сколько раз тот или иной символ в ней встречается. Если какие-то символы встречаются одинаковое кол-во раз, то вернуть их в любом порядке (оба ответа ок).

Например, на вход пришла строка: "a55dgggGPP"
Количество повторений символов в строке:
a - 1
5 - 2
g - 3
G - 1
P - 2
Ответ: "gggPP55aG" (варианты "ggg55PPaG", "ggg55PPGa", "gggPP55Ga" тоже ок)

Ограничения:
- Длина строки от 1 до 5 х 10^5
- Строка может состоять только из строчных и заглавных букв английского алфавита и символов

Ссылочка на задачу, как всегда.

Алгоритм решения будет следующий:
1. Подсчитаем и сохраним частоту каждого символа в хэш-таблице
2. Закинем все символы в PriorityQueue, используя собственный Comparator (будем сравнивать частоты символов из хэш-таблицы и закидывать по убыванию - наверху кучи самый частый)
3. Извлекаем из кучи символы и записываем в результирущую строку (использую StringBuilder) в том количестве, в котором они хранятся в нашей хэш-таблице
4. Возвращаем результат

Кстати, есть еще решение, когда храним в куче и символы и частоты, так будет меньше get-ов (можно, поэксперементировать🙌)

Итак, код:

public String frequencySort(String s) {
    StringBuilder result = new StringBuilder();
    Map<Character, Integer> frequencyMap = new HashMap<>();

    for (char c : s.toCharArray()) {
        frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
    }

    PriorityQueue<Character> heap = new PriorityQueue<>(
        (a, b) -> frequencyMap.get(b) - frequencyMap.get(a));
    
    heap.addAll(frequencyMap.keySet());

    while (!heap.isEmpty()) {
        char sym = heap.poll();
        int count = frequencyMap.get(sym);
        for (int i = 0; i < count; i++) {
            result.append(sym);
        }
    }
    return result.toString();
}

Временная сложность: O(n log k), т.к. O(n) - добавление в хэш-таблицу (от количества символов в строке), O(k log k) - добавление в очередь, где k - кол-во уникальных символов в строке, извлечение из очереди и добавление в StringBuilder - O(f log k), где f - частота символа, а log k - скорость извлечения. Итого O (n log k) - т.к. повторяем операцию извлечения и присоединения для всех символов в строке. Но в худшем случае скорость будет O (n log n), если k = n, т.е. все символы уникальные.

Пространственная сложность: O(n), т.к. O(k) - хэш-таблица, O(k) - куча (очередь), O (n) - результирующая строка.

Кстати, здесь есть еще подход с решением с использованием массива символов, он чуть выиграет по памяти, но проиграет по скорости на больших строках с большим кол-вом повторений символов:) - хотя leetcode покажет более быстрый runtime.

Задача "Time Needed to Buy Tickets"

Уровень: easy

Еще одна задача на очереди со следующим условием: в очереди стоят люди за билетами. Каждому человеку нужно купить Х билетов. За один подход к кассе человек может купить только 1 билет и встать в конец очереди, если ему нужны еще билеты. Покупка одного билета одним человеком занимает 1 секунду. Нужно посчитать, сколько секунд займет покупка всех билетов человеком, который стоит на k-ой позиции в очереди.

Например, в очереди стоят люди, которым нужно купить [1, 3, 2, 2] билетов соответственно. Нужно посчитать кол-во секунд, которое займет покупка всех билетов у человека, находящегося на 3-ей позиции (1-ый человек находятся на позиции 0).

После первого круга:
[0,2,1,1] - 4 секунды
После второго круга:
[1,0,0] - 3 секунды (наш человек купил билет)
Итого: 7 секунд

Важно: когда показатель стал 0 (т.е. человек больше не нуждается в билетах), он покидает очередь.

Можно решить с использованием очередей (задача же на очереди, хех), но там будет пространственная сложность O(n), так как мы будем хранить в очереди людей из массива (точнее, нужно им кол-во билетов), и пространственная сложность будет O(sum(tickets)) - сумма всех элементов массива, т.к. каждое уменьшение элемента массива требует прохода через очередь.
К тому же код достаточно длинный.

Есть решение элегантнее:)

Итак, алгоритм:
Основная идея — подсчитать, сколько билетов получит каждый человек, пока человек под индексом k не получит все свои билеты. Для этого нужно учитывать два сценария:

1. Если человек находится перед человеком с индексом k, он может получить только столько билетов, сколько у него изначально было, или столько же, сколько у человека под индексом k, если у него больше билетов.
2. Если человек находится после человека с индексом k, он может получить максимум на один билет меньше, чем человек под индексом k.

Итак, код:

public int timeRequiredToBuy(int[] tickets, int k) {
     int seconds = 0;
     for (int i = 0; i < tickets.length; i++) {
         if (i <= k) {
             seconds += Math.min(tickets[i], tickets[k]);
         } else {
            seconds += Math.min(tickets[i], tickets[k] - 1);
        }
    }
    return seconds;
}

Временная сложность - O(n), так как мы проходим по массиву tickets один раз.
Пространственная сложность - O(1), так как требуется постоянное кол-во памяти под переменную seconds.

Спасибо за ваши реакции на посты, приятно!🙌

Задача "Number of Students Unable to Eat Lunch"

Уровень: easy

Начала прорешивать задачи на очереди. Делюсь решением одной из них.

Итак, задача:
В столовой стоят студенты в очереди за сэндвичами. Каждый студент предпочитает либо круглый, либо квадратный сэндвич. Сэндвичи лежат в стопке. Если предпочтения студентов совпадает с верхним сэндвичем, то он забирает сэндвич и уходит, иначе встает в конец очереди. Количество сэндвичей и студентов одинаковое. Нужно вернуть количество студентов, которые останутся без сэндвича (т.е. когда ни один студент в очереди не захочет взять верхний сэндвич).

На вход мы получаем два массива: студенты и сэндвичи. В массивах хранятся значения 0 и 1. 0 - круглый сэндвич, 1 - квадратный.

Ссылка на задачу, как всегда

Ограничения:
- Кол-во студентов и сэндвичей от 1 до 100
- Кол-во студентов = кол-ву сэндвичей
- sandwiches[i] либо 0, либо 1
- studentes[i] либо 0, либо 1

Пройдемся по алгоритму решения:
1. Заводим две очереди для студентов и сэндвичей и заполняем их.
2. Заводим переменную под хранение неудачных попыток (когда предпочтения студента не совпали с верхним сэндвичем)
3. Проходим по очереди, проверяя, соответствует ли предпочтение первого студента верхнему сэндвичу.
- Если да, удаляем обоих.
- Если нет, перемещаем студента в конец очереди.
4. Если количество неудачных попыток равняется размеру очереди, значит, оставшиеся студенты не могут взять сэндвич, и мы заканчиваем.
5. Если очередь из студентов закончилась (пустая), значит они все взяли сэндвичи, и мы тоже заканчиваем.

public int countStudents(int[] students, int[] sandwiches) {
    Queue<Integer> studentQ = new LinkedList();
    Queue<Integer> sandwichQ = new LinkedList();

    int failedAttempts = 0;

    for (int student: students) {
        studentQ.offer(student);
    }

    for (int sandwich: sandwiches) {
        sandwichQ.offer(sandwich);
    }

    while (!studentQ.isEmpty() && failedAttempts < studentQ.size()) {
        if (studentQ.peek() == sandwichQ.peek()) {
            studentQ.poll();
            sandwichQ.poll();
            failedAttempts = 0;
        } else {
            studentQ.offer(studentQ.poll());
            failedAttempts++;
        }
    }
    return studentQ.size();
}

Временная сложность - O(n), т.к. заполнение очередей сэндвичами и студентами займет O(n), перемещение каждого студента в конец очереди выполняется за O(1), а кол-во таких перемещений может составить n раз. Цикл прекращается, когда количество неудачных попыток достигнет количества студентов n. Это гарантирует, что цикл выполняется не более n раз.
Пространственная сложность - O(n), т.к. потребуется память по две очереди, размер которых будет зависеть от размера входных массивов.

Но есть способ решения без очередей:)
И он даст пространственную сложность O(1), так как в нем понадобится только две примитивные интовые переменные для кол-ва студентов, предпочитающих круглые и квадратные сэндвичи.

public int countStudents(int[] students, int[] sandwiches) {
    int countZero = 0; 
    int countOne = 0; 
        
    for (int student : students) {
        if (student == 0) {
            countZero++;
        } else {
            countOne++;
        }
    }

    for (int sandwich : sandwiches) {
        if (sandwich == 0) {
            if (countZero > 0) {
                countZero--; // Студент взял круглый сэндвич
            } else 
                break; 
        } else {
            if (countOne > 0) {
                countOne--; // Студент взял квадратный сэндвич
            } else 
                break; 
        }
    }
    return countZero + countOne;
}

Пояснения:
1. Вычисляем кол-во студентов предпочитающих круглые и квадратные сэндвичи
2. Идем по стопке сэндвичей, если круглый - уменьшаем кол-во студентов, предпочитающих круглый (так как он возьмет и уйдет в какой-то момент), если квадратный - квадратных.
3. Возвращаем суммарное кол-во оставшихся студентов

Бинарные деревья

На днях выкладывала статью на хабр по бинарным деревьям (с которой, видимо, тут собралось много народу). Подумала, не помешает краткий пост на эту же тему с основными поинтами, чтобы спустя время легко можно было освежить в памяти.

Итак, бинарные деревья - иерархические структура данных, в которой каждый узел имеет не более двух дочерних узлов (правый и левый потомки). Каждый потомок - тоже узел со своими потомками, если нет потомков у узла, то он называется листом.

Бинарное дерево поиска - отсортированная структура данных, у которого все значения в узлах левого дочернего поддерева меньше значения родительского узла, а правого - больше.

Для решения алгоритмических задач на бинарные деревья преимущественно используется два способа:
- BFS (обход в ширину)
- DFS (обход в глубину)

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

Для обхода в ширину обычно используется очередь (Queue, а именно LinkedList), но лично я обхожусь списком (ArrayList) - тут можно дискутировать.

Пример задачи на обход в глубину:
Требуется обойти дерево в глубину прямым обходом (NLR) и вернуть последовательность узлов в виде списка.

Ссылка на задачу, как всегда

Рекурсивный способ:

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList();
    helper(root, result);
    return result;
}

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

Итеративный способ (с ArrayList, можете с ArrayDeque - тоже повод для дискуссии):

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
          return result;
    }

    List<TreeNode> stack = new ArrayList<>();
    stack.add(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.remove(stack.size() - 1);
        result.add(node.val);

        // Добавляем правого ребенка в стек первым, чтобы левый обрабатывался первым
        if (node.right != null) {
            stack.add(node.right);
        }
        if (node.left != null) {
            stack.add(node.left);
        }
    }

    return result;
}

Временная сложность: O(n) - в обоих случаях, т.к. обходим каждый узел один раз
Пространственная сложность - O(n) - в обоих случаях, т.к. размер итогового списка (result) будет зависеть от входного дерева.

Итеративный способ лучше использовать, если дерево слишком глубокое (для современных машинок более 1000 узлов можно считать глубоким), чтобы не увидеть StackOverFlow.

Если дерево не глубокое, то использование рекурсии удобнее с точки зрения компактности кода.

Полный текст статьи здесь: https://habr.com/ru/articles/835706/

Неожиданным образом в канале собралось уже больше 100 человек, шок 😮

Задача Remove Duplicates from Sorted Array

Уровень: easy

Итак, задачка следующая: дан отсортированный массив чисел (по возрастанию), в котором нужно удалить дубликаты, и вернуть количество чисел, которые останутся в исходном массиве.

Пример:
Исходный массив: [1,1,2,3,4,4,5,6,6]
Ответ: 6, массив на выходе - [1,2,3,4,5,6,_,_,_] (последние 3 элемента тоже будут заполнены, но этот кусок массива нас уже не интересует)

Ограничения:
1. Длина массива от 1 до 3 * 10^4
2. Значения элементов массива от -100 до 100
3. Массив отсортирован по возрастанию

Ссылочка на задачу, как всегда

Подход к решению:
Нам нужно будет обойти весь массив и сравнивать последний уникальный элемент с текущим. Если они не равны, то значит найден новый уникальный элемент, его значение записывается в текущее значение массива, а индекс последнего уникального элемента увеличивается на 1. По завершению алгоритма мы вернем значение индекса, увеличенного на 1.

Итак, код (пройдемся по шагам по нему)

public int removeDuplicates(int[] nums) {
    int index = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[index] != nums[i]) {
            index++;
            nums[index] = nums[i];
        }
    }
    return index + 1;
}

1. Инициализация переменной index, которая указывает на последний уникальный элемент нашего массива.
2. Цикл, с помощью которого мы будем обходить все элементы массива
3. Сравнение элементов внутри цикла: сравниваем текущий элемент с последним уникальным
4. Если последний уникальный элемент не равен текущему (nums[index] != nums[i]), значит найден новый уникальный элемент.
5. Если обнаружен новый уникальный элемент, то происходит обновление переменной index на 1, и этот новый элемент (nums[i]) записывается в позицию nums[index].
6. По завершению цикла возвращается значение, соответствующее кол-ву уникальных элементов в массиве, т.е. значение index увеличенное на 1 (т.к. длина массива на 1 больше, чем индекс последнего уникального элемента)

Временная сложность алгоритма составит O(n), т.к. придется пройтись по всем элементам массива
Пространственная сложность составит O(1), т.к. будет выделено ограниченное кол-во памяти под переменные index и i, которые не зависят от размера входного массива.

Шаг 3:
Хэш-таблица на начало работы шага: [0,1],[1,1],[7,1]
- Отрезок: [1,6, -5]
- Промежуточная сумма: 2
- Искомый отрезок на отсечение в хэш-таблице: 2 - 2 = 0 (вот его-то мы и добавили в начале!!!)
Мы всегда заранее добавляем в хэш-таблицу значение (0, 1), чтобы не пропустить подмассив, когда не нужно ничего отсекать.
- Результат (финальный): 1
- Записываем в хэш-таблицу значение [2,1], где ключ (2) - текущее значение отрезка, значение (1) - кол-во таких отрезков

Шаг 4:
Хэш-таблица на начало работы шага: [0,1], [1,1],[7,1],[2,1]
- Отрезок: [1,6, -5, 7]
- Промежуточная сумма: 9
- Искомый отрезок на отсечение в хэш-таблице: 9 - 2 = 7 (такой есть - это сумма с шага 2 - [1,6]), если мы отсечем этот отрезок, то останется отрезок [-5,7] - сумма чисел которого равняется 2.
- Результат (финальный): 2
- Записываем в хэш-таблицу значение [9,1], где ключ (9) - текущее значение отрезка, значение (1) - кол-во таких отрезков

Шаг 5:
Хэш-таблица на начало работы шага: [0,1],[1,1],[7,1],[2,1],[9,1]
- Отрезок: [1,6, -5, 7, 2]
- Промежуточная сумма: 11
- Искомый отрезок на отсечение в хэш-таблице: 11 - 2 = 9 (такой есть)
- Результат (финальный): 3
- Записываем в хэш-таблицу значение [11,1], где ключ (11) - текущее значение отрезка, значение (1) - кол-во таких отрезков

Продолжаем так пока не дойдем до конца массива.

Теперь изобразим в коде:

public int subarraySum(int[] nums, int k) {
    int result = 0;
    int subarraySum = 0;
    Map<Integer, Integer> prefixSumCount = new HashMap();
    prefixSumCount.put(0, 1);

    for (int num: nums) {
        subarraySum += num;
        int partToBeRemoved = subarraySum - k;
        result += prefixSumCount.getOrDefault(partToBeRemoved, 0);
        prefixSumCount.put(subarraySum, prefixSumCount.getOrDefault(subarraySum, 0) + 1);
    }
    return result;
}

Временная сложность такого алгоритма составит O(n) - в два раза быстрее!! т.к. мы проходим по каждому элементу массива всего 1 раз.
Пространственная сложность (да, похуже) - O(n), т.к. нужна память под хэш-таблицу, и в худшем случае она будет пропорциональна кол-ву элементов.

Задача Subarray Sum Equals K

Уровень: medium

Сегодня разберу задачку, в которой требуется найти количество подмассивов в массиве, сумма чисел которых равна некоторому числу k.

Итак, условие задачи: на вход мы получаем массив int[] nums и число k. Требуется найти количество подмассивов в массиве nums, сумма чисел в каждом из которых равняется числу k. Массив (и, соответственно, подмассив) - это непрерывная последовательность чисел.

Разберем на примере, что от нас хотят. Допустим, на вход мы получили следующие условия:
int[] nums = [1, 6, -5, 7, 2, 10, -8, 1], k = 2
Найдем, сколько существует подмассивов, сумма чисел в которых равна 2:
[1, 6, -5], [-5, 7], [2], [10, -8]
Ответ: 4.

p.s. сумма чисел в исходном массиве 1 (первый элемент) + 1(последний элемент) тоже равна 2, но это не удовлетворяет условию, что подмассив - это непрерывная последовательность чисел.

Ссылка на задачу тут. (https://leetcode.com/problems/subarray-sum-equals-k/description/)

Ограничения:
1. Длина массива от 1 до 2 * 10^4
2. Значения элементов массива от -1000 до 1000
3. Значения k от -10^7 до 10^7

Есть несколько подходов к решению:

- Первый способ решения
Проверять каждый подмассив, начиная с самого левого значения, постепенно двигая границу вправо. Если значение суммы станет равной искомому числу, то увеличить результат на единицу. Для реализации нам бы понадобилось два цикла - внешним мы бы двигали левую границу, а внутренним пробегались по остальным числам, находящимся справа от него, и суммировали бы их. На нашем примере это выглядело бы так:
[1, 6, -5, 7, 2, 10, -8, 1], k = 2
Шаг 1: Подмассивы, начинающиеся с числа 1: [1], [1,6], [1, 6,-5],[1, 6,-5,7], [1, 6,-5, 7, 2], [1, 6, -5, 7, 2, 10], [1, 6, -5, 7, 2, 10, -8], [1, 6, -5, 7, 2, 10, -8, 1]
Суммы каждого подмассива: 1, 7, 2 (совпало, увеличиваем результат), 9, 11, 21, 13, 14
Шаг 2: Подмассивы, начинающиеся с числа 6: [6], [6,-5],[6,-5,7], [6,-5, 7, 2], [6, -5, 7, 2, 10], [6, -5, 7, 2, 10, -8], [6, -5, 7, 2, 10, -8, 1]
Суммы каждого подмассива: 6, 1, 8, 10, 20, 12, 13 - ничего не совпало

И так далее мы бы двигали левую границу вправо, пока не достигли бы конца массива.

Временная сложность такого алгоритма составила бы О(n^2) - так как нам надо пройтись под каждому числу массива, которых n штук + по каждому числу, справа от него, т.е. еще по n.
Пространственная сложность: O(1), т.к. мы выделяем константное кол-во памяти под результат и под промежуточные суммы.

Код выглядел бы так:

public int subarraySum(int[] nums, int k) {
    int result = 0;
    for (int start = 0; start < nums.length; start++) {
       int subarraySum = 0;
       for (int end = start; end < nums.length; end++) {
           subarraySum += nums[end];
           if (subarraySum == k) {
               result++;
           }
       }
    }
    return result;
}

Второй способ решения
Способ называется подсчет суммы на префиксах, и для его реализации нам потребуется хэш-таблица. Что, собственно, мы будем делать:
1. Создаем хэш-таблицу, где будут храниться значения промежуточных сумм (отрезков) и их количество
2. Проходимся по значения массива, проверяя, есть ли в нашей хэш таблице значение отрезка, который можно отсечь, чтобы получилось число k.
3. Если есть, увеличиваем результат на единицу
4. Добавляем сумму чисел нового (текущего) отрезка в хэш-таблицу

На нашем примере это было бы так:
Шаг 1:
Хэш-таблица на начало работы шага: [0,1] - позже объясню, почему там лежит эта пара
- Отрезок: [1]
- Промежуточная сумма: 1
- Искомый отрезок на отсечение в хэш-таблице: 1 - 2 = -1 (такого не существует)
- Результат (финальный): 0
- Записываем в хэш-таблицу значение [1,1], где ключ (1) - текущее значение отрезка, значение (1) - кол-во таких отрезков

Шаг 2:
Хэш-таблица на начало работы шага: [0,1],[1,1]
- Отрезок: [1,6]
- Промежуточная сумма: 7
- Искомый отрезок на отсечение в хэш-таблице: 7 - 2 = 5 (такого нет)
- Результат (финальный): 0
- Записываем в хэш-таблицу значение [7,1], где ключ (7) - текущее значение отрезка, значение (1) - кол-во таких отрезков