Java | LeetCode

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

Задача: 667. Beautiful Arrangement II Сложность: medium Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию: Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них. Пример:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

👨‍💻 Алгоритм: 1⃣Инициализация списка: Начните с создания списка от 1 до n: [1, 2, 3, ..., n]. 2⃣Конструирование шаблона с k различиями: Для обеспечения k различных значений разностей используйте следующий подход: Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей. Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей. 3⃣Заполнение списка: Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n. 😎 Решение:

public class Solution {
    public int[] constructArray(int n, int k) {
        int[] answer = new int[n];
        int left = 1, right = n;
        
        for (int i = 0; i <= k; i++) {
            if (i % 2 == 0) {
                answer[i] = left++;
            } else {
                answer[i] = right--;
            }
        }
        
        if (k % 2 == 0) {
            for (int i = k + 1; i < n; i++) {
                answer[i] = right--;
            }
        } else {
            for (int i = k + 1; i < n; i++) {
                answer[i] = left++;
            }
        }
        
        return answer;
    }
}

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

Задача: 1046. Last Stone Weight Сложность: easy Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y имеет новый вес y - x. В конце игры остается не более одного камня. Верните вес последнего оставшегося камня. Если камней не осталось, верните 0. Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

import java.util.Collections;
import java.util.PriorityQueue;

public class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int stone : stones) {
            maxHeap.add(stone);
        }
        
        while (maxHeap.size() > 1) {
            int first = maxHeap.poll();
            int second = maxHeap.poll();
            if (first != second) {
                maxHeap.add(first - second);
            }
        }
        
        return maxHeap.isEmpty() ? 0 : maxHeap.poll();
    }
}

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

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

Задача: 1531. String Compression II Сложность: hard Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной. Найдите минимальную длину сжатой версии строки s после удаления не более k символов. Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

👨‍💻 Алгоритм: 1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования. 2⃣Для определения состояния DP используем следующие параметры: количество пройденных символов (чтобы знать, какой символ обрабатывать следующим), последний добавленный символ в сжатую строку (чтобы определить изменение сжатия при добавлении нового символа), количество последнего символа (для правильного изменения длины сжатия при добавлении символа) и количество оставшихся символов, которые можно удалить. 3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия. 😎 Решение:

import java.util.*;

public class Solution {
    private Map<Integer, Integer> memo = new HashMap<>();
    private Set<Integer> add = Set.of(1, 9, 99);

    public int getLengthOfOptimalCompression(String s, int k) {
        return dp(s, 0, (char) ('a' + 26), 0, k);
    }

    private int dp(String s, int idx, char lastChar, int lastCharCount, int k) {
        if (k < 0) {
            return Integer.MAX_VALUE / 2;
        }

        if (idx == s.length()) {
            return 0;
        }

        int key = idx * 101 * 27 * 101 + (lastChar - 'a') * 101 * 101 + lastCharCount * 101 + k;

        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int deleteChar = dp(s, idx + 1, lastChar, lastCharCount, k - 1);
        int keepChar;
        if (s.charAt(idx) == lastChar) {
            keepChar = dp(s, idx + 1, lastChar, lastCharCount + 1, k) + (add.contains(lastCharCount) ? 1 : 0);
        } else {
            keepChar = dp(s, idx + 1, s.charAt(idx), 1, k) + 1;
        }
        int res = Math.min(keepChar, deleteChar);
        memo.put(key, res);

        return res;
    }
}

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

В турагентство на удаленку требуются стажеры Клиентов предоставим. Можно без опыта и совмещая с основной работой или декретом. С нас обучение с гарантированной стажировкой. Доход после обучения: от 50 000₽ до 220 000₽. Оплата в процессе обучения зависит от вашей вовлеченности. Задачи: Помогать людям организовывать путешествия: подбор самых выгодных предложений на отдых со скидкой до 50% в новых сервисах бронирования. Условия: ✅ Без опыта — обучение с нуля за 2 месяца, первые выплаты в среднем в течение 2 недель; ✅Удаленная работа или совмещение с офисом (по желанию, зависит от вашего города). Хотите проверить, подойдет ли это вам? Регистрируйтесь на бесплатный вводный урок, на котором узнаете: — как подбирать туры для себя и близких с выгодой до 40% — как получать комиссию 7-10% с каждого тура. Узнать больше #реклама 16+ via-tourism-school.space О рекламодателе

Задача: 977. Squares of a Sorted Array Сложность: easy Дан целочисленный массив nums, отсортированный в неубывающем порядке. Верните массив квадратов каждого числа, отсортированный в неубывающем порядке. Пример:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

👨‍💻 Алгоритм: 1⃣Создайте массив квадратов каждого элемента. 2⃣Отсортируйте массив квадратов. 3⃣Верните отсортированный массив квадратов. 😎 Решение:

import java.util.Arrays;

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = nums[i] * nums[i];
        }
        Arrays.sort(ans);
        return ans;
    }
}

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

Как списать долги? Бесплатно через МФЦ! Долги от 200 000₽. Поможем бесплатно списать долг и расторгнуть все кредитные договоры! Узнать больше #реклама нет-кредит.рф О рекламодателе

Задача: 463. Island Perimeter Сложность: easy Дан массив размером row x col, представляющий карту, где grid[i][j] = 1 обозначает сушу, а grid[i][j] = 0 обозначает воду. Клетки сетки соединены горизонтально/вертикально (не по диагонали). Сетка полностью окружена водой, и на ней находится ровно один остров (т.е. одна или более соединённых ячеек суши). У острова нет "озёр", то есть вода внутри не соединена с водой вокруг острова. Одна ячейка - это квадрат со стороной 1. Сетка прямоугольная, ширина и высота не превышают 100. Определите периметр острова. Пример:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

👨‍💻 Алгоритм: 1⃣Пройти через каждую ячейку сетки и, когда вы находитесь в ячейке с значением 1 (ячейка суши), проверить окружающие (СВЕРХУ, СПРАВА, СНИЗУ, СЛЕВА) ячейки. 2⃣Ячейка суши без каких-либо окружающих ячеек суши будет иметь периметр 4. Вычесть 1 за каждую окружающую ячейку суши. 3⃣Когда вы находитесь в ячейке с значением 0 (ячейка воды), ничего не делать. Просто перейти к следующей ячейке. 😎 Решение:

public class Solution {
    public int islandPerimeter(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        int result = 0;
        
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    int up = (r == 0) ? 0 : grid[r-1][c];
                    int left = (c == 0) ? 0 : grid[r][c-1];
                    int down = (r == rows-1) ? 0 : grid[r+1][c];
                    int right = (c == cols-1) ? 0 : grid[r][c+1];
                    
                    result += 4 - (up + left + right + down);
                }
            }
        }
        
        return result;
    }
}

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка для вас и 3-х ваших близких 30 дней бесплатно. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте сейчас❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

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

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

import java.util.*;

class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        Set<Integer> visited = new HashSet<>();
        List<Set<Integer>> components = new ArrayList<>();
        
        void dfs(int node) {
            Stack<Integer> stack = new Stack<>();
            stack.push(node);
            Set<Integer> component = new HashSet<>();
            while (!stack.isEmpty()) {
                int u = stack.pop();
                if (!visited.contains(u)) {
                    visited.add(u);
                    component.add(u);
                    for (int v = 0; v < n; v++) {
                        if (graph[u][v] == 1 && !visited.contains(v)) {
                            stack.push(v);
                        }
                    }
                }
            }
            components.add(component);
        }
        
        for (int i = 0; i < n; i++) {
            if (!visited.contains(i)) {
                dfs(i);
            }
        }
        
        int[] infectedInComponent = new int[components.size()];
        int[] nodeToComponent = new int[n];
        Arrays.fill(nodeToComponent, -1);
        
        for (int idx = 0; idx < components.size(); idx++) {
            Set<Integer> component = components.get(idx);
            for (int node : component) {
                nodeToComponent[node] = idx;
                if (Arrays.stream(initial).anyMatch(x -> x == node)) {
                    infectedInComponent[idx]++;
                }
            }
        }
        
        int minInfected = Integer.MAX_VALUE;
        int resultNode = Arrays.stream(initial).min().getAsInt();
        
        for (int node : initial) {
            int componentIdx = nodeToComponent[node];
            if (infectedInComponent[componentIdx] == 1) {
                int componentSize = components.get(componentIdx).size();
                if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
                    minInfected = componentSize;
                    resultNode = node;
                }
            }
        }
        
        return resultNode;
    }
}

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

⚡️Начинающий в Android-разработке? Хотите создавать кроссплатформенные приложения с минимальными затратами? 15 июля в 20:00 МСК на открытом вебинаре курса «Android Developer» мы создадим простое приложение — игру крестики-нолики, выделим логику в кроссплатформенный модуль и создадим визуальную часть с использованием Compose multiplatform. Этот урок будет полезен тем, кто хочет освоить основы UI-разработки на Android и перейти к созданию кроссплатформенных приложений. Вы поймете, почему выгодно начинать с Android, и как с помощью подхода write once and run anywhere разрабатывать для мобильных устройств и других платформ. 👉Все участники получат скидку на полный курс, зарегистрируйтесь, чтобы не пропустить: https://otus.pw/Lnz6/ Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Получи грант на обучение в Центральном университете Несгораемый грант до 2 800 000 Р на учебу в бакалавриате Центрального университета. Подробнее о гранте: – Покрывает до 100% стоимости обучения – Выдается на все 4 года обучения в вузе – Сумма гранта не уменьшается, а может увеличиться за дополнительные достижения и успехи в учебе. Для учеников 10-х и 11-х классов. Участвуй в отборе! Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 1189. Maximum Number of Balloons Сложность: easy Дана строка text. Вы хотите использовать символы строки text, чтобы сформировать как можно больше экземпляров слова "balloon". Каждый символ строки text можно использовать не более одного раза. Верните максимальное количество экземпляров, которые можно сформировать. Пример:

Input: text = "nlaebolko"
Output: 1

👨‍💻 Алгоритм: 1⃣Подсчитайте количество появлений каждого символа 'b', 'a', 'l', 'o', 'n' в строке text. 2⃣Вычислите потенциал для каждого символа: для 'b' и 'a' потенциал равен количеству их появлений, для 'l' и 'o' потенциал равен количеству их появлений, деленному на 2, а для 'n' потенциал равен количеству его появлений. 3⃣Найдите символ с наименьшим потенциалом среди 'b', 'a', 'l', 'o', 'n', который ограничивает количество возможных слов "balloon", и верните это значение. 😎 Решение:

class Solution {
    public int maxNumberOfBalloons(String text) {
        int bCount = 0, aCount = 0, lCount = 0, oCount = 0, nCount = 0;

        for (int i = 0; i < text.length(); i++) {
            if (text.charAt(i) == 'b') {
                bCount++;
            } else if (text.charAt(i) == 'a') {
                aCount++;
            } else if (text.charAt(i) == 'l') {
                lCount++;
            } else if (text.charAt(i) == 'o') {
                oCount++;
            } else if (text.charAt(i) == 'n') {
                nCount++;
            }
        }

        lCount = lCount / 2;
        oCount = oCount / 2;

        return Math.min(bCount, Math.min(aCount, Math.min(lCount, Math.min(oCount, nCount))));
    }
}

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

Задача: 1024. Video Stitching Сложность: medium Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1. Пример:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

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

import java.util.Arrays;

public class Solution {
    public int videoStitching(int[][] clips, int T) {
        Arrays.sort(clips, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int end = -1, end2 = 0, res = 0;
        
        for (int[] clip : clips) {
            if (end2 >= T || clip[0] > end2) break;
            if (end < clip[0] && clip[0] <= end2) {
                res++;
                end = end2;
            }
            end2 = Math.max(end2, clip[1]);
        }
        return end2 >= T ? res : -1;
    }
}

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

🎉 easyoffer 2.0 — релиз уже в этом месяце! Вас ждут новые фичи, о которых мы ранее даже не упоминали. Они сделают путь к офферам ещё быстрее и эффективнее. Расскажу о них чуть позже 👀 В честь запуска мы готовим ограниченную акцию: Первые 500 покупателей получат: 🚀 PRO тариф на 1 год с 50% скидкой Что нужно сделать: 🔔 Подпишитесь на этот Telegram-канал, чтобы первыми узнать о старте релиза. Сообщение появится в нем раньше, чем где-либо еще — вы успеете попасть в число первых 500 и получить максимальную выгоду. 🎁 А еще только для подписчиков канала ценный бонус в подарок к PRO тарифу. 📅 Официальный запуск — уже совсем скоро. Следите за новостями и не пропустите старт!

Пассивный доход от недвижимости с вложениями от 10 000 ₽ ЗПИФ Сбера позволяет инвестировать в коммерческую недвижимость без крупных вложений. Вход — от 10 000 ₽. Управление осуществляют эксперты. Оформить паи можно онлайн в СберБанк Онлайн. Узнать больше Финансовые услуги оказывает: ПАО Сбербанк. #реклама 16+ sberbank.com О рекламодателе

Задача: 988. Smallest String Starting From Leaf Сложность: medium Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'. Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня. Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей. Например, "ab" лексикографически меньше, чем "aba". Лист узла - это узел, у которого нет потомков. Пример:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка: Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк). Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы. 2⃣Обход дерева: Если текущий узел пуст (null), просто вернитесь из функции. Добавьте текущий символ (соответствующий значению узла) в начало строки пути. Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше. Рекурсивно вызовите dfs для левого и правого потомков текущего узла. 3⃣Возврат результата: Вызовите функцию dfs с корневым узлом и пустым путем. Верните значение переменной ans, содержащее лексикографически наименьший путь от листа до корня. 😎 Решение:

public class Solution {
    private String ans = "~";

    public String smallestFromLeaf(TreeNode root) {
        dfs(root, new StringBuilder());
        return ans;
    }

    private void dfs(TreeNode node, StringBuilder path) {
        if (node == null) return;
        path.append((char) (node.val + 'a'));
        if (node.left == null && node.right == null) {
            path.reverse();
            String s = path.toString();
            path.reverse();
            if (s.compareTo(ans) < 0) {
                ans = s;
            }
        }
        dfs(node.left, path);
        dfs(node.right, path);
        path.deleteCharAt(path.length() - 1);
    }
}

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

В турагентство на удаленку требуются стажеры Клиентов предоставим. Можно без опыта и совмещая с основной работой или декретом. С нас обучение с гарантированной стажировкой. Доход после обучения: от 50 000₽ до 220 000₽. Оплата в процессе обучения зависит от вашей вовлеченности. Задачи: Помогать людям организовывать путешествия: подбор самых выгодных предложений на отдых со скидкой до 50% в новых сервисах бронирования. Условия: ✅ Без опыта — обучение с нуля за 2 месяца, первые выплаты в среднем в течение 2 недель; ✅Удаленная работа или совмещение с офисом (по желанию, зависит от вашего города). Хотите проверить, подойдет ли это вам? Регистрируйтесь на бесплатный вводный урок, на котором узнаете: — как подбирать туры для себя и близких с выгодой до 40% — как получать комиссию 7-10% с каждого тура. Узнать больше #реклама 16+ via-tourism-school.space О рекламодателе

Задача: 238. Product of Array Except Self Сложность: medium Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i]. Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число. Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления. Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

👨‍💻 Алгоритм: 1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1]. 2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево. 3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его. 😎 Решение:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] L = new int[length];
        int[] R = new int[length];
        int[] answer = new int[length];

        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }

        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }

        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }

        return answer;
    }
}

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