Java | LeetCode

Задача: 404. Sum of Left Leaves Сложность: easy Если задан корень бинарного дерева, верните сумму всех левых листьев. Лист - это узел, не имеющий детей. Левый лист - это лист, который является левым ребенком другого узла. Пример:

    
        Input: root = [3,9,20,null,null,15,7]
Output: 24{}
    

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

    
        public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return dfs(root, false);
    }
    
    private int dfs(TreeNode node, boolean isLeft) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return isLeft ? node.val : 0;
        return dfs(node.left, true) + dfs(node.right, false);
    }
}{}
    

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

CRM, которая помогает управлять отделом продаж Что делает Битрикс24 CRM: – ставит задачи менеджерам автоматически – интегрируется с 1С и онлайн-кассами – показывает, где теряются деньги – возвращает клиентов и ищет повторные продажи – помогает руководителю контролировать процессы. Битрикс24 CRM работает на результат. Регистрируйтесь бесплатно Зарегистрироваться #реклама 16+ bitrix24.ru О рекламодателе

Задача: 371. Sum of Two Integers Сложность: medium Даны два целых числа a и b. Вернуть сумму этих двух чисел, не используя операторы + и -. Пример:

    
        Input: a = 1, b = 2
Output: 3{}
    

👨‍💻 Алгоритм: 1⃣Упростите задачу до двух случаев: сумма или вычитание двух положительных целых чисел: x ± y, где x > y. Запомните знак результата. 2⃣Если нужно вычислить сумму: Пока перенос не равен нулю (y != 0): Текущий ответ без переноса равен XOR x и y: answer = x ^ y. Текущий перенос равен сдвинутому влево AND x и y: carry = (x & y) << 1. Подготовьтесь к следующему циклу: x = answer, y = carry. Верните x * sign. 3⃣Если нужно вычислить разность: Пока заимствование не равно нулю (y != 0): Текущий ответ без заимствования равен XOR x и y: answer = x ^ y. Текущее заимствование равно сдвинутому влево AND НЕ x и y: borrow = ((~x) & y) << 1. Подготовьтесь к следующему циклу: x = answer, y = borrow. Верните x * sign. 😎 Решение:

    
        public class Solution {
    public int getSum(int a, int b) {
        int x = Math.abs(a), y = Math.abs(b);
        if (x < y) return getSum(b, a);
        int sign = a > 0 ? 1 : -1;

        if (a * b >= 0) {
            while (y != 0) {
                int carry = (x & y) << 1;
                x ^= y;
                y = carry;
            }
        } else {
            while (y != 0) {
                int borrow = ((~x) & y) << 1;
                x ^= y;
                y = borrow;
            }
        }
        return x * sign;
    }
}{}
    

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

Совершенная технология Oral-B iO* в ассортименте Oral-B. Беспощадна к налёту, нежная к дёснам. Купить #реклама market.yandex.ru О рекламодателе

Задача: 1662. Check If Two String Arrays are Equivalent Сложность: easy Даны два массива строк word1 и word2. Верните true, если два массива представляют одну и ту же строку, и false в противном случае. Строка представлена массивом, если элементы массива, соединенные в порядке, образуют строку. Пример:

    
        Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.{}
    

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

    
        class Solution {
    public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
        List<Character> list2 = new ArrayList<>();
        for (String s : word2) {
            for (char c : s.toCharArray()) {
                list2.add(c);
            }
        }
        int list2Length = list2.size();
        int index = 0;
        for (String s : word1) {
            for (char c : s.toCharArray()) {
                if (index >= list2Length || c != list2.get(index)) {
                    return false;
                }
                index++;
            }
        }
        return true;
    }
}{}
    

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

🔍Тестовое собеседование с Java-разработчиком из Мегафон уже завтра Уже сегодня в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Java-разработчика. Как это будет: 📂 Мария Пивоварова, старший разработчик в Мегафон, будет задавать реальные вопросы и задачи разработчику-добровольцу 📂 Мария будет комментировать каждый ответ респондента, чтобы дать понять, чего от вас ожидает собеседующий на интервью 📂 В конце можно будет задать любой вопрос Марии Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для Java-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы. Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_sh_bot Реклама. О рекламодателе.

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

Задача: 1047. Remove All Adjacent Duplicates In String Сложность: easy Вам дана строка s, состоящая из строчных английских букв. Удаление дубликатов заключается в выборе двух соседних и одинаковых букв и их удалении. Мы многократно производим удаление дубликатов в s, пока не перестанем это делать. Верните конечную строку после того, как все такие удаления дубликатов будут произведены. Можно доказать, что ответ уникален. Пример:

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

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

    
        public class Solution {
    public String removeDuplicates(String s) {
        StringBuilder stack = new StringBuilder();
        for (char c : s.toCharArray()) {
            int len = stack.length();
            if (len > 0 && stack.charAt(len - 1) == c) {
                stack.deleteCharAt(len - 1);
            } else {
                stack.append(c);
            }
        }
        return stack.toString();
    }
}{}
    

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

Задача: 726. Number of Atoms Сложность: hard Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой. Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами. Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число. Пример:

    
        Input: formula = "H2O"
Output: "H2O"{}
    

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

    
        import java.util.*;

public class Solution {
    public String countOfAtoms(String formula) {
        Stack<Map<String, Integer>> stack = new Stack<>();
        stack.push(new HashMap<>());
        int n = formula.length();
        int i = 0;
        
        while (i < n) {
            if (formula.charAt(i) == '(') {
                stack.push(new HashMap<>());
                i++;
            } else if (formula.charAt(i) == ')') {
                Map<String, Integer> top = stack.pop();
                i++;
                int start = i;
                while (i < n && Character.isDigit(formula.charAt(i))) {
                    i++;
                }
                int multiplicity = i > start ? Integer.parseInt(formula.substring(start, i)) : 1;
                for (String name : top.keySet()) {
                    int count = top.get(name);
                    stack.peek().put(name, stack.peek().getOrDefault(name, 0) + count * multiplicity);
                }
            } else {
                int start = i;
                i++;
                while (i < n && Character.isLowerCase(formula.charAt(i))) {
                    i++;
                }
                String name = formula.substring(start, i);
                start = i;
                while (i < n && Character.isDigit(formula.charAt(i))) {
                    i++;
                }
                int multiplicity = i > start ? Integer.parseInt(formula.substring(start, i)) : 1;
                stack.peek().put(name, stack.peek().getOrDefault(name, 0) + multiplicity);
            }
        }
        
        Map<String, Integer> countMap = stack.pop();
        StringBuilder sb = new StringBuilder();
        for (String name : new TreeMap<>(countMap).keySet()) {
            sb.append(name);
            int count = countMap.get(name);
            if (count > 1) {
                sb.append(count);
            }
        }
        return sb.toString();
    }
}{}
    

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