Задача: 1402. Reducing Dishes
Сложность: hard

Шеф-повар собрал данные об уровне удовлетворенности от своих n блюд. Шеф может приготовить любое блюдо за 1 единицу времени.

Коэффициент удовольствия от блюда определяется как время, затраченное на приготовление этого блюда вместе с предыдущими блюдами, умноженное на уровень удовлетворенности от этого блюда, то есть time[i] * satisfaction[i].

Верните максимальную сумму коэффициентов удовольствия, которую шеф-повар может получить после приготовления некоторого количества блюд.

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

Пример:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

👨‍💻 Алгоритм:

1⃣Отсортируйте массив satisfaction в порядке возрастания.

2⃣Создайте таблицу мемоизации memo размером N x N и инициализируйте все значения -1, что будет означать, что ответ для всех состояний еще не рассчитан.

3⃣Реализуйте функцию, которая вызывается с параметрами index = 0 и time = 1, чтобы найти ответ:
Если достигнут конец массива, т.е. index == satisfaction.length, верните 0, так как больше нет блюд для приготовления и нельзя получить дополнительное значение.
Если значение в массиве memo для пары {index, time} не равно -1, верните это значение, так как это подразумевает, что данная подзадача уже была решена; поэтому рекурсивный вызов не требуется, и можно вернуть сохраненное значение из таблицы memo.
Рассчитайте максимум из двух вариантов:
- добавьте значение коэффициента для данного блюда satisfaction[index] * time к рекурсивному результату с index = index + 1 и time = time + 1.
- пропустите текущее блюдо и сделайте рекурсивный вызов для index = index + 1 и time = time.

😎 Решение:

class Solution {
    int findMaxSatisfaction(int[] satisfaction, int[][] memo, int index, int time) {
        if (index == satisfaction.length) {
            return 0;
        }

        if (memo[index][time] != -1) {
            return memo[index][time];
        }

        return memo[index][time] = Math.max(satisfaction[index] * time + findMaxSatisfaction(satisfaction, memo, index + 1, time + 1),
                findMaxSatisfaction(satisfaction, memo, index + 1, time));
    }

    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);

        int[][] memo = new int[satisfaction.length + 1][satisfaction.length + 1];
        for (int i = 0; i < satisfaction.length; i++) {
            Arrays.fill(memo[i], -1);
        }

        return findMaxSatisfaction(satisfaction, memo, 0, 1);
    }
}

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

Задача: 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;
    }
}

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

На easyoffer 2.0 появится:
Тренажер "Реальное собеседование"

🟠 Сценарии вопросов из реального собеседования
🟠Возможность подготовиться к собеседованию в конкретную компанию
🟠Итоговая статистика (прошёл/не прошёл)

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

Уже в начале следующей недели стартует краудфандинг кампания, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки. Первые 150 донатеров получать особо-выгодную цену и бонус. Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 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);
    }
}

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

Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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();
    }
}

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

На easyoffer 2.0 появится:
База тестовых заданий

🟠Тестовые задания для разных грейдов
🟠Фильтрация тестовых заданий по технологиям и компаниям

Когда я только начинал учиться на программиста, я постоянно выдумывал себе задачи для практики и тратил на это много времени. Но только в момент поиска работы я столкнулся с тестовыми заданиями, и понял насколько круто они прокачивают навыки. Нужно было еще на этапе обучения пробовать их делать. Все компании стараются составить тестовое задание "под себя", это дает большой выбор в тематике задач и технологий. На easyoffer 2.0 вы сможете отфильтровать тестовые задания по навыкам/грейдам и найти те, что подходят лично вам для практики.

В течение 1-2 дней я объявлю о краудфандинг кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки и смогут попасть на закрытое бета-тестирование. А первые 150 донатеров получать особо-выгодную цену и бонус.

🚀 Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 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;
    }
}

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

Задача: 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];
    }
}

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

Задача: 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>();
    }
}

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

Задача: 1801. Number of Orders in the Backlog
Сложность: medium

Дан двумерный целочисленный массив orders, где каждый элемент orders[i] = [pricei, amounti, orderTypei] обозначает, что было размещено amounti заказов типа orderTypei по цене pricei. Тип заказа orderTypei может быть:

- 0, если это партия заказов на покупку, или
- 1, если это партия заказов на продажу.

Обратите внимание, что orders[i] представляет собой партию из amounti независимых заказов с одинаковой ценой и типом. Все заказы, представленные orders[i], будут размещены перед всеми заказами, представленными orders[i+1] для всех допустимых i.

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

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

Верните общее количество заказов в списке невыполненных заказов после размещения всех заказов из входных данных. Поскольку это число может быть большим, верните его по модулю 10^9 + 7.

Пример:

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6

👨‍💻 Алгоритм:

1⃣Обрабатывайте каждый заказ в orders. Для заказа на покупку сравните с самыми дешевыми заказами на продажу в списке и выполняйте их при возможности, иначе добавьте в список.

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

3⃣Подсчитайте общее количество оставшихся заказов в списке и верните его по модулю 10^9 + 7.

😎 Решение:

class Solution {
    public int getNumberOfBacklogOrders(int[][] orders) {
        int MOD = 1_000_000_007;
        PriorityQueue<int[]> buyOrders = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        PriorityQueue<int[]> sellOrders = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        for (int[] order : orders) {
            int price = order[0], amount = order[1], orderType = order[2];

            PriorityQueue<int[]> targetQueue = orderType == 0 ? sellOrders : buyOrders;
            PriorityQueue<int[]> sourceQueue = orderType == 0 ? buyOrders : sellOrders;
            boolean isBuyOrder = orderType == 0;

            while (amount > 0 && !targetQueue.isEmpty() && 
                   (isBuyOrder ? targetQueue.peek()[0] <= price : targetQueue.peek()[0] >= price)) {
                int[] topOrder = targetQueue.poll();
                int executedAmount = Math.min(amount, topOrder[1]);
                amount -= executedAmount;
                if (topOrder[1] > executedAmount) {
                    targetQueue.offer(new int[]{topOrder[0], topOrder[1] - executedAmount});
                }
            }
            if (amount > 0) {
                sourceQueue.offer(new int[]{price, amount});
            }
        }

        return (int) (streamQueue(buyOrders, MOD) + streamQueue(sellOrders, MOD)) % MOD;
    }

    private long streamQueue(PriorityQueue<int[]> queue, int mod) {
        long total = 0;
        while (!queue.isEmpty()) {
            total = (total + queue.poll()[1]) % mod;
        }
        return total;
    }
}

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

Задача: 785. Is Graph Bipartite?
Сложность: medium

Есть неориентированный граф с n узлами, где каждый узел пронумерован от 0 до n - 1. Вам дан двумерный массив graph, где graph[u] — это массив узлов, смежных с узлом u. Более формально, для каждого v в graph[u] существует неориентированное ребро между узлом u и узлом v. Граф обладает следующими свойствами:

Нет петель (graph[u] не содержит u).
Нет параллельных ребер (graph[u] не содержит дублирующихся значений).
Если v есть в graph[u], то u есть в graph[v] (граф неориентированный).
Граф может быть несвязным, то есть могут существовать два узла u и v, между которыми нет пути.
Граф является двудольным, если узлы можно разделить на два независимых множества A и B так, что каждое ребро в графе соединяет узел из множества A с узлом из множества B.

Верните true, если и только если граф является двудольным.

Пример:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

👨‍💻 Алгоритм:

1⃣Мы будем хранить массив (или hashmap) для поиска цвета каждого узла: color[node]. Цвета могут быть 0, 1 или неокрашенные (-1 или null).

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

3⃣Для выполнения поиска в глубину мы используем стек. Для каждого неокрашенного соседа в graph[node] мы будем его окрашивать и добавлять в наш стек, который действует как своего рода "список дел" для узлов, которые нужно посетить дальше. Наш внешний цикл для start... гарантирует, что мы окрасим каждый узел.

😎 Решение:

class Solution {
    public boolean isBipartite(int[][] graph) {
        Map<Integer, Integer> color = new HashMap<>();
        for (int node = 0; node < graph.length; node++) {
            if (!color.containsKey(node)) {
                Stack<Integer> stack = new Stack<>();
                stack.push(node);
                color.put(node, 0);
                while (!stack.isEmpty()) {
                    int node = stack.pop();
                    for (int nei : graph[node]) {
                        if (!color.containsKey(nei)) {
                            stack.push(nei);
                            color.put(nei, color.get(node) ^ 1);
                        } else if (color.get(nei).equals(color.get(node))) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

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

Задача: 952. Largest Component Size by Common Factor
Сложность: hard

Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.

Пример:

Input: nums = [4,6,15,35]
Output: 4

👨‍💻 Алгоритм:

1⃣Построить граф, в котором узлы представляют числа из массива, а ребра между узлами существуют, если два числа имеют общий делитель больше 1.

2⃣Использовать алгоритм Union-Find для объединения узлов в связные компоненты.
Для каждого числа в массиве nums найти его простые делители и использовать их для объединения узлов.

3⃣Найти размер наибольшей связной компоненты.

😎 Решение:

import java.util.*;

class Solution {
    public int largestComponentSize(int[] nums) {
        Map<Integer, Integer> parent = new HashMap<>();
        Map<Integer, Integer> rank = new HashMap<>();
        
        for (int num : nums) {
            parent.put(num, num);
            rank.put(num, 0);
        }
        
        int find(int x) {
            if (parent.get(x) != x) {
                parent.put(x, find(parent.get(x)));
            }
            return parent.get(x);
        }
        
        void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank.get(rootX) > rank.get(rootY)) {
                    parent.put(rootY, rootX);
                } else if (rank.get(rootX) < rank.get(rootY)) {
                    parent.put(rootX, rootY);
                } else {
                    parent.put(rootY, rootX);
                    rank.put(rootX, rank.get(rootX) + 1);
                }
            }
        }
        
        Set<Integer> primeFactors(int n) {
            Set<Integer> factors = new HashSet<>();
            int d = 2;
            while (d * d <= n) {
                while (n % d == 0) {
                    factors.add(d);
                    n /= d;
                }
                d++;
            }
            if (n > 1) {
                factors.add(n);
            }
            return factors;
        }
        
        Map<Integer, List<Integer>> primeToIndex = new HashMap<>();
        for (int num : nums) {
            Set<Integer> primes = primeFactors(num);
            for (int prime : primes) {
                primeToIndex.computeIfAbsent(prime, k -> new ArrayList<>()).add(num);
            }
        }
        
        for (List<Integer> primes : primeToIndex.values()) {
            for (int i = 1; i < primes.size(); i++) {
                union(primes.get(0), primes.get(i));
            }
        }
        
        Map<Integer, Integer> size = new HashMap<>();
        for (int num : nums) {
            int root = find(num);
            size.put(root, size.getOrDefault(root, 0) + 1);
        }
        
        return Collections.max(size.values());
    }
}

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

Задача: 1071. Greatest Common Divisor of Strings
Сложность: easy

Для двух строк s и t мы говорим, что "t делит s", если и только если s = t + t + t + ... + t (т.е. t соединена сама с собой один или более раз).

Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2.

Пример:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

👨‍💻 Алгоритм:

1⃣Найдите более короткую строку среди str1 и str2, для простоты пусть это будет str1.

2⃣Начните с base = str1 и проверьте, состоят ли обе строки str1 и str2 из множителей строки base. Если это так, верните base. В противном случае, попробуйте более короткую строку, удалив последний символ из base.

3⃣Если вы проверили все префиксные строки и не нашли строку GCD, верните "".

😎 Решение:

class Solution {
    fun valid(str1: String, str2: String, k: Int): Boolean {
        val len1 = str1.length
        val len2 = str2.length
        if (len1 % k > 0 || len2 % k > 0) {
            return false
        } else {
            val base = str1.substring(0, k)
            val n1 = len1 / k
            val n2 = len2 / k
            return str1 == base.repeat(n1) && str2 == base.repeat(n2)
        }
    }

    fun gcdOfStrings(str1: String, str2: String): String {
        val len1 = str1.length
        val len2 = str2.length
        for (i in minOf(len1, len2) downTo 1) {
            if (valid(str1, str2, i)) {
                return str1.substring(0, i)
            }
        }
        return ""
    }
}

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

Задача: 974. Subarray Sums Divisible by K
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните количество непустых подмассивов, сумма которых делится на k.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

👨‍💻 Алгоритм:

1⃣Инициализация и подготовка. Инициализируйте prefixMod = 0 для хранения остатка от суммы элементов до текущего индекса при делении на k. Инициализируйте result = 0 для хранения количества подмассивов, сумма которых делится на k. Инициализируйте массив modGroups длиной k, где modGroups[R] хранит количество подмассивов с остатком R. Установите modGroups[0] = 1.

2⃣Итерирование по массиву. Для каждого элемента массива nums вычислите новый prefixMod как (prefixMod + nums[i] % k + k) % k, чтобы избежать отрицательных значений. Увеличьте result на значение modGroups[prefixMod], чтобы добавить количество подмассивов с текущим остатком. Увеличьте значение modGroups[prefixMod] на 1 для будущих совпадений.

3⃣Возврат результата. Верните значение result, которое содержит количество подмассивов, сумма которых делится на k.

😎 Решение:

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int prefixMod = 0, result = 0;
        int[] modGroups = new int[k];
        modGroups[0] = 1;

        for (int num : nums) {
            prefixMod = (prefixMod + num % k + k) % k;
            result += modGroups[prefixMod];
            modGroups[prefixMod]++;
        }

        return result;
    }
}

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

Задача: 683. K Empty Slots
Сложность: hard

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

Вам дан массив bulbs длины n, где bulbs[i] = x означает, что в (i+1)-й день мы включим лампочку в позиции x, где i индексируется с 0, а x индексируется с 1.

Дано целое число k, верните минимальный номер дня, такой что существует две включенные лампочки, между которыми ровно k выключенных лампочек. Если такого дня не существует, верните -1.

Пример:

Input: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.

👨‍💻 Алгоритм:

1⃣Поддерживайте active, отсортированную структуру данных, содержащую каждую лампочку, которая в данный момент включена. Это позволит быстро находить соседей для вновь добавленных лампочек и проверять условия задачи.

2⃣Когда вы добавляете лампочку в active, проверьте ее нижних и верхних соседей. Для этого найдите ближайшие включенные лампочки с обеих сторон и проверьте количество выключенных лампочек между ними.

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

😎 Решение:

import java.util.TreeSet;

class Solution {
    public int kEmptySlots(int[] flowers, int k) {
        TreeSet<Integer> active = new TreeSet<>();
        int day = 0;
        
        for (int flower : flowers) {
            day++;
            active.add(flower);
            Integer lower = active.lower(flower);
            Integer higher = active.higher(flower);
            
            if ((lower != null && flower - lower - 1 == k) ||
                (higher != null && higher - flower - 1 == k)) {
                return day;
            }
        }
        return -1;
    }
}

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

Задача: 1312. Minimum Insertion Steps to Make a String Palindrome
Сложность: hard

Дана строка s. За один шаг вы можете вставить любой символ в любой индекс строки.

Верните минимальное количество шагов, необходимых для превращения s в палиндром.

Палиндром — это строка, которая читается одинаково как вперед, так и назад.

Пример:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.

👨‍💻 Алгоритм:

1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте строковую переменную sReverse и установите её значение как обратную строку s.

2⃣Создайте двумерный массив memo размером n + 1 на n + 1, где memo[i][j] будет содержать длину наибольшей общей подпоследовательности, учитывая первые i символов строки s и первые j символов строки sReverse. Инициализируйте массив значением -1.

3⃣Верните n - lcs(s, sReverse, n, n, memo), где lcs - это рекурсивный метод с четырьмя параметрами: первая строка s1, вторая строка s2, длина подстроки от начала s1, длина подстроки от начала s2 и memo. Метод возвращает длину наибольшей общей подпоследовательности в подстроках s1 и s2. В этом методе выполните следующее:
Если m == 0 или n == 0, это означает, что одна из двух подстрок пуста, поэтому верните 0.
Если memo[m][n] != -1, это означает, что мы уже решили эту подзадачу, поэтому верните memo[m][n].
Если последние символы подстрок совпадают, добавьте 1 и найдите длину наибольшей общей подпоследовательности, исключив последний символ обеих подстрок. Верните memo[i][j] = 1 + lcs(s1, s2, m - 1, n - 1, memo).
В противном случае, если последние символы не совпадают, рекурсивно найдите наибольшую общую подпоследовательность в обеих подстроках, исключив их последние символы по одному. Верните memo[i][j] = max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo)).

😎 Решение:

class Solution {
    private int lcs(String s1, String s2, int m, int n, int[][] memo) {
        if (m == 0 || n == 0) {
            return 0;
        }
        if (memo[m][n] != -1) {
            return memo[m][n];
        }
        if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
            return memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, memo);
        }
        return memo[m][n] = Math.max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo));
    }

    public int minInsertions(String s) {
        int n = s.length();
        String sReverse = new StringBuilder(s).reverse().toString();
        int[][] memo = new int[n + 1][n + 1];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                memo[i][j] = -1;
            }
        }

        return n - lcs(s, sReverse, n, n, memo);
    }
}

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