#medium
Задача: 753. Cracking the Safe

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public String crackSafe(int n, int k) {
        Set<String> seen = new HashSet<>();
        StringBuilder result = new StringBuilder();

        String startNode = "0".repeat(n - 1);
        dfs(startNode, k, seen, result);

        result.append(startNode);
        return result.toString();
    }

    private void dfs(String node, int k, Set<String> seen, StringBuilder result) {
        for (int x = 0; x < k; x++) {
            String neighbor = node + x;
            if (!seen.contains(neighbor)) {
                seen.add(neighbor);
                dfs(neighbor.substring(1), k, seen, result);
                result.append(x);
            }
        }
    }
}

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

#medium
Задача: 754. Reach a Number

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

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

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

public class Solution {
    public int reachTarget(int target) {
        target = Math.abs(target);
        int position = 0;
        int steps = 0;
        while (position < target || (position - target) % 2 != 0) {
            steps++;
            position += steps;
        }
        return steps;
    }

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

#medium
Задача: 755. Pour Water

Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке.

Пример:

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]

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

1⃣Инициализируйте цикл для добавления объема воды.

2⃣Для каждой единицы воды: Проверьте, может ли вода двигаться влево и упасть на более низкий уровень. Если нет, проверьте, может ли вода двигаться вправо и упасть на более низкий уровень. Если нет, добавьте воду в текущую позицию.

3⃣Повторите шаг 2, пока не будет добавлен весь объем воды.

😎 Решение:

public class Solution {
    public int[] pourWater(int[] heights, int volume, int k) {
        for (int v = 0; v < volume; v++) {
            int dropIndex = k;
            for (int d : new int[]{-1, 1}) {
                int i = k;
                while (i + d >= 0 && i + d < heights.length && heights[i + d] <= heights[i]) {
                    if (heights[i + d] < heights[i]) {
                        dropIndex = i + d;
                    }
                    i += d;
                }
                if (dropIndex != k) {
                    break;
                }
            }
            heights[dropIndex]++;
        }
        return heights;
    }

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

На easyoffer 2.0 появится новый раздел:
Задачи с собеседований

🟠Задачи на Алгоритмические, Live-coding и System Design из реальных собеседований
🟠Вероятность встретить ту или иную задачу
🟠Возможность подготовиться к задачам конкретной компании

Есть много сайтов, на которых можно тренироваться решать задачи, но у них у всех одна проблема – сами задачи люди просто выдумывают. На easyoffer 2.0 вы сможете готовиться к live-coding и system design секциям на основе задач из реальных собеседований. Вы можете найдете самые частые задачи и сделаете упор на их решение.

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

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

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