Задача: 981. Time Based Key-Value Store
Сложность: medium

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

Реализуйте класс TimeMap:

TimeMap() Инициализирует объект структуры данных.
void set(String key, String value, int timestamp) Сохраняет ключ key с значением value в заданное время timestamp.
String get(String key, int timestamp) Возвращает значение, такое что set был вызван ранее с timestamp_prev <= timestamp. Если таких значений несколько, возвращается значение, связанное с наибольшим timestamp_prev. Если значений нет, возвращается "".

Пример:

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

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

1⃣Создайте hashmap keyTimeMap, который хранит строку в качестве ключа и другой hashmap в качестве значения, как обсуждалось выше.

2⃣В функции set() сохраните значение в позиции timestamp в корзине ключа keyTimeMap, т.е. keyTimeMap[key][timestamp] = value.

3⃣В функции get() итерируйтесь по всем временам в порядке убывания от timestamp до 1. Для любого времени во время итерации, если существует значение в корзине ключа, верните это значение. В противном случае, в конце верните пустую строку.

😎 Решение:

import java.util.*;

class TimeMap {
    private Map<String, TreeMap<Integer, String>> keyTimeMap;

    public TimeMap() {
        keyTimeMap = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        keyTimeMap.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
    }

    public String get(String key, int timestamp) {
        if (!keyTimeMap.containsKey(key)) {
            return "";
        }
        TreeMap<Integer, String> times = keyTimeMap.get(key);
        for (int currTime = timestamp; currTime >= 1; --currTime) {
            if (times.containsKey(currTime)) {
                return times.get(currTime);
            }
        }
        return "";
    }
}

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

Задача: 910. Smallest Range II
Сложность: medium

Вам дан целочисленный массив nums и целое число k. Для каждого индекса i, где 0 <= i < nums.length, измените nums[i] на nums[i] + k или nums[i] - k. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после изменения значений в каждом индексе.

Пример:

Input: nums = [1], k = 0
Output: 0

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

1⃣Отсортировать массив nums.

2⃣Рассчитать начальную разницу между максимальным и минимальным элементами.

3⃣Пройтись по всем элементам массива, пытаясь минимизировать разницу, изменяя текущий элемент на +k и -k и вычисляя новые максимальные и минимальные значения массива.

😎 Решение:

import java.util.Arrays;

class Solution {
    public int smallestRangeII(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int minVal = nums[0];
        int maxVal = nums[n - 1];
        int result = maxVal - minVal;

        for (int i = 0; i < n - 1; i++) {
            int high = Math.max(nums[i] + k, maxVal - k);
            int low = Math.min(nums[i + 1] - k, minVal + k);
            result = Math.min(result, high - low);
        }

        return result;
    }
}

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

Задача: 1434. Number of Ways to Wear Different Hats to Each Other
Сложность: hard

Дано n человек и 40 видов шляп, пронумерованных от 1 до 40.

Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком.

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

Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7.

Пример:

Input: hats = [[3,4],[4,5],[5]]
Output: 1
Explanation: There is only one way to choose hats given the conditions. 
First person choose hat 3, Second person choose hat 4 and last one hat 5.

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

1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей.

2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп.

3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп.

😎 Решение:

class Solution {
    int[][] memo;
    int done;
    int n;
    int MOD = 1000000007;
    Map<Integer, ArrayList<Integer>> hatsToPeople;
    
    public int numberWays(List<List<Integer>> hats) {
        n = hats.size();
        
        hatsToPeople = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int hat: hats.get(i)) {
                hatsToPeople.computeIfAbsent(hat, k -> new ArrayList<>()).add(i);
            }
        }
        
        done = (1 << n) - 1;
        memo = new int[41][done];
        
        for (int i = 0; i < 41; i++) {
            Arrays.fill(memo[i], -1);
        }
        
        return dp(1, 0);
    }
    
    private int dp(int hat, int mask) {
        if (mask == done) {
            return 1;
        }
        
        if (hat > 40) {
            return 0;
        }
        
        if (memo[hat][mask] != -1) {
            return memo[hat][mask];
        }
        
        int ans = dp(hat + 1, mask);
        
        if (hatsToPeople.containsKey(hat)) {
            for (int person: hatsToPeople.get(hat)) {
                if ((mask & (1 << person)) == 0) {
                    ans = (ans + dp(hat + 1, mask | (1 << person))) % MOD;
                }
            }
        }
        
        memo[hat][mask] = ans;
        return ans;
    }
}

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

Задача: 759. Employee Free Time
Сложность: hard

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

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

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

import java.util.*;

class Interval {
    public int start;
    public int end;
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> intervals = new ArrayList<>();
        for (List<Interval> employee : schedule) {
            intervals.addAll(employee);
        }
        
        intervals.sort((a, b) -> Integer.compare(a.start, b.start));
        
        List<Interval> merged = new ArrayList<>();
        for (Interval interval : intervals) {
            if (merged.isEmpty() || merged.get(merged.size() - 1).end < interval.start) {
                merged.add(interval);
            } else {
                merged.get(merged.size() - 1).end = Math.max(merged.get(merged.size() - 1).end, interval.end);
            }
        }
        
        List<Interval> freeTime = new ArrayList<>();
        for (int i = 1; i < merged.size(); i++) {
            if (merged.get(i).start > merged.get(i - 1).end) {
                freeTime.add(new Interval(merged.get(i - 1).end, merged.get(i).start));
            }
        }
        
        return freeTime;
    }

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

Задача: 765. Couples Holding Hands
Сложность: hard

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

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

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

Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

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

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

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

😎 Решение:

class Solution {
    int N;
    int[][] pairs;

    public int minSwapsCouples(int[] row) {
        N = row.length / 2;
        pairs = new int[N][2];
        for (int i = 0; i < N; ++i) {
            pairs[i][0] = row[2 * i] / 2;
            pairs[i][1] = row[2 * i + 1] / 2;
        }
        return solve(0);
    }

    public void swap(int a, int b, int c, int d) {
        int t = pairs[a][b];
        pairs[a][b] = pairs[c][d];
        pairs[c][d] = t;
    }

    public int solve(int i) {
        if (i == N) return 0;
        int x = pairs[i][0], y = pairs[i][1];
        if (x == y) return solve(i + 1);

        int jx = 0, kx = 0, jy = 0, ky = 0;
        for (int j = i + 1; j < N; ++j) {
            for (int k = 0; k <= 1; ++k) {
                if (pairs[j][k] == x) { jx = j; kx = k; }
                if (pairs[j][k] == y) { jy = j; ky = k; }
            }
        }

        swap(i, 1, jx, kx);
        int ans1 = 1 + solve(i + 1);
        swap(i, 1, jx, kx);

        swap(i, 0, jy, ky);
        int ans2 = 1 + solve(i + 1);
        swap(i, 0, jy, ky);

        return Math.min(ans1, ans2);
    }
}

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

Задача: 344. Reverse String
Сложность: easy

Напишите функцию, которая переворачивает строку. Входная строка представлена в виде массива символов s.

Вы должны сделать это, изменяя входной массив на месте с использованием O(1) дополнительной памяти.

Пример:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

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

1⃣Инициализация указателей:
Установите два указателя: один на начало массива (left), другой на конец массива (right).

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

3⃣Завершение работы:
Повторяйте шаг 2 до тех пор, пока левый указатель не станет больше или равен правому.

😎 Решение:

public class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

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

Задача: 210. Course Schedule II
Сложность: medium

Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.

Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

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

1⃣Инициализация и построение графа:
Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе.
Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма.

2⃣Запуск поиска в глубину (DFS):
Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла.
Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны.

3⃣Обработка узлов и возвращение результата:
После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке.
После обработки всех узлов просто верните узлы в порядке их присутствия в стеке от вершины до основания.

😎 Решение:

class Solution {
    static int WHITE = 1;
    static int GRAY = 2;
    static int BLACK = 3;

    boolean isPossible;
    Map<Integer, Integer> color;
    Map<Integer, List<Integer>> adjList;
    List<Integer> topologicalOrder;

    private void init(int numCourses) {
        this.isPossible = true;
        this.color = new HashMap<>();
        this.adjList = new HashMap<>();
        this.topologicalOrder = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            this.color.put(i, WHITE);
        }
    }

    private void dfs(int node) {
        if (!this.isPossible) return;
        this.color.put(node, GRAY);
        for (Integer neighbor : this.adjList.getOrDefault(node, new ArrayList<>())) {
            if (this.color.get(neighbor) == WHITE) {
                this.dfs(neighbor);
            } else if (this.color.get(neighbor) == GRAY) {
                this.isPossible = false;
            }
        }
        this.color.put(node, BLACK);
        this.topologicalOrder.add(node);
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        this.init(numCourses);
        for (int i = 0; i < prerequisites.length; i++) {
            int dest = prerequisites[i][0];
            int src = prerequisites[i][1];
            List<Integer> lst = adjList.getOrDefault(src, new ArrayList<>());
            lst.add(dest);
            adjList.put(src, lst);
        }
        for (int i = 0; i < numCourses; i++) {
            if (this.color.get(i) == WHITE) {
                this.dfs(i);
            }
        }
        if (this.isPossible) {
            int[] order = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                order[i] = this.topologicalOrder.get(numCourses - i - 1);
            }
            return order;
        } else {
            return new int[0];
        }
    }
}

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

Задача: 1422. Maximum Score After Splitting a String
Сложность: easy

Дана строка s из нулей и единиц. Верните максимальное количество очков после разбиения строки на две непустые подстроки (т.е. левую подстроку и правую подстроку).

Количество очков после разбиения строки - это количество нулей в левой подстроке плюс количество единиц в правой подстроке.

Пример:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

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

1⃣Посчитайте количество единиц в строке и инициализируйте счётчики нулей и максимального значения.

2⃣Перебирайте символы строки до предпоследнего символа, обновляя счётчики нулей и единиц.

3⃣Обновляйте максимальное значение, если текущая сумма нулей и единиц больше предыдущего максимума.

😎 Решение:

class Solution {
    public int maxScore(String s) {
        int ones = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                ones++;
            }
        }
        
        int ans = 0;
        int zeros = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '1') {
                ones--;
            } else {
                zeros++;
            }
            
            ans = Math.max(ans, zeros + ones);
        }
        
        return ans;
    }
}

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

Задача: 722. Remove Comments
Сложность: medium

Дана программа на C++, удалите из нее комментарии. Исходный текст программы представляет собой массив строк source, где source[i] - это i-я строка исходного кода. Это результат разбиения исходной строки исходного кода символом новой строки '\n'. В C++ существует два типа комментариев: строчные и блочные. Строка "//" обозначает строчный комментарий, который означает, что он и остальные символы справа от него в той же строке должны игнорироваться. Строка "/*" обозначает блочный комментарий, который означает, что все символы до следующего (не перекрывающегося) вхождения "*/" должны игнорироваться. (Здесь вхождения происходят в порядке чтения: строка за строкой слева направо.) Чтобы было понятно, строка "/*/" еще не завершает блочный комментарий, так как окончание будет перекрывать начало. Первый эффективный комментарий имеет приоритет над остальными.

Например, если строка "//" встречается в блочном комментарии, она игнорируется. Аналогично, если строка "/*" встречается в строчном или блочном комментарии, она также игнорируется. Если после удаления комментариев определенная строка кода оказывается пустой, вы не должны выводить эту строку: каждая строка в списке ответов будет непустой.

Пример:

Input: source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", "int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", "   testing */", "a = b + c;", "}"]
Output: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]

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

1⃣Создайте строку buffer для хранения текущей строки кода без комментариев и флаг inBlock для отслеживания, находимся ли мы внутри блочного комментария.

2⃣Пройдите по каждой строке source и по каждому символу в этой строке, обрабатывая комментарии: Если встречен блочный комментарий /*, установите флаг inBlock и пропустите символы до */. Если встречен строчный комментарий //, прекратите обработку текущей строки. Если не находимся внутри комментария, добавьте символ в buffer.

3⃣После обработки всех строк добавьте непустые строки из buffer в результат.

😎 Решение:

import java.util.*;

public class Solution {
    public List<String> removeComments(String[] source) {
        boolean inBlock = false;
        StringBuilder buffer = new StringBuilder();
        List<String> result = new ArrayList<>();
        
        for (String line : source) {
            int i = 0;
            if (!inBlock) buffer = new StringBuilder();
            while (i < line.length()) {
                if (!inBlock && i + 1 < line.length() && line.charAt(i) == '/' && line.charAt(i + 1) == '*') {
                    inBlock = true;
                    i++;
                } else if (inBlock && i + 1 < line.length() && line.charAt(i) == '*' && line.charAt(i + 1) == '/') {
                    inBlock = false;
                    i++;
                } else if (!inBlock && i + 1 < line.length() && line.charAt(i) == '/' && line.charAt(i + 1) == '/') {
                    break;
                } else if (!inBlock) {
                    buffer.append(line.charAt(i));
                }
                i++;
            }
            if (!inBlock && buffer.length() > 0) {
                result.add(buffer.toString());
            }
        }
        return result;
    }
}

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

Задача: 944. Delete Columns to Make Sorted
Сложность: easy

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

Пример:

Input: strs = ["cba","daf","ghi"]
Output: 1

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

1⃣Инициализировать переменную count для отслеживания количества столбцов, которые нужно удалить.

2⃣Пройти по каждому столбцу от 0 до длины строки.
Для каждого столбца проверить, отсортированы ли символы лексикографически.
Если столбец не отсортирован, увеличить count.

3⃣Вернуть count.

😎 Решение:

class Solution {
    public int minDeletionSize(String[] strs) {
        int count = 0;
        int rows = strs.length;
        int cols = strs[0].length();
        for (int col = 0; col < cols; col++) {
            for (int row = 1; row < rows; row++) {
                if (strs[row].charAt(col) < strs[row - 1].charAt(col)) {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}

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

Задача: 278. First Bad Version
Сложность: easy

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

Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими.

Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API.

Пример:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

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

1⃣Инициализация границ поиска:
Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n.

2⃣Бинарный поиск:
Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid).
Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1.

3⃣Возврат результата:
Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии.

😎 Решение:

public int firstBadVersion(int n) {
    int left = 1;
    int right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

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

Задача: 1305. All Elements in Two Binary Search Trees
Сложность: medium

Даны два бинарных дерева поиска root1 и root2. Вернуть список, содержащий все целые числа из обоих деревьев, отсортированные в порядке возрастания.

Пример:

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

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

1⃣Выполните итеративный обход в порядке возрастания обоих деревьев параллельно.

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

3⃣Верните выходной список.

😎 Решение:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        ArrayDeque<TreeNode> stack1 = new ArrayDeque<>(), stack2 = new ArrayDeque<>();
        List<Integer> output = new ArrayList<>();

        while (root1 != null || root2 != null || !stack1.isEmpty() || !stack2.isEmpty()) {
            while (root1 != null) {
                stack1.push(root1);
                root1 = root1.left;
            }
            while (root2 != null) {
                stack2.push(root2);
                root2 = root2.left;
            }
            if (stack2.isEmpty() || (!stack1.isEmpty() && stack1.peek().val <= stack2.peek().val)) {
                root1 = stack1.pop();
                output.add(root1.val);
                root1 = root1.right;
            } else {
                root2 = stack2.pop();
                output.add(root2.val);
                root2 = root2.right;
            }
        }
        return output;
    }
}

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

Задача: 1406. Stone Game III
Сложность: hard

Алиса и Боб продолжают свои игры с кучами камней. Камни расположены в ряд, и каждый камень имеет ассоциированное значение, которое представлено целым числом в массиве stoneValue.
Алиса и Боб ходят по очереди, начиная с Алисы. В свой ход каждый игрок может взять 1, 2 или 3 камня из первых оставшихся камней в ряду.

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

Предположим, что Алиса и Боб играют оптимально.
Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом.

Пример:

Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

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

1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0.

2⃣Итеративно обновляйте dp[i] для всех i от n-1 до 0, вычисляя максимальную разницу в баллах, которые могут получить игроки при оптимальной игре.

3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья.

😎 Решение:

class Solution {
    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] dp = new int [n + 1];
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = stoneValue[i] - dp[i + 1];
            if (i + 2 <= n) {
                dp[i] = Math.max(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2]);
            }
            if (i + 3 <= n) {
                dp[i] = Math.max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3]);
            }
        }
        if (dp[0] > 0) {
            return "Alice";
        }
        if (dp[0] < 0) {
            return "Bob";
        }
        return "Tie";
    }
}

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

Задача: 41. First Missing Positive
сложность: hard

Дан неотсортированный массив целых чисел nums. Верните наименьшее положительное целое число, которого нет в массиве nums.

Необходимо реализовать алгоритм, который работает за время O(n) и использует O(1) дополнительной памяти.

Пример:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

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

1⃣Инициализировать переменную n длиной массива nums. Создать массив seen размером n + 1. Отметить элементы в массиве nums как просмотренные в массиве seen.
Для каждого числа num в массиве nums, если num больше 0 и меньше или равно n, установить seen[num] в значение true.

2⃣Найти наименьшее недостающее положительное число:
Проитерировать от 1 до n, и если seen[i] не равно true, вернуть i как наименьшее недостающее положительное число.

3⃣Если массив seen содержит все элементы от 1 до n, вернуть n + 1 как наименьшее недостающее положительное число.

😎 Решение:

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        boolean[] seen = new boolean[n + 1];

        for (int num : nums) {
            if (num > 0 && num <= n) {
                seen[num] = true;
            }
        }

        for (int i = 1; i <= n; i++) {
            if (!seen[i]) {
                return i;
            }
        }

        return n + 1;
    }
}

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

Задача: №21. Merge Two Sorted Lists
Сложность: easy

Вам даны заголовки двух отсортированных связанных списков list1 и list2.
Объедините их в один отсортированный список, сшивая существующие узлы.
Верните заголовок нового объединенного списка.

Пример:

Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

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

1⃣Если один из списков пуст — возвращаем второй как результат.

2⃣Сравниваем значения текущих узлов списков: выбираем меньший и рекурсивно вызываем mergeTwoLists для оставшейся части.

3⃣Связываем меньший узел с результатом рекурсивного вызова и возвращаем его как текущий.

😎 Решение:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }
        return list1 != null ? list1 : list2;
    }
}

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

Задача: 202. Happy Number
Сложность: easy

Напишите алгоритм для определения, является ли число n счастливым.

Счастливое число определяется следующим процессом:

Начиная с любого положительного целого числа, замените число суммой квадратов его цифр.
Повторяйте процесс, пока число не станет равным 1 (где оно и останется), или пока оно бесконечно не будет циклически повторяться в цикле, который не включает 1.
Те числа, для которых этот процесс завершается 1, являются счастливыми.
Верните true, если n является счастливым числом, и false, если нет.

Пример:

Input: n = 2
Output: false

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

1⃣Для заданного числа n определите следующее число в последовательности: используйте операторы деления и взятия остатка для последовательного извлечения цифр из числа, пока не закончатся все цифры. Каждую извлеченную цифру возводите в квадрат и суммируйте полученные значения. Это техника "последовательного извлечения цифр" является полезным инструментом для решения множества задач.

2⃣Отслеживайте цепочку чисел и определяйте, не вошли ли вы в цикл, используя структуру данных HashSet. Каждый раз, генерируя следующее число в цепочке, проверяйте, присутствует ли оно уже в HashSet.

3⃣Если числа нет в HashSet, добавьте его туда. Если число уже есть в HashSet, это означает, что вы находитесь в цикле, и следует вернуть false. HashSet используется вместо Vector, List или Array, потому что проверка присутствия числа в HashSet занимает время O(1), тогда как в других структурах данных это займет время O(n). Правильный выбор структур данных является ключевым элементом решения подобных задач.

😎 Решение:

class Solution {
    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
}

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