Java | LeetCode

Курсы 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();
    }
}

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

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 368. Largest Divisible Subset Сложность: medium Дан набор различных положительных целых чисел nums. Вернуть наибольшее подмножество answer, такое что каждая пара (answer[i], answer[j]) элементов в этом подмножестве удовлетворяет условию: answer[i] % answer[j] == 0, или answer[j] % answer[i] == 0 Если существует несколько решений, вернуть любое из них. Пример:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

👨‍💻 Алгоритм: 1⃣Если число 8 может быть разделено на элемент X_i, то добавив число 8 к EDS(X_i), мы получим еще одно делимое подмножество, которое заканчивается на 8, согласно нашему следствию I. И это новое подмножество является потенциальным значением для EDS(8). Например, поскольку 8 % 2 == 0, то {2,8} может быть конечным значением для EDS(8), и аналогично для подмножества {2,4,8}, полученного из EDS(4). 2⃣Если число 8 не может быть разделено на элемент X_i, то можно быть уверенным, что значение EDS(X_i) не повлияет на EDS(8), согласно определению делимого подмножества. Например, подмножество EDS(7)={7} не имеет влияния на EDS(8). 3⃣Затем мы выбираем наибольшие новые подмножества, которые мы формируем с помощью EDS(X_i). В частности, подмножество {8} является допустимым кандидатом для EDS(8). И в гипотетическом случае, когда 8 не может быть разделено ни на один из предыдущих элементов, мы бы имели EDS(8)={8}. 😎 Решение:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        if (n == 0) return new ArrayList<>();

        Arrays.sort(nums);
        List<List<Integer>> EDS = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            EDS.add(new ArrayList<>());
        }

        for (int i = 0; i < n; i++) {
            List<Integer> maxSubset = new ArrayList<>();
            for (int k = 0; k < i; k++) {
                if (nums[i] % nums[k] == 0 && maxSubset.size() < EDS.get(k).size()) {
                    maxSubset = EDS.get(k);
                }
            }
            EDS.get(i).addAll(maxSubset);
            EDS.get(i).add(nums[i]);
        }

        List<Integer> ret = new ArrayList<>();
        for (List<Integer> subset : EDS) {
            if (ret.size() < subset.size()) {
                ret = subset;
            }
        }
        return ret;
    }
}

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

Задача: 1427. Perform String Shifts Сложность: easy Вам дана строка s, содержащая строчные английские буквы, и матрица shift, где shift[i] = [directioni, amounti]: directioni может быть 0 (для сдвига влево) или 1 (для сдвига вправо). amounti - это количество, на которое строка s должна быть сдвинута. Сдвиг влево на 1 означает удаление первого символа строки s и добавление его в конец. Аналогично, сдвиг вправо на 1 означает удаление последнего символа строки s и добавление его в начало. Верните итоговую строку после всех операций. Пример:

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation: 
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

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

class Solution {
  public String stringShift(String string, int[][] shift) {
    
    int[] overallShifts = new int[2];
    for (int[] move : shift) {
      overallShifts[move[0]] += move[1];
    }
    int leftShifts = overallShifts[0];
    int rightShifts = overallShifts[1];
      
    int len = string.length();
    if (leftShifts > rightShifts) {
      leftShifts = (leftShifts - rightShifts) % len;
      string = string.substring(leftShifts) + string.substring(0, leftShifts);
    }
    else if (rightShifts > leftShifts) {
      rightShifts = (rightShifts - leftShifts) % len;
      string = string.substring(len - rightShifts) + string.substring(0, len - rightShifts);
    }
    
    return string;
  }
}

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

Задача: 98. Validate Binary Search Tree Сложность: medium Дан корень бинарного дерева. Определите, является ли это дерево допустимым бинарным деревом поиска (BST). Допустимое BST определяется следующим образом: Левое поддерево узла содержит только узлы с ключами, меньшими, чем ключ узла. Правое поддерево узла содержит только узлы с ключами, большими, чем ключ узла. Оба поддерева — левое и правое — также должны быть бинарными деревьями поиска. Пример:

Input: root = [2,1,3]
Output: true

👨‍💻 Алгоритм: 1⃣Давайте воспользуемся порядком узлов при симметричном обходе (inorder traversal): Левый -> Узел -> Правый. Здесь узлы перечисляются в порядке их посещения, и вы можете следовать последовательности 1-2-3-4-5 для сравнения различных стратегий. Порядок "Левый -> Узел -> Правый" при симметричном обходе означает, что для BST каждый элемент должен быть меньше следующего. 2⃣Следовательно, алгоритм с временной сложностью O(N) и пространственной сложностью O(N) может быть простым: Вычислить список симметричного обхода inorder. Проверить, меньше ли каждый элемент в списке inorder следующего за ним. 3⃣Нужно ли сохранять весь список симметричного обхода? На самом деле, нет. Достаточно последнего добавленного элемента inorder, чтобы на каждом шаге убедиться, что дерево является BST (или нет). Следовательно, можно объединить оба шага в один и уменьшить используемое пространство. 😎 Решение:

class Solution {
    private Integer prev;

    public boolean isValidBST(TreeNode root) {
        prev = null;
        return inorder(root);
    }

    private boolean inorder(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!inorder(root.left)) {
            return false;
        }
        if (prev != null && root.val <= prev) {
            return false;
        }
        prev = root.val;
        return inorder(root.right);
    }
}

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

Получи грант на обучение в Центральном университете Получи несгораемый грант до 2 800 000 ₽ на учебу в бакалавриате Центрального университета. Грант покрывает до 100% стоимости обучения. Сумма гранта не уменьшается, а может увеличиться за дополнительные достижения и успехи в учебе. Участвуй в отборе! Для учеников 10-х и 11-х классов, колледжей. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 104. Maximum Depth of Binary Tree Сложность: easy Дан корень бинарного дерева, верните его максимальную глубину. Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла. Пример:

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

👨‍💻 Алгоритм: 1⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS). 2⃣Для данной задачи подойдет несколько способов. 3⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии. 😎 Решение:

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int left_height = maxDepth(root.left);
            int right_height = maxDepth(root.right);
            return java.lang.Math.max(left_height, right_height) + 1;
        }
    }
}

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

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

Задача: 1519. Number of Nodes in the Sub-Tree With the Same Label Сложность: medium Вам дано дерево (т.е. связный неориентированный граф без циклов), состоящее из n узлов, пронумерованных от 0 до n - 1, и ровно n - 1 ребра. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая является строчной буквой, указанной в строке labels (т.е. узел с номером i имеет метку labels[i]). Массив edges дан в форме edges[i] = [ai, bi], что означает, что существует ребро между узлами ai и bi в дереве. Верните массив размера n, где ans[i] — это количество узлов в поддереве узла i, которые имеют ту же метку, что и узел i. Поддерево дерева T — это дерево, состоящее из узла в T и всех его дочерних узлов. Пример:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

👨‍💻 Алгоритм: 1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X. 2⃣Инициализируйте массив ans, хранящий ответ для каждого узла, и заполните его нулями. 3⃣Начните обход в глубину (DFS). 😎 Решение:

class Solution {
    public int[] dfs(int node, int parent, Map<Integer, List<Integer>> adj, char[] labels, int[] ans) {
        int[] nodeCounts = new int[26];
        nodeCounts[labels[node] - 'a'] = 1;

        if (!adj.containsKey(node))
            return nodeCounts;

        for (int child : adj.get(node)) {
            if (child == parent) {
                continue;
            }
            int[] childCounts = dfs(child, node, adj, labels, ans);
            for (int i = 0; i < 26; i++) {
                nodeCounts[i] += childCounts[i];
            }
        }

        ans[node] = nodeCounts[labels[node] - 'a'];
        return nodeCounts;
    }

    public int[] countSubTrees(int n, int[][] edges, String labels) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1];
            adj.computeIfAbsent(a, value -> new ArrayList<>()).add(b);
            adj.computeIfAbsent(b, value -> new ArrayList<>()).add(a);
        }

        int[] ans = new int[n];
        char[] label = labels.toCharArray();
        dfs(0, -1, adj, label, ans);
        return ans;
    }
}

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

Задача: 219. Contains Duplicate II Сложность: easy Дан массив целых чисел nums и целое число k. Верните true, если в массиве существуют два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k. Пример:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

👨‍💻 Алгоритм: 1⃣Создайте пустое множество set. 2⃣Пройдитесь по массиву nums: Если текущий элемент уже есть в множестве, верните true. Добавьте текущий элемент в множество. Если размер множества больше k, удалите элемент, который был добавлен k шагов назад. 3⃣Если не найдены дублирующиеся элементы на расстоянии k или менее, верните false. 😎 Решение:

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; ++i) {
        if (set.contains(nums[i])) return true;
        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}

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

Сколько приложений нужно вашей команде для работы? Всего один сервис — Битрикс24! А внутри десятки инструментов для совместной работы и бизнеса. Читайте подробнее в карточках. Регистрируйтесь сейчас, чтобы забрать их все себе бесплатно😊 Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе

Задача: 674. Longest Continuous Increasing Subsequence Сложность: easy Дан неотсортированный массив целых чисел nums, верните длину самой длинной непрерывной возрастающей подпоследовательности (т.е. подмассива). Подпоследовательность должна быть строго возрастающей. Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1]. Пример:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

👨‍💻 Алгоритм: 1⃣Каждая (непрерывная) возрастающая подпоследовательность не пересекается, и граница каждой такой подпоследовательности возникает, когда nums[i-1] >= nums[i]. В этом случае начинается новая возрастающая подпоследовательность с nums[i], и мы сохраняем такой i в переменной anchor. 2⃣Например, если nums = [7, 8, 9, 1, 2, 3], то anchor начинается с 0 (nums[anchor] = 7) и затем устанавливается на anchor = 3 (nums[anchor] = 1). Независимо от значения anchor, мы записываем кандидата на ответ длиной i - anchor + 1, длина подмассива nums[anchor], nums[anchor+1], ..., nums[i], и наш ответ обновляется соответствующим образом. 3⃣Возвращаем максимальную длину найденной непрерывной возрастающей подпоследовательности. 😎 Решение:

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ans = 0, anchor = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (i > 0 && nums[i-1] >= nums[i]) anchor = i;
            ans = Math.max(ans, i - anchor + 1);
        }
        return ans;
    }
}

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

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

Задача: 437. Path Sum III Сложность: medium Дан корень бинарного дерева и целое число targetSum, вернуть количество путей, где сумма значений вдоль пути равна targetSum. Путь не обязательно должен начинаться или заканчиваться в корне или на листе, но он должен идти вниз (т.е. перемещаться только от родительских узлов к дочерним). Пример:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

👨‍💻 Алгоритм: 1⃣Инициализируем счетчик путей в дереве count = 0 и хеш-таблицу h, где ключ - это префиксная сумма, а значение - сколько раз она встречалась. Выполним рекурсивный обход дерева в порядке preorder: узел -> левый -> правый. Функция preorder(node: TreeNode, curr_sum: int) принимает два аргумента: узел дерева и префиксную сумму перед этим узлом. Чтобы запустить рекурсию, вызовем preorder(root, 0). 2⃣Сначала обновим текущую префиксную сумму, добавив значение текущего узла: curr_sum += node.val. Теперь можно обновить счетчик. Рассмотрим две ситуации. В первой ситуации путь в дереве с целевой суммой начинается с корня. Это означает, что текущая префиксная сумма равна целевой сумме curr_sum == k, поэтому увеличиваем счетчик на 1: count += 1. Во второй ситуации путь с целевой суммой начинается где-то ниже. Это означает, что нужно добавить к счетчику количество раз, когда мы видели префиксную сумму curr_sum - target: count += h[curr_sum - target]. 3⃣Логика проста: текущая префиксная сумма - это curr_sum, а несколько элементов назад префиксная сумма была curr_sum - target. Все элементы между ними суммируются до curr_sum - (curr_sum - target) = target. Теперь обновим хеш-таблицу: h[curr_sum] += 1. Проанализируем левое и правое поддеревья: preorder(node.left, curr_sum), preorder(node.right, curr_sum). После обработки текущего поддерева удалим текущую префиксную сумму из хеш-таблицы, чтобы не смешивать параллельные поддеревья: h[curr_sum] -= 1. Когда обход в порядке preorder завершен, счетчик обновлен. Вернем его. 😎 Решение:

class Solution {
    public int pathSum(TreeNode root, int sum) {
        final int[] count = {0};
        final int k = sum;
        Map<Integer, Integer> h = new HashMap<>();
        
        preorder(root, 0, h, count, k);
        
        return count[0];
    }
    
    private void preorder(TreeNode node, int currSum, Map<Integer, Integer> h, int[] count, int k) {
        if (node == null) return;
        
        currSum += node.val;
        
        if (currSum == k) {
            count[0]++;
        }
        
        count[0] += h.getOrDefault(currSum - k, 0);
        
        h.put(currSum, h.getOrDefault(currSum, 0) + 1);
        
        preorder(node.left, currSum, h, count, k);
        preorder(node.right, currSum, h, count, k);
        
        h.put(currSum, h.get(currSum) - 1);
    }
}

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

Бесплатный курс по дизайну в FIGMA Онлайн-программа с наставником и чатом. Осторожно! 80% практики. По результату обучения у вас будет портфолио из нескольких работ. Сертификат о прохождении курса. Возможность пройти полное обучение и получить гарантированное трудоустройство! Учитесь дизайну у профессионалов. Переходи по кнопки: "Узнать больше" и начинай свое обучение. Доступ 0 руб. Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе