Задача на сегодня 2657. Find the Prefix Common Array of Two Arrays решается в лоб, но иногда стоит рассматривать и такие простые!
📝 Описание задачи
Даны две перестановки целых чисел A и B длины n. Необходимо вычислить массив общего префикса C, где C[i] равен количеству чисел, присутствующих в обеих перестановках на индексах от 0 до i.
Пример:
- Input:
A = [1,3,2,4], B = [3,1,2,4]
- Output:
[0,2,3,4]
💡 Идея
Чтобы быстро подсчитать количество общих элементов в префиксе, мы будем использовать два булевых массива для отслеживания того, какие элементы уже встречались в каждой из перестановок. Это позволит эффективно определять, какие элементы являются общими на каждом шаге.
📋 Подробности подхода
- Создаем два булевых массива
seen_in_a и seen_in_b длины n + 1 для отслеживания элементов, уже встреченных в A и B.
- Проходим по массивам
A и B одновременно:
- Помечаем текущие элементы
A[i] и B[i] как "увиденные".
- Увеличиваем счетчик общих элементов, если текущий элемент уже был встречен в другом массиве.
- На каждом шаге добавляем текущее значение счетчика общих элементов в результат.
Читать дальше →
ответить
Сегодня у нас интересная задача на битовые манипуляции – 2429. Minimize XOR.
📜 Описание задачи
Дано два положительных числа num1 и num2. Нужно найти число x, такое что:
- Количество установленных битов в числе
x равно количеству установленных битов в num2.
- Результат операции
XOR между x и num1 минимален.
💡 Идея
Для минимизации XOR мы
- Стремимся сохранить как можно больше старших битов из числа num1, так как они оказывают наибольшее влияние на минимизацию результата.
- Если остаются неиспользованные биты, мы добавляем младшие биты, чтобы завершить формирование числа x с требуемым количеством установленных битов.
✨ Детали подхода
-
Подсчёт установленных битов:
- Используем метод
count_ones, чтобы подсчитать количество установленных битов в числе num2.
-
Сохранение старших битов:
- Проходим по битам
num1 с самого старшего до младшего.
- Если бит установлен, включаем его в результат и уменьшаем счётчик оставшихся битов.
Читать дальше →
1 ответ
Наша новая задача – 2425. Bitwise XOR of All Pairings решается "размышлениями на салфетке" и потом очень быстро и просто программируется.
📋 Описание задачи
Даны два массива nums1 и nums2, содержащие неотрицательные числа. Для каждой пары чисел, взятых из этих массивов, вычисляется побитовый XOR. Нужно вернуть результат XOR всех таких пар.
🧠 Идея
XOR обладает полезными свойствами:
- Результат XOR числа с самим собой равен
0 (a ^ a = 0).
- XOR ассоциативен и коммутативен, что позволяет упрощать вычисления.
Только если длина одного массива нечётная, элементы второго массива оказывают влияние на результат, так как они "непарные".
В итоге вклад в результат зависит от длины второго массива для каждого массива из входной пары.
😃 Детали подхода
- Найти длины массивов
nums1 и nums2.
- Если длина
nums2 нечётная, XOR всех элементов nums1 добавляется в результат.
- Если длина
nums1 нечётная, XOR всех элементов nums2 добавляется в результат.
- Возвратить результат как итоговый XOR.
⏱️ Асимптотика
-
Время:
O(n + m), где n и m — длины массивов nums1 и nums2.- XOR всех элементов каждого массива занимает линейное время.
-
Память:
O(1), используется небольшое число дополнительных переменных.
💻 Исходный код
use std::ops::BitXor;
impl Solution {
pub fn xor_all_nums(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let len_nums1 = nums1.len();
let len_nums2 = nums2.len();
// Initialize result as 0
let mut result = 0;
// If nums1 has an odd number of elements, XOR all elements of nums2
if len_nums1 % 2 == 1 {
result ^= nums2.into_iter().fold(0, i32::bitxor);
}
// If nums2 has an odd number of elements, XOR all elements of nums1
if len_nums2 % 2 == 1 {
result ^= nums1.into_iter().fold(0, i32::bitxor);
}
result
}
}
Задача на сегодня 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 с двумя очередями, где приоритет отдается движениям без изменения направления.
🛠️ Детали подхода
- Две очереди:
Читать дальше →
ответить
Следующая задача 407. Trapping Rain Water II даёт возможность потренировать пространственное воображение (по крайней мере на этапе выбора адекватного для её решения алгоритма).
📋 Описание задачи
Дана 3D-сетка, представляющая высоты ячеек. Необходимо вычислить объем воды, который можно удержать после дождя. Вода может заполнять только области, окруженные ячейками с большей высотой.
💡 Идея
Мы рассматриваем каждую ячейку как часть сетки, где вода может стекать только в соседние ячейки с меньшей или равной высотой. Используя структуру данных непересекающихся множеств (Disjoint-Set или Union-Find), мы группируем соединённые ячейки и отслеживаем их связь с границами, чтобы определить, какие ячейки могут удерживать воду.
🛠️ Детали подхода
-
Представление и сортировка:
- Преобразуем все ячейки в список, где каждая ячейка представлена своей высотой и координатами.
- Сортируем ячейки по высоте в порядке возрастания.
-
Структура объединения множеств:
- Создаем дискретное множество для ячеек, добавляя виртуальный узел для границ сетки.
Читать дальше →
ответить
В следующей задаче - 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 для каждой строки/столбца.
Читать дальше →
ответить
