Java | LeetCode

Задача: 509. Fibonacci Number
Сложность: easy

Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
Дано n, вычислите F(n).

Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

👨‍💻 Алгоритм:

1⃣Проверка начального условия
Если N <= 1, вернуть N.

2⃣Инициализация переменных
Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения.

3⃣Итерация и вычисление
Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации.

😎 Решение:

class Solution {
    public int fib(int N) {
        if (N <= 1) {
            return N;
        }

        int current = 0;
        int prev1 = 1;
        int prev2 = 0;

        for (int i = 2; i <= N; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
}

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

Задача: 1009. Complement of Base 10 Integer
Сложность: easy

Дополнение целого числа - это целое число, которое получается, если перевернуть все 0 в 1 и все 1 в 0 в его двоичном представлении. Например, целое число 5 - это "101" в двоичном представлении, а его дополнение - "010", то есть целое число 2. Если задано целое число n, верните его дополнение.

Пример:

Input: n = 5
Output: 2

👨‍💻 Алгоритм:

1⃣Определение длины двоичного представления:
Найдите длину двоичного представления числа n.

2⃣Создание маски:
Создайте маску, которая состоит из всех единиц и имеет ту же длину, что и двоичное представление числа n.

3⃣Вычисление дополнения:
Примените побитовую операцию XOR между числом n и маской, чтобы получить дополнение числа.

😎 Решение:

public class Solution {
    public int findComplement(int num) {
        int length = Integer.toBinaryString(num).length();
        int mask = (1 << length) - 1;
        return num ^ mask;
    }
}

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

Завтра последний день!

Успей купить пожизненный easyoffer PRO - по цене 1 года

Покупаешь один раз — пользуешься всю жизнь.

👉 Акция до 31 марта: https://easyoffer.ru/pro

Задача: 1228. Missing Number In Arithmetic Progression
Сложность: easy

В массиве arr значения находились в арифметической прогрессии: значения arr[i + 1] - arr[i] равны для всех 0 <= i < arr.length - 1.

Из массива arr было удалено значение, которое не было первым или последним значением в массиве.

Дан массив arr, вернуть удаленное значение.

Пример:

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

👨‍💻 Алгоритм:

1⃣Рассчитать разность difference между элементами арифметической прогрессии.

2⃣Начать с первого элемента массива и последовательно увеличивать ожидаемое значение на difference, проверяя каждый элемент массива.

3⃣Вернуть первое ожидаемое значение, которое не совпадает с текущим значением в массиве.

😎 Решение:

class Solution {
    public int missingNumber(int[] arr) {
        int n = arr.length;

        int difference = (arr[arr.length - 1] - arr[0]) / n;

        int expected = arr[0];

        for (int val : arr) {
            if (val != expected) return expected;

            expected += difference;
        }
        return expected;
    }
}

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

Задача: 821. Shortest Distance to a Character
Сложность: easy

Дана строка s и символ c, который встречается в s. Верните массив целых чисел answer, где answer.length == s.length, и answer[i] - это расстояние от индекса i до ближайшего появления символа c в строке s.

Расстояние между двумя индексами i и j равно abs(i - j), где abs - это функция абсолютного значения.

Пример:

Input: s = "loveleetcode", c = "e"
Output: [3,2,1,0,1,0,0,1,2,2,1,0]
Explanation: The character 'e' appears at indices 3, 5, 6, and 11 (0-indexed).
The closest occurrence of 'e' for index 0 is at index 3, so the distance is abs(0 - 3) = 3.
The closest occurrence of 'e' for index 1 is at index 3, so the distance is abs(1 - 3) = 2.
For index 4, there is a tie between the 'e' at index 3 and the 'e' at index 5, but the distance is still the same: abs(4 - 3) == abs(4 - 5) = 1.
The closest occurrence of 'e' for index 8 is at index 6, so the distance is abs(8 - 6) = 2.

👨‍💻 Алгоритм:

1⃣При проходе слева направо будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет i - prev.

2⃣При проходе справа налево будем запоминать индекс prev последнего символа C, который мы видели. Тогда ответ будет prev - i.

3⃣Мы берем минимальное значение из этих двух ответов для создания нашего окончательного ответа.

😎 Решение:

class Solution {
    public int[] shortestToChar(String S, char C) {
        int N = S.length();
        int[] ans = new int[N];
        int prev = -N;

        for (int i = 0; i < N; ++i) {
            if (S.charAt(i) == C) {
                prev = i;
            }
            ans[i] = i - prev;
        }

        prev = 2 * N;
        for (int i = N - 1; i >= 0; --i) {
            if (S.charAt(i) == C) {
                prev = i;
            }
            ans[i] = Math.min(ans[i], prev - i);
        }

        return ans;
    }

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

Задача: 320. Generalized Abbreviation
Сложность: medium

Обобщенная аббревиатура слова может быть построена путем замены любых неперекрывающихся и несмежных подстрок на их соответствующие длины.

Например, "abcde" можно сократить следующим образом:

"a3e" ("bcd" заменено на "3")
"1bcd1" ("a" и "e" заменены на "1")
"5" ("abcde" заменено на "5")
"abcde" (без замены подстрок)
Однако следующие аббревиатуры недействительны:

"23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные.
"22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются.
Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке.

Пример:

Input: word = "a"
Output: ["1","a"]

👨‍💻 Алгоритм:

1⃣Создание битовых масок
Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур.

2⃣Генерация аббревиатур
Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик.

3⃣Перебор всех комбинаций
Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1.

😎 Решение:

public class Solution {
    public List<String> generateAbbreviations(String word) {
        List<String> ans = new ArrayList<>();
        for (int x = 0; x < (1 << word.length()); ++x)
            ans.add(abbr(word, x));
        return ans;
    }

    private String abbr(String word, int x) {
        StringBuilder builder = new StringBuilder();
        int k = 0, n = word.length();
        for (int i = 0; i < n; ++i, x >>= 1) {
            if ((x & 1) == 0) {
                if (k != 0) {
                    builder.append(k);
                    k = 0;
                }
                builder.append(word.charAt(i));
            } else {
                ++k;
            }
        }
        if (k != 0) builder.append(k);
        return builder.toString();
    }
}

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

Задача: 744. Find Smallest Letter Greater Than Target
Сложность: easy

Нам дан массив символов letters, отсортированный в неубывающем порядке, и символ target. В массиве letters есть как минимум два разных символа. Возвращается наименьший символ в letters, который лексикографически больше target. Если такого символа не существует, возвращается первый символ в буквах.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

👨‍💻 Алгоритм:

1⃣Использовать бинарный поиск для нахождения позиции первого символа в letters, который лексикографически больше target.

2⃣Если найденный символ существует, вернуть его.

3⃣Если такого символа не существует, вернуть первый символ в letters.

😎 Решение:

public class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (letters[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return letters[left % letters.length];
    }
}

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

Задача: №25. Reverse Nodes in k-Group
Сложность: hard

Учитывая заголовок связанного списка, поменяйте местами узлы списка по k за раз и верните изменённый список.
Если количество узлов не кратно k, то последние остаются без изменений.
*Изменять можно только связи между узлами, а не их значения.*

Пример:

Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5]

👨‍💻 Алгоритм:

1⃣Создать фиктивный узел dummy, указывающий на head, и использовать указатель pointer для прохода по списку.

2⃣В каждом шаге проверять, есть ли впереди k узлов — если нет, завершить процесс. Иначе — развернуть группу из k узлов.

3⃣После разворота связать конец текущей группы с началом следующей и перейти к следующей группе, сдвинув pointer.

😎 Решение:

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode pointer = dummy;

    while (pointer != null) {
        ListNode node = pointer;
        for (int i = 0; i < k && node != null; i++) node = node.next;
        if (node == null) break;

        ListNode prev = null, curr = pointer.next;
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        ListNode tail = pointer.next;
        tail.next = curr;
        pointer.next = prev;
        pointer = tail;
    }

    return dummy.next;
}

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

Задача: 128. Longest Consecutive Sequence
Сложность: Medium

Дан несортированный массив целых чисел nums. Верните длину самой длинной последовательности последовательных элементов.

Необходимо написать алгоритм, который работает за время O(n).

Пример:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

👨‍💻 Алгоритм:

1⃣Проверка базового случая:
Перед началом работы проверяем базовый случай с пустым массивом.
Самая длинная последовательность в пустом массиве, очевидно, равна 0, поэтому мы можем просто вернуть это значение.

2⃣Обработка чисел в массиве:
Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим).
Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу.
Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем.

3⃣Завершение обработки и возврат результата:
В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность).
Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной.

😎 Решение:

class Solution {
    private boolean arrayContains(int[] arr, int num) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == num) {
                return true;
            }
        }

        return false;
    }

    public int longestConsecutive(int[] nums) {
        int longestStreak = 0;

        for (int num : nums) {
            int currentNum = num;
            int currentStreak = 1;

            while (arrayContains(nums, currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = Math.max(longestStreak, currentStreak);
        }

        return longestStreak;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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++];
            }
        }
    }
}

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

Задача: 209. Minimum Size Subarray Sum
Сложность: medium

Дан массив положительных целых чисел nums и положительное целое число target. Верните минимальную длину подмассива, сумма которого больше или равна target. Если такого подмассива нет, верните 0.

Пример:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
Создайте три целочисленные переменные left, right и sumOfCurrentWindow. Переменные left и right формируют подмассив, указывая на начальные и конечные индексы текущего подмассива (или окна), а sumOfCurrentWindow хранит сумму этого окна. Инициализируйте все их значением 0.
Создайте еще одну переменную res для хранения ответа на задачу. Инициализируйте ее большим целым значением.

2⃣Итерация по массиву:
Итерируйте по массиву nums с помощью right, начиная с right = 0 до nums.length - 1, увеличивая right на 1 после каждой итерации. Выполняйте следующее внутри этой итерации:
Добавьте элемент с индексом right к текущему окну, увеличив sumOfCurrentWindow на nums[right].
Проверьте, если sumOfCurrentWindow >= target. Если да, у нас есть подмассив, который удовлетворяет условию. В результате, попытайтесь обновить переменную ответа res длиной этого подмассива. Выполните res = min(res, right - left + 1). Затем удалите первый элемент из этого окна, уменьшив sumOfCurrentWindow на nums[left] и увеличив left на 1. Этот шаг повторяется во внутреннем цикле, пока sumOfCurrentWindow >= target.

3⃣Возврат результата:
Текущая сумма окна теперь меньше target. Нужно добавить больше элементов в окно. В результате, увеличивается right на 1.
Верните res.

😎 Решение:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, sumOfCurrentWindow = 0;
        int res = Integer.MAX_VALUE;

        for(right = 0; right < nums.length; right++) {
            sumOfCurrentWindow += nums[right];

            while (sumOfCurrentWindow >= target) {
                res = Math.min(res, right - left + 1);
                sumOfCurrentWindow -= nums[left++];
            }
        }

        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

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

Задача: 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];
    }
}

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

Задача: 556. Next Greater Element III
Сложность: medium

Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:

Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1.

Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1.

Пример:

Input: n = 12
Output: 21

👨‍💻 Алгоритм:

1⃣Нахождение и перестановка цифр
Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j.

2⃣Обратный порядок оставшихся цифр
Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной.

3⃣Проверка результата и преобразование обратно в число
Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число.

😎 Решение:

import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    public String swap(String s, int i0, int i1) {
        if (i0 == i1)
            return s;
        String s1 = s.substring(0, i0);
        String s2 = s.substring(i0 + 1, i1);
        String s3 = s.substring(i1 + 1);
        return s1 + s.charAt(i1) + s2 + s.charAt(i0) + s3;
    }

    ArrayList<String> list = new ArrayList<>();

    void permute(String a, int l, int r) {
        int i;
        if (l == r)
            list.add(a);
        else {
            for (i = l; i <= r; i++) {
                a = swap(a, l, i);
                permute(a, l + 1, r);
                a = swap(a, l, i);
            }
        }
    }

    public int nextGreaterElement(int n) {
        String s = "" + n;
        permute(s, 0, s.length() - 1);
        Collections.sort(list);
        int i;
        for (i = list.size() - 1; i >= 0; i--) {
            if (list.get(i).equals("" + n))
                break;
        }
        return i == list.size() - 1 ? -1 : Integer.parseInt(list.get(i + 1));
    }
}

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