Java | LeetCode

Задача: 421. Maximum XOR of Two Numbers in an Array Сложность: medium Дан целочисленный массив nums, верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n. Пример:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

👨‍💻 Алгоритм: 1⃣Вычислите количество битов L для использования. Это длина максимального числа в двоичном представлении. Инициализируйте max_xor = 0. 2⃣Запустите цикл от i = L−1 до i = 0 (от самого левого бита L−1 до самого правого бита 0): Сдвигайте max_xor влево, чтобы освободить следующий бит. Инициализируйте переменную curr_xor = max_xor | 1, установив 1 в самом правом бите max_xor. Теперь проверьте, можно ли выполнить curr_xor, используя доступные префиксы. 3⃣Вычислите все возможные префиксы длины L−i, итерируя по nums: Поместите в HashSet префиксы префикс текущего числа длиной L−i: num >> i. Итерируйте по всем префиксам и проверьте, можно ли выполнить curr_xor, используя два из них: p1 ^ p2 == curr_xor. Используя свойство самопреобразования XOR p1 ^ p2 ^ p2 = p1, можно переписать это как p1 == curr_xor ^ p2 и просто проверить для каждого p, если curr_xor ^ p есть в префиксах. Если так, установите max_xor равным curr_xor, т.е. установите 1-бит в самом правом бите. В противном случае, пусть max_xor оставит 0-бит в самом правом бите. 😎 Решение:

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

public class Solution {
    public int findMaximumXOR(int[] nums) {
        int maxNum = nums[0];
        for (int num : nums) maxNum = Math.max(maxNum, num);
        int L = (Integer.toBinaryString(maxNum)).length();

        int maxXor = 0, currXor;
        Set<Integer> prefixes = new HashSet<>();
        for (int i = L - 1; i > -1; --i) {
            maxXor <<= 1;
            currXor = maxXor | 1;
            prefixes.clear();
            for (int num : nums) prefixes.add(num >> i);
            for (int p : prefixes) {
                if (prefixes.contains(currXor ^ p)) {
                    maxXor = currXor;
                    break;
                }
            }
        }
        return maxXor;
    }
}

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

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 908. Smallest Range I Сложность: easy Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем. Пример:

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

👨‍💻 Алгоритм: 1⃣Найти минимальное и максимальное значения массива nums. 2⃣Рассчитать потенциальные новые минимальные и максимальные значения после применения операции. 3⃣Вычислить минимальную оценку, сравнивая разницу между всеми возможными новыми минимальными и максимальными значениями. 😎 Решение:

class Solution {
    public int smallestRangeI(int[] nums, int k) {
        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num < minVal) minVal = num;
            if (num > maxVal) maxVal = num;
        }
        return Math.max(0, (maxVal - k) - (minVal + k));
    }
}

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

👩‍💻 Ищем Java разработчиков. Удалёнка, релокейт платим много! Специально для Вас, собираем лучшие вакансии для Java разработчиков с прямыми контактами в Telegram на канале @it_match_java Подпишись чтобы не упустить свой шанс получить лучший оффер! ➡️ Посмотреть вакансии

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 811. Subdomain Visit Count Сложность: medium Веб-сайт с доменом "discuss.leetcode.com" состоит из различных поддоменов. На верхнем уровне у нас есть "com", на следующем уровне - "leetcode.com", и на самом нижнем уровне - "discuss.leetcode.com". Когда мы посещаем домен, такой как "discuss.leetcode.com", мы также автоматически посещаем родительские домены "leetcode.com" и "com". Домен с парным счетчиком - это домен, который имеет один из двух форматов "rep d1.d2.d3" или "rep d1.d2", где rep - это количество посещений домена, а d1.d2.d3 - это сам домен. Например, "9001 discuss.leetcode.com" - это домен с парным счетчиком, указывающий на то, что discuss.leetcode.com был посещен 9001 раз. Дан массив доменов с парными счетчиками cpdomains, верните массив доменов с парными счетчиками для каждого поддомена во входных данных. Вы можете вернуть ответ в любом порядке. Пример:

Input: cpdomains = ["9001 discuss.leetcode.com"]
Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
Explanation: We only have one website domain: "discuss.leetcode.com".
As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

👨‍💻 Алгоритм: 1⃣Следуем указаниям из условия задачи. 2⃣Для адреса вида a.b.c, подсчитываем a.b.c, b.c и c. Для адреса вида x.y, подсчитываем x.y и y. 3⃣Для подсчета этих строк используем хеш-таблицу. Для разделения строк на требуемые части используем библиотечные функции split. 😎 Решение:

import java.util.*;

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        Map<String, Integer> ans = new HashMap<>();
        for (String domain : cpdomains) {
            String[] parts = domain.split(" ");
            int count = Integer.parseInt(parts[0]);
            String[] frags = parts[1].split("\\.");
            for (int i = 0; i < frags.length; i++) {
                String subdomain = String.join(".", Arrays.copyOfRange(frags, i, frags.length));
                ans.put(subdomain, ans.getOrDefault(subdomain, 0) + count);
            }
        }
        List<String> res = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : ans.entrySet()) {
            res.add(entry.getValue() + " " + entry.getKey());
        }
        return res;
    }

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

📱 Java Developer — мастхев для любого джависта Канал Team Lead'a с полезными советами и практиками для Java-разработчиков: ➖ Книги, статьи, тесты ➖ Spring, Hibernate, Docker, SQL ➖ Алгоритмы, вопросы и задачи с собеседований Присоединяйтесь: @java_tg

Задача: 682. Baseball Game Сложность: medium Вы ведете учет очков в бейсбольной игре с необычными правилами. В начале игры у вас пустая запись. Вам дается список строк operations, где operations[i] — это i-я операция, которую вы должны применить к записи, и она может быть одной из следующих: Целое число x. Записать новый счет, равный x. '+'. Записать новый счет, который является суммой двух предыдущих очков. 'D'. Записать новый счет, который в два раза больше предыдущего очка. 'C'. Аннулировать предыдущее очко, удалив его из записи. Верните сумму всех очков в записи после применения всех операций. Тестовые случаи сформированы таким образом, что ответ и все промежуточные вычисления умещаются в 32-битное целое число, и что все операции корректны. Пример:

Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record, record is now [5].
"2" - Add 2 to the record, record is now [5, 2].
"C" - Invalidate and remove the previous score, record is now [5].
"D" - Add 2 * 5 = 10 to the record, record is now [5, 10].
"+" - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.

👨‍💻 Алгоритм: 1⃣Поддерживайте значение каждого действительного раунда в стеке при обработке данных. Используйте стек, так как операции касаются только последнего или предпоследнего действительного раунда. 2⃣Обрабатывайте каждую операцию из списка operations последовательно, выполняя соответствующее действие: добавление, суммирование, удвоение или удаление очков. 3⃣После обработки всех операций верните сумму всех значений в стеке. 😎 Решение:

class Solution {
    public int calPoints(String[] ops) {
        Stack<Integer> stack = new Stack<>();

        for (String op : ops) {
            if (op.equals("+")) {
                int top = stack.pop();
                int newTop = top + stack.peek();
                stack.push(top);
                stack.push(newTop);
            } else if (op.equals("C")) {
                stack.pop();
            } else if (op.equals("D")) {
                stack.push(2 * stack.peek());
            } else {
                stack.push(Integer.valueOf(op));
            }
        }

        int ans = 0;
        for (int score : stack) {
            ans += score;
        }
        return ans;
    }
}

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

Задача: 730. Count Different Palindromic Subsequences Сложность: hard Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi. Пример:

Input: s = "bccb"
Output: 6

👨‍💻 Алгоритм: 1⃣Используйте динамическое программирование для подсчета количества палиндромных подпоследовательностей. 2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j. 3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок. 😎 Решение:

public class Solution {
    public int countPalindromicSubsequences(String s) {
        int MOD = 1000000007;
        int n = s.length();
        int[][] dp = new int[n][n];

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

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    int l = i + 1, r = j - 1;
                    while (l <= r && s.charAt(l) != s.charAt(i)) l++;
                    while (l <= r && s.charAt(r) != s.charAt(j)) r--;
                    if (l > r) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
                    } else if (l == r) {
                        dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1];
                    }
                } else {
                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
                }
                dp[i][j] = (dp[i][j] + MOD) % MOD;
            }
        }

        return dp[0][n - 1];
    }
}

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

Офисные башни JOIS от MR Office в 5 мин от Москва-Сити JOIS - это современные башни класса А от нового бренда, объединяющего все офисные объекты MR Group. Проект премиального бизнес-центра включает две башни: 1) 43-этажный небоскреб MAST с офисами от 96 м² и возможностью приобретения офисных помещений по отдельности, а также целыми этажами или блоками 2) Башня CREDO представляет из себя единый офис площадью 22 000 м² Главные преимущества будущего проекта: ✨Ландшафтный парк площадью 1,3 Га и пешеходный маршрут более 2,3 км ✨Расположение в 5 минутах до ТТК и Москва-сити ✨3-уровневый подземный паркинг, рассчитанный на 400 машиномест ✨Отделка Shell&Core - оптимальное решение для создания эксклюзивного интерьера ✨Рассрочка 0% на приобретение коммерческой недвижимости Узнать больше Проектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО СЗ Л2-ДЕВЕЛОПМЕНТ #реклама mr-group.ru О рекламодателе

Задача: 1535. Find the Winner of an Array Game Сложность: medium Дан целочисленный массив arr из различных целых чисел и целое число k. Игра будет проводиться между первыми двумя элементами массива (т.е. arr[0] и arr[1]). В каждом раунде игры мы сравниваем arr[0] с arr[1], большее число побеждает и остается на позиции 0, а меньшее число перемещается в конец массива. Игра заканчивается, когда одно число выигрывает k подряд раундов. Верните число, которое выиграет игру. Гарантируется, что у игры будет победитель. Пример:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

👨‍💻 Алгоритм: 1⃣Инициализируйте maxElement как максимальный элемент в arr, queue как очередь с элементами массива, кроме первого, curr = arr[0] и winstreak = 0. 2⃣Пока очередь не пуста (или используйте бесконечный цикл), извлеките opponent из начала очереди. Если curr > opponent, добавьте opponent в конец очереди и увеличьте winstreak на 1. В противном случае добавьте curr в конец очереди, установите curr = opponent и winstreak = 1. 3⃣Если winstreak = k или curr = maxElement, верните curr. Код никогда не должен достигать этой точки, так как гарантированно есть победитель. Верните любое значение. 😎 Решение:

class Solution {
    public int getWinner(int[] arr, int k) {
        int maxElement = arr[0];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i < arr.length; i++) {
            maxElement = Math.max(maxElement, arr[i]);
            queue.offer(arr[i]);
        }
        
        int curr = arr[0];
        int winstreak = 0;
        
        while (!queue.isEmpty()) {
            int opponent = queue.poll();
            
            if (curr > opponent) {
                queue.offer(opponent);
                winstreak++;
            } else {
                queue.offer(curr);
                curr = opponent;
                winstreak = 1;
            }
            
            if (winstreak == k || curr == maxElement) {
                return curr;
            }
        }
        
        return -1;
    }
}

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

Задача: 720. Longest Word in Dictionary Сложность: medium Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова. Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

👨‍💻 Алгоритм: 1⃣Отсортируйте массив слов по длине и лексикографическому порядку. 2⃣Используйте множество для отслеживания слов, которые можно построить. 3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве. 😎 Решение:

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

public class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> validWords = new HashSet<>();
        validWords.add("");
        String longest = "";
        for (String word : words) {
            if (validWords.contains(word.substring(0, word.length() - 1))) {
                validWords.add(word);
                if (word.length() > longest.length()) {
                    longest = word;
                }
            }
        }
        return longest;
    }
}

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

Задача: 222. Count Complete Tree Nodes Сложность: easy Учитывая корень полного двоичного дерева, верните количество узлов в дереве. Согласно Википедии, в полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. Он может содержать от 1 до 2 в степени n узлов включительно на последнем уровне n. Разработайте алгоритм, который выполняется за время, меньшее, чем O(n). Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализация и проверка пустоты дерева Если дерево пустое, вернуть 0. Рассчитать глубину дерева d. 2⃣Поиск узлов на последнем уровне Использовать двоичный поиск, чтобы найти количество узлов на последнем уровне. Функция exists используется для проверки наличия узла по индексу. 3⃣Вычисление общего количества узлов Вернуть сумму узлов на всех уровнях, кроме последнего, и узлов на последнем уровне. 😎 Решение:

class Solution {
  public int computeDepth(TreeNode node) {
    int d = 0;
    while (node.left != null) {
      node = node.left;
      ++d;
    }
    return d;
  }

  public boolean exists(int idx, int d, TreeNode node) {
    int left = 0, right = (int)Math.pow(2, d) - 1;
    int pivot;
    for(int i = 0; i < d; ++i) {
      pivot = left + (right - left) / 2;
      if (idx <= pivot) {
        node = node.left;
        right = pivot;
      }
      else {
        node = node.right;
        left = pivot + 1;
      }
    }
    return node != null;
  }

  public int countNodes(TreeNode root) {
    if (root == null) return 0;

    int d = computeDepth(root);
    if (d == 0) return 1;

    int left = 1, right = (int)Math.pow(2, d) - 1;
    int pivot;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (exists(pivot, d, root)) left = pivot + 1;
      else right = pivot - 1;
    }

    return (int)Math.pow(2, d) - 1 + left;
  }
}

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

Курсы JAVA-разработки Гарантия ЗП от 120 000р в договоре Jаvа — это язык, на котором строятся банковские системы, мобильные приложения, крупные веб-сервисы и многое другое, а спрос на Jаvа-разработчиков стабильно высок. Благодаря кроссплатформенности и надежности, ты сможешь работать в любой сфере IТ — от финансов до Коммерческой отрасли.📊💰 Почему это работает?✨ - Минимальные вложения. - Тысячи человек уже в IТ. Наши выпускники работают в крутых компаниях: от стартапов до международных корпораций. - Наши менторы — это опытные разработчики, которые ежедневно работают в IТ и готовы делиться актуальными знаниями. P.S. Если всё ещё сомневаешься и думаешь что будет сложно — просто попробуй.😊 Мы берем на себя все риски: ты оплачиваешь основную стоимость обучения только после успешного трудоустройства — это закреплено в договоре. Подать заявку #реклама 16+ kata.academy О рекламодателе

Задача: 37. Sudoku Solver Сложность: hard Напишите программу для решения головоломки Судоку, заполнив пустые ячейки. Решение Судоку должно удовлетворять всем следующим правилам: Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждой строке. Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом столбце. Каждая из цифр от 1 до 9 должна встречаться ровно один раз в каждом из 9 подблоков 3x3 сетки. Символ '.' обозначает пустые ячейки. Пример:

Input: board = 
[["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
Output: 
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

👨‍💻 Алгоритм: 1⃣Теперь все готово для написания функции обратного поиска backtrack(row = 0, col = 0). Начните с верхней левой ячейки row = 0, col = 0. Продолжайте, пока не дойдете до первой свободной ячейки. 2⃣Итерируйте по числам от 1 до 9 и попробуйте поставить каждое число d в ячейку (row, col). Если число d еще не в текущей строке, столбце и блоке: Поместите d в ячейку (row, col). Запишите, что d теперь присутствует в текущей строке, столбце и блоке. 3⃣Если вы на последней ячейке row == 8, col == 8: Это означает, что судоку решено. В противном случае продолжайте размещать дальнейшие числа. Откат, если решение еще не найдено: удалите последнее число из ячейки (row, col). 😎 Решение:

import java.util.*;

class Solution {
    public void solveSudoku(char[][] board) {
        int n = 3, N = n * n;
        List<Map<Character, Integer>> track = new ArrayList<>(N * 3);
        for (int i = 0; i < N * 3; i++) track.add(new HashMap<>());

        for (int r = 0; r < N; r++) for (int c = 0; c < N; c++) 
            if (board[r][c] != '.') update(board, r, c, board[r][c], true, n, track);

        backtrack(board, 0, 0, n, N, track);
    }

    private boolean backtrack(char[][] board, int r, int c, int n, int N, List<Map<Character, Integer>> track) {
        if (c == N) { r++; c = 0; }
        if (r == N) return true;

        if (board[r][c] != '.') return backtrack(board, r, c + 1, n, N, track);

        for (char num = '1'; num <= '9'; num++) 
            if (canPlace(num, r, c, n, track)) {
                update(board, r, c, num, true, n, track);
                if (backtrack(board, r, c + 1, n, N, track)) return true;
                update(board, r, c, num, false, n, track);
            }

        return false;
    }

    private boolean canPlace(char num, int r, int c, int n, List<Map<Character, Integer>> track) {
        int idx = r / n * n + c / n;
        return track.get(r).getOrDefault(num, 0) == 0 && track.get(n + c).getOrDefault(num, 0) == 0 
            && track.get(2 * n + idx).getOrDefault(num, 0) == 0;
    }

    private void update(char[][] board, int r, int c, char num, boolean place, int n, List<Map<Character, Integer>> track) {
        int idx = r / n * n + c / n, delta = place ? 1 : -1;
        track.get(r).put(num, track.get(r).getOrDefault(num, 0) + delta);
        track.get(n + c).put(num, track.get(n + c).getOrDefault(num, 0) + delta);
        track.get(2 * n + idx).put(num, track.get(2 * n + idx).getOrDefault(num, 0) + delta);
        board[r][c] = place ? num : '.';
    }
}

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

Высшее образование дистанционно от 6700 ₽/мес. Поступи в Московский технологический институт в мае! — Высшее образование в московском вузе без выезда на сессии. — Полностью дистанционный онлайн-формат. — Обучайся дома, на работе, в путешествии. — Диплом государственного образца. — 73 направления и программы обучения. — Программа колледж + вуз без ЕГЭ. Скидка 10% на платное обучение при оплате за год. Подать заявку #реклама 16+ mti-vuz.ru О рекламодателе

Задача: 987. Vertical Order Traversal of a Binary Tree Сложность: medium Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным. Верните пересечение этих двух списков интервалов. Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b. Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3]. Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

👨‍💻 Алгоритм: 1⃣Инициализация указателей: Создать словарь для хранения узлов по их координатам (col, row). Создать очередь для обхода в ширину (BFS), содержащую начальную пару (root, (0, 0)). 2⃣Поиск пересечений: Выполнить BFS обход дерева. Для каждого узла сохранить его значение в словаре по ключу (col, row). Добавить левый потомок в очередь с координатами (row + 1, col - 1). Добавить правый потомок в очередь с координатами (row + 1, col + 1). 3⃣Возврат результата: Отсортировать ключи словаря по col и затем по row. Для каждого столбца, упорядочить узлы по row и значениям, и добавить их в результирующий список. 😎 Решение:

import java.util.*;

public class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<int[]>> colTable = new TreeMap<>();
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{root, 0, 0});
        
        while (!queue.isEmpty()) {
            int[] info = queue.poll();
            TreeNode node = (TreeNode) info[0];
            int row = info[1], col = info[2];
            
            colTable.putIfAbsent(col, new ArrayList<>());
            colTable.get(col).add(new int[]{row, node.val});
            
            if (node.left != null) {
                queue.offer(new int[]{node.left, row + 1, col - 1});
            }
            if (node.right != null) {
                queue.offer(new int[]{node.right, row + 1, col + 1});
            }
        }
        
        List<List<Integer>> result = new ArrayList<>();
        for (int col : colTable.keySet()) {
            Collections.sort(colTable.get(col), (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
            List<Integer> sortedCol = new ArrayList<>();
            for (int[] p : colTable.get(col)) {
                sortedCol.add(p[1]);
            }
            result.add(sortedCol);
        }
        
        return result;
    }
}

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

Задача: 120. Triangle Сложность: medium Дан массив в виде треугольника, верните минимальную сумму пути сверху вниз. На каждом шаге вы можете перейти к соседнему числу в строке ниже. Более формально, если вы находитесь на индексе i в текущей строке, вы можете перейти либо к индексу i, либо к индексу i + 1 в следующей строке. Пример:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

👨‍💻 Алгоритм: 1⃣Простейший способ реализации этого заключается в перезаписи входных данных, то есть в использовании алгоритма "на месте". В подходе 2 мы рассмотрим, как модифицировать алгоритм так, чтобы он не перезаписывал входные данные, но при этом не требовал более чем O(n) дополнительного пространства. 2⃣Когда этот алгоритм завершит свою работу, каждая ячейка (строка, столбец) входного треугольника будет перезаписана минимальной суммой пути от (0, 0) (вершины треугольника) до (строка, столбец) включительно. Совет на собеседовании: Алгоритмы "на месте" перезаписывают входные данные для экономии места, но иногда это может вызвать проблемы. Вот несколько ситуаций, когда алгоритм "на месте" может быть неуместен. 3⃣1. Алгоритму необходимо работать в многопоточной среде, без эксклюзивного доступа к массиву. Другим потокам может потребоваться читать массив тоже, и они могут не ожидать, что он будет изменен. 2. Даже если поток один, или у алгоритма есть эксклюзивный доступ к массиву во время выполнения, массив может потребоваться повторно использовать позже или другим потоком после освобождения блокировки. 😎 Решение:

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for (int row = 1; row < triangle.size(); row++) {
            for (int col = 0; col <= row; col++) {
                int smallestAbove = Integer.MAX_VALUE;
                if (col > 0) {
                    smallestAbove = triangle.get(row - 1).get(col - 1);
                }
                if (col < row) {
                    smallestAbove = Math.min(
                        smallestAbove,
                        triangle.get(row - 1).get(col)
                    );
                }
                int path = smallestAbove + triangle.get(row).get(col);
                triangle.get(row).set(col, path);
            }
        }
        return Collections.min(triangle.get(triangle.size() - 1));
    }
}

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

Задача: 1146. Snapshot Array Сложность: medium Реализуйте SnapshotArray, который поддерживает следующий интерфейс: SnapshotArray(int length) инициализирует структуру данных, похожую на массив, с заданной длиной. Изначально каждый элемент равен 0. void set(index, val) устанавливает элемент с заданным индексом равным val. int snap() делает снимок массива и возвращает snap_id: общее количество вызовов snap() минус 1. int get(index, snap_id) возвращает значение на заданном индексе в момент, когда мы сделали снимок с указанным snap_id. Пример:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

👨‍💻 Алгоритм: 1⃣Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0]. 2⃣Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index]. 3⃣Методы snap и get: Метод snap возвращает snap_id и увеличивает его на 1. Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1]. 😎 Решение:

class SnapshotArray {
    int snapId = 0;
    TreeMap<Integer, Integer>[] historyRecords;
    
    public SnapshotArray(int length) {
        historyRecords = new TreeMap[length];
        for (int i = 0; i < length; i++) {
            historyRecords[i] = new TreeMap<Integer, Integer>();
            historyRecords[i].put(0, 0);
        }
    }

    public void set(int index, int val) {
        historyRecords[index].put(snapId, val);
    }

    public int snap() {
        return snapId++;
    }

    public int get(int index, int snapId) {
        return historyRecords[index].floorEntry(snapId).getValue();
    }
}

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