Задача: 646. Maximum Length of Pair Chain
Сложность: medium

Вам дан массив из n пар, где pairs[i] = [lefti, righti] и lefti < righti. Пара p2 = [c, d] следует за парой p1 = [a, b], если b < c. Таким образом можно построить цепочку пар. Верните самую длинную цепочку, которую можно составить. Вам не нужно использовать все заданные интервалы. Вы можете выбирать пары в любом порядке.

Пример:

Input: nums = [1,2,2,4]
Output: [2,3]

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

1⃣Отсортируйте пары по второму элементу каждой пары (righti).

2⃣Используйте динамическое программирование или жадный алгоритм, чтобы построить цепочку максимальной длины.

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

😎 Решение:

import java.util.Arrays;

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
        int currentEnd = Integer.MIN_VALUE;
        int count = 0;
        for (int[] pair : pairs) {
            if (currentEnd < pair[0]) {
                currentEnd = pair[1];
                count++;
            }
        }
        return count;
    }
}

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

Задача: 611. Valid Triangle Number
Сложность: medium

Если задан целочисленный массив nums, верните количество выбранных из массива троек, которые могут образовывать треугольники, если принять их за длины сторон треугольника.

Пример:

Input: nums = [2,2,3,4]
Output: 3

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

1⃣Отсортируйте массив nums.

2⃣Используйте три вложенных цикла: для каждого фиксированного третьего элемента, используйте два указателя для поиска подходящих первых двух элементов, которые удовлетворяют неравенству треугольника.

3⃣Увеличивайте счетчик на количество подходящих пар для каждого третьего элемента.

😎 Решение:

import java.util.Arrays;

public class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int count = 0;
        
        for (int k = n - 1; k >= 2; k--) {
            int i = 0;
            int j = k - 1;
            while (i < j) {
                if (nums[i] + nums[j] > nums[k]) {
                    count += j - i;
                    j--;
                } else {
                    i++;
                }
            }
        }
        
        return count;
    }
}

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

Задача: 478. Generate Random Point in a Circle
Сложность: medium

Дан радиус и положение центра окружности, реализуйте функцию randPoint, которая генерирует равномерно случайную точку внутри окружности.

Реализуйте класс Solution:

- Solution(double radius, double x_center, double y_center) инициализирует объект с радиусом окружности radius и положением центра (x_center, y_center).
- randPoint() возвращает случайную точку внутри окружности. Точка на окружности считается находящейся внутри окружности. Ответ возвращается в виде массива [x, y].

Пример:

Input
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
Output
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Explanation
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // return [-0.02493, -0.38077]
solution.randPoint(); // return [0.82314, 0.38945]
solution.randPoint(); // return [0.36572, 0.17248]

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

1⃣ Генерируем равномерно случайные точки в квадрате S с длиной стороны 2R.

2⃣ Сохраняем все точки, которые находятся на расстоянии не более R от центра, и отклоняем все, которые дальше этого расстояния.

3⃣ Повторяем процесс до получения нужного количества точек, учитывая, что примерно 78.5% от всех сгенерированных точек будут приемлемыми, и ожидаемое число попыток до получения приемлемой точки составляет примерно 1.274 раза.

😎 Решение:

class Solution {
    double rad, xc, yc;

    public Solution(double radius, double x_center, double y_center) {
        rad = radius;
        xc = x_center;
        yc = y_center;
    }

    public double[] randPoint() {
        double x0 = xc - rad;
        double y0 = yc - rad;

        while (true) {
            double xg = x0 + Math.random() * rad * 2;
            double yg = y0 + Math.random() * rad * 2;
            if (Math.sqrt(Math.pow((xg - xc), 2) + Math.pow((yg - yc), 2)) <= rad) {
                return new double[]{xg, yg};
            }
        }
    }
}

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

Задача: 322. Coin Change
Сложность: medium

Дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.

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

Вы можете предположить, что у вас есть неограниченное количество монет каждого типа.

Пример:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

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

1⃣Инициализация и вызов функции backtracking
Инициализируйте переменные для хранения минимального количества монет и вызовите функцию backtracking с начальными параметрами.

2⃣Функция backtracking
Внутри функции backtracking для каждой монеты из массива coins:
Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет.

3⃣Возврат результата
Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1.

😎 Решение:

public class Solution {

    public int coinChange(int[] coins, int amount) {
        return coinChange(0, coins, amount);
    }

    private int coinChange(int idxCoin, int[] coins, int amount) {
        if (amount == 0) return 0;
        if (idxCoin < coins.length && amount > 0) {
            int maxVal = amount / coins[idxCoin];
            int minCost = Integer.MAX_VALUE;
            for (int x = 0; x <= maxVal; x++) {
                if (amount >= x * coins[idxCoin]) {
                    int res = coinChange(idxCoin + 1, coins, amount - x * coins[idxCoin]);
                    if (res != -1)
                        minCost = Math.min(minCost, res + x);
                }
            }
            return (minCost == Integer.MAX_VALUE) ? -1 : minCost;
        }
        return -1;
    }
}

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

Задача: 1207. Unique Number of Occurrences
Сложность: easy

Дан массив целых чисел arr. Верните true, если количество вхождений каждого значения в массиве уникально, или false в противном случае.

Пример:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

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

1⃣Сохраните частоты элементов массива arr в хэш-таблице freq.

2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet.

3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false.

😎 Решение:

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        Set<Integer> freqSet = new HashSet<>(freq.values());
        
        return freq.size() == freqSet.size();
    }
}

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

Задача: 244. Shortest Word Distance II
Сложность: medium

Создайте структуру данных, которая будет инициализироваться массивом строк, а затем должна отвечать на запросы о наименьшем расстоянии между двумя разными строками из массива.

Реализуйте класс WordDistance:

WordDistance(String[] wordsDict) инициализирует объект с массивом строк wordsDict.
int shortest(String word1, String word2) возвращает наименьшее расстояние между word1 и word2 в массиве wordsDict.

Пример:

Input
["WordDistance", "shortest", "shortest"]
[[["practice", "makes", "perfect", "coding", "makes"]], ["coding", "practice"], ["makes", "coding"]]
Output
[null, 3, 1]
Explanation
WordDistance wordDistance = new WordDistance(["practice", "makes", "perfect", "coding", "makes"]);
wordDistance.shortest("coding", "practice"); // return 3
wordDistance.shortest("makes", "coding");    // return 1

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

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

2⃣Для данной пары слов получите список индексов (вхождений в исходный массив слов). Назовём эти два массива loc1 и loc2. Инициализируйте две переменные-указателя l1 = 0 и l2 = 0.

3⃣Для данных l1 и l2 обновите (если возможно) минимальную разницу (расстояние) до текущего момента, т.е. dist = min(dist, abs(loc1[l1] - loc2[l2])). Затем проверьте, если loc1[l1] < loc2[l2], и если это так, переместите l1 на один шаг вперёд, т.е. l1 = l1 + 1. В противном случае, переместите l2 на один шаг вперёд, т.е. l2 = l2 + 1. Продолжайте это делать, пока все элементы в меньшем из двух массивов позиций не будут обработаны. Верните глобальное минимальное расстояние между словами.

😎 Решение:

import java.util.*;

class WordDistance {
    Map<String, List<Integer>> locations;

    public WordDistance(String[] words) {
        locations = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            locations.computeIfAbsent(words[i], k -> new ArrayList<>()).add(i);
        }
    }

    public int shortest(String word1, String word2) {
        List<Integer> loc1 = locations.get(word1);
        List<Integer> loc2 = locations.get(word2);
        int l1 = 0, l2 = 0, minDiff = Integer.MAX_VALUE;

        while (l1 < loc1.size() && l2 < loc2.size()) {
            minDiff = Math.min(minDiff, Math.abs(loc1.get(l1) - loc2.get(l2)));
            if (loc1.get(l1) < loc2.get(l2)) {
                l1++;
            } else {
                l2++;
            }
        }
        return minDiff;
    }
}

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

Задача: 168. Excel Sheet Column Title
Сложность: easy

Дано целое число columnNumber, верните соответствующий заголовок столбца, как он отображается в таблице Excel.

Например:
A -> 1
B -> 2
C -> 3
Z -> 26
AA -> 27
AB -> 28

Пример:

Input: columnNumber = 1
Output: "A"

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

1⃣Инициализация пустой строки ans:
Создайте пустую строку ans, которая будет хранить заголовок столбца.

2⃣Циклическое преобразование числа в буквы:
Пока columnNumber больше 0, выполняйте следующие действия:
Вычтите 1 из columnNumber для корректировки индекса (Excel использует 1-индексацию).
Найдите символ, соответствующий остатку от деления columnNumber на 26, и добавьте его в начало строки ans.
Присвойте columnNumber значение от деления columnNumber на 26

3⃣Переворот и возврат результата:
Так как символы добавляются в начало строки, то по завершению цикла строка ans содержит заголовок столбца в обратном порядке. Переверните строку ans, чтобы представить её в правильном порядке.
Верните полученный заголовок столбца.

😎 Решение:

class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder ans = new StringBuilder();

        while (columnNumber > 0) {
            columnNumber--;
            ans.append((char) (((columnNumber) % 26) + 'A'));
            columnNumber = (columnNumber) / 26;
        }
        return ans.reverse().toString();
    }
}

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

Задача: 201. Bitwise AND of Numbers Range
Сложность: medium

Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно.

Пример:

Input: left = 5, right = 7
Output: 4

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

1⃣Сдвигать left и right вправо, пока они не станут равными.

2⃣Подсчитать количество сдвигов.

3⃣Сдвинуть left влево на количество сдвигов и вернуть результат.

😎 Решение:

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n) {
            m >>= 1;
            n >>= 1;
            ++shift;
        }
        return m << shift;
    }
}

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

Задача: 767. Reorganize String
Сложность: medium

Дана строка s, переставьте символы строки s так, чтобы любые два соседних символа не были одинаковыми.

Верните любую возможную перестановку строки s или верните "", если это невозможно.

Пример:

Input: s = "aab"
Output: "aba"

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

1⃣Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет.

2⃣Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации.

3⃣В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans.

😎 Решение:

import java.util.*;

class Solution {
    public String reorganizeString(String s) {
        int[] charCounts = new int[26];
        for (char c : s) {
            charCounts[c - 'a']++;
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < 26; i++) {
            if (charCounts[i] > 0) {
                pq.add(new int[]{charCounts[i], i + 'a'});
            }
        }
        
        StringBuilder result = new StringBuilder();
        while (!pq.isEmpty()) {
            int[] first = pq.poll();
            if (result.length() == 0 || first[1] != result.charAt(result.length() - 1)) {
                result.append((char)first[1]);
                if (--first[0] > 0) {
                    pq.add(first);
                }
            } else {
                if (pq.isEmpty()) {
                    return "";
                }
                int[] second = pq.poll();
                result.append((char)second[1]);
                if (--second[0] > 0) {
                    pq.add(second);
                }
                pq.add(first);
            }
        }

        return result.toString();
    }
}

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

Задача: 1464. Maximum Product of Two Elements in an Array
Сложность: easy

Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1).

Пример:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

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

1⃣Инициализируйте biggest = 0 и secondBiggest = 0.

2⃣Итерируйте по каждому элементу массива nums:
Если текущий элемент больше biggest, обновите secondBiggest = biggest и biggest = текущий элемент.
Иначе обновите secondBiggest, если текущий элемент больше secondBiggest.

3⃣Верните (biggest - 1) * (secondBiggest - 1).

😎 Решение:

class Solution {
    public int maxProduct(int[] nums) {
        int biggest = 0;
        int secondBiggest = 0;
        for (int num : nums) {
            if (num > biggest) {
                secondBiggest = biggest;
                biggest = num;
            } else {
                secondBiggest = Math.max(secondBiggest, num);
            }
        }
        
        return (biggest - 1) * (secondBiggest - 1);
    }
}

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

Задача: 845. Longest Mountain in Array
Сложность: medium

Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.

Пример:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

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

1⃣Инициализируйте переменные для отслеживания текущего основания и максимальной длины горного массива.

2⃣Для каждого индекса, который может быть началом горного массива, определите пиковый элемент и найдите правую границу горного массива.

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

😎 Решение:

class Solution {
    public int longestMountain(int[] A) {
        int N = A.length;
        int ans = 0, base = 0;
        while (base < N) {
            int end = base;
            if (end + 1 < N && A[end] < A[end + 1]) {
                while (end + 1 < N && A[end] < A[end + 1]) end++;

                if (end + 1 < N && A[end] > A[end + 1]) {
                    while (end + 1 < N && A[end] > A[end + 1]) end++;
                    ans = Math.max(ans, end - base + 1);
                }
            }

            base = Math.max(end, base + 1);
        }

        return ans;
    }
}

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