Java | LeetCode

#hard Задача: 297. Serialize and Deserialize Binary Tree Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по сетевому соединению для последующего восстановления в той же или другой компьютерной среде. Разработайте алгоритм для сериализации и десериализации бинарного дерева. Нет ограничений на то, как ваш алгоритм сериализации/десериализации должен работать. Вам нужно просто гарантировать, что бинарное дерево может быть сериализовано в строку, и эта строка может быть десериализована в исходную структуру дерева. Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы. Пример:

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

👨‍💻 Алгоритм: 1⃣Сериализация дерева: Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree. Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None". 2⃣Пример: Начните с корня, узел 1, строка сериализации становится "1,". Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,". Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None"). Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,"). 3⃣Десериализация строки: Разделите строку на список значений. Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой. 😎 Решение:

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Codec {
    private void rserialize(TreeNode root, StringBuilder str) {
        if (root == null) {
            str.append("null,");
        } else {
            str.append(root.val).append(",");
            rserialize(root.left, str);
            rserialize(root.right, str);
        }
    }

    public String serialize(TreeNode root) {
        StringBuilder str = new StringBuilder();
        rserialize(root, str);
        return str.toString();
    }

    private TreeNode rdeserialize(LinkedList<String> data) {
        if (data.get(0).equals("null")) {
            data.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(data.remove(0)));
        root.left = rdeserialize(data);
        root.right = rdeserialize(data);
        return root;
    }

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

#medium Задача: 433. Minimum Genetic Mutation Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'. Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке. Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией. Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой. Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1. Обратите внимание, что начальная строка считается допустимой, поэтому она может не быть включена в банк. Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

👨‍💻 Алгоритм: 1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene. 2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen. 3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1. 😎 Решение:

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        Queue<String> queue = new LinkedList<>();
        Set<String> seen = new HashSet<>();
        queue.add(start);
        seen.add(start);
        
        int steps = 0;
        
        while (!queue.isEmpty()) {
            int nodesInQueue = queue.size();
            for (int j = 0; j < nodesInQueue; j++) {
                String node = queue.remove();
                if (node.equals(end)) {
                    return steps;
                }

                for (char c: new char[] {'A', 'C', 'G', 'T'}) {
                    for (int i = 0; i < node.length(); i++) {
                        String neighbor = node.substring(0, i) + c + node.substring(i + 1);
                        if (!seen.contains(neighbor) && Arrays.asList(bank).contains(neighbor)) {
                            queue.add(neighbor);
                            seen.add(neighbor);
                        }
                    }
                }
            }
            
            steps++;
        }
        
        return -1;
    }
}

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

#medium Задача: 298. Binary Tree Longest Consecutive Sequence Дан корень бинарного дерева, верните длину самого длинного пути последовательных значений. Путь последовательных значений — это путь, где значения увеличиваются на единицу вдоль пути. Обратите внимание, что путь может начинаться с любого узла в дереве, и вы не можете перейти от узла к его родителю на пути. Пример:

Input: root = [1,null,3,2,4,null,null,null,5]
Output: 3
Explanation: Longest consecutive sequence path is 3-4-5, so return 3.

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

class Solution {
    private int maxLength = 0;

    public int longestConsecutive(TreeNode root) {
        dfs(root, null, 0);
        return maxLength;
    }

    private void dfs(TreeNode node, TreeNode parent, int length) {
        if (node == null) return;
        if (parent != null && node.val == parent.val + 1) {
            length++;
        } else {
            length = 1;
        }
        maxLength = Math.max(maxLength, length);
        dfs(node.left, node, length);
        dfs(node.right, node, length);
    }
}

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

#medium Задача: 299. Bulls and Cows Вы играете в игру "Быки и коровы" со своим другом. Вы записываете секретное число и просите своего друга угадать, что это за число. Когда ваш друг делает предположение, вы даете ему подсказку со следующей информацией: Количество "быков", то есть цифры в предположении, которые находятся на правильной позиции. Количество "коров", то есть цифры в предположении, которые есть в вашем секретном числе, но находятся на неправильной позиции. Конкретно, это не-бычьи цифры в предположении, которые можно переставить так, чтобы они стали быками. Дано секретное число secret и предположение вашего друга guess, верните подсказку для предположения вашего друга. Подсказка должна быть в формате "xAyB", где x — количество быков, а y — количество коров. Обратите внимание, что и secret, и guess могут содержать повторяющиеся цифры. Пример:

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

👨‍💻 Алгоритм: 1⃣Инициализация счетчиков: Инициализируйте количество быков и коров значениями ноль. Создайте хеш-таблицу для хранения символов строки secret и их частот. 2⃣Обход строки guess: Для каждого символа ch в строке guess: Если ch присутствует в строке secret: Если текущий символ ch совпадает с символом на той же позиции в secret (ch == secret[idx]): Увеличьте количество быков: bulls += 1. Обновите количество коров, если количество текущего символа в хеш-таблице отрицательное или равно нулю (то есть этот символ уже использовался для коров): cows -= int(h[ch] <= 0). Если текущий символ ch не совпадает с символом на той же позиции в secret (ch != secret[idx]): Увеличьте количество коров, если количество текущего символа в хеш-таблице больше нуля: cows += int(h[ch] > 0). Обновите хеш-таблицу, помечая текущий символ как использованный: h[ch] -= 1. 3⃣Возврат результата: Верните количество быков и коров в формате "xAyB". 😎 Решение:

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

class Solution {
    public String getHint(String secret, String guess) {
        Map<Character, Integer> h = new HashMap<>();
        for (char ch : secret.toCharArray()) {
            h.put(ch, h.getOrDefault(ch, 0) + 1);
        }

        int bulls = 0;
        int cows = 0;
        int n = guess.length();
        char[] secretArray = secret.toCharArray();
        char[] guessArray = guess.toCharArray();

        for (int idx = 0; idx < n; idx++) {
            char ch = guessArray[idx];
            if (h.containsKey(ch)) {
                if (ch == secretArray[idx]) {
                    bulls++;
                    if (h.get(ch) <= 0) {
                        cows--;
                    }
                } else {
                    if (h.get(ch) > 0) {
                        cows++;
                    }
                }
                h.put(ch, h.get(ch) - 1);
            }
        }

        return bulls + "A" + cows + "B";
    }
}

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

⚡️ IT-обучение теперь в Telegram! В cвязи с недавнем замедлением Ютуба — лучшие обучающие каналы переехали в Telegram Вот каналы для айтишников: 👩‍💻 Java: @Java 👩‍💻 Моб. разработка: @MobDev 📱 GitHub: @GitHub ⚙️ Backend: @Backend 🤓 Общее айти: @portalToIT 👩‍💻 Python: @Python 👩‍💻 Frontend: @Frontend 👩‍💻 C#: @Csharp 👩‍💻 С/С++: @Cpp 🖥 Базы Данных & SQL: @SQL 👩‍💻 Golang: @Golang 👩‍💻 PHP: @PHP 👩‍💻 Разработка игр: @GameDev 👩‍💻 DevOps: @DevOps 🖥 Data Science: @DataScience 🤔 Хакинг & ИБ: @InfoSec 🐞 Тестирование: @QA 📱 Маркетинг: @Marketing 🖥 Дизайн: @Design ➡️ Сохраняйте себе, чтобы не потерять

#medium Задача: 281. Zigzag Iterator Даны два вектора целых чисел v1 и v2, реализуйте итератор, который возвращает их элементы поочередно. Реализуйте класс ZigzagIterator: ZigzagIterator(List<int> v1, List<int> v2) инициализирует объект с двумя векторами v1 и v2. boolean hasNext() возвращает true, если в итераторе еще есть элементы, и false в противном случае. int next() возвращает текущий элемент итератора и перемещает итератор к следующему элементу. Пример:

Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].

👨‍💻 Алгоритм: 1⃣Инициализация объекта: Создайте класс ZigzagIterator с двумя списками v1 и v2. Сохраните эти списки в структуре vectors. Инициализируйте очередь queue, содержащую пары индексов: индекс списка и индекс элемента в этом списке, если список не пуст. 2⃣Метод next: Удалите первую пару индексов из очереди. Извлеките элемент из соответствующего списка по указанным индексам. Если в текущем списке есть еще элементы, добавьте новую пару индексов (тот же список, следующий элемент) в конец очереди. Верните извлеченный элемент. 3⃣Метод hasNext: Проверьте, пуста ли очередь. Верните true, если в очереди есть элементы, и false в противном случае. 😎 Решение:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import javafx.util.Pair;

public class ZigzagIterator {
    private List<List<Integer>> vectors = new ArrayList<>();
    private LinkedList<Pair<Integer, Integer>> queue = new LinkedList<>();

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        this.vectors.add(v1);
        this.vectors.add(v2);
        int index = 0;
        for (List<Integer> vec : this.vectors) {
            if (vec.size() > 0)
                this.queue.add(new Pair<>(index, 0));
            index++;
        }
    }

    public int next() {
        Pair<Integer, Integer> pointer = this.queue.removeFirst();
        Integer vecIndex = pointer.getKey();
        Integer elemIndex = pointer.getValue();
        Integer nextElemIndex = elemIndex + 1;
        if (nextElemIndex < this.vectors.get(vecIndex).size())
            this.queue.addLast(new Pair<>(vecIndex, nextElemIndex));

        return this.vectors.get(vecIndex).get(elemIndex);
    }

    public boolean hasNext() {
        return !this.queue.isEmpty();
    }
}

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

#medium Задача: 300. Longest Increasing Subsequence Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности. Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

👨‍💻 Алгоритм: 1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i. 2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1). 3⃣Верните максимальное значение из dp. 😎 Решение:

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;

        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }

        return maxLength;
    }

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

Senior-разработчик создал крутейший канал про SQL Благодаря простым картинкам даже новичок научится разрабатывать приложения с использованием баз данных. Присоединяйтесь: @SQL

#medium Задача: 395. Longest Substring with At Least K Repeating Characters Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k. Если такой подстроки не существует, верните 0. Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

👨‍💻 Алгоритм: 1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке. 2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой. 3⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки. 😎 Решение:

class Solution {
    public int longestSubstring(String s, int k) {
        if (s.length() == 0 || k > s.length()) {
            return 0;
        }
        int[] countMap = new int[26];
        int n = s.length();
        int result = 0;
        
        for (int start = 0; start < n; start++) {
            Arrays.fill(countMap, 0);
            for (int end = start; end < n; end++) {
                countMap[s.charAt(end) - 'a']++;
                if (isValid(countMap, k)) {
                    result = Math.max(result, end - start + 1);
                }
            }
        }
        return result;
    }

    private boolean isValid(int[] countMap, int k) {
        int countLetters = 0, countAtLeastK = 0;
        for (int count : countMap) {
            if (count > 0) countLetters++;
            if (count >= k) countAtLeastK++;
        }
        return countLetters == countAtLeastK;
    }
}

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

🔥 Ресурсы для подготовки к работе в IT! 🔥 1️⃣ База собеседований IT – это уникальная коллекция собеседований от реальных топовых компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и многие другие! 🏢 Мы собрали 150+ собеседований, чтобы ты мог подготовиться к интервью с уверенностью и успехом. 2️⃣ База тестовых заданий – твоё секретное оружие для успешного прохождения этапов отбора! 📋 Здесь ты найдёшь 121+ тестовых заданий от тех же топовых компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries. Решай реальные задачи и набирайся опыта для будущих собеседований! 🎯 Присоединяйся к базам и прокачай свои шансы на успешное трудоустройство!

#hard Задача: 301. Remove Invalid Parentheses Дана строка s, содержащая скобки и буквы. Удалите минимальное количество неверных скобок, чтобы сделать строку допустимой. Верните список уникальных строк, которые являются допустимыми с минимальным количеством удалений. Вы можете вернуть ответ в любом порядке. Пример:

Input: s = "()())()"
Output: ["(())()","()()()"]

👨‍💻 Алгоритм: 1⃣Инициализация: Инициализируйте массив, который будет хранить все допустимые выражения. Начните рекурсию с самой левой скобки в последовательности и двигайтесь вправо. Определите состояние рекурсии переменной index, представляющей текущий обрабатываемый индекс в исходном выражении. Также используйте переменные left_count и right_count для отслеживания количества добавленных левых и правых скобок соответственно. 2⃣Обработка текущего символа: Если текущий символ (S[i]) не является скобкой, добавьте его к окончательному решению для текущей рекурсии. Если текущий символ является скобкой (S[i] == '(' или S[i] == ')'), у вас есть два варианта: либо отбросить этот символ как недопустимый, либо рассмотреть эту скобку как часть окончательного выражения. 3⃣Завершение рекурсии и проверка: Когда все скобки в исходном выражении обработаны, проверьте, является ли текущее выражение допустимым, проверяя значения left_count и right_count (должны быть равны). Если выражение допустимо, проверьте количество удалений (rem_count) и сравните его с минимальным количеством удалений, необходимых для получения допустимого выражения до сих пор. Если текущее значение rem_count меньше, обновите глобальный минимум и добавьте новое выражение в массив допустимых выражений. 😎 Решение:

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

class Solution {
    private Set<String> validExpressions = new HashSet<>();
    private int minimumRemoved = Integer.MAX_VALUE;

    private void reset() {
        validExpressions.clear();
        minimumRemoved = Integer.MAX_VALUE;
    }

    private void recurse(String s, int index, int leftCount, int rightCount, StringBuilder expression, int removedCount) {
        if (index == s.length()) {
            if (leftCount == rightCount) {
                if (removedCount <= minimumRemoved) {
                    String possibleAnswer = expression.toString();
                    if (removedCount < minimumRemoved) {
                        validExpressions.clear();
                        minimumRemoved = removedCount;
                    }
                    validExpressions.add(possibleAnswer);
                }
            }
            return;
        }

        char currentCharacter = s.charAt(index);
        int length = expression.length();

        if (currentCharacter != '(' && currentCharacter != ')') {
            expression.append(currentCharacter);
            recurse(s, index + 1, leftCount, rightCount, expression, removedCount);
            expression.deleteCharAt(length);
        } else {
            recurse(s, index + 1, leftCount, rightCount, expression, removedCount + 1);
            expression.append(currentCharacter);

            if (currentCharacter == '(') {
                recurse(s, index + 1, leftCount + 1, rightCount, expression, removedCount);
            } else if (rightCount < leftCount) {
                recurse(s, index + 1, leftCount, rightCount + 1, expression, removedCount);
            }

            expression.deleteCharAt(length);
        }
    }

    public List<String> removeInvalidParentheses(String s) {
        reset();
        recurse(s, 0, 0, 0, new StringBuilder(), 0);
        return new ArrayList<>(validExpressions);
    }

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

CodHub теперь в Telegram! Бесплатные обучающие материалы, которые лучше платных — книги, ресурсы, статьи и курсы топовых вузов страны тут: 👩‍💻 Материалы по Python 👩‍💻 Материалы по Frontend 👩‍💻 Материалы по Java 👩‍💻 Материалы по С# 👩‍💻 Материалы по C/C++ 👩‍💻 Материалы по Хакингу 🖥 Материалы по SQL 👩‍💻 Материалы по Kotlin/Swift 👩‍💻 Материалы по Linux 🐞 Материалы по QA 👩‍💻 Материалы по Go 👩‍💻 Материалы по PHP Подписываетесь: @CodHub_tg

#medium Задача: 280. Wiggle Sort Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3].... Вы можете считать, что входной массив всегда имеет допустимый ответ. Пример:

Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.

👨‍💻 Алгоритм: 1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена. 2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1]. 😎 Решение:

class Solution {
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void wiggleSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (((i % 2 == 0) && nums[i] > nums[i + 1])
                    || ((i % 2 == 1) && nums[i] < nums[i + 1])) {
                swap(nums, i, i + 1);
            }
        }
    }
}

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

#medium Задача: 394. Decode String Дана закодированная строка, вернуть её декодированную версию. Правило кодирования следующее: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом. Можно предположить, что входная строка всегда допустима; нет лишних пробелов, квадратные скобки корректно сформированы и т.д. Более того, можно предположить, что исходные данные не содержат никаких цифр, и что цифры используются только для обозначения количества повторений, k. Например, не будет таких входных данных, как 3a или 2[4]. Тестовые случаи сгенерированы так, что длина выходной строки никогда не превысит 105. Пример:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

👨‍💻 Алгоритм: 1⃣Проходите по строке s и обрабатывайте каждый символ. Если текущий символ не является закрывающей скобкой ], поместите его в стек. 2⃣Если текущий символ является закрывающей скобкой ], начните декодировать последнюю пройденную строку. Извлекайте из стека символы, пока следующий символ не станет открывающей скобкой [, и добавляйте каждый символ (a-z) к decodedString. Затем извлеките открывающую скобку [ из стека и извлекайте символы, пока следующий символ является цифрой (0-9), чтобы собрать число k. 3⃣Декодируйте шаблон k[decodedString], помещая decodedString в стек k раз. После того как вся строка будет пройдена, извлеките результат из стека и верните его. 😎 Решение:

class Solution {
    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char ch : s.toCharArray()) {
            if (ch == ']') {
                StringBuilder decodedString = new StringBuilder();
                while (stack.peek() != '[') {
                    decodedString.insert(0, stack.pop());
                }
                stack.pop();
                
                int k = 0;
                int base = 1;
                while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    k = k + (stack.pop() - '0') * base;
                    base *= 10;
                }
                
                for (int i = 0; i < k; i++) {
                    for (char c : decodedString.toString().toCharArray()) {
                        stack.push(c);
                    }
                }
            } else {
                stack.push(ch);
            }
        }
        
        StringBuilder result = new StringBuilder();
        for (char ch : stack) {
            result.append(ch);
        }
        
        return result.toString();
    }
}

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

👩‍💻 Программирование уже в Telegram! Вот 10 обучающих каналов по самым востребованным направлениям в IT. Выбирай своё направление: 👩‍💻 Python: @python_ready 👩‍💻 Java: @java_ready 👩‍💻 C/C++: @cpp_ready 👩‍💻 C#: @csharp_ready 👩‍💻 Backend: @backend_ready 👩‍💻 Frontend: @code_ready 🖥 Базы Данных & SQL: @sql_ready 👩‍💻 Весь IT: @roadmap_ready 📖 IT Архив: @archive_ready 🖥 Design: @time_design 📌 Ресурсы, гайды, шпаргалки, книги и задачи для каждого языка программирования.

#medium Задача: 393. UTF-8 Validation Дан целочисленный массив data, представляющий данные, верните, является ли это допустимой UTF-8 кодировкой (т.е. переводится в последовательность допустимых UTF-8 закодированных символов). Символ в UTF-8 может быть от 1 до 4 байтов в длину, при этом соблюдаются следующие правила: Для 1-байтового символа первый бит — 0, за которым следует его Unicode код. Для n-байтового символа первые n битов — все единицы, (n + 1)-й бит — 0, за которыми следуют n - 1 байт с наиболее значимыми 2 битами, равными 10. Это работает следующим образом:

     Количество байтов  |        UTF-8 Октетная последовательность
                       |              (бинарная)
   --------------------+-----------------------------------------
            1          |   0xxxxxxx
            2          |   110xxxxx 10xxxxxx
            3          |   1110xxxx 10xxxxxx 10xxxxxx
            4          |   11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

x обозначает бит в бинарной форме байта, который может быть как 0, так и 1. Примечание: Вход представляет собой массив целых чисел. Используются только 8 младших значимых битов каждого целого числа. Это означает, что каждое целое число представляет только 1 байт данных. Пример:

Input: data = [197,130,1]
Output: true
Explanation: data represents the octet sequence: 11000101 10000010 00000001.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

👨‍💻 Алгоритм: 1⃣Начните обработку целых чисел в данном массиве одно за другим. Для каждого целого числа получите его двоичное представление в виде строки. Поскольку целые числа могут быть очень большими, следует учитывать только 8 младших значимых битов данных и отбросить остальные, как указано в условии задачи. После этого шага у вас должно быть 8-битное или 1-байтовое строковое представление целого числа. Назовем эту строку bin_rep. 2⃣Далее нужно рассмотреть два сценария. Первый — мы находимся в процессе обработки некоторого UTF-8 закодированного символа. В этом случае нужно просто проверить первые два бита строки и посмотреть, равны ли они "10", т.е. наиболее значимые два бита целого числа равны 1 и 0. bin_rep[:2] == "10". Второй сценарий — мы уже обработали несколько допустимых UTF-8 символов и должны начать обработку нового UTF-8 символа. В этом случае нужно посмотреть на префикс строкового представления и посчитать количество единиц, которые мы встречаем до первой нули. Это скажет нам, каков размер следующего UTF-8 символа. 3⃣Продолжайте обрабатывать целые числа массива таким образом, пока не обработаете их все или не обнаружите недопустимый сценарий. Теперь давайте перейдем к реализации этого алгоритма. 😎 Решение:

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.validUtf8(new int[]{197, 130, 1})); // true
        System.out.println(solution.validUtf8(new int[]{235, 140, 4})); // false
    }
}

class Solution {
    public boolean validUtf8(int[] data) {
        int nBytes =

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

#easy Задача: 392. Is Subsequence Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false. Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является). Пример:

Input: s = "abc", t = "ahbgdc"
Output: true

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

class Solution {
    public boolean isSubsequence(String s, String t) {
        int leftBound = s.length(), rightBound = t.length();
        int pLeft = 0, pRight = 0;

        while (pLeft < leftBound && pRight < rightBound) {
            if (s.charAt(pLeft) == t.charAt(pRight)) {
                pLeft += 1;
            }
            pRight += 1;
        }
        return pLeft == leftBound;
    }
}

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

❗️Страх обосраться это нормально❗️

Я уже устал.. долго учу Java, но так и не начал ходить по собесам

Узнаешь себя? Наш знакомый эксперт в Java - Павел Сорокин, разобрал самые частые вопросы с которыми к нему обращаются люди на консультациях👇 1️⃣ Постоянно кажется, что я не готов. Процесс обучения длится уже больше 1.5 года, начинаю забывать основы, которые учил в начале. При обучении одна из самых больших ошибок - это распыление фокуса. Определяешь просто частые технологии и вопросы, которые задают на собесах и идешь строго по ним, не распыляясь писал об этом тут. Первые собесы - тренировочные. Можете от них вообще не ожидать никаких результатов, не надеятся - это ТРЕНИРОВКА. Страх будет всегда, его просто нужно принять и идти дальше. Страх возникает из-за неизвестности, неодобрения со стороны других. Даже если вы провалите собес, что самое плохое случится? Вас не убьют, ничего с вами не сделают, вы и также будете сидеть в своем уютном доме. Любой страх уничтожается действием. 2️⃣ Не понимаю насколько глубоко нужно изучать технологию Каждую технологию необходимо понимать ровно настолько, насколько она необходима тебе. Если работаешь с БД и нет каких-то больших нагрузок, то нет смысла углубляться устройство БД. Не нужно знать как Spring устроен под капотом для того, чтобы найти работу. Рациональный подход - просто учить минимальный достаточный набор и улучшать его по пути. 3️⃣ Конкуренция большая, на собеседования невозможно пробиться Конкуренции на самом деле не существует. Если ты обходишь своих конкурентов по резюме/софт-скиллам/хард-скиллам, то для тебя нет конкуренции, когда ты лучше всех. Единственное, что остается - обойти всех. О двух действенных способах пройти на собес рассказал в полной версии поста ‼️ В своем канале Паша дает много информации по вкату и развитию в Java, можно начать ознакомление с его каналом с этого поста с разбором базовых вопросов на собеседованиях. Также у Паши есть отличные бесплатные видео-материалы - полный гайд по Java Core и Многопоточке и реальное успешное собеседование на Junior Java. Можете забрать их в его боте.

Тестовое собеседование на Middle Java-разработчика в среду Заходи 9 октября, в среду в 19:00 по мск на открытое онлайн-собеседование от ШОРТКАТ, чтобы узнать: ● Чего ждут от кандидатов на Middle позиции в Java-разработке ● Какие вопросы задают на интервью и зачем ● Как подготовиться к собесу, чтобы получить оффер Интервью проведёт Роман Половинцев, ex. TeamLead в Сбере. Чтобы записаться на эфир, переходи в бот → @shortcut_sh_bot Реклама. ООО "ШОРТКАТ", ИНН: 9731139396, erid: 2VtzqvcFxoL

#easy Задача: 389. Find the Difference Даны две строки s и t. Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию. Верните букву, которая была добавлена в t. Пример:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

👨‍💻 Алгоритм: 1⃣Отсортируйте строки s и t. 2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s. 3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время. 😎 Решение:

class Solution {
    public char findTheDifference(String s, String t) {
        char[] sortedS = s.toCharArray();
        char[] sortedT = t.toCharArray();
        Arrays.sort(sortedS);
        Arrays.sort(sortedT);

        int i = 0;
        while (i < s.length()) {
            if (sortedS[i] != sortedT[i]) {
                return sortedT[i];
            }
            i += 1;
        }

        return sortedT[i];
    }
}

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