Java | LeetCode

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

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true

👨‍💻 Алгоритм: 1⃣Если оба дерева пусты, они эквивалентны, вернуть true. Если одно дерево пустое, а другое нет, они не эквивалентны, вернуть false. 2⃣Если значения корней деревьев не совпадают, вернуть false. Проверить два условия: Левое поддерево первого дерева эквивалентно левому поддереву второго дерева и правое поддерево первого дерева эквивалентно правому поддереву второго дерева. Левое поддерево первого дерева эквивалентно правому поддереву второго дерева и правое поддерево первого дерева эквивалентно левому поддереву второго дерева. 3⃣Вернуть true, если выполняется хотя бы одно из этих условий. 😎 Решение:

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        if (root1.val != root2.val) return false;
        
        return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
               (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
    }
}

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

ТГУ и Wildberries&Russ открыли магистратуру по аналитике Прямо сейчас ты можешь подать заявку в магистратуру, которая откроет тебе дверь в топ-компании России! Это программа "Дата-аналитика для бизнеса" от Томского госуниверситета и Wildberries & Russ. Программа разработана специалистами одного из сильнейших вузов страны— ТГУ, поэтому в магистратуре - крепкий фундаментальный подход. В то же время студенты пройдут практику в Wildberries, где будущие аналитики научатся решать реальные задачи под руководством крутых наставников. В магистратуре можно выбрать одну из трёх специализаций: ⚡продуктовая аналитика, ⚡маркетинговая аналитика, ⚡BI-аналитика. Программа онлайн, но со всеми плюсами очного формата. Старт обучения — 18 сентября 2025 года. Выпускники получат сразу два диплома: магистра ТГУ и ДПО от партнера программы. Узнать больше #реклама 16+ ai.tsu.ru О рекламодателе

Задача: 340. Longest Substring with At Most K Distinct Characters Сложность: medium Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов. Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        int left = 0;
        int right = 0;
        Map<Character, Integer> charCount = new HashMap<>();
        int maxLength = 0;
        
        while (right < s.length()) {
            charCount.put(s.charAt(right), charCount.getOrDefault(s.charAt(right), 0) + 1);
            while (charCount.size() > k) {
                charCount.put(s.charAt(left), charCount.get(s.charAt(left)) - 1);
                if (charCount.get(s.charAt(left)) == 0) {
                    charCount.remove(s.charAt(left));
                }
                left++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        }
        
        return maxLength;
    }
}

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

Задача: 1217. Minimum Cost to Move Chips to The Same Position Сложность: easy У нас есть n фишек, где позиция i-й фишки равна position[i]. Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на: position[i] + 2 или position[i] - 2 с затратами = 0. position[i] + 1 или position[i] - 1 с затратами = 1. Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию. Пример:

Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at position  3 to position 2. Each move has cost = 1. The total cost = 2.

👨‍💻 Алгоритм: 1⃣Посчитать количество фишек на четных и нечетных позициях. 2⃣Сравнить количество фишек на четных и нечетных позициях. 3⃣Вернуть минимальное количество фишек как минимальную стоимость для перемещения всех фишек в одну позицию. 😎 Решение:

class Solution {
    public int minCostToMoveChips(int[] position) {
        int even_cnt = 0;
        int odd_cnt = 0;
        for (int i : position) {
            if (i % 2 == 0) {
                even_cnt++;
            } else {
                odd_cnt++;
            }
        }
        return Math.min(odd_cnt, even_cnt);
    }
}

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

Виртуальная инфраструктура с GPU Мы открыли для тестирования новый сервис «Виртуальная инфраструктура с GPU» ⚡Первыми на рынке запускаем это решение с инновационными NVIDIA H200. В составе «Публичного облака» услуга будет доступна в двух вариантах: ✅ виртуальные машины; ✅ Linux-контейнеры с GPU на базе NVIDIA H200. Чтобы протестировать флагманский сервис прямо сейчас, напишите нам на почту. Попробовать #реклама 16+ cloud.rt.ru О рекламодателе

Задача: 1259. Handshakes That Don't Cross Сложность: hard Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически. Пример:

Input: numPeople = 4
Output: 2

👨‍💻 Алгоритм: 1⃣Определим массив для хранения каталановых чисел. 2⃣Заполним массив каталановых чисел с помощью рекуррентной формулы. 3⃣Вернем 𝐶𝑛𝑢𝑚𝑃𝑒𝑜𝑝𝑙𝑒/2C. 😎 Решение:

public class Solution {
    public int numHandshakes(int numPeople) {
        int n = numPeople / 2;
        int[] catalan = new int[n + 1];
        catalan[0] = 1;

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

        return catalan[n];
    }
}

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

Корпоративное питание в офис. Яндекс Go для бизнеса Больше не нужно думать, чем кормить сотрудников. Вы устанавливаете лимиты - сотрудники сами выбирают еду в приложении. Вы получаете все отчеты. Никаких дополнительных комиссий и расходов. Узнать больше #реклама 16+ business.go.yandex О рекламодателе Реклама на Яндексе

Задача: 737. Sentence Similarity II Сложность: medium Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"]. Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи. Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

👨‍💻 Алгоритм: 1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false. 2⃣Построить граф схожести слов с использованием словаря. 3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях. 😎 Решение:

import java.util.*;

public class Solution {
    public boolean areSentencesSimilar(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
        if (sentence1.length != sentence2.length) {
            return false;
        }
        
        Map<String, List<String>> graph = new HashMap<>();
        for (List<String> pair : similarPairs) {
            graph.computeIfAbsent(pair.get(0), k -> new ArrayList<>()).add(pair.get(1));
            graph.computeIfAbsent(pair.get(1), k -> new ArrayList<>()).add(pair.get(0));
        }
        
        for (int i = 0; i < sentence1.length; i++) {
            if (!sentence1[i].equals(sentence2[i]) && !dfs(sentence1[i], sentence2[i], graph, new HashSet<>())) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean dfs(String word1, String word2, Map<String, List<String>> graph, Set<String> visited) {
        if (word1.equals(word2)) {
            return true;
        }
        visited.add(word1);
        for (String neighbor : graph.getOrDefault(word1, Collections.emptyList())) {
            if (!visited.contains(neighbor) && dfs(neighbor, word2, graph, visited)) {
                return true;
            }
        }
        return false;
    }
}

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

⚡️Хотите стать Android-разработчиком и создавать масштабируемые мобильные приложения с нуля? Курс «Android Developer» идеален для новичков, которые хотят попасть в IT, а также для тестировщиков и сисадминов, желающих перейти в разработку. За 10 месяцев обучения вы освоите Kotlin, научитесь разрабатывать приложения на Android SDK, работать с фреймворками Dagger2, RxJava и Jetpack Compose, а также освоите тестирование и CI/CD. Мы научим вас проектировать многомодульные архитектуры, работать с базами данных (Room, DataStore), создавать UI, использовать современные фреймворки и оптимизировать приложения. Все это с реальными задачами, которые помогут вам построить сильное портфолио и стать успешным разработчиком. 📲Оставьте заявку и получите скидку на обучение: https://otus.pw/UMbu/ Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

СберМобайл - 50 Гб и 300 минут за 390 рублей! СберМобайл - дарим 30 Гб каждый месяц при переносе номера. Безлимит на мессенджеры. Защита от спама. eSIM за 5 минут. Подключайтесь. Перейти на сайт #реклама sbermobile.ru О рекламодателе

Задача: 502. IPO Сложность: hard Предположим, что LeetCode скоро начнет свое IPO. Чтобы продать свои акции по хорошей цене венчурным капиталистам, LeetCode хочет выполнить несколько проектов для увеличения своего капитала перед IPO. Поскольку у компании ограниченные ресурсы, она может завершить не более k различных проектов до IPO. Помогите LeetCode разработать лучший способ максимизации общего капитала после завершения не более k различных проектов. Вам дано n проектов, где i-й проект имеет чистую прибыль profits[i] и требует минимального капитала capital[i] для его начала. Изначально у вас есть капитал w. Когда вы завершаете проект, вы получаете его чистую прибыль, и эта прибыль добавляется к вашему общему капиталу. Выберите список из не более чем k различных проектов из данных, чтобы максимально увеличить ваш конечный капитал, и верните окончательно максимизированный капитал. Ответ гарантированно поместится в 32-битное целое число со знаком. Пример:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

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

class Solution {
    class Project implements Comparable<Project> {
        int capital, profit;

        public Project(int capital, int profit) {
            this.capital = capital;
            this.profit = profit;
        }

        public int compareTo(Project project) {
            return capital - project.capital;
        }
    }

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        Project[] projects = new Project[n];
        for (int i = 0; i < n; i++) {
            projects[i] = new Project(capital[i], profits[i]);
        }
        Arrays.sort(projects);
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(n, Collections.reverseOrder());
        int ptr = 0;
        for (int i = 0; i < k; i++) {
            while (ptr < n && projects[ptr].capital <= w) {
                q.add(projects[ptr++].profit);
            }
            if (q.isEmpty()) {
                break;
            }
            w += q.poll();
        }
        return w;
    }
}

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

Задача: 73. Set Matrix Zeroes Сложность: medium Дана матрица размером m×n, состоящая из целых чисел. Если элемент матрицы равен 0, установите в 0 все элементы его строки и столбца. Необходимо выполнить это действие на месте, не используя дополнительное пространство для другой матрицы. Пример:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

👨‍💻 Алгоритм: 1⃣Мы перебираем матрицу и отмечаем первую ячейку строки i и первую ячейку столбца j, если условие в приведенном выше псевдокоде выполняется, т.е. если cell[i][j] == 0. 2⃣Первая ячейка строки и столбца для первой строки и первого столбца совпадают, т.е. cell[0][0]. Поэтому мы используем дополнительную переменную, чтобы узнать, был ли отмечен первый столбец, а cell[0][0] используется для того же для первой строки. 3⃣Теперь мы перебираем исходную матрицу, начиная со второй строки и второго столбца, т.е. с matrix[1][1]. Для каждой ячейки мы проверяем, были ли ранее отмечены строка r или столбец c, проверяя соответствующую первую ячейку строки или первую ячейку столбца. Если любая из них была отмечена, мы устанавливаем значение в ячейке на 0. Обратите внимание, что первая строка и первый столбец служат как row_set и column_set, которые мы использовали в первом подходе. Затем мы проверяем, равна ли cell[0][0] нулю, если это так, мы отмечаем первую строку как ноль. И, наконец, если первый столбец был отмечен, мы делаем все записи в нем нулевыми. 😎 Решение:

class Solution {
    public void setZeroes(int[][] matrix) {
        Boolean isCol = false;
        int R = matrix.length;
        int C = matrix[0].length;

        for (int i = 0; i < R; i++) {
            if (matrix[i][0] == 0) {
                isCol = true;
            }
            for (int j = 1; j < C; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

        for (int i = 1; i < R; i++) {
            for (int j = 1; j < C; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        if (matrix[0][0] == 0) {
            for (int j = 0; j < C; j++) {
                matrix[0][j] = 0;
            }
        }

        if (isCol) {
            for (int i = 0; i < R; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

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

Аптечка финансового директора ⚡30 проверенных инструментов, которые должны быть всегда под рукой у финансиста. Все эти материалы можно получить бесплатно 📊 13 Эксель-моделей и форм для финансового анализа - Методичка. Что ответить собственнику на вопросы о деньгах компании - Инструкция по выгрузке отчетов из 1С - 12 Промптов для ИИ под основные финансовые задачи - Чек-лист перед защитой отчетности - Шаблон Резюме, которое точно понравится рекрутеру - 15 практических схем налоговой оптимизации 📞 Закрытый телеграм-чат с топами и вакансиями - среди участников телеграм-канала финдиры Газпром Нефть, Азбука Вкуса, Подружка, АндерСон, и 3000 других ✅ Чтобы забрать инструменты в работу, вам нужно подписаться на канал Финансовый директор Скачать #реклама 16+ click.tgtrack.ru О рекламодателе

Задача: 1232. Check If It Is a Straight Line Сложность: easy Вам дан массив координат, coordinates[i] = [x, y], где [x, y] - координаты точки. Проверьте, образуют ли эти точки прямую линию в плоскости XY. Пример:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

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

public class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        int x0 = coordinates[0][0], y0 = coordinates[0][1];
        int x1 = coordinates[1][0], y1 = coordinates[1][1];
        
        for (int[] point : coordinates) {
            int x = point[0], y = point[1];
            if ((x1 - x0) * (y - y0) != (y1 - y0) * (x - x0)) {
                return false;
            }
        }
        return true;
    }
}

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

Задача: CodeTestcaseTest ResultTest Result1187. Make Array Strictly Increasing Сложность: hard Даны два целочисленных массива arr1 и arr2. Верните минимальное количество операций (возможно, ноль), необходимых для того, чтобы сделать arr1 строго возрастающим. В одной операции вы можете выбрать два индекса 0 <= i < arr1.length и 0 <= j < arr2.length и выполнить присваивание arr1[i] = arr2[j]. Если нет способа сделать arr1 строго возрастающим, верните -1. Пример:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

👨‍💻 Алгоритм: 1⃣Сначала отсортируйте массив arr2 и инициализируйте хэш-таблицу dp для хранения промежуточных результатов. Определите функцию dfs(i, prev), которая вычисляет минимальное количество операций для сортировки массива arr1, начиная с индекса i, при условии, что предыдущий элемент равен prev. Если результат для (i, prev) уже существует в dp, то просто верните сохраненное значение. 2⃣Внутри функции dfs инициализируйте переменную cost значением float('inf'). Если arr1[i] больше, чем prev, обновите значение cost результатом вызова dfs(i + 1, arr1[i]). Используйте бинарный поиск, чтобы найти индекс idx наименьшего значения в arr2, которое больше prev. Если такой индекс существует, обновите значение cost результатом минимального значения между текущим значением cost и 1 + dfs(i + 1, arr2[idx]). 3⃣После всех вычислений обновите dp[(i, prev)] значением cost и верните cost. В конце вызовите dfs(0, -1) и верните его значение, если оно не равно float('inf'); в противном случае верните -1. 😎 Решение:

class Solution { 
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        Arrays.sort(arr2);
        
        int answer = dfs(0, -1, arr1, arr2);
        
        return answer < 2_001 ? answer : -1;
    }
    
    Map<Pair<Integer, Integer>, Integer> dp = new HashMap<>();
    private int dfs(int i, int prev, int[] arr1, int[] arr2) {
        if (i == arr1.length) {
            return 0;
        }
        if (dp.containsKey(new Pair<>(i, prev))) {
            return dp.get(new Pair<>(i, prev));
        }

        int cost = 2_001;

        // If arr1[i] is already greater than prev, we can leave it be.
        if (arr1[i] > prev) {
            cost = dfs(i + 1, arr1[i], arr1, arr2);
        }

        // Find a replacement with the smallest value in arr2.
        int idx = bisectRight(arr2, prev);

        // Replace arr1[i], with a cost of 1 operation.
        if (idx < arr2.length) {
            cost = Math.min(cost, 1 + dfs(i + 1, arr2[idx], arr1, arr2));
        }

        dp.put(new Pair<>(i, prev), cost);
        return cost;
    }
    
    private static int bisectRight(int[] arr, int value) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] <= value) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    } 
}

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

Современная магистратура от Центрального университета Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 4 офлайн программы по востребованным направлениям ИТ - Онлайн-программа по машинному обучению - 300 мест с грантами до 1,2 млн руб. - Вечерние занятия и учеба по выходным — удобно совмещать с работой - Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса - Возможность стажировок и трудоустройства в ведущих компаниях - Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 1029. Two City Scheduling Сложность: medium Компания планирует провести интервью с 2n людьми. Учитывая массив costs, где costs[i] = [aCosti, bCosti], стоимость перелета i-го человека в город a равна aCosti, а стоимость перелета i-го человека в город b равна bCosti. Выведите минимальную стоимость перелета каждого человека в город, чтобы в каждый город прибыло ровно n человек. Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

public class Solution {
    public int twoCitySchedCost(int[][] costs) {
        Arrays.sort(costs, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));
        int totalCost = 0;
        int n = costs.length / 2;
        for (int i = 0; i < n; i++) {
            totalCost += costs[i][0];
            totalCost += costs[i + n][1];
        }
        return totalCost;
    }
}

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

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 1218. Longest Arithmetic Subsequence of Given Difference Сложность: medium Дан массив целых чисел arr и целое число difference. Верните длину самой длинной подпоследовательности в arr, которая является арифметической последовательностью, так что разница между соседними элементами в подпоследовательности равна difference. Подпоследовательность — это последовательность, которую можно получить из arr, удалив некоторые или ни одного элемента, не меняя порядок оставшихся элементов. Пример:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

👨‍💻 Алгоритм: 1⃣Инициализируйте пустой хеш-таблицу dp и установите answer = 1. 2⃣Итеративно обработайте массив arr. Для каждого элемента arr[i]: Вычислите before_a, максимальную длину арифметической подпоследовательности, заканчивающейся на arr[i] - difference: - если arr[i] - difference существует в dp, установите before_a = dp[arr[i] - difference]. - в противном случае, установите before_a = 0. Установите dp[arr[i]] = before_a + 1, обновите answer как answer = max(answer, dp[arr[i]]). 3⃣Верните answer после завершения итерации. 😎 Решение:

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        Map<Integer, Integer> dp = new HashMap<>();
        int answer = 1;
        
        for (int a : arr) {
            int beforeA = dp.getOrDefault(a - difference, 0);
            dp.put(a, beforeA + 1);
            answer = Math.max(answer, dp.get(a));
        }
        
        return answer;
    }
}

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе