Java | LeetCode

Задача: 1255. Maximum Score Words Formed by Letters Сложность: hard Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно. Пример:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23

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

import java.util.*;

public class Solution {
    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        int maxScore = 0;
        Map<Character, Integer> letterCount = new HashMap<>();
        for (char ch : letters) {
            letterCount.put(ch, letterCount.getOrDefault(ch, 0) + 1);
        }

        for (int i = 1; i < (1 << words.length); i++) {
            int currScore = 0;
            Map<Character, Integer> usedLetters = new HashMap<>();
            boolean valid = true;
            for (int j = 0; j < words.length; j++) {
                if ((i & (1 << j)) != 0) {
                    for (char ch : words[j].toCharArray()) {
                        usedLetters.put(ch, usedLetters.getOrDefault(ch, 0) + 1);
                        if (usedLetters.get(ch) > letterCount.getOrDefault(ch, 0)) {
                            valid = false;
                            break;
                        }
                        currScore += score[ch - 'a'];
                    }
                }
                if (!valid) break;
            }
            if (valid) {
                maxScore = Math.max(maxScore, currScore);
            }
        }

        return maxScore;
    }
}

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

Начисляем 10000 бонусов каждому за открытие бизнес-счёта Откройте счет для бизнеса в Москве, получите 10 000 бонусов СберБизнес Спасибо и тратьте их на развитие вашего бизнеса. Например: ✅ Подключайте СберТаргет и запускайте рекламные кампании для привлечения клиентов ✅ Доверьте документацию профессионалам с онлайн-сервисом Бухгалтерии для бизнеса ✅ Воспользуйтесь Комплаенс-помощником, чтобы проверить операции на наличие рисков по 115-Ф3 И главный лайфхак — теперь бонусы можно потратить на подписку СберБизнес Прайм. Благодаря ей обслуживание бизнес-счёта станет для вас бесплатным на несколько месяцев! Успейте принять участие в акции и получите гарантированный буст для развития бизнеса! Узнать больше Финансовые услуги оказывает: ПАО Сбербанк. #реклама sberbank.com О рекламодателе

Задача: 133. Clone Graph Сложность: medium Дана ссылка на узел в связанном неориентированном графе. Верните глубокую копию (клон) графа. Каждый узел в графе содержит значение (целое число) и список (List[Node]) своих соседей. Пример:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

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

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;

class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val, List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }

        HashMap<Node, Node> visited = new HashMap();
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(node);
        visited.put(node, new Node(node.val, new ArrayList()));

        while (!queue.isEmpty()) {
            Node n = queue.remove();
            for (Node neighbor : n.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    visited.put(neighbor, new Node(neighbor.val, new ArrayList()));
                    queue.add(neighbor);
                }
                visited.get(n).neighbors.add(visited.get(neighbor));
            }
        }
        return visited.get(node);
    }
}

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

Задача: 528. Random Pick with Weight Сложность: medium Вам дан массив положительных целых чисел w, где w[i] описывает вес индекса i. Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w). Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%). Пример:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

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

class Solution {
    private int[] prefixSums;
    private int totalSum;

    public Solution(int[] w) {
        this.prefixSums = new int[w.length];

        int prefixSum = 0;
        for (int i = 0; i < w.length; ++i) {
            prefixSum += w[i];
            this.prefixSums[i] = prefixSum;
        }
        this.totalSum = prefixSum;
    }

    public int pickIndex() {
        double target = this.totalSum * Math.random();
        int i = 0;
        for (; i < this.prefixSums.length; ++i) {
            if (target < this.prefixSums[i])
                return i;
        }
        return i - 1;
  }
}

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

Гайд для HRD и HRBP по проведению эффективных вебинаров Как HRD и HRBP ускорить адаптацию и обучение новых сотрудников с помощью вебинаров? Гайд от МТС Линк по подготовке и проведению эффективных вебинаров. ✅ В гайде: - Как лучше использовать вебинары для онбординга и обучения новых сотрудников; - Как упростить рекрутинг и снизить нагрузку на HR-команду; - Как ускорить адаптацию новичков и сократить отток на испытательном сроке; - Как сэкономить время на организации вебинара и пригласить всех участников в 2 клика. Бонус внутри: 5 прикладных советов по контролю внимания участников во время вебинара ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Ура, друзья! Изиоффер переходит в публичное бета-тестирование! 🎉 Что нового: 🟢Анализ IT собеседований на основе 4500+ реальных интервью 🟢Вопросы из собеседований с вероятностью встречи 🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов 🟢Пример лучшего ответа 🟢Задачи из собеседований 🟢Тестовые задания 🟢Примеры собеседований 🟢Фильтрация всего контента по грейдам, компаниям 🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек 🟡Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро) 🟢Автоотклики на HeadHunter 🟢Закрытое сообщество easyoffer 💎 Акция в честь открытия для первых 500 покупателей: 🚀 Скидка 50% на PRO тариф на 1 год (15000₽ → 7500₽) 🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 525. Contiguous Array Сложность: medium Дан бинарный массив nums. Верните максимальную длину непрерывного подмассива с равным количеством 0 и 1. Пример:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

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

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        countMap.put(0, -1);
        int maxLength = 0;
        int count = 0;
        
        for (int i = 0; i < nums.length; i++) {
            count += (nums[i] == 1 ? 1 : -1);
            
            if (countMap.containsKey(count)) {
                maxLength = Math.max(maxLength, i - countMap.get(count));
            } else {
                countMap.put(count, i);
            }
        }
        
        return maxLength;
    }
}

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

Франшиза кафе Мидий в Уфе! Окупаемость от 4 месяцев! ⚡Акция - дизайн-проект помещения в подарок до конца месяца! 💰 Получайте прибыль уже через 30 дней! ✅ Сопровождаем партнера на стадии открытия и после! - Юридическое оформление; - Подберем помещение; - Разработаем дизайн-проект; - Поможем в подборе сотрудников; - Адаптируем меню, тех. карты, поставщиков; - Выстроим маркетинг; ⚡Успейте открыть в вашем городе! 📊Мидии — новый тренд в общепите! Перейти на сайт #реклама musselhouse-franchise.ru О рекламодателе

Задача: 950. Reveal Cards In Increasing Order Сложность: medium Вам дана колода целочисленных массивов. Имеется колода карт, в которой каждая карта имеет уникальное целое число. Целое число на i-й карте - deck[i]. Вы можете упорядочить колоду в любом порядке. Изначально все карты в одной колоде лежат лицевой стороной вниз (нераскрытыми). Вы будете выполнять следующие действия несколько раз, пока все карты не будут раскрыты: возьмите верхнюю карту колоды, раскройте ее и выньте из колоды. Если в колоде еще есть карты, положите следующую верхнюю карту колоды на дно колоды. Если еще есть нераскрытые карты, вернитесь к шагу 1. В противном случае остановитесь. Верните порядок колоды, при котором карты раскрываются в порядке возрастания. Обратите внимание, что первая запись в ответе считается верхом колоды. Пример:

Input: deck = [17,13,11,2,3,5,7]
Output: [2,13,3,11,5,17,7]

👨‍💻 Алгоритм: 1⃣Создать индексы карт в порядке, в котором они будут раскрываться. 2⃣Отсортировать колоду карт по возрастанию. 3⃣Заполнить результат раскрытия карт по ранее созданным индексам. 😎 Решение:

import java.util.*;

class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        int n = deck.length;
        Queue<Integer> index = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            index.add(i);
        }
        
        Arrays.sort(deck);
        int[] result = new int[n];
        
        for (int card : deck) {
            result[index.poll()] = card;
            if (!index.isEmpty()) {
                index.add(index.poll());
            }
        }
        
        return result;
    }
}

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

Задача: 69. Sqrt(x) Сложность: easy Дано неотрицательное целое число x. Верните квадратный корень из x, округлённый вниз до ближайшего целого числа. Возвращаемое целое число также должно быть неотрицательным. Вы не должны использовать встроенные функции или операторы для возведения в степень. Например, не следует использовать pow(x, 0.5) в C++ или x ** 0.5 в Python. Пример:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

👨‍💻 Алгоритм: 1⃣Если x < 2, верните x. Установите левую границу left = 2 и правую границу right = x / 2. 2⃣Пока left ≤ right: Возьмите num = (left + right) / 2 в качестве предположения. Вычислите num × num и сравните его с x: Если num × num > x, переместите правую границу right = pivot − 1. В противном случае, если num × num < x, переместите левую границу left = pivot + 1. В противном случае num × num == x, целочисленный квадратный корень найден, давайте вернем его. 3⃣Верните right. 😎 Решение:

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;

        long num;
        int pivot, left = 2, right = x / 2;
        while (left <= right) {
            pivot = left + (right - left) / 2;
            num = (long) pivot * pivot;
            if (num > x) right = pivot - 1;
            else if (num < x) left = pivot + 1;
            else return pivot;
        }

        return right;
    }
}

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

Внимание ученики 1-9 класса и их родители! С 1 июня стартует бесплатная 3-х месячная программа по углубленному изучению школьных предметов с 1 по 4 класс, с 5 по 8 класс и с 9 по 11 класс от резидента Сколково. Программа предлагает подтянуть знания по основным предметам: — Математика: 83% учеников повышают оценку до 4 или 5 за 2 месяца — Подготовиться к контрольным и ВПР — Подготовка к ОГЭ и ЕГЭ без стресса — Русский язык: средний балл ВПР 87 при общешкольном показателе 65 — Английский: 72% учащихся переходят на уровень выше за 4 месяца Для участия достаточно заполнить заявку. Жмите "Записаться" Записаться #реклама 16+ mrqz.me О рекламодателе

Задача: 1319. Number of Operations to Make Network Connected Сложность: medium Дано n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть. Вам даны начальные соединения сети. Вы можете извлекать определённые кабели между двумя напрямую соединёнными компьютерами и размещать их между любыми парами несоединённых компьютеров, чтобы сделать их напрямую соединёнными. Верните минимальное количество раз, которое необходимо сделать это, чтобы соединить все компьютеры. Если это невозможно, верните -1. Пример:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

👨‍💻 Алгоритм: 1⃣Проверьте размер connections. Если он меньше n - 1, у нас недостаточно ребер, чтобы соединить весь граф. В этом случае возвращаем -1. 2⃣Создайте список смежности с помощью connections, где adj[x] содержит всех соседей узла x. Создайте целое число numberOfConnectedComponents, которое хранит количество компонент связности в графе. Инициализируйте его значением 0. 3⃣Создайте массив visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS: Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i. Отметьте узел как посещенный. Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла. Верните numberOfConnectedComponents - 1. 😎 Решение:

class Solution {
    public void dfs(int node, Map<Integer, List<Integer>> adj, boolean[] visit) {
        visit[node] = true;
        if (!adj.containsKey(node)) {
            return;
        }
        for (int neighbor : adj.get(node)) {
            if (!visit[neighbor]) {
                visit[neighbor] = true;
                dfs(neighbor, adj, visit);
            }
        }
    }

    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) {
            return -1;
        }

        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] connection : connections) {
            adj.computeIfAbsent(connection[0], k -> new ArrayList<Integer>()).add(connection[1]);
            adj.computeIfAbsent(connection[1], k -> new ArrayList<Integer>()).add(connection[0]);
        }

        int numberOfConnectedComponents = 0;
        boolean[] visit = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                numberOfConnectedComponents++;
                dfs(i, adj, visit);
            }
        }

        return numberOfConnectedComponents - 1;
    }
}

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

Дизайн в FIGMA с нуля. Бесплатный курс + портфолио Онлайн-программа с наставником и чатом. Дизайн от профессионалов. Доступ 0 руб. Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 232. Implement Queue using Stacks Сложность: easy Реализуйте очередь (FIFO) с использованием только двух стеков. Реализованная очередь должна поддерживать все функции обычной очереди (push, peek, pop и empty). Реализуйте класс MyQueue: void push(int x) добавляет элемент x в конец очереди. int pop() удаляет элемент из начала очереди и возвращает его. int peek() возвращает элемент из начала очереди. boolean empty() возвращает true, если очередь пуста, и false в противном случае. Пример:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

👨‍💻 Алгоритм: 1⃣Добавление элемента: Для метода push(int x) переместите все элементы из стека s1 в стек s2. Добавьте элемент x в стек s2. Затем переместите все элементы обратно из стека s2 в стек s1. Если стек s1 пуст, обновите переменную front значением x. 2⃣Удаление и проверка первого элемента: Для метода pop() удалите элемент из начала очереди, извлекая верхний элемент из стека s1. Обновите переменную front на новый верхний элемент стека s1, если он не пуст. Для метода peek() верните значение переменной front, так как она всегда хранит первый элемент очереди. 3⃣Проверка на пустоту: Для метода empty() верните результат проверки, является ли стек s1 пустым. 😎 Решение:

class MyQueue {
    private Stack<Integer> s1 = new Stack<>();
    private Stack<Integer> s2 = new Stack<>();
    private int front;

    public void push(int x) {
        if (s1.empty())
            front = x;
        while (!s1.isEmpty())
            s2.push(s1.pop());
        s2.push(x);
        while (!s2.isEmpty())
            s1.push(s2.pop());
    }

    public int pop() {
        int res = s1.pop();
        if (!s1.empty())
            front = s1.peek();
        return res;
    }

    public boolean empty() {
        return s1.isEmpty();
    }

    public int peek() {
        return front;
    }
}

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

Задача: 331. Verify Preorder Serialization of a Binary Tree Сложность: medium Один из способов сериализации бинарного дерева — использование обхода в порядке предварительного прохода (preorder traversal). Когда мы встречаем ненулевой узел, мы записываем значение узла. Если это нулевой узел, мы записываем его с использованием специального значения, такого как '#'. Дана строка, содержащая значения, разделенные запятыми, представляющие предварительный обход дерева (preorder). Верните true, если это правильная сериализация предварительного обхода бинарного дерева. Гарантируется, что каждое значение в строке, разделенное запятыми, должно быть либо целым числом, либо символом '#', представляющим нулевой указатель. Вы можете предположить, что формат ввода всегда действителен. Например, он никогда не может содержать две последовательные запятые, такие как "1,,3". Примечание: Вам не разрешено восстанавливать дерево. Пример:

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

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

class Solution {
  public boolean isValidSerialization(String preorder) {
    int slots = 1;

    for(String node : preorder.split(",")) {
      --slots;

      if (slots < 0) return false;

      if (!node.equals("#")) slots += 2;
    }

    return slots == 0;
  }
}

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

Бесплатный марафон похудения для женщин старше 40 лет Метаболическое похудение - это уникальный метод, который поможет избавиться от лишнего веса раз и навсегда без голодовок, диет и изнуряющих тренировок. Уже на бесплатном марафоне вы сможете похудеть на 2-4 кг. На марафоне вас ждут: 👍Меню питания на весь день для всех участниц 👍Эфир о диетах: почему после диет вес всегда возвращается 👍Общий чат для всех участниц марафона ⚡Но самое главное: после нашего марафона вы точно будете знать, как похудеть раз и навсегда без вреда для здоровья! Каждая участница марафона получит пошаговый план похудения. Записаться #реклама 16+ adv.vesbalans.ru О рекламодателе

Задача: 445. Add Two Numbers II Сложность: medium Вам даны два непустых связанных списка, представляющих два неотрицательных целых числа. Самый значимый разряд стоит первым, и каждый из их узлов содержит одну цифру. Сложите два числа и верните сумму в виде связанного списка. Вы можете предположить, что оба числа не содержат начальных нулей, за исключением самого числа 0. Пример:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

👨‍💻 Алгоритм: 1⃣Создайте два связанных списка r1 и r2, чтобы хранить перевернутые связанные списки l1 и l2 соответственно. Создайте два целых числа totalSum и carry для хранения суммы и переноса текущих цифр. Создайте новый ListNode, ans, который будет хранить сумму текущих цифр. Мы будем складывать два числа, используя перевернутый список, добавляя цифры по одной. Продолжаем, пока не пройдем все узлы в r1 и r2. 2⃣Если r1 не равен null, добавляем r1.val к totalSum. Если r2 не равен null, добавляем r2.val к totalSum. Устанавливаем ans.val = totalSum % 10. Сохраняем перенос как totalSum / 10. Создаем новый ListNode, newNode, который будет иметь значение как перенос. Устанавливаем next для newNode как ans. Обновляем ans = newNode, чтобы использовать ту же переменную ans для следующей итерации. Обновляем totalSum = carry. 3⃣Если carry == 0, это означает, что newNode, созданный в финальной итерации цикла while, имеет значение 0. Поскольку мы выполняем ans = newNode в конце каждой итерации цикла while, чтобы избежать возврата связанного списка с головой, равной 0 (начальный ноль), возвращаем следующий элемент, т.е. возвращаем ans.next. В противном случае, если перенос не равен 0, значение ans не равно нулю. Следовательно, просто возвращаем ans. 😎 Решение:

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode temp = null;
        while (head != null) {
            temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode r1 = reverseList(l1);
        ListNode r2 = reverseList(l2);

        int totalSum = 0;
        int carry = 0;
        ListNode ans = new ListNode();
        while (r1 != null || r2 != null) {
            if (r1 != null) {
                totalSum += r1.val;
                r1 = r1.next;
            }
            if (r2 != null) {
                totalSum += r2.val;
                r2 = r2.next;
            }

            ans.val = totalSum % 10;
            carry = totalSum / 10;
            ListNode head = new ListNode(carry);
            head.next = ans;
            ans = head;
            totalSum = carry;
        }

        return carry == 0 ? ans.next : ans;
    }
}

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

Зарабатывайте на установках Яндекс Браузера Партнёрская программа для сервисных центров, магазинов компьютерной техники, сайтов для скачивания файлов и авторов статей. Вы можете предлагать его своим клиентам и аудитории — и зарабатывать на новых установках. Выплаты до 500₽ за каждую установку Яндекс Браузера. Подать заявку #реклама 0+ partner.browser.yandex.ru О рекламодателе

Задача: 592. Fraction Addition and Subtraction Сложность: medium Дана строка, представляющая выражение сложения и вычитания дробей, верните результат вычисления в строковом формате. Окончательный результат должен быть несократимой дробью. Если ваш окончательный результат является целым числом, преобразуйте его в формат дроби с знаменателем 1. Таким образом, 2 должно быть преобразовано в 2/1. Пример:

Input: expression = "-1/2+1/2+1/3"
Output: "1/3"

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

class Solution {
  public String fractionAddition(String expression) {
    List<Character> sign = new ArrayList<>();
    if (expression.charAt(0) != '-') sign.add('+');
    for (int i = 0; i < expression.length(); i++) {
      if (expression.charAt(i) == '+' || expression.charAt(i) == '-')
        sign.add(expression.charAt(i));
    }
    int prev_num = 0, prev_den = 1, i = 0;
    for (String sub : expression.split("(\\+)|(-)")) {
      if (sub.length() > 0) {
        String[] fraction = sub.split("/");
        int num = (Integer.parseInt(fraction[0]));
        int den = (Integer.parseInt(fraction[1]));
        int g = Math.abs(gcd(den, prev_den));
        if (sign.get(i++) == '+') prev_num = prev_num * den / g + num * prev_den / g;
        else prev_num = prev_num * den / g - num * prev_den / g;
        prev_den = den * prev_den / g;
        g = Math.abs(gcd(prev_den, prev_num));
        prev_num /= g;
        prev_den /= g;
      }
    }
    return prev_num + "/" + prev_den;
  }

  public int gcd(int a, int b) {
    while (b != 0) {
      int t = b;
      b = a % b;
      a = t;
    }
    return a;
  }
}

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

Получи грант до 1,2 млн руб. на обучение в магистратуре Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 4 офлайн программы по востребованным направлениям ИТ - Онлайн-программа по машинному обучению - 300 мест с грантами до 1,2 млн руб. - Вечерние занятия и учеба по выходным — удобно совмещать с работой - Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса - Возможность стажировок и трудоустройства в ведущих компаниях - Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе