Java | LeetCode

Пожизненный PRO доступ на easyoffer — по цене одного года! До 31 марта вы можете купить PRO навсегда. Запускаем акцию, чтобы ускорить развитие сервиса. Что добавим в PRO в ближайшие полгода: – Автоотклики – Агрегатор вакансий – Проход ATS без отсева – Уникальные резюме и письма под каждую вакансию Покупаешь один раз — пользуешься всю жизнь. 👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro

Задача: 153. Find Minimum in Rotated Sorted Array Сложность: medium Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать: [4,5,6,7,0,1,2], если он был повернут 4 раза. [0,1,2,4,5,6,7], если он был повернут 7 раз. Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива. Вы должны написать алгоритм, который работает за время O(log n). Пример:

    
        Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.{}
    

👨‍💻 Алгоритм: 1⃣Нахождение середины массива: Определите элемент, находящийся посередине массива. 2⃣Определение направления поиска: Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины. Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины. 3⃣Остановка поиска при нахождении точки перегиба: Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий: nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом. nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом. 😎 Решение:

    
        class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int left = 0, right = nums.length - 1;
        if (nums[right] > nums[0]) {
            return nums[0];
        }

        while (right >= left) {
           
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }
            if (nums[mid - 1] > nums[mid]) {
                return nums[mid];
            }
            if (nums[mid] > nums[0]) {
                left = mid + 1;
            } else {
            }
        }
        return Integer.MAX_VALUE;
    }
}{}
    

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

Задача: 902. Numbers At Most N Given Digit Set Сложность: hard Дан массив цифр, отсортированный в неубывающем порядке. Вы можете записывать числа, используя каждый digits[i] столько раз, сколько захотите. Например, если digits = ['1','3','5'], мы можем записать такие числа, как '13', '551' и '1351315'. Возвращает количество положительных целых чисел, которые могут быть сгенерированы и которые меньше или равны заданному целому числу n. Пример:

    
        Input: digits = ["1","3","5","7"], n = 100
Output: 20{}
    

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

    
        class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        String s = String.valueOf(n);
        int K = s.length();
        int[] dp = new int[K + 1];
        dp[K] = 1;

        for (int i = K - 1; i >= 0; --i) {
            for (String d : digits) {
                if (d.charAt(0) < s.charAt(i)) {
                    dp[i] += Math.pow(digits.length, K - i - 1);
                } else if (d.charAt(0) == s.charAt(i)) {
                    dp[i] += dp[i + 1];
                }
            }
        }

        for (int i = 1; i < K; ++i) {
            dp[0] += Math.pow(digits.length, i);
        }

        return dp[0];
    }
}{}
    

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

Задача: 291. Word Pattern II Сложность: medium Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону. Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки. Пример:

    
        Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"{}
    

👨‍💻 Алгоритм: 1⃣Инициализация структур данных и определение рекурсивной функции: Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s. Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ. Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону. 2⃣Рекурсивная проверка соответствия: Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false. Получите символ из шаблона по индексу pIndex. Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне. 3⃣Отображение новых подстрок: Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки. Для каждой новой подстроки проверьте, существует ли она уже в ` 😎 Решение:

    
        import java.util.HashMap;
import java.util.HashSet;

public class Solution {
    public boolean wordPatternMatch(String pattern, String s) {
        HashMap<Character, String> symbolMap = new HashMap<>();
        HashSet<String> wordSet = new HashSet<>();
        return isMatch(s, 0, pattern, 0, symbolMap, wordSet);
    }

    private boolean isMatch(String s, int sIndex, String pattern, int pIndex,
                            HashMap<Character, String> symbolMap, HashSet<String> wordSet) {
        if (pIndex == pattern.length()) {
            return sIndex == s.length();
        }
        char symbol = pattern.charAt(pIndex);
        if (symbolMap.containsKey(symbol)) {
            String word = symbolMap.get(symbol);
            if (!s.startsWith(word, sIndex)) {
                return false;
            }
            return isMatch(s, sIndex + word.length(), pattern, pIndex + 1, symbolMap, wordSet);
        }
        for (int k = sIndex + 1; k <= s.length(); k++) {
            String newWord = s.substring(sIndex, k);
            if (wordSet.contains(newWord)) {
                continue;
            }
            symbolMap.put(symbol, newWord);
            wordSet.add(newWord);
            if (isMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
                return true;
            }
            symbolMap.remove(symbol);
            wordSet.remove(newWord);
        }
        return false;
    }
}{}
    

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

Задача: 1135. Connecting Cities With Minimum Cost Сложность: medium Есть n городов, пронумерованных от 1 до n. Вам даны целое число n и массив connections, где connections[i] = [xi, yi, costi] указывает, что стоимость соединения города xi и города yi (двунаправленное соединение) равна costi. Верните минимальную стоимость для соединения всех n городов так, чтобы между каждой парой городов был хотя бы один путь. Если невозможно соединить все n городов, верните -1. Стоимость - это сумма использованных стоимостей соединений. Пример:

    
        Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.{}
    

👨‍💻 Алгоритм: 1⃣Сортировка рёбер: Отсортируйте все соединения (рёбра) в графе по их весам (стоимости) в порядке возрастания. 2⃣Итерация по рёбрам и объединение: Используйте структуру данных Disjoint Set (Union-Find) для проверки циклов и объединения поддеревьев. Для каждого ребра проверьте, принадлежат ли его концы разным поддеревьям, и если да, объедините их, добавив ребро в минимальное остовное дерево (MST). 3⃣Проверка соединённости: Подсчитайте количество рёбер в MST. Если оно меньше n-1, верните -1, так как соединить все города невозможно. Иначе верните суммарную стоимость рёбер в MST. 😎 Решение:

    
        class DisjointSet {
    private int[] parents;

    public void Union(int a, int b) {
        int rootA = Find(a);
        int rootB = Find(b);
        if (rootA == rootB) return;
        this.parents[rootB] = rootA;
    }

    public int Find(int a) {
        while (a != this.parents[a]) {
            a = this.parents[a];
        }
        return a;
    }

    public boolean isInSameGroup(int a, int b) {
        return Find(a) == Find(b);
    }

    public DisjointSet(int N) {
        this.parents = new int[N + 1];
        for (int i = 1; i <= N; ++i) {
            this.parents[i] = i;
        }
    }
}{}
    

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

Задача: 507. Perfect Number Сложность: easy Совершенное число — это положительное целое число, которое равно сумме своих положительных делителей, исключая само число. Делитель целого числа x — это целое число, которое может делить x нацело. Дано целое число n, верните true, если n является совершенным числом, в противном случае верните false. Пример:

    
        Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.{}
    

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

    
            public boolean checkPerfectNumber(int num) {
        if (num <= 0) {
            return false;
        }
        int sum = 0;
        for (int i = 1; i * i <= num; i++) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) {
                    sum += num / i;
                }

            }
        }
        return sum - num == num;
    }
}{}
    

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

Задача: 274. H-Index Сложность: medium Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью. Верните h-индекс исследователя. Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз. Пример:

    
        Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.{}
    

👨‍💻 Алгоритм: 1⃣Отсортировать массив цитирований по убыванию: Отсортировать массив citations в порядке убывания, чтобы наибольшее количество цитирований было в начале массива. 2⃣Найти наибольшее значение i, для которого citations[i] > i: Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i. Это значение будет индексом, при котором количество цитирований статьи больше индекса. 3⃣Рассчитать h-индекс: h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге. 😎 Решение:

    
        public class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] papers = new int[n + 1];
        for (int c : citations)
            papers[Math.min(n, c)]++;
        int k = n;
        for (int s = papers[n]; k > s; s += papers[k])
            k--;
        return k;
    }
}{}
    

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

Задача: 389. Find the Difference Сложность: easy Даны две строки s и t. Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию. Верните букву, которая была добавлена в t. Пример:

    
        Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.{}
    

👨‍💻 Алгоритм: 1⃣Отсортируйте строки s и t. 2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s. 3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время. 😎 Решение:

    
        class Solution {
    public char findTheDifference(String s, String t) {
        char[] sortedS = s.toCharArray();
        char[] sortedT = t.toCharArray();
        Arrays.sort(sortedS);
        Arrays.sort(sortedT);

        int i = 0;
        while (i < s.length()) {
            if (sortedS[i] != sortedT[i]) {
                return sortedT[i];
            }
            i += 1;
        }

        return sortedT[i];
    }
}{}
    

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

Задача: 1057. Campus Bikes Сложность: medium В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|. Пример:

    
        Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]{}
    

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

    
        import java.util.*;

public class Solution {
    public int[] assignBikes(int[][] workers, int[][] bikes) {
        List<int[]> pairs = new ArrayList<>();
        
        for (int i = 0; i < workers.length; i++) {
            for (int j = 0; j < bikes.length; j++) {
                int distance = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
                pairs.add(new int[]{distance, i, j});
            }
        }
        
        pairs.sort((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });
        
        int[] result = new int[workers.length];
        boolean[] bikeTaken = new boolean[bikes.length];
        boolean[] workerAssigned = new boolean[workers.length];
        
        Arrays.fill(result, -1);
        
        for (int[] pair : pairs) {
            int workerIdx = pair[1];
            int bikeIdx = pair[2];
            if (!workerAssigned[workerIdx] && !bikeTaken[bikeIdx]) {
                result[workerIdx] = bikeIdx;
                bikeTaken[bikeIdx] = true;
                workerAssigned[workerIdx] = true;
            }
        }
        
        return result;
    }
}{}
    

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

Задача: 912. Sort an Array Сложность: medium Задав массив целых чисел nums, отсортируйте массив по возрастанию и верните его. Вы должны решить задачу без использования встроенных функций за время O(nlog(n)) и с минимально возможной пространственной сложностью. Пример:

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

👨‍💻 Алгоритм: 1⃣Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма. 2⃣Разделить массив на две половины. Рекурсивно отсортировать каждую половину. 3⃣Слить две отсортированные половины. 😎 Решение:

    
        import java.util.Arrays;

public class Main {
    public static void mergeSort(int[] nums) {
        if (nums.length > 1) {
            int mid = nums.length / 2;
            int[] left_half = Arrays.copyOfRange(nums, 0, mid);
            int[] right_half = Arrays.copyOfRange(nums, mid, nums.length);

            mergeSort(left_half);
            mergeSort(right_half);

            int i = 0, j = 0, k = 0;
            while (i < left_half.length && j < right_half.length) {
                if (left_half[i] < right_half[j]) {
                    nums[k++] = left_half[i++];
                } else {
                    nums[k++] = right_half[j++];
                }
            }

            while (i < left_half.length) {
                nums[k++] = left_half[i++];
            }

            while (j < right_half.length) {
                nums[k++] = right_half[j++];
            }
        }
    }
}{}
    

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