Java | LeetCode

Обучение по специальности «Финансы» в МБЭПК Учись у профессионалов: 80% наших преподавателей — кандидаты и доктора наук! Узнать больше #реклама 16+ online.apk-college.ru О рекламодателе

Задача: 621. Task Scheduler Сложность: medium Вам дан массив задач процессора, каждая из которых представлена буквами от A до Z, и время охлаждения, n. Каждый цикл или интервал позволяет завершить одну задачу. Задачи могут быть выполнены в любом порядке, но есть ограничение: одинаковые задачи должны быть разделены не менее чем n интервалами из-за времени охлаждения. Верните минимальное количество интервалов, необходимое для выполнения всех задач. Пример:

    
        Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8{}
    

👨‍💻 Алгоритм: 1⃣Подсчитайте количество каждой задачи и найдите максимальное количество вхождений (maxFreq). 2⃣Вычислите количество интервалов, необходимых для задач с maxFreq: (maxFreq - 1) * (n + 1) + countMaxFreq, где countMaxFreq - количество задач, имеющих maxFreq. 3⃣Верните максимум между вычисленным значением и длиной массива задач, поскольку некоторые задачи могут заполнять интервал до n. 😎 Решение:

    
        import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> taskCounts = new HashMap<>();
        for (char task : tasks) {
            taskCounts.put(task, taskCounts.getOrDefault(task, 0) + 1);
        }
        
        int maxFreq = taskCounts.values().stream().max(Integer::compare).get();
        int countMaxFreq = (int) taskCounts.values().stream().filter(count -> count == maxFreq).count();
        
        return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + countMaxFreq);
    }
}{}
    

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

Задача: 506. Relative Ranks Сложность: easy Вам дан целочисленный массив score размером n, где score[i] — это результат i-го спортсмена на соревновании. Все результаты гарантированно уникальны. Спортсмены размещаются на основе своих результатов: спортсмен, занявший 1-е место, имеет наивысший результат, спортсмен, занявший 2-е место, имеет второй по величине результат и так далее. Размещение каждого спортсмена определяет его ранг: Ранг спортсмена, занявшего 1-е место, — "Gold Medal". Ранг спортсмена, занявшего 2-е место, — "Silver Medal". Ранг спортсмена, занявшего 3-е место, — "Bronze Medal". Для спортсменов, занявших с 4-го по n-е место, их ранг соответствует их номеру в размещении (т.е. ранг спортсмена, занявшего x-е место, — "x"). Верните массив answer размером n, где answer[i] — это ранг i-го спортсмена. Пример:

    
        Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].{}
    

👨‍💻 Алгоритм: 1⃣Инициализация и нахождение максимального значения Инициализируйте переменную N длиной массива score. Определите функцию findMax, которая находит максимальный балл в массиве score. 2⃣Создание вспомогательных структур Инициализируйте массив scoreToIndex размером M + 1, где M — это максимальное значение в массиве score. Заполните scoreToIndex таким образом, чтобы для каждого score[i] его индекс сохранялся в scoreToIndex[score[i]]. 3⃣Присваивание рангов и формирование ответа Создайте массив rank для хранения рангов спортсменов. Используйте цикл для присваивания медалей и рангов в зависимости от значений в scoreToIndex, начиная с наибольшего. 😎 Решение:

    
        class Solution {
    private int findMax(int[] score) {
        int maxScore = 0;
        for (int s : score) {
            if (s > maxScore) {
                maxScore = s;
            }
        }
        return maxScore;
    }

    public String[] findRelativeRanks(int[] score) {
        int N = score.length;

        int M = findMax(score);
        int[] scoreToIndex = new int[M + 1];
        for (int i = 0; i < N; i++) {
            scoreToIndex[score[i]] = i + 1;
        }

        final String[] MEDALS = {"Gold Medal", "Silver Medal", "Bronze Medal"};

        String[] rank = new String[N];
        int place = 1;
        for (int i = M; i >= 0; i--) {
            if (scoreToIndex[i] != 0) {
                int originalIndex = scoreToIndex[i] - 1;
                if (place < 4) {
                    rank[originalIndex] = MEDALS[place - 1];
                } else {
                    rank[originalIndex] = String.valueOf(place);
                }
                place++;
            }
        }
        return rank;
    }
}{}
    

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

Задача: 1023. Camelcase Matching Сложность: medium Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа. Пример:

    
        Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]{}
    

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте массив answer для хранения результатов соответствия каждого запроса шаблону. 2⃣Проверка каждого запроса: Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу. Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса. 3⃣Возврат результата: Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false. Верните массив answer. 😎 Решение:

    
        public class Solution {
    public boolean[] camelMatch(String[] queries, String pattern) {
        boolean matches(String query, String pattern) {
            int i = 0, j = 0;
            while (i < query.length()) {
                if (j < pattern.length() && query.charAt(i) == pattern.charAt(j)) {
                    j++;
                } else if (Character.isUpperCase(query.charAt(i))) {
                    return false;
                }
                i++;
            }
            return j == pattern.length();
        }
        
        boolean[] answer = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            answer[i] = matches(queries[i], pattern);
        }
        
        return answer;
    }
}{}
    

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

Задача: 1055. Shortest Way to Form String Сложность: medium Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1. Пример:

    
        Input: source = "abc", target = "abcbc"
Output: 2{}
    

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

    
        public class Solution {
    public int minSubsequences(String source, String target) {
        int subsequencesCount = 0;
        int targetIndex = 0;

        while (targetIndex < target.length()) {
            int sourceIndex = 0;
            subsequencesCount++;
            int startIndex = targetIndex;

            while (sourceIndex < source.length() && targetIndex < target.length()) {
                if (source.charAt(sourceIndex) == target.charAt(targetIndex)) {
                    targetIndex++;
                }
                sourceIndex++;
            }

            if (targetIndex == startIndex) {
                return -1;
            }
        }

        return subsequencesCount;
    }
}{}
    

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

Задача: 919. Complete Binary Tree Inserter Сложность: medium Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен, а все узлы расположены как можно дальше влево. Разработайте алгоритм вставки нового узла в полное двоичное дерево, сохраняя его полным после вставки. Реализуйте класс CBTInserter: CBTInserter(TreeNode root) Инициализирует структуру данных корнем полного бинарного дерева. int insert(int v) Вставляет TreeNode в дерево со значением Node.val == val так, что дерево остается полным, и возвращает значение родителя вставленного TreeNode. TreeNode get_root() Возвращает корневой узел дерева. Пример:

    
        Input
["CBTInserter", "insert", "insert", "get_root"]
[[[1, 2]], [3], [4], []]
Output
[null, 1, 2, [1, 2, 3, 4]]{}
    

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

    
        import java.util.*;

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

class CBTInserter {
    private TreeNode root;
    private Queue<TreeNode> deque;

    public CBTInserter(TreeNode root) {
        this.root = root;
        this.deque = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left == null || node.right == null) {
                deque.add(node);
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    public int insert(int v) {
        TreeNode node = deque.peek();
        TreeNode newNode = new TreeNode(v);
        if (node.left == null) {
            node.left = newNode;
        } else {
            node.right = newNode;
            deque.poll();
        }
        deque.add(newNode);
        return node.val;
    }

    public TreeNode get_root() {
        return root;
    }
}{}
    

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

Задача: 1273. Delete Tree Nodes Сложность: medium Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве. Пример:

    
        Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2{}
    

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

    
        import java.util.*;

public class Solution {
    public int deleteTreeNodes(int nodes, int[] parent, int[] value) {
        Map<Integer, List<Integer>> tree = new HashMap<>();
        for (int i = 0; i < nodes; i++) {
            tree.computeIfAbsent(parent[i], k -> new ArrayList<>()).add(i);
        }

        return dfs(0, tree, value)[1];
    }

    private int[] dfs(int node, Map<Integer, List<Integer>> tree, int[] value) {
        int totalSum = value[node];
        int totalCount = 1;
        if (tree.containsKey(node)) {
            for (int child : tree.get(node)) {
                int[] childResult = dfs(child, tree, value);
                totalSum += childResult[0];
                totalCount += childResult[1];
            }
        }
        if (totalSum == 0) {
            return new int[]{0, 0};
        }
        return new int[]{totalSum, totalCount};
    }
}{}
    

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

Кэшбэк до 10% за путешествия Отдыхать приятнее с кэшбэком. В Т-Путешествиях на карту вернется до 10% за: - Авиабилеты - Отели, глэмпинги, хостелы и апартаменты Планируйте поездки с выгодой в Т-Путешествиях. Узнать больше #реклама tbank.ru О рекламодателе

Задача: 973. K Closest Points to Origin Сложность: medium Дан массив точек, где points[i] = [xi, yi] представляет собой точку на плоскости X-Y, и целое число k. Верните k точек, ближайших к началу координат (0, 0). Расстояние между двумя точками на плоскости X-Y является евклидовым расстоянием (то есть √((x1 - x2)² + (y1 - y2)²)). Вы можете вернуть ответ в любом порядке. Гарантируется, что ответ будет уникальным (за исключением порядка). Пример:

    
        Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].{}
    

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

    
        import java.util.Arrays;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        Arrays.sort(points, (a, b) -> squaredDistance(a) - squaredDistance(b));
        return Arrays.copyOfRange(points, 0, k);
    }

    private int squaredDistance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}{}
    

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

Задача: 991. Broken Calculator Сложность: medium Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно: Умножить число на экране на 2, или Вычесть 1 из числа на экране. Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе. Пример:

    
        Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.{}
    

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

    
        public class Solution {
    public int brokenCalc(int startValue, int target) {
        int operations = 0;
        
        while (target > startValue) {
            operations++;
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target += 1;
            }
        }
        
        return operations + (startValue - target);
    }
}{}
    

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