Java | LeetCode

Задача: 1382. Balance a Binary Search Tree Сложность: medium Дан корень бинарного дерева поиска. Верните сбалансированное бинарное дерево поиска с теми же значениями узлов. Если существует более одного ответа, верните любой из них. Бинарное дерево поиска считается сбалансированным, если глубина двух поддеревьев каждого узла никогда не отличается более чем на 1. Пример:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

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

class Solution {
    public TreeNode balanceBST(TreeNode root) {
        if (root == null) return null;

        TreeNode vineHead = new TreeNode(0);
        vineHead.right = root;
        TreeNode current = vineHead;

        while (current.right != null) {
            if (current.right.left != null) {
                rightRotate(current, current.right);
            } else {
                current = current.right;
            }
        }

        int nodeCount = 0;
        current = vineHead.right;
        while (current != null) {
            nodeCount++;
            current = current.right;
        }

        int m = (int) Math.pow(2, Math.floor(Math.log(nodeCount + 1) / Math.log(2))) - 1;
        makeRotations(vineHead, nodeCount - m);
        while (m > 1) {
            m /= 2;
            makeRotations(vineHead, m);
        }

        TreeNode balancedRoot = vineHead.right;
        return balancedRoot;
    }

    private void rightRotate(TreeNode parent, TreeNode node) {
        TreeNode tmp = node.left;
        node.left = tmp.right;
        tmp.right = node;
        parent.right = tmp;
    }

    private void leftRotate(TreeNode parent, TreeNode node) {
        TreeNode tmp = node.right;
        node.right = tmp.left;
        tmp.left = node;
        parent.right = tmp;
    }

    private void makeRotations(TreeNode vineHead, int count) {
        TreeNode current = vineHead;
        for (int i = 0; i < count; i++) {
            TreeNode tmp = current.right;
            leftRotate(current, tmp);
            current = current.right;
        }
    }
}

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

Выигрывай мечты с Черноголовкой Купи колу и лимонад Черноголовка, загрузи чек на сайт и выиграй мечту: 1 000 000 ₽. Узнать больше #реклама chernogolovka-promo.ru О рекламодателе

Задача: 1122. Relative Sort Array Сложность: easy Даны два массива arr1 и arr2, элементы arr2 уникальны, и все элементы arr2 также присутствуют в arr1. Отсортируйте элементы arr1 таким образом, чтобы относительный порядок элементов в arr1 был таким же, как в arr2. Элементы, которые не встречаются в arr2, должны быть размещены в конце arr1 в порядке возрастания. Пример:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

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

class Solution {

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> countMap = new HashMap<>();
        List<Integer> remaining = new ArrayList<>();
        List<Integer> result = new ArrayList<>();

        for (int value : arr2) {
            countMap.put(value, 0);
        }

        for (int value : arr1) {
            if (countMap.containsKey(value)) {
                countMap.put(value, countMap.get(value) + 1);
            } else {
                remaining.add(value);
            }
        }

        Collections.sort(remaining);

        for (int value : arr2) {
            for (int j = 0; j < countMap.get(value); j++) {
                result.add(value);
            }
        }

        result.addAll(remaining);

        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

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

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

Задача: 1203. Sort Items by Groups Respecting Dependencies Сложность: hard Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета. Верните отсортированный список предметов таким образом: Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке. Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета). Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует. Пример:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

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

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        int groupId = m;
        for (int i = 0; i < n; i++) if (group[i] == -1) group[i] = groupId++;

        Map<Integer, List<Integer>> itemGraph = new HashMap<>();
        Map<Integer, List<Integer>> groupGraph = new HashMap<>();
        int[] itemIndegree = new int[n], groupIndegree = new int[groupId];
        for (int i = 0; i < n; i++) itemGraph.put(i, new ArrayList<>());
        for (int i = 0; i < groupId; i++) groupGraph.put(i, new ArrayList<>());

        for (int curr = 0; curr < n; curr++) {
            for (int prev : beforeItems.get(curr)) {
                itemGraph.get(prev).add(curr);
                itemIndegree[curr]++;
                if (group[curr] != group[prev]) {
                    groupGraph.get(group[prev]).add(group[curr]);
                    groupIndegree[group[curr]]++;
                }
            }
        }

        List<Integer> itemOrder = topologicalSort(itemGraph, itemIndegree);
        List<Integer> groupOrder = topologicalSort(groupGraph, groupIndegree);
        if (itemOrder.isEmpty() || groupOrder.isEmpty()) return new int[0];

        Map<Integer, List<Integer>> orderedGroups = new HashMap<>();
        for (int item : itemOrder) orderedGroups.computeIfAbsent(group[item], k -> new ArrayList<>()).add(item);

        List<Integer> answerList = new ArrayList<>();
        for (int groupIndex : groupOrder) answerList.addAll(orderedGroups.getOrDefault(groupIndex, new ArrayList<>()));

        return answerList.stream().mapToInt(Integer::intValue).toArray();
    }

    private List<Integer> topologicalSort(Map<Integer, List<Integer>> graph, int[] indegree) {
        List<Integer> visited = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        for (int key : graph.keySet()) if (indegree[key] == 0) stack.add(key);

        while (!stack.isEmpty()) {
            int curr = stack.pop();
            visited.add(curr);
            for (int next : graph.get(curr)) if (--indegree[next] == 0) stack.add(next);
        }

        return visited.size() == graph.size() ? visited : new ArrayList<>();
    }
}

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

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

Задача: 665. Non-decreasing Array Сложность: medium Дан массив nums из n целых чисел. Ваша задача - проверить, можно ли сделать его неубывающим, изменив не более одного элемента. Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется условие nums[i] <= nums[i + 1]. Пример:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Завести переменную count для подсчета числа изменений. Проверить последовательность чисел в массиве nums. 2⃣Проверка условий: Если nums[i] > nums[i + 1], то увеличиваем count. Если count превышает 1, возвращаем false, так как больше одного изменения недопустимо. Если nums[i - 1] > nums[i + 1] и nums[i] > nums[i + 2], то возвращаем false. 3⃣Возврат результата: Если количество изменений не превышает 1, вернуть true. 😎 Решение:

public class Solution {
    public boolean checkPossibility(int[] nums) {
        int count = 0;
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                if (count > 0) {
                    return false;
                }
                count++;
                if (i == 1 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }
        
        return true;
    }
}

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

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

Задача: №21. Merge Two Sorted Lists Сложность: easy Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините их в один отсортированный список, сшивая существующие узлы. Верните заголовок нового объединенного списка. Пример:

Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }
        return list1 != null ? list1 : list2;
    }
}

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

Кинопоиск до 360 дней бесплатно Кинопоиск — тысячи фильмов и сериалов без рекламы, в высоком качестве. Яндекс Музыка и Книги тоже в мультиподписке Плюс. Попробуйте бесплатно ❤️ Попробовать #реклама 18+ kinopoisk.ru О рекламодателе

Задача: 210. Course Schedule II Сложность: medium Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai. Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1. Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив. Пример:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0.
Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].

👨‍💻 Алгоритм: 1⃣Инициализация и построение графа: Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе. Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма. 2⃣Запуск поиска в глубину (DFS): Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла. Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны. 3⃣Обработка узлов и возвращение результата: После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке. После обработки всех узлов просто верните узлы в порядке их присутствия в стеке от вершины до основания. 😎 Решение:

class Solution {
    static int WHITE = 1;
    static int GRAY = 2;
    static int BLACK = 3;

    boolean isPossible;
    Map<Integer, Integer> color;
    Map<Integer, List<Integer>> adjList;
    List<Integer> topologicalOrder;

    private void init(int numCourses) {
        this.isPossible = true;
        this.color = new HashMap<>();
        this.adjList = new HashMap<>();
        this.topologicalOrder = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            this.color.put(i, WHITE);
        }
    }

    private void dfs(int node) {
        if (!this.isPossible) return;
        this.color.put(node, GRAY);
        for (Integer neighbor : this.adjList.getOrDefault(node, new ArrayList<>())) {
            if (this.color.get(neighbor) == WHITE) {
                this.dfs(neighbor);
            } else if (this.color.get(neighbor) == GRAY) {
                this.isPossible = false;
            }
        }
        this.color.put(node, BLACK);
        this.topologicalOrder.add(node);
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        this.init(numCourses);
        for (int i = 0; i < prerequisites.length; i++) {
            int dest = prerequisites[i][0];
            int src = prerequisites[i][1];
            List<Integer> lst = adjList.getOrDefault(src, new ArrayList<>());
            lst.add(dest);
            adjList.put(src, lst);
        }
        for (int i = 0; i < numCourses; i++) {
            if (this.color.get(i) == WHITE) {
                this.dfs(i);
            }
        }
        if (this.isPossible) {
            int[] order = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                order[i] = this.topologicalOrder.get(numCourses - i - 1);
            }
            return order;
        } else {
            return new int[0];
        }
    }
}

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

Аренда и размещение серверов в дата-центрах Москвы ITSOFT оказывает услуги коммерческого дата-центра в Москве. 👌Аренда физических выделенных серверов (Dedicated Servers) в готовых конфигурациях и в рамках индивидуальных сборок. 👌Colocation и аренда серверных стоек. 👌Предоставление инфраструктурных ИТ-решений для физических лиц и корпоративных клиентов. 👌Предоставление высокоскоростных каналов передачи данных. Узнать цену #реклама 16+ itsoft.ru О рекламодателе

Задача: 926. Flip String to Monotone Increasing Сложность: medium Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0. Пример:

Input: s = "00110"
Output: 1

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

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int[] left = new int[n + 1];
        int[] right = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            left[i + 1] = left[i] + (s.charAt(i) == '1' ? 1 : 0);
        }
        
        for (int i = n - 1; i >= 0; i--) {
            right[i] = right[i + 1] + (s.charAt(i) == '0' ? 1 : 0);
        }
        
        int result = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            result = Math.min(result, left[i] + right[i]);
        }
        return result;
    }
}

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

Гастробар «Виновные» в Москве Гастробар «Виновные» на Китай-городе. Летняя веранда, авторская кухня Узнать больше #реклама vinovniye.ru О рекламодателе

Задача: 786. K-th Smallest Prime Fraction Сложность: medium Вам дан отсортированный массив целых чисел arr, содержащий 1 и простые числа, где все элементы массива arr уникальны. Также дано целое число k. Для каждого i и j, где 0 <= i < j < arr.length, мы рассматриваем дробь arr[i] / arr[j]. Верните k-ую наименьшую дробь из рассмотренных. Верните ответ в виде массива из двух целых чисел размера 2, где answer[0] == arr[i] и answer[1] == arr[j]. Пример:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

👨‍💻 Алгоритм: 1⃣Инициализируйте пустую приоритетную очередь pq для хранения пар дробей и соответствующих им индексов. Итеративно пройдите по входному массиву arr, используя переменную цикла i. Для каждого элемента arr[i] вычислите дробь, образованную делением его на наибольший элемент в массиве (arr[arr.size() - 1]). Поместите пару, состоящую из отрицательного значения дроби (-1.0 * arr[i] / arr[arr.size() - 1]) и соответствующих индексов (i для числителя и arr.size() - 1 для знаменателя), в приоритетную очередь pq. Приоритетная очередь pq теперь содержит все дроби, образованные делением каждого элемента на наибольший элемент в массиве, отсортированные в порядке возрастания значений дробей. 2⃣Повторите следующие шаги k - 1 раз: удалите верхний элемент (наименьшую дробь) из приоритетной очереди pq и сохраните его индексы в переменной cur. Уменьшите индекс знаменателя (cur[1]--). Вычислите новую дробь, образованную делением числителя в cur[0] на уменьшенный знаменатель (arr[cur[1]]). Поместите новое значение дроби (-1.0 * arr[cur[0]] / arr[cur[1]]) и соответствующие индексы (cur[0] для числителя и cur[1] для знаменателя) в приоритетную очередь pq. После k - 1 итераций верхний элемент приоритетной очереди pq будет k-й наименьшей дробью. 3⃣Извлеките индексы числителя и знаменателя из верхнего элемента приоритетной очереди и сохраните их в result. Верните массив, содержащий значения числителя (arr[result[0]]) и знаменателя (arr[result[1]]), соответствующие k-й наименьшей дроби. 😎 Решение:

import java.util.PriorityQueue;

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Double.compare((double)arr[a[0]] / arr[a[1]], (double)arr[b[0]] / arr[b[1]]));
        
        for (int i = 0; i < arr.length - 1; i++) {
            pq.offer(new int[]{i, arr.length - 1});
        }
        
        for (int i = 0; i < k - 1; i++) {
            int[] cur = pq.poll();
            if (cur[1] - 1 > cur[0]) {
                pq.offer(new int[]{cur[0], cur[1] - 1});
            }
        }
        
        int[] result = pq.poll();
        return new int[]{arr[result[0]], arr[result[1]]};
    }
}

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

Регистрируйся на ИТ-Пикник от Т-Банка 8 августа 8 августа — время отложить ноутбуки и встретиться офлайн на ИТ-Пикнике от Т-Банка в музее-заповеднике «Коломенское». Вот сколько всего запланировано: — научпоп-лекции; — мастер-классы; — дискуссии об ИИ и больших языковых моделях; — доклады о кибербезопасности; — примеры, как данные из логов становятся решениями; — много музыки. Бери с собой друзей, супругов и детей — каждый найдет себе что-то по душе. Узнать больше #реклама 16+ it-picnic.ru О рекламодателе

🔴 Завтра тестовое собеседование с Java-разработчиком 5 августа(уже завтра!) в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Java-разработчика. Как это будет: 📂 Сергей Чамкин, старший разработчик из Uzum, ex-WildBerries, будет задавать реальные вопросы и задачи разработчику-добровольцу 📂 Cергей будет комментировать каждый ответ респондента, чтобы дать понять чего от вас ожидает собеседующий на интервью 📂 В конце можно будет задать любой вопрос Сергею Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для Java-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы. Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_sh_bot Реклама. О рекламодателе.

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

Задача: 439. Ternary Expression Parser Сложность: medium Дана строка expression, представляющая произвольно вложенные тернарные выражения, вычислите это выражение и верните его результат. Можно всегда считать, что данное выражение является корректным и содержит только цифры, '?', ':', 'T' и 'F', где 'T' означает истину, а 'F' - ложь. Все числа в выражении являются однозначными числами (т.е. в диапазоне от 0 до 9). Условные выражения группируются справа налево (как обычно в большинстве языков), и результат выражения всегда будет либо цифрой, либо 'T', либо 'F'. Пример:

Input: expression = "T?2:3"
Output: "2"
Explanation: If true, then result is 2; otherwise result is 3.

👨‍💻 Алгоритм: 1⃣Определите вспомогательную функцию isValidAtomic(s), которая принимает строку s и возвращает True, если s является допустимым атомарным выражением. В противном случае функция возвращает False. Функция будет вызываться только с пятисимвольными строками. Если все следующие условия выполнены, функция возвращает True, иначе - False: s[0] является T или F. s[1] является ?. s[2] является T, F или цифрой от 0 до 9. s[3] является :. s[4] является T, F или цифрой от 0 до 9. 2⃣Определите вспомогательную функцию solveAtomic(s), которая принимает строку s и возвращает значение атомарного выражения. Значение атомарного выражения равно E1, если B - это T, иначе значение равно E2. Функция будет вызываться только с пятисимвольными строками и возвращать один символ:. 3⃣Если s[0] является T, функция возвращает s[2], иначе возвращает s[4]. В функции parseTernary(expression) уменьшайте выражение до тех пор, пока не останется односимвольная строка. Инициализируйте j как expression.size() - 1 (это будет самый правый индекс окна). Пока самое правое окно длиной 5 не является допустимым атомарным выражением, уменьшайте j на 1. Когда будет найдено самое правое допустимое атомарное выражение, решите его и уменьшите до одного символа. Замените самое правое допустимое атомарное выражение одним символом, после чего длина выражения уменьшится на 4. В итоге останется односимвольная строка, которую и верните. 😎 Решение:

class Solution {
    public String parseTernary(String expression) {
        boolean isValidAtomic(String s) {
            return s.charAt(0) == 'T' || s.charAt(0) == 'F' &&
                   s.charAt(1) == '?' &&
                   "TF0123456789".indexOf(s.charAt(2)) != -1 &&
                   s.charAt(3) == ':' &&
                   "TF0123456789".indexOf(s.charAt(4)) != -1;
        }

        char solveAtomic(String s) {
            return s.charAt(0) == 'T' ? s.charAt(2) : s.charAt(4);
        }

        while (expression.length() != 1) {
            int j = expression.length() - 1;
            while (!isValidAtomic(expression.substring(j-4, j+1))) {
                j -= 1;
            }
            expression = expression.substring(0, j-4) + solveAtomic(expression.substring(j-4, j+1)) + expression.substring(j+1);
        }

        return expression;
    }
}

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

Yandex Ecom Open Air — летнее событие про онлайн-продажи Yandex Ecom Open Air 2026 объединяет деловую программу, живое общение и атмосферу фестиваля в одном потоке. Здесь обсуждают технологии, которые становятся частью среды. Исследуют силы, которые влияют на весь рынок. Находят новые связи, идеи и точки роста. В течение дня пространство фестиваля наполняют выступления, дискуссии, встречи, специальные форматы, музыка и активности партнёров. Присоединиться к происходящему можно из любой точки — на площадке фестиваля или через онлайн-трансляцию. Зарегистрироваться #реклама 18+ ecomfest.ru О рекламодателе