Java | LeetCode

Задача: 1361. Validate Binary Tree Nodes Сложность: easy У вас есть n узлов бинарного дерева, пронумерованных от 0 до n-1, где узел i имеет двух детей: leftChild[i] и rightChild[i]. Верните true, если и только если все заданные узлы образуют ровно одно допустимое бинарное дерево. Если у узла i нет левого ребенка, то leftChild[i] будет равен -1, аналогично для правого ребенка. Обратите внимание, что узлы не имеют значений и мы используем только номера узлов в этой задаче. Пример:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

👨‍💻 Алгоритм: 1⃣Проверка количества родителей для каждого узла: Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false. 2⃣Поиск корневого узла и проверка на единственное дерево: Найдите корневой узел (узел с нулевым количеством родителей). Если корневых узлов нет или больше одного, верните false. Используйте BFS или DFS, чтобы проверить, что все узлы достижимы от корня и что нет циклов. 3⃣Проверка на достижение всех узлов: Проверьте, что количество посещенных узлов равно n. Если нет, верните false. В противном случае, верните true. 😎 Решение:

import java.util.HashSet;
import java.util.Set;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] parents = new int[n];
        
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1) {
                parents[leftChild[i]]++;
                if (parents[leftChild[i]] > 1) {
                    return false;
                }
            }
            if (rightChild[i] != -1) {
                parents[rightChild[i]]++;
                if (parents[rightChild[i]] > 1) {
                    return false;
                }
            }
        }
        
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == 0) {
                if (root == -1) {
                    root = i;
                } else {
                    return false;
                }
            }
        }
        
        if (root == -1) {
            return false;
        }
        
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (!visited.add(node)) {
                return false;
            }
            if (leftChild[node] != -1) {
                queue.add(leftChild[node]);
            }
            if (rightChild[node] != -1) {
                queue.add(rightChild[node]);
            }
        }
        
        return visited.size() == n;
    }
}

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

Получайте больше продаж из поиска Яндекса Анализируйте метрики и получайте рекомендации для роста продаж в Яндекс Товарах ⚡ Попробовать #реклама merchants.yandex.ru О рекламодателе

Задача: 282. Expression Add Operators Сложность: hard Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target. Учтите, что операнды в возвращаемых выражениях не должны содержать ведущих нулей. Пример:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

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

class Solution {

  public ArrayList<String> answer;
  public String digits;
  public long target;

  public void recurse(
      int index, long previousOperand, long currentOperand, long value, ArrayList<String> ops) {
    String nums = this.digits;

    if (index == nums.length()) {
      if (value == this.target && currentOperand == 0) {
        StringBuilder sb = new StringBuilder();
        ops.subList(1, ops.size()).forEach(v -> sb.append(v));
        this.answer.add(sb.toString());
      }
      return;
    }

    currentOperand = currentOperand * 10 + Character.getNumericValue(nums.charAt(index));
    String current_val_rep = Long.toString(currentOperand);
    int length = nums.length();

    if (currentOperand > 0) {
      recurse(index + 1, previousOperand, currentOperand, value, ops);
    }

    ops.add("+");
    ops.add(current_val_rep);
    recurse(index + 1, currentOperand, 0, value + currentOperand, ops);
    ops.remove(ops.size() - 1);
    ops.remove(ops.size() - 1);

    if (ops.size() > 0) {
      ops.add("-");
      ops.add(current_val_rep);
      recurse(index + 1, -currentOperand, 0, value - currentOperand, ops);
      ops.remove(ops.size() - 1);
      ops.remove(ops.size() - 1);

      ops.add("*");
      ops.add(current_val_rep);
      recurse(
          index + 1,
          currentOperand * previousOperand,
          0,
          value - previousOperand + (currentOperand * previousOperand),
          ops);
      ops.remove(ops.size() - 1);
      ops.remove(ops.size() - 1);
    }
  }

  public List<String> addOperators(String num, int target) {
    if (num.length() == 0) {
      return new ArrayList<String>();
    }

    this.target = target;
    this.digits = num;
    this.answer = new ArrayList<String>();
    this.recurse(0, 0, 0, 0, new ArrayList<String>());
    return this.answer;
  }
}

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

Новая мощь от Virtus.pro X-TURBO по суперцене. Успей прокачать реакцию, пока другие тормозят. Купить #реклама 18+ xturboenergy.ru О рекламодателе

Задача: 311. Sparse Matrix Multiplication Сложность: medium Даны две разреженные матрицы mat1 размером m x k и mat2 размером k x n. Верните результат перемножения матриц mat1 x mat2. Вы можете предположить, что умножение всегда возможно. Пример:

Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]

👨‍💻 Алгоритм: 1⃣Инициализация результирующей матрицы Создайте результирующую матрицу result размером m x n, заполненную нулями. 2⃣Хранение ненулевых элементов Пройдите по каждой строке матрицы mat1 и сохраните индексы и значения ненулевых элементов в хеш-карте mat1_map. Пройдите по каждой колонке матрицы mat2 и сохраните индексы и значения ненулевых элементов в хеш-карте mat2_map. 3⃣Вычисление произведения Для каждой строки i в mat1 и для каждой колонки j в mat2: Если в mat1_map есть ненулевой элемент в строке i и в mat2_map есть ненулевой элемент в колонке j с одинаковым индексом k, добавьте произведение этих элементов к result[i][j]. 😎 Решение:

public class Solution {
    public int[][] multiply(int[][] mat1, int[][] mat2) {
        int n = mat1.length;
        int k = mat1[0].length;
        int m = mat2[0].length;
        
        int[][] ans = new int[n][m];
        
        for (int rowIndex = 0; rowIndex < n; rowIndex++) {
            for (int elementIndex = 0; elementIndex < k; elementIndex++) {
                if (mat1[rowIndex][elementIndex] != 0) {
                    for (int colIndex = 0; colIndex < m; colIndex++) {
                        ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex];
                    }
                }
            }
        }
        
        return ans;
    }
}

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

Почему выбирают PostgreSQL как сервис от РТК-ЦОД? Сервис PostgreSQL от РТК-ЦОД позволяет быстро развернуть, эксплуатировать и масштабировать базу данных в облаке. Процесс установки и настройки полностью автоматизирован. Почему выбирают нас? — Личный кабинет — Надежное хранение данных: дата-центры уровня Tier III в России, сертифицированные Uptime Institute — Детальный SLA — Оптимальная конфигурация: выделенный кластер только под вас — Опция администрирования вашей базы данных — Квалифицированная техподдержка в режиме 24х7 ✅ 30 дней бесплатно: тестируйте наш сервис с полным доступом ко всем возможностям. Оставьте заявку на www.cloud.rt.ru Узнать больше #реклама 16+ cloud.rt.ru О рекламодателе

Задача: 362. Design Hit Counter Сложность: medium Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке. Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной. Пример:

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

👨‍💻 Алгоритм: 1⃣При вызове метода hit(int timestamp), добавьте временную метку в очередь. 2⃣ При вызове метода getHits(int timestamp), удалите все временные метки из очереди, которые старше 300 секунд от текущей временной метки. 3⃣Верните размер очереди как количество попаданий за последние 5 минут. 😎 Решение:

class HitCounter {
    private Queue<Integer> hits; 

    public HitCounter() {
        this.hits = new LinkedList<Integer>();
    }
    
    public void hit(int timestamp) {
        this.hits.add(timestamp);
    }
    
    public int getHits(int timestamp) {
        while (!this.hits.isEmpty()) {
            int diff = timestamp - this.hits.peek();
            if (diff >= 300) this.hits.remove();
            else break;
        }
        return this.hits.size();
    }
}

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

Теперь сайты будет создавать искусственный интеллект В Битрикс24 появился AI-помощник, который по текстовому запросу генерирует готовый сайт с дизайном и контентом. Вот это уровень, мое почтение. Узнать больше #реклама sites-24.bitrix24.ru О рекламодателе

Задача: 77. Combinations Сложность: medium Даны два целых числа n и k. Верните все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Ответ можно вернуть в любом порядке. Пример:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

👨‍💻 Алгоритм: 1⃣Инициализировать массив ответов ans и массив для построения комбинаций curr. 2⃣Создать функцию обратного вызова backtrack, которая принимает curr в качестве аргумента, а также целое число firstNum: Если длина curr равна k, добавить копию curr в ans и вернуться. Вычислить available, количество чисел, которые мы можем рассмотреть в текущем узле. Итерировать num от firstNum до firstNum + available включительно. Для каждого num, добавить его в curr, вызвать backtrack(curr, num + 1), а затем удалить num из curr. 3⃣Вызвать backtrack с изначально пустым curr и firstNum = 1. Вернуть ans. 😎 Решение:

class Solution {
    private int n;
    private int k;

    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(new ArrayList<>(), 1, ans);
        return ans;
    }

    public void backtrack(
        List<Integer> curr,
        int firstNum,
        List<List<Integer>> ans
    ) {
        if (curr.size() == k) {
            ans.add(new ArrayList<>(curr));
            return;
        }

        int need = k - curr.size();
        int remain = n - firstNum + 1;
        int available = remain - need;

        for (int num = firstNum; num <= firstNum + available; num++) {
            curr.add(num);
            backtrack(curr, num + 1, ans);
            curr.remove(curr.size() - 1);
        }
    }
}

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

Задача: 980. Unique Paths III Сложность: hard Вам дан целочисленный массив grid размером m x n, где grid[i][j] может быть: 1, представляющая начальную клетку. Существует ровно одна начальная клетка. 2, представляющая конечную клетку. Существует ровно одна конечная клетка. 0, представляющая пустые клетки, по которым можно ходить. -1, представляющая препятствия, по которым нельзя ходить. Верните количество 4-направленных путей от начальной клетки до конечной клетки, которые проходят по каждой непересекаемой клетке ровно один раз. Пример:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

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

class Solution {
    int rows, cols;
    int[][] grid;
    int path_count;

    protected void backtrack(int row, int col, int remain) {
        if (this.grid[row][col] == 2 && remain == 1) {
            this.path_count += 1;
            return;
        }

        int temp = grid[row][col];
        grid[row][col] = -4;
        remain -= 1;

        int[] row_offsets = {0, 0, 1, -1};
        int[] col_offsets = {1, -1, 0, 0};
        for (int i = 0; i < 4; ++i) {
            int next_row = row + row_offsets[i];
            int next_col = col + col_offsets[i];

            if (0 > next_row || next_row >= this.rows || 0 > next_col || next_col >= this.cols)
                continue;

            if (grid[next_row][next_col] < 0)
                continue;

            backtrack(next_row, next_col, remain);
        }

        grid[row][col] = temp;
    }

    public int uniquePathsIII(int[][] grid) {
        int non_obstacles = 0, start_row = 0, start_col = 0;

        this.rows = grid.length;
        this.cols = grid[0].length;

        for (int row = 0; row < rows; ++row)
            for (int col = 0; col < cols; ++col) {
                int cell = grid[row][col];
                if (cell >= 0)
                    non_obstacles += 1;
                if (cell == 1) {
                    start_row = row;
                    start_col = col;
                }
            }

        this.path_count = 0;
        this.grid = grid;

        backtrack(start_row, start_col, non_obstacles);

        return this.path_count;
    }
}

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

ИИ — просто, по делу и с душой Хотите разобраться в теме искусственного интеллекта, но не знаете, с чего начать? Или уже в теме, но хочется быть в курсе нового и понимать, что действительно важно? That's IT — не просто Telegram-канал, а живое коммьюнити, где каждый день проходят обсуждения, споры и обмен опытом. Здесь вы найдёте краткие и понятные разборы сложных тем, новости без шума и воды, и реальные кейсы использования ИИ. Автор канала — тимлид с 11-летним опытом, который сам внедряет ИИ в продукты и делится тем, что работает на практике. 💡 Особенно зайдёт тем, кто: • хочет развиваться, не тратя часы на чтение технических статей • ищет, как применить ИИ в жизни и на работе • любит, когда между новостями про нейросети мелькают милые котики 🐾 😇 Подписывайтесь: That's IT | Сергей Фролов

ORAC: стеновые 3D покрытия ⚡Европейские тренды лепного декора Где традиции встречаются с современностью, начинается магия создания идеального пространства. - стеновые 3D панели - молдинги - плинтусы - карнизы - профили скрытого освещения Материал Purotouch/Duropolymer ✨Откройте новые измерения дизайна интерьеров! Перейти на сайт #реклама oracdecor.ru О рекламодателе

Задача: 82. Remove Duplicates from Sorted List II Сложность: medium Дана голова отсортированного связного списка. Удалите все узлы, содержащие повторяющиеся числа, оставив только уникальные числа из исходного списка. Верните отсортированный связный список. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализация "стража" и предшественника: Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены. Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж. 2⃣Проход по списку с проверкой на дубликаты: Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val. Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов pred.next = head.next, тем самым пропуская весь блок дублированных узлов. 3⃣Переход к следующему узлу и возврат результата: Если текущий узел не имел дубликатов, просто переводим предшественника pred на следующий узел. Двигаем указатель head на следующий узел в списке. После завершения цикла возвращаем список, начиная с узла, на который указывает sentinel.next, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов. 😎 Решение:

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode sentinel = new ListNode(0, head);
        ListNode pred = sentinel;

        while (head != null) {
            if (head.next != null && head.val == head.next.val) {
                while (head.next != null && head.val == head.next.val) {
                    head = head.next;
                }
                pred.next = head.next;
            } else {
                pred = pred.next;
            }
            head = head.next;
        }
        return sentinel.next;
    }
}

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

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

Задача: 499. The Maze III Сложность: hard В лабиринте есть мячик с пустыми пространствами (0) и стенами (1). Мячик может катиться вверх, вниз, влево или вправо, пока не столкнется со стеной, затем выбрать новое направление. В лабиринте также есть отверстие, куда мячик упадет, если закатится в него. Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо). Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно). Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны. Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

👨‍💻 Алгоритм: 1⃣Инициализация и вспомогательные функции Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной. 2⃣Запуск алгоритма Дейкстры Инициализируйте очередь с начальной позицией мяча, где элементы с меньшим расстоянием имеют высокий приоритет, а при равных расстояниях выбирайте минимальную строку пути. Создайте структуру seen для отслеживания посещенных узлов. 3⃣Поиск кратчайшего пути Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible". 😎 Решение:

class State {
    int row, col, dist;
    String path;
    State(int r, int c, int d, String p) { row = r; col = c; dist = d; path = p; }
}

class Solution {
    int[][] directions = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    String[] textDirections = {"l", "u", "r", "d"};
    int m, n;

    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        m = maze.length; n = maze[0].length;
        PriorityQueue<State> heap = new PriorityQueue<>((a, b) -> a.dist == b.dist ? a.path.compareTo(b.path) : a.dist - b.dist);
        boolean[][] seen = new boolean[m][n];
        heap.add(new State(ball[0], ball[1], 0, ""));
        
        while (!heap.isEmpty()) {
            State curr = heap.remove();
            if (seen[curr.row][curr.col]) continue;
            if (curr.row == hole[0] && curr.col == hole[1]) return curr.path;
            seen[curr.row][curr.col] = true;
            
            for (State nextState : getNeighbors(curr.row, curr.col, maze, hole)) {
                heap.add(new State(nextState.row, nextState.col, curr.dist + nextState.dist, curr.path + nextState.path));
            }
        }
        return "impossible";
    }
    
    private List<State> getNeighbors(int row, int col, int[][] maze, int[] hole) {
        List<State> neighbors = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            int dy = directions[i][0], dx = directions[i][1], dist = 0, currRow = row, currCol = col;
            String direction = textDirections[i];
            while (valid(currRow + dy, currCol + dx, maze)) {
                currRow += dy; currCol += dx; dist++;
                if (currRow == hole[0] && currCol == hole[1]) break;
            }
            neighbors.add(new State(currRow, currCol, dist, direction));
        }
        return neighbors;
    }
    
    private boolean valid(int row, int col, int[][] maze) {
        return row >= 0 && row < m && col >= 0 && col < n && maze[row][col] == 0;
    }
}

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

Купить новый EXEED RX по спец. цене в Москве! Особые условия на покупку EXEED RX. Выгодный Трейд-Ин + Подарки. Узнайте VIP-цену! Узнать цену #реклама rolfexeed-msk.ru О рекламодателе

Задача: 972. Equal Rational Numbers Сложность: hard Даны две строки s и t, каждая из которых представляет собой неотрицательное рациональное число. Вернуть true тогда и только тогда, когда они представляют одно и то же число. Строки могут использовать скобки для обозначения повторяющейся части рационального числа. Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов: <ЦелаяЧасть> Например, 12, 0 и 123. <ЦелаяЧасть><.><НеповторяющаясяЧасть> Например, 0.5, 1., 2.12 и 123.0001. <ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)> Например, 0.1(6), 1.(9), 123.00(1212). Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например: 1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66). Пример:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

👨‍💻 Алгоритм: 1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина. 2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии. 3⃣Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения. 😎 Решение:

class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
}

class Solution {
    Map<Integer, Employee> emap;
    
    public int getImportance(List<Employee> employees, int queryid) {
        emap = new HashMap<>();
        for (Employee e : employees) {
            emap.put(e.id, e);
        }
        return dfs(queryid);
    }
    
    public int dfs(int eid) {
        Employee employee = emap.get(eid);
        int ans = employee.importance;
        for (Integer subid : employee.subordinates) {
            ans += dfs(subid);
        }
        return ans;
    }
}

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

Data и ML для бизнеса. Большая конференция Яндекса Для продактов, владельцев бизнеса и менеджеров Data/IT-проектов: о применении генеративных моделей, LLM-агентов, чат-ботов и речевой аналитики. Зарегистрироваться #реклама 16+ yandex.cloud О рекламодателе Реклама на Яндексе

Задача: 309. Best Time to Buy and Sell Stock with Cooldown Сложность: medium Дан массив prices, где prices[i] — цена данной акции в i-й день. Найдите максимальную прибыль, которую можно получить. Вы можете совершить любое количество транзакций (т. е. купить и продать одну акцию несколько раз) с следующими ограничениями: После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать). Пример:

Input: prices = [1]
Output: 0

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

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        
        int hold = -prices[0];
        int sold = 0;
        int cooldown = 0;
        
        for (int i = 1; i < prices.length; i++) {
            int newHold = Math.max(hold, cooldown - prices[i]);
            int newSold = hold + prices[i];
            int newCooldown = Math.max(cooldown, sold);
            
            hold = newHold;
            sold = newSold;
            cooldown = newCooldown;
        }
        
        return Math.max(sold, cooldown);
    }
}

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

Виртуальный сервер в аренду в Турции или России. Отказоустойчивый виртуальный облачный сервер на базе виртуализации VMWARE по модели подписки. - Бесплатная миграция инфраструктуры в Турцию - Размещайте ресурсы в Турции или России и оплачивайте в рублях, турицких лирах или евро. - Храните резервные копии данных за рубежом для минимизации рисков - Продолжайте использовать импортное ПО, скачивайте обновления и патчи, общайтесь с техподдержкой - Доступность сервиса — от 99,982% SLA - Дата центры Tier III в России и Турции - Почасовой биллинг и постоплата Подключите услугу сегодня со скидкой 50% на инфраструктуру. Подать заявку #реклама cloud4y.ru О рекламодателе