Задача на сегодня 2381. Shifting Letters II - решается несложно, но используемая идея мне лично кажется интересной и симпатичной.
Описание задачи 🔎
Дана строка s и список операций shifts, где каждая операция задаёт начало и конец диапазона, а также направление (вперёд или назад).
Ваша задача — применить все сдвиги к строке и вернуть окончательный результат.
Идея 🔄
Для оптимизации решения и избежания повторных расчётов сдвигов, мы используем алгоритм, основанный на префиксных суммах. Это позволяет эффективно сохранять кумулятивный эффект от всех сдвигов в отдельном массиве и применять их конечному результату за один проход.
Детали решения 📝
- Создадим массив
net_shifts, где будут храниться чистые значения сдвигов для каждой позиции в строке.
- Пройдемся по всем операциям и обновим массив
net_shifts, добавляя значения в начале диапазона и вычитая их сразу после его окончания.
- Произведем один последовательный проход по строке, вычисляя кумулятивные сдвиги и применяя их для каждого символа.
Асимптотика ⏳
- Время:
O(n + m), где n — длина строки, m — количество операций.
- Память:
O(n) для массива net_shifts.
Читать дальше →
ответить
Новая задача - 689. Maximum Sum of 3 Non-Overlapping Subarrays.
Описание задачи 📜
Дано: массив чисел nums и целое число k.
Задача: найти три непересекающихся подмассива длины k с максимальной суммой и вернуть индексы их начала.
Если существует несколько решений, вернуть лексикографически минимальное.
Идея 💡
Для нахождения оптимального решения нам нужно:
- Вычислить суммы всех подмассивов длины
k с помощью техники скользящего окна.
- Найти лучшие индексы подмассивов для правой, средней и левой частей массива, используя динамическое программирование.
Это позволяет эффективно комбинировать результаты и найти оптимальное выделение трёх подмассива.
Детали подхода 🛠️
-
Скользящее окно для вычисления сумм:
- Вычисляем суммы всех подмассивов длины
k, чтобы избежать повторных расчетов.
-
Поиск лучших правых подмассивов:
- Сканируем массив справа налево, чтобы сохранить индексы подмассивов с максимальной суммой для каждого положения.
Читать дальше →
ответить
Ссылка на задачу – 2342. Max Sum of a Pair With Equal Sum of Digits
📌 Условие задачи
Дан массив положительных чисел nums. Необходимо найти максимальную сумму двух различных элементов, у которых одинаковая сумма цифр. Если таких пар нет — вернуть -1.
💡 Идея решения
Вместо хранения всех чисел с одинаковой суммой цифр, достаточно хранить только максимальное из них.
Таким образом, при встрече нового числа с такой же суммой цифр можно сразу проверять, образует ли оно лучшую пару.
🔍 Подход к решению
- Используем массив
max_per_dsum, в котором храним наибольшее число для каждой суммы цифр.
- Максимальная сумма цифр для i32 — 82, но мы ограничиваем массив сотней для простоты.
- Обрабатываем
nums за один проход, применяя функциональный стиль с filter_map:
- вычисляем сумму цифр
d_sum для числа n;
- если уже есть число с таким
d_sum, определяем текущую сумму пары и сохраняем обновлённое максимальное число;
- если это первое число с данным
d_sum, просто сохраняем его в max_per_dsum;
filter_map отбрасывает неопределённые суммы пар (None), оставляя только валидные.
Читать дальше →
ответить
Продолжаем череду задач на перебор - 1079. Letter Tile Possibilities.
📜 Описание задачи
У нас есть набор плиток, на каждой из которых напечатана одна буква, представленный в виде строки.
Необходимо подсчитать количество различных возможных непустых последовательностей букв, которые можно составить, используя плитки.
💡 Идея решения
- Будем использовать бэктрекинг.
- Чтобы избежать проверки на уникальность через
HashSet, сначала сортируем плитки, а затем группируем одинаковые плитки в сегменты.
- Далее, с помощью рекурсии, перебираем все возможные последовательности, гарантируя, что одинаковые плитки не будут использоваться более одного раза в одном наборе последовательностей.
🧑💻 Подробности подхода
- Сортировка плиток:
- Плитки сортируются для того, чтобы одинаковые плитки оказались рядом. Это позволяет нам эффективно группировать их в сегменты.
- Группировка плиток:
- Создаем массив сегментов, где каждый элемент представляет собой количество одинаковых плиток.
- Например, для строки
"AAB" сегменты будут равны [2, 1] (2 плитки "A" и 1 плитка "B").
- Бэктрекинг — для каждого сегмента мы:
- пытаемся использовать плитку (уменьшаем количество плиток в этом сегменте);
Читать дальше →
ответить
Следующая наша задача - 2559. Count Vowel Strings in Ranges.
📝 Описание задачи
Нам дан массив строк words и массив запросов queries, где каждый запрос задаётся парой [li, ri]. Необходимо для каждого запроса определить количество строк из диапазона [li, ri], которые начинаются и заканчиваются на гласные буквы ('a', 'e', 'i', 'o', 'u').
Вернуть массив ответов, где каждый элемент соответствует результату очередного запроса.
💡 Идея
Чтобы эффективно отвечать на диапазонные запросы, мы можем заранее подсчитать кумулятивные суммы валидных строк (начинающихся и заканчивающихся на гласные) в массиве префиксных сумм. Это позволяет сократить обработку каждого запроса до константного времени.
🔍 Подробности подхода
- Создание префиксных сумм:
- Сначала создаём итератор
prefix_sum_iter, вычисляющий кумулятивное количество "валидных" строк
(неплохой повод воспользоваться для этого методом std::iter::scan).
- Добавляем
0 в начало итогового массива (см. std::iter::once и std::iter::chain), чтобы упростить расчёты для запросов (исключая лишнюю проверку условий для обработки начала диапазона).
Читать дальше →
ответить
Ссылка на задачу – 1261. Find Elements in a Contaminated Binary Tree.
📝 Описание задачи
Дано двоичное дерево, в котором:
- Корень всегда имеет значение
0.
- Для каждого узла со значением
x:
- Если есть левый потомок, то его значение
2 * x + 1.
- Если есть правый потомок, то его значение
2 * x + 2.
Значения всех узлов загрязнены (-1).
Нужно реализовать структуру FindElements, которая:
- Принимает корень «загрязнённого» дерева в конструкторе.
- Реализует
find(target) — метод, проверяющий существует ли узел с таким значением.
💡 Идея
Восстанавливать дерево не требуется!
Вместо этого мы вычисляем путь к узлу target, определяя его родителя и положение.
🔍 Детали подхода
- Поиск родителя (
parent):
Читать дальше →
ответить
В очередной задаче для обзора - 802. Find Eventual Safe States нам предстоит найти вершины, не попадающие в циклы графа.
📋 Описание задачи
Нужно определить безопасные вершины в ориентированном графе.
- Безопасная вершина — это такая вершина, из которой невозможно попасть в цикл. Если из вершины можно попасть только в терминальные вершины или другие безопасные, она считается безопасной.
- Граф представлен в виде списка смежности, где
graph[i] содержит все вершины, в которые можно попасть из вершины i.
- Вернуть необходимо список всех безопасных вершин в возрастающем порядке.
- Граф из примера имеет безопасными вершины:
[4,5,6]
💡 Идея
Задача решается с помощью обхода графа в глубину (DFS) и вектора состояний.
Каждому узлу присваивается одно из трёх состояний:
Unseen (ещё не обработан);Processing (в процессе обработки; узлы, являющиеся частью цикла, остаются в этом состоянии и после обработки);Safe (безопасный).
🔍 Детальное описание подхода
Читать дальше →
ответить
Ссылка на задачу – 1910. Remove All Occurrences of a Substring.
📌 Описание задачи
Даны две строки s и part. Нужно избавиться от всех вхождений part из s, выполняя следующую операцию:
- Найти самое левое вхождение
part в s и удалить его
- Повторять, пока
part больше не встречается в s.
🐢 Анализ наивного решения
Достаточно несложно быстро набросать следующее решение:
impl Solution {
pub fn remove_occurrences(mut s: String, part: String) -> String {
let P = part.len();
while let Some(idx) = s.find(&part) {
s.replace_range(idx..idx+P, "");
}
s
}
}
- Временная сложность такого решения в худшем случае достигает
O(N²/P)
Читать дальше →
1 ответ
Задача: 2940. Find Building Where Alice and Bob Can Meet
Описание задачи 📝
У нас есть массив heights, где heights[i] представляет высоту здания i.
Также даны запросы в виде массива queries, где каждый запрос [ai,bi>] требует определить самое левое здание, на которое могут попасть Алиса и Боб, начав с ai и bi соответственно, при соблюдении следующих условий:
- Алиса и Боб могут двигаться только в здания с индексами больше их текущего.
- Они могут перейти только на здания с высотой больше их текущей.
Если подходящее здание невозможно найти, результат для данного запроса равен −1.
Идея 💡
Мне сходу не известна эффективная структура данных для онлайн-разрешения запросов.
Но можно поступить хитрее, а именно:
- Немедленно обработать "простые" запросы, где результат очевиден.
- Для сложных запросов использовать технику отложенной обработки:
- Сначала отсортировать их по индексу правого здания.
- Затем разрешать запросы, итерируясь по зданиям, и, храня кандидатов на разрешение в двоичной куче.
Читать дальше →
ответить
Задача - 1639. Number of Ways to Form a Target String Given a Dictionary
🔍 Описание задачи
Дано: список строк words одинаковой длины и строка target.
Цель: определить, сколькими способами можно собрать строку target, следуя правилам:
- В очередной шаг можно использовать символ, совпадающий с необходимым очередным символом
target, из любой допустимой позиции таблицы words.
- После выбора символа из определённой позиции все символы всех слов левее или равные этой позиции становятся недоступными.
- Вернуть количество способов по модулю
1_000_000_007
💡 Идея
Мы можем использовать подход динамического программирования. Для быстрого обновления состояний ДП предварительно подсчитаем частоты символов для каждой позиции в words.
Формула ДП:
Пусть dp[i][j] — количество способов собрать первые i символов строки target, используя первые j-й позиции в строках words. Тогда:
dp[i][j] = dp[i][j−1] + dp[i−1][j−1]⋅freqj(target[i]]), где:
Читать дальше →
ответить
В следующей задаче - 2661. First Completely Painted Row or Column можно не симулировать в лоб, и за счёт этого сэкономить память при решении (хоть и не получится асимптотически лучше).
📋 Описание задачи
- Нам дан массив
arr и матрица mat, содержащие числа от 1 до m * n.
- Массив
arr задаёт порядок закраски ячеек матрицы mat (закрашивается ячейка, содержащая указанное число).
- В следующем примере:
arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
Необходимо найти первый такой индекс i в массиве arr, при котором:
- Либо вся строка, либо весь столбец матрицы окажется закрашенным.
💡 Идея
Задачу можно переформулировать:
- Каждая строка и каждый столбец закрашиваются, если все элементы строки/столбца обработаны в порядке массива
arr.
- Получается, что для решения задачи нужно:
- Найти максимальный индекс появления значений из
arr для каждой строки/столбца.
Читать дальше →
ответить
Задача на выходные - 2097. Valid Arrangement of Pairs
Описание задачи 📜
Нужно переставить заданные пары [starti,endi] так, чтобы получилось корректное расположение,
где для каждой пары i: endi−1=starti. Гарантируется, что такое расположение существует.
Обзор решения 🛠
Для решения задачи используется алгоритм Хирхольцера, который позволяет построить Эйлеров путь (или цикл) в ориентированном графе. Основная идея — удалять рёбра во время обхода, что упрощает структуру данных и предотвращает повторное использование рёбер.
Ключевые шаги 🚀
-
Построение графа:
- Граф представляется в виде списка смежности (
HashMap<i32, Vec<i32>>), где каждая вершина хранит список своих исходящих рёбер.
- Параллельно вычисляются разницы степеней вершин (входящих и исходящих рёбер) для определения начальной вершины пути.
-
Поиск начальной вершины:
- Начальная вершина — это вершина с положительным балансом исходящих рёбер. Если таких нет, берётся любая вершина из входных данных.
-
Итеративный DFS с удалением рёбер:
- Вместо стандартного рекурсивного DFS используется итеративный подход с явным стеком. Это повышает эффективность памяти и скорость.
- При посещении вершины рёбра удаляются из списка смежности, что гарантирует, что каждое ребро используется ровно один раз.
Читать дальше →
ответить
Задача: 2872. Maximum Number of K-Divisible Components
Описание задачи 📋
Дано неориентированное дерево с n узлами, пронумерованными от 0 до n−1. Также даны:
- массив рёбер edges, где каждое ребро связывает два узла,
- массив значений values, где значение values[i] связано с узлом i,
- число k.
- гарантируется, что сумма всех значений values кратна k
Необходимо найти максимальное количество компонентов, на которые можно разделить дерево, удаляя рёбра, чтобы сумма значений в каждом компоненте делилась на k.
Идея 💡
Будем разбивать дерево на компоненты рекурсивно (DFS), начиная с произвольного узла.
Несложно показать, что родительская вершина должна быть в одной компененте со всеми дочерними, для которых сумма значений в соответствующем поддереве не делится на k.
Детали подхода 🚀
-
Построение графа:
- Представляем дерево в виде списка смежности для удобного обхода.
-
Обход дерева:
Читать дальше →
ответить
Сегодня мы разберём задачу 916. Word Subsets.
📝 Описание задачи
Вам даны два массива строк words1 и words2.
Задача: найти все строки из words1, которые являются универсальными относительно всех строк из words2.
Условие универсальности:
Строка a из words1 универсальна, если для каждой строки b из words2 строка b является подмножеством строки a (Подмножество строки: строка b является подмножеством строки a, если каждая буква в b встречается в a как минимум столько же раз).
Пример:
["warrior", "world"] и ["wrr"]
Ответ: ["warrior"], так как только warrior покрывает все буквы из wrr.
💡 Идея
Для эффективного решения задачи:
- Определим максимальное количество вхождений каждой буквы по всем строкам из words2.
- Для каждой строки из words1 проверим, удовлетворяет ли она этим требованиям.
🔍 Детали подхода
Читать дальше →
ответить
Наша очередная задача - 1930. Unique Length-3 Palindromic Subsequences.
📝 Описание задачи
Дана строка s. Необходимо определить количество уникальных палиндромов длины 3, которые являются подпоследовательностями строки.
Подпоследовательность — это строка, полученная из исходной строки удалением некоторых (возможно, нуля) символов без изменения их порядка. Например, для строки "abcde" строка "ace" является подпоследовательностью.
Палиндром — это строка, которая читается одинаково в прямом и обратном направлениях.
💡 Идея
Основная идея заключается в том, что палиндром длины 3 определяется первыми и последними символами, которые совпадают, а также любым допустимым символом посередине.
Мы можем эффективно отслеживать такие пары (первый и последний символы) с помощью битового массива (bitset), что позволяет минимизировать использование памяти.
🔍 Детали подхода
- Массивы частот:
prefix_frequency: хранит частоты символов слева от рассматриваемого.suffix_frequency: хранит частоты символов справа от рассматриваемого.
Читать дальше →
ответить
Сегодня нам предстоит решить задачу 2577. Minimum Time to Visit a Cell In a Grid.
📝 Описание задачи
- Дана матрица
grid размером m x n, где каждая ячейка (row, col) содержит время открытия ворот, ведущих в эту ячейку. До этого времени в ячейку попасть нельзя.
- Вы начинаете в ячейке (
0, 0) с временем 0 и можете двигаться на 1 ячейку за секунду в любом из 4 направлений (вверх, вниз, влево, вправо).
- Важно: стоять на месте запрещено — вы должны перемещаться на каждое движение.
- Цель — найти минимальное время, чтобы добраться до ячейки (
m-1, n-1). Если это невозможно, вернуть -1.
💡 Идея
Задача сводится к поиску кратчайшего пути с учётом времени открытия ворот в каждой ячейке. Можно представить задачу как динамический граф, где вершины — это пары (время, ячейка), а рёбра — это возможные переходы между ячейками. Вместо того чтобы хранить весь граф, мы динамически вычисляем возможные переходы из посещаемых вершин. Вершины будем перебирать в порядке времён достижимости ячейки (как в алгоритме Дейкстры).
🔑 Подход к решению
- 🧑💻 Графовая модель:
- Ячейки матрицы — вершины графа.
- Рёбра между вершинами имеют вес
1.
Читать дальше →
ответить
Задача, что мы рассмотрим сегодня - 2948. Make Lexicographically Smallest Array by Swapping Elements
📝 Описание задачи:
- Дан массив положительных чисел
nums и положительное число limit.
- Разрешено менять местами элементы массива
nums[i] и nums[j], если выполняется условие:
|nums[i] - nums[j]| <= limit.
- Необходимо получить лексикографически минимальный массив, выполняя такие операции любое количество раз.
Лексикографический порядок: Массив a меньше массива b, если на первой позиции i, где они различаются, a[i] < b[i].
💡 Идея:
Будем эксплуатировать следующие замечания:
- Элементы могут менять местами только внутри определённых групп, где (после её вырезания и сортировки) выполняется условие:
|nums[group[i+1]] - nums[group[i]]| <= limit.
- Индексная сортировка по значениям
nums поможет нас найти группы, внутри которых возможны перестановки.
- Сортировка каждой из этих групп может быть эффективно выполнена с помощью дополнительного индексного массива.
🔍 Детали подхода:
- Сортировка индексов: На первом шаге создаём массив
sorted_indices, заполняя его значениями [0, 1, ..., n-1]. Затем сортируем этот массив по значениям массива nums, чтобы определить относительный порядок элементов.
Читать дальше →
ответить
Сегодня нам предстоит решить задачу 1792. Maximum Average Pass Ratio.
Описание задачи 📚
У нас есть школа, где классы проводят итоговые экзамены. Каждый класс описывается массивом [pass_i,total_i], где:
pass_i — количество учеников,
Читать дальше →
2 ответа
На этот раз наша задача выглядит заковыристо - 2982. Find Longest Special Substring That Occurs Thrice II.
📝 Описание задачи
Необходимо найти длину самой длинной "особенной" подстроки, которая встречается в строке хотя бы три раза. Если такой подстроки нет, вернуть -1.
"Особенная" подстрока — это подстрока, содержащая один и тот же символ.
😊 Идея
Отбросим сразу идею перебора всех возможных подстрок (что крайне неэффективно).
Вместо этого мы сосредоточимся на последовательных участках каждого символа.
Для каждого символа достаточно рассмотреть только длины его подряд идущих сегментов, и это позволит нам эффективно вычислить искомый результат.
🚀 Подход
- Перебираем все строчные английские буквы (
'a' до 'z').
- Для каждой буквы:
- Находим все её подряд идущие сегменты (например, для
'aaaabbaab' сегменты: [4,2], [2,1] для 'a' и 'b').
- Сортируем длины сегментов по убыванию.
- Вычисляем максимальную возможную длину "особенной" подстроки, встречающейся как минимум три раза, используя метод
get_triple_length.
Читать дальше →
4 ответа
Ссылка на задачу – 3105. Longest Strictly Increasing or Strictly Decreasing Subarray.
😎 Описание задачи
Дан массив целых чисел nums. Необходимо найти длину самой длинной последовательности, которая является либо строго возрастающей, либо строго убывающей.
🤔 Идея
Разбить массив на группы (чанки) по непрерывной монотонности (либо возрастающей, либо убывающей).
Для каждой группы вычислить её длину, а затем выбрать максимальное значение среди всех групп.
🚀 Детали подхода
- Разбиение на чанки:
Используем метод chunk_by для разбиения массива:
- Для строго возрастающей последовательности используем сравнение
a < b.
- Для строго убывающей последовательности используем сравнение
a > b.
- Вычисление максимальной длины:
- Для каждого набора чанков вычисляем длину каждой группы, выбираем максимальную длину для возрастающих и убывающих групп.
- Результат:
- Возвращаем максимум между максимальной длиной возрастающей и максимальной длиной убывающей последовательности.
⏱ Асимптотика
- Время:
O(n) — каждый элемент обрабатывается один раз при разбиении на чанки.
- Память:
O(1) — используется дополнительная память только для итераторов, не зависящая от размера входного массива.
📜 Исходный код
impl Solution {
pub fn longest_monotonic_subarray(nums: Vec<i32>) -> i32 {
// Group strictly increasing segments using chunk_by
let max_increasing_len = nums.chunk_by(|a, b| a < b)
.map(|c| c.len()).max().unwrap_or(0);
// Group strictly decreasing segments using chunk_by
let max_decreasing_len = nums.chunk_by(|a, b| a > b)
.map(|c| c.len()).max().unwrap_or(0);
max_increasing_len.max(max_decreasing_len) as i32
}
}
Tags: #rust #algorithms #iterators
1 ответ
Задача на сегодня 3152. Special Array II.
📝 Условие:
- Нам дан массив
nums и запросы queries.
- Для каждого запроса
[from, to] нужно проверить, является ли подмассив nums[from..=to] "особым".
- Подмассив считается "особым", если каждая пара соседних элементов в нём имеет разную чётность (один чётный, другой нечётный).
🧠 Идея:
- Решение основано на идее "вычисли один раз — используй много раз".
- Сначала выполняем линейные предвычисления префиксных количеств пар соседних элементов разной чётности.
- Затём каждый запрос обрабатывается мгновенно за
O(1), что делает решение особенно эффективным для больших массивов и множества запросов 😊
💡 Подход:
-
Префиксная сумма:
- Создаём массив
prefix_count, где prefix_count[i] хранит количество пар соседних элементов с разной чётностью от начала массива до индекса i.
- Заполняем его за
O(n) в одном проходе.
-
Обработка запросов:
- Для каждого запроса
[from, to] считаем количество таких пар в диапазоне через разность: prefix_count[to] - prefix_count[from].
Читать дальше →
ответить
Задача на сегодня 1368. Minimum Cost to Make at Least One Valid Path in a Grid - достаточно стандартная вариация лабиринта с бесплатными переходами.
📝 Описание задачи
У нас есть поле размером m×n, где каждая клетка содержит указание направления движения. Необходимо найти минимальную стоимость перехода из левого верхнего угла (0, 0) в правый нижний угол (m−1,n−1).
Каждая клетка указывает направление движения:
1 — вправо,2 — влево,3 — вниз,4 — вверх.
Изменение направления перехода возможно, но со стоимостью 1, и его можно выполнить только один раз для каждой клетки.
💡 Идея
Поле можно рассматривать как ориентированный граф, где клетки являются вершинами, а направления задают ребра. Наша цель — найти минимальную стоимость пути из начальной клетки в конечную. Для этого используется модифицированный BFS с двумя очередями, где приоритет отдается движениям без изменения направления.
🛠️ Детали подхода
- Две очереди:
Читать дальше →
ответить
Сегодня у нас интересная задача на битовые манипуляции – 2429. Minimize XOR.
📜 Описание задачи
Дано два положительных числа num1 и num2. Нужно найти число x, такое что:
- Количество установленных битов в числе
x равно количеству установленных битов в num2.
- Результат операции
XOR между x и num1 минимален.
💡 Идея
Для минимизации XOR мы
- Стремимся сохранить как можно больше старших битов из числа num1, так как они оказывают наибольшее влияние на минимизацию результата.
- Если остаются неиспользованные биты, мы добавляем младшие биты, чтобы завершить формирование числа x с требуемым количеством установленных битов.
✨ Детали подхода
-
Подсчёт установленных битов:
- Используем метод
count_ones, чтобы подсчитать количество установленных битов в числе num2.
-
Сохранение старших битов:
- Проходим по битам
num1 с самого старшего до младшего.
- Если бит установлен, включаем его в результат и уменьшаем счётчик оставшихся битов.
Читать дальше →
1 ответ
Ссылка на задачу – 1726. Tuple with Same Product.
📜 Описание задачи
Дан массив nums из различных положительных чисел. Нужно вернуть количество кортежей (a, b, c, d), таких что произведение a * b равно произведению c * d, при условии, что все элементы кортежа различны.
💡 Идея
- Для каждой уникальной пары элементов из массива nums вычисляем произведение и подсчитываем частоту его появления с помощью HashMap.
- Для каждого произведения, встречающегося больше одного раза необходимо учесть, что существует 8 уникальных вариантов составления кортежей:
a*b=c*d; a*b=d*c; b*a=c*d; b*a=d*c; c*d=a*b; c*d=b*a; d*c=a*b; d*c=b*a
- Соответственно, итоговый вклад, каждого произведения вычисляется как
4 * frequency * (frequency - 1)
🔍 Детали подхода
- Подсчет в HashMap:
- Используем два вложенных цикла для перебора всех уникальных пар
(i, j) с условием i < j и вычисляем их произведение.
- Результаты произведений сохраняем в
HashMap, где ключ — это само произведение, а значение — количество его вхождений.
- Расчет кортежей:
- Для каждого произведения с частотой больше
1, добавляем в итоговый результат значение
4 * frequency * (frequency - 1).
- Возврат результата:
Читать дальше →
1 ответ
Первая задача в этом году - 1422. Maximum Score After Splitting a String несложная, и интересно решить её за один проход по массиву.
📋 Описание задачи
Дана бинарная строка, состоящая из символов 0 и 1.
Требуется найти максимальный результат разбиения строки на две непустые подстроки.
Результат определяется как:
Результат = (Количество нулей в левой подстроке) + (Количество единиц в правой подстроке).
💡 Идея
Для эффективного решения задачи:
- Рассчитаем динамический баланс для каждого допустимого разбиения строки. Баланс показывает, насколько выгодно разделить строку в конкретной точке.
- Пройдем по строке, обновляя текущий баланс и максимальный результат. Пропустим последнюю итерацию, чтобы обе подстроки оставались непустыми.
🔍 Подробности подхода
- Формула результата: Для разбиения в точке
i:
Result = zero_count + (total_ones - ones_count)
, где:
zero_count – число нулей слева
Читать дальше →
ответить
Страница
1
2
3
4
