Java | LeetCode

Задача: 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 элементов массива. 😎 Решение:

    
        class Solution {
    fun kClosest(points: Array<IntArray>, k: Int): Array<IntArray> {
        points.sortBy { squaredDistance(it) }
        return points.take(k).toTypedArray()
    }

    private fun squaredDistance(point: IntArray): Int {
        return point[0] * point[0] + point[1] * point[1]
    }
}{}
    

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

Задача: 347. Top K Frequent Elements Сложность: medium Дан массив целых чисел nums и целое число k. Верните k самых частых элементов. Вы можете вернуть ответ в любом порядке. Пример:

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

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

    
        import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
            (a, b) -> b.getValue() - a.getValue());
        heap.addAll(count.entrySet());
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(heap.poll().getKey());
        }
        return result;
    }
}{}
    

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

Задача: 651. 4 Keys Keyboard Сложность: medium Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш. Пример:

    
        Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]{}
    

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

    
        public class Solution {
    public int maxA(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            for (int j = 2; j < i; j++) {
                dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
            }
        }
        return dp[n];
    }
}{}
    

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

Задача: 349. Intersection of Two Arrays Сложность: easy Даны два целочисленных массива nums1 и nums2. Верните массив их пересечения. Каждый элемент в результате должен быть уникальным, и вы можете вернуть результат в любом порядке. Пример:

    
        Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]{}
    

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

    
        public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        for (int num : nums1) {
            set1.add(num);
        }
        Set<Integer> set2 = new HashSet<>();
        for (int num : nums2) {
            set2.add(num);
        }
        set1.retainAll(set2);
        int[] result = new int[set1.size()];
        int i = 0;
        for (int num : set1) {
            result[i++] = num;
        }
        return result;
    }
}{}
    

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

Дизайн в FIGMA с нуля. Бесплатный курс + портфолио Онлайн-программа с наставником и чатом. Дизайн от профессионалов. Доступ 0 руб. Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 1086. High Five Сложность: easy Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента. Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания. Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления. Пример:

    
        Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]{}
    

👨‍💻 Алгоритм: 1⃣Создайте словарь для хранения оценок каждого студента, где ключом будет ID студента, а значением — список его оценок. Переберите элементы в массиве items и добавьте каждую оценку в соответствующий список в словаре, используя ID студента как ключ. 2⃣Создайте список для хранения результата result. Переберите словарь и для каждого студента отсортируйте его оценки в порядке убывания, возьмите пять лучших оценок, вычислите их среднее значение (с целочисленным делением на 5) и добавьте пару [ID, topFiveAverage] в результат. 3⃣Отсортируйте список result по возрастанию ID студента и верните его. 😎 Решение:

    
        class Solution {
    private int K = 5;

    public List<int[]> highFive(int[][] items) {
        Arrays.sort(items, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return b[1] - a[1];
        });

        List<int[]> solution = new ArrayList<>();
        int n = items.length;
        int i = 0;
        while (i < n) {
            int id = items[i][0];
            int sum = 0;
            for (int k = i; k < i + K; ++k) {
                sum += items[k][1];
            }
            while (i < n && items[i][0] == id) {
                i++;
            }
            solution.add(new int[]{id, sum / K});
        }
        return solution;
    }
}{}
    

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

Задача: 893. Groups of Special-Equivalent Strings Сложность: medium Вам дан массив строк одинаковой длины words. За один ход вы можете поменять местами любые два четных или любые два нечетных символа строки words[i]. Две строки words[i] и words[j] являются специально-эквивалентными, если после любого количества ходов words[i] == words[j]. Например, words[i] = "zzxy" и words[j] = "xyzz" являются специально-эквивалентными, потому что мы можем делать ходы "zzxy" -> "xzzy" -> "xyzz". Группа специально-эквивалентных строк из слов - это непустое подмножество слов, такое, что: каждая пара строк в группе специально-эквивалентна, и группа имеет максимально возможный размер (т.е, не существует строки words[i], не входящей в группу, такой, что words[i] является специально-эквивалентной каждой строке в группе). Верните количество групп специально-эквивалентных строк из слов. Пример:

    
        Input: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3{}
    

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

    
        import java.util.*;

class Solution {
    public int numSpecialEquivGroups(String[] words) {
        Set<String> uniqueForms = new HashSet<>();
        
        for (String word : words) {
            char[] evenChars = new char[(word.length() + 1) / 2];
            char[] oddChars = new char[word.length() / 2];
            
            for (int i = 0; i < word.length(); i++) {
                if (i % 2 == 0) {
                    evenChars[i / 2] = word.charAt(i);
                } else {
                    oddChars[i / 2] = word.charAt(i);
                }
            }
            
            Arrays.sort(evenChars);
            Arrays.sort(oddChars);
            String canonicalForm = new String(evenChars) + new String(oddChars);
            uniqueForms.add(canonicalForm);
        }
        
        return uniqueForms.size();
    }{}
    

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

Задача: №31. Next Permutation Сложность: medium Перестановка массива целых чисел — это упорядочивание его элементов в определённую последовательность. Нужно изменить текущий массив nums, чтобы получить следующую лексикографически большую перестановку. Если такой не существует (массив в убывающем порядке) — отсортировать его по возрастанию. Пример:

    
        Input: nums = [1,2,3] Output: [1,3,2]{}
    

👨‍💻 Алгоритм: 1⃣Найти самый длинный невозрастающий суффикс справа. Элемент перед ним — это "точка поворота" i. 2⃣Найти справа от i наименьшее число, большее nums[i], и поменять их местами. 3⃣Развернуть все элементы после позиции i — они были в убывающем порядке, а нам нужно минимальное по возрастанию завершение. 😎 Решение:

    
        public class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}{}
    

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

Задача: 1271. Hexspeak Сложность: easy Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR". Пример:

    
        Input: num = "257"
Output: "IOI"{}
    

👨‍💻 Алгоритм: 1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре. 2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I' 3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR". 😎 Решение:

    
        public class Solution {
    public String toHexString(String num) {
        String hexStr = Long.toHexString(Long.parseLong(num)).toUpperCase().replace('0', 'O').replace('1', 'I');
        for (char c : hexStr.toCharArray()) {
            if ("ABCDEFIO".indexOf(c) == -1) {
                return "ERROR";
            }
        }
        return hexStr;
    }
}{}
    

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

Задача: 1329. Sort the Matrix Diagonally Сложность: medium Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2]. Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу. Пример:

    
        Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]{}
    

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

    
        class Solution {
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        Map<Integer, PriorityQueue<Integer>> diagonals = new HashMap<>();

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int key = row - col;
                diagonals.putIfAbsent(key, new PriorityQueue<>());
                diagonals.get(key).add(mat[row][col]);
            }
        }

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int key = row - col;
                mat[row][col] = diagonals.get(key).poll();
            }
        }

        return mat;
    }
}{}
    

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