Java | LeetCode

Задача: 660. Remove 9 Сложность: hard Начните с целого числа 1, уберите любое число, которое содержит 9, такое как 9, 19, 29... Теперь у вас будет новая последовательность целых чисел [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...]. Дано целое число n, верните n-е (начиная с 1) целое число в новой последовательности. Пример:

Input: n = 9
Output: 10

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

public class Solution {
    public int newInteger(int n) {
        int count = 0;
        int num = 0;
        while (count < n) {
            num++;
            if (!Integer.toString(num).contains("9")) {
                count++;
            }
        }
        return num;
    }
}

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

Задача: 1263. Minimum Moves to Move a Box to Their Target Location Сложность: hard Кладовщик - это игра, в которой игрок перемещает коробки по складу, пытаясь доставить их в целевые места. Игра представлена сеткой символов m x n, где каждый элемент - это стена, пол или коробка. Ваша задача - переместить коробку "B" в целевую позицию "T" по следующим правилам: символ "S" представляет игрока. Игрок может перемещаться вверх, вниз, влево, вправо по сетке, если это пол (пустая клетка). Символ '.' обозначает пол, что означает свободную клетку для ходьбы. Символ '#' обозначает стену, что означает препятствие (туда невозможно пройти). В сетке есть только одна коробка 'B' и одна целевая клетка 'T'. Коробку можно переместить на соседнюю свободную клетку, стоя рядом с коробкой, а затем двигаясь в направлении коробки. Это толчок. Игрок не может пройти через коробку. Верните минимальное количество толчков, чтобы переместить коробку к цели. Если нет возможности добраться до цели, верните -1. Пример:

Input: grid = [["#","#","#","#","#","#"],
               ["#","T","#","#","#","#"],
               ["#",".",".","B",".","#"],
               ["#",".","#","#",".","#"],
               ["#",".",".",".","S","#"],
               ["#","#","#","#","#","#"]]
Output: 3

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

import java.util.*;

public class Solution {
    public int minPushBox(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        Queue<int[]> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        int[] player = new int[2], box = new int[2], target = new int[2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'S') {
                    player = new int[]{i, j};
                } else if (grid[i][j] == 'B') {
                    box = new int[]{i, j};
                } else if (grid[i][j] == 'T') {
                    target = new int[]{i, j};
                }
            }
        }
        
        queue.offer(new int[]{player[0], player[1], box[0], box[1], 0});
        visited.add(player[0] + "," + player[1] + "," + box[0] + "," + box[1]);
        
        while (!queue.isEmpty()) {
            int[] state = queue.poll();
            int px = state[0], py = state[1], bx = state[2], by = state[3], pushes = state[4];
            if (bx == target[0] && by == target[1]) {
                return pushes;
            }
            for (int[] dir : directions) {
                int npx = px + dir[0], npy = py + dir[1];
                if (isValid(npx, npy, m, n, grid)) {
                    if (npx == bx && npy == by) {
                        int nbx = bx + dir[0], nby = by + dir[1];
                        if (isValid(nbx, nby, m, n, grid) && visited.add(npx + "," + npy + "," + nbx + "," + nby)) {
                            queue.offer(new int[]{npx, npy, nbx, nby, pushes + 1});
                        }
                    } else if (visited.add(npx + "," + npy + "," + bx + "," + by)) {
                        queue.offer(new int[]{npx, npy, bx, by, pushes});
                    }
                }
            }
        }
        
        return -1;
    }
    
    private boolean isValid(int x, int y, int m, int n, char[][] grid) {
        return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
    }
}

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

Задача: 414. Third Maximum Number Сложность: easy Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число. Пример:

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

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

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int thirdMax(int[] nums) {
        Integer first = null;
        Integer second = null;
        Integer third = null;
        
        for (Integer num : nums) {
            if (num.equals(first) || num.equals(second) || num.equals(third)) {
                continue;
            }
            if (first == null || num > first) {
                third = second;
                second = first;
                first = num;
            } else if (second == null || num > second) {
                third = second;
                second = num;
            } else if (third == null || num > third) {
                third = num;
            }
        }
        
        return third != null ? third : first;
    }
}

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

Задача: 443. String Compression Сложность: medium Дан массив символов chars, сжать его, используя следующий алгоритм: Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars: Если длина группы равна 1, добавьте символ к строке s. В противном случае добавьте символ, а за ним длину группы. Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars. После того как вы закончите модификацию входного массива, верните новую длину массива. Вы должны написать алгоритм, который использует только постоянное дополнительное пространство. Пример:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

👨‍💻 Алгоритм: 1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0. 2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе. 3⃣Верните res. 😎 Решение:

class Solution {
    public int compress(char[] chars) {
        int i = 0;
        int res = 0;
        while (i < chars.length) {
            int groupLength = 1;
            while (i + groupLength < chars.length && chars[i + groupLength] == chars[i]) {
                groupLength++;
            }
            chars[res++] = chars[i];
            if (groupLength > 1) {
                String strRepr = Integer.toString(groupLength);
                for (char ch : strRepr.toCharArray()) {
                    chars[res++] = ch;
                }
            }
            i += groupLength;
        }
        return res;
    }
}

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

Задача: 54. Spiral Matrix Сложность: medium Для матрицы размером m на n верните все элементы матрицы в спиральном порядке. Пример:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

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

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int rows = matrix.length;
        int columns = matrix[0].length;
        int up = 0;
        int left = 0;
        int right = columns - 1;
        int down = rows - 1;

        while (result.size() < rows * columns) {
            for (int col = left; col <= right; col++) {
                result.add(matrix[up][col]);
            }
            for (int row = up + 1; row <= down; row++) {
                result.add(matrix[row][right]);
            }
            if (up != down) {
                for (int col = right - 1; col >= left; col--) {
                    result.add(matrix[down][col]);
                }
            }
            if (left != right) {
                for (int row = down - 1; row > up; row--) {
                    result.add(matrix[row][left]);
                }
            }
            left++;
            right--;
            up++;
            down--;
        }

        return result;
    }
}

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

Методичка: как сделать онлайн-встречи эффективнее Надоело ждать коллег, которые постоянно забывают о встречах, а отсутствие повестки и потерянные договоренности мешают нормально работать? Команда МТС Линк собрала на 37 страницах полезные материалы, чек-листы и кейсы, которые помогают компаниям проводить эффективные совещания в онлайне с помощью сервиса Встречи. Из методички узнаете: - Как создать постоянную ссылку и подключаться на встречи в 2 клика, - Как делать заметки и работать с файлами, не переживая за качество связи и безопасность данных. - Как облегчает жизнь ИИ, который расшифровывает созвоны в текст и автоматически отправляет расшифровку на почту. Еще в методичке описаны 7 способов оценки текущей эффективности ваших онлайн-встреч. Получить гайд можно бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 387. First Unique Character in a String Сложность: easy Дана строка s, найдите первый неповторяющийся символ в ней и верните его индекс. Если такого символа не существует, верните -1. Пример:

Input: s = "leetcode"
Output: 0

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

import java.util.Random;

public class Solution {
    private int[] original;
    private int[] array;
    private Random rand = new Random();

    public Solution(int[] nums) {
        array = nums.clone();
        original = nums.clone();
    }

    public int[] reset() {
        array = original.clone();
        return original;
    }

    public int[] shuffle() {
        for (int i = 0; i < array.length; i++) {
            int randIndex = rand.nextInt(array.length - i) + i;
            int temp = array[i];
            array[i] = array[randIndex];
            array[randIndex] = temp;
        }
        return array;
    }
}

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

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать

Задача: 819. Most Common Word Сложность: easy Дана строка paragraph и массив строк banned, представляющий запрещенные слова. Верните наиболее часто встречающееся слово, которое не запрещено. Гарантируется, что существует хотя бы одно слово, которое не запрещено, и что ответ является уникальным. Слова в paragraph нечувствительны к регистру, и ответ должен быть возвращен в нижнем регистре. Пример:

Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

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

class Solution {
    public String mostCommonWord(String paragraph, List<String> banned) {
        String normalizedStr = paragraph.replaceAll("[^a-zA-Z0-9 ]", " ").toLowerCase();
        String[] words = normalizedStr.split("\\s+");
        Map<String, Integer> wordCount = new HashMap<>();
        Set<String> bannedWords = new HashSet<>(banned);

        for (String word : words) {
            if (!bannedWords.contains(word)) {
                wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
            }
        }

        return Collections.max(wordCount.entrySet(), Map.Entry.comparingByValue()).getKey();
    }

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

1 метод, который помогает бьюти-мастерам стабильно расти Преврати "окна" в стабильный доход с нашим методом "10 легких шагов"! Стабильный рост - это не магия, а система. И ты прямо сейчас можешь ее внедрить! Жми "Скачать" и забирай бесплатно! Скачать #реклама 16+ mikheev-school.com О рекламодателе

Задача: 319. Bulb Switcher Сложность: medium Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку. На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку. Верните количество лампочек, которые будут включены после n раундов. Пример:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

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

class Solution {
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n);
    }
}

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

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 162. Find Peak Element Сложность: medium Пиковым элементом называется элемент, который строго больше своих соседей. Для массива целых чисел nums с индексацией с нуля найдите пиковый элемент и верните его индекс. Если в массиве несколько пиков, верните индекс любого из пиков. Вы можете представить, что nums[-1] = nums[n] = -∞. Другими словами, элемент всегда считается строго большим, чем сосед, находящийся за пределами массива. Необходимо написать алгоритм, который работает за время O(log n). Пример:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

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

public class Solution {
    public int findPeakElement(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }

    public int search(int[] nums, int l, int r) {
        if (l == r) return l;
        int mid = (l + r) / 2;
        if (nums[mid] > nums[mid + 1]) return search(nums, l, mid);
        return search(nums, mid + 1, r);
    }
}

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

Регистрируйтесь на Yandex Ecom Open Air 8 августа Море инсайтов для бизнеса, музыкальный open-air, лекции и нетворкинг. Участие бесплатно! Зарегистрироваться #реклама 18+ ecomfest.ru О рекламодателе

Задача: 924. Minimize Malware Spread Сложность: hard Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО. Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

import java.util.*;

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        Set<Integer> initialSet = new HashSet<>();
        for (int node : initial) {
            initialSet.add(node);
        }
        Arrays.sort(initial);
        int minInfected = Integer.MAX_VALUE;
        int bestNode = initial[0];
        
        for (int node : initial) {
            Set<Integer> infected = new HashSet<>(initialSet);
            infected.remove(node);
            for (int i : initialSet) {
                if (i != node) {
                    dfs(graph, i, infected);
                }
            }
            if (infected.size() < minInfected) {
                minInfected = infected.size();
                bestNode = node;
            }
        }
        
        return bestNode;
    }
    
    private void dfs(int[][] graph, int node, Set<Integer> infected) {
        for (int neighbor = 0; neighbor < graph.length; neighbor++) {
            if (graph[node][neighbor] == 1 && !infected.contains(neighbor)) {
                infected.add(neighbor);
                dfs(graph, neighbor, infected);
            }
        }
    }
}

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

Задача: 559. Maximum Depth of N-ary Tree Сложность: easy Дано n-арное дерево, найдите его максимальную глубину. Максимальная глубина - это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего листового узла. Сериализация ввода n-арного дерева представлена в порядке уровня, каждая группа дочерних узлов разделена значением null (см. примеры). Пример:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3

👨‍💻 Алгоритм: 1⃣Интуитивный подход заключается в решении задачи с помощью рекурсии. 2⃣Здесь мы демонстрируем пример с использованием стратегии поиска в глубину (DFS - Depth First Search). 3⃣Применяя DFS, проходим через все узлы дерева, вычисляя максимальную глубину. 😎 Решение:

class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        } else if (root.children.isEmpty()) {
            return 1;  
        } else {
            List<Integer> heights = new LinkedList<>();
            for (Node item : root.children) {
                heights.add(maxDepth(item)); 
            }
            return Collections.max(heights) + 1;
        }
    }
}

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

Устали от ИТ-проблем? Полный аутсорсинг "под ключ" EFSOL Резервные копии, обновления, срочные выезды — забираем на себя! 👌 Сосредоточьтесь на развитии, а не на поломках. EFSOL: • мониторинг 1С (блокировки, ошибки); • восстановление данных из бэкапа от 5 мин; • поддержка 24/7. ⚡Закажите бесплатный аудит IT! Заказать #реклама efsol.ru О рекламодателе

Задача: 616. Add Bold Tag in String Сложность: medium Вам дана строка s и массив строк words. Вы должны добавить закрытую пару полужирных тегов <b> и </b>, чтобы обернуть подстроки в s, которые существуют в words. Если две такие подстроки пересекаются, вы должны обернуть их вместе только одной парой закрытых полужирных тегов. Если две подстроки, обернутые полужирными тегами, идут подряд, вы должны объединить их. Верните s после добавления полужирных тегов. Пример:

Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"

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

public class Solution {
    public String addBoldTag(String s, String[] words) {
        int n = s.length();
        boolean[] bold = new boolean[n];
        
        for (String word : words) {
            int start = s.indexOf(word);
            while (start != -1) {
                for (int i = start; i < start + word.length(); i++) {
                    bold[i] = true;
                }
                start = s.indexOf(word, start + 1);
            }
        }
        
        StringBuilder result = new StringBuilder();
        int i = 0;
        while (i < n) {
            if (bold[i]) {
                result.append("<b>");
                while (i < n && bold[i]) {
                    result.append(s.charAt(i));
                    i++;
                }
                result.append("</b>");
            } else {
                result.append(s.charAt(i));
                i++;
            }
        }
        
        return result.toString();
    }
}

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

Регистрируйтесь на Yandex Ecom Open Air 8 августа Море инсайтов для бизнеса, музыкальный open-air, лекции и нетворкинг. Участие бесплатно! Зарегистрироваться #реклама 18+ ecomfest.ru О рекламодателе

Задача: 315. Count of Smaller Numbers After Self Сложность: hard Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i]. Пример:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

👨‍💻 Алгоритм: 1⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4. 2⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия: Смещайте число на num + offset. Запросите количество элементов в дереве отрезков, которые меньше текущего числа. Обновите счетчик текущего числа в дереве отрезков. 3⃣Верните результат. 😎 Решение:

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int offset = 10000;
        int size = 2 * 10000 + 1;
        int[] tree = new int[size * 2];
        List<Integer> result = new ArrayList<Integer>();

        for (int i = nums.length - 1; i >= 0; i--) {
            int smaller_count = query(0, nums[i] + offset, tree, size);
            result.add(smaller_count);
            update(nums[i] + offset, 1, tree, size);
        }
        Collections.reverse(result);
        return result;
    }

    private void update(int index, int value, int[] tree, int size) {
        index += size;
        tree[index] += value;
        while (index > 1) {
            index /= 2;
            tree[index] = tree[index * 2] + tree[index * 2 + 1];
        }
    }

    private int query(int left, int right, int[] tree, int size) {
        int result = 0;
        left += size;
        right += size;
        while (left < right) {
            if (left % 2 == 1) {
                result += tree[left];
                left++;
            }
            left /= 2;
            if (right % 2 == 1) {
                right--;
                result += tree[right];
            }
            right /= 2;
        }
        return result;
    }
}

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