Ссылка на задачу – 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 ответ
Задача - 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]]), где:
Читать дальше →
ответить
А и Б играют в игру. Игрок А по секрету от Б пишет на двух клочках бумаги два различных числа. Игрок Б выбирает из них случайный и смотрит, какое число на нём написано. Игрок Б должен угадать, больше оно оставшегося числа или меньше.
Если Б подкинет монетку, он угадает с вероятностью 1/2. Существует ли стратегия для Б, позволяющая независимо от того, какие числа написал игрок А, победить с вероятностью больше 1/2?
16 ответов
Слушайте, а кто-нибудь понимает, растёт ли сейчас быстро хоть что-нибудь?
Мне нравится следующая парадигма: в мире всегда сначала происходит технологический прорыв, а затем он за несколько лет отыгрывается бизнесом.
Появились компьютеры как таковые, и в какой-то момент они стали по карману типичным организациям среднего размера, в которых есть какой-то учет, какая-то логистика. Соответственно, появились базы данных и компания Oracle. Компьютеры стали дешевле, появился смысл устанавливать их на массовые рабочие места. Соответственно, до конца 1990-х all the rage была автоматизация офисного рабочего места, на чем выросла сначала компания IBM, потом компания Microsoft. Параллельно оттуда же пошла ветка персональных компьютеров с видеоиграми.
Потом пошел расти интернет. Капиталисты быстро сообразили, что через него скоро можно будет торговать. Да, тут произошел фальстарт с dot com бумом, но с ростом пользовательской базы стали быстро расти и настоящие сервисы, которые затем уже никуда не делись (Гугл, Яндекс, mail.ru, Амазон, Озон - все из тех времен). Проникновение интернета в какой-то момент дошло почти до 100%, зато возникли новые устройства, которые позволяют постоянно носить с собой фотоаппарат, камеру и интернет, а пропускная способность сети стала позволять нормально смотреть видео. Отсюда следующие 100 (или 1000, точно не знаю) компаний-единорогов. Ну и вот, you are here, появление мобильников, кажется, уже отыграно, экспоненты подзатухли, на рынке CS работы уныние и сокращения, стартапы чем дальше, тем более сомнительны.
AI с точки зрения бизнеса пока что выглядит как интернет в 1998. Кажется, что это фальстарт, технология еще не там, автоматизировать даже очень глупого человека сложнее, чем все думали, и из компаний, занявшихся этим прямщас, умрут примерно все. А кто все-таки не умрет, угадать заранее очень сложно. Еком требует совершенно чудовищных затрат с сопутствующими лавкрафтианскими организациями, никакой один человек там ничего не изменит, и вообще успех там не от технологии, как мне кажется, зависит. Роботы растут, но очень медленно, в материальном мире есть некоторое упрямство материала. Если ты сделал даже очень крутого и полезного робота/беспилотник, сделать и продать теперь хотя бы жалкую тысячу (т.е. менее одного робота на каждые 8 млн землян) это отдельный долгий и совершенно нетривиальный процесс, железки не копипастятся.
Читать дальше →
5 ответов
Дано: копатель 15 грейда. Работаю около года. Особого прогресса кроме "теперь я погрузился в предметную область" и совсем немного прокачавшихся hard skills я у себя не вижу. Старшие коллеги как казались недосягаемыми богами в начале работы, так и кажутся до сих пор.
Вопрос: Как расти? Что делать чтобы стать лучше? Чего наоборот не делать? Накидайте советов, опытные товарищи
9 ответов
На этот раз наша задача выглядит заковыристо - 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 ответ
Статья спасена из Яндекс.Кью
Сразу после февральских событий 1917 у большевиков возникла навязчивая идея увековечить память павших героев революции, воздвигнув в их честь некий грандиозный монумент, который непременно должен был «украсить» исторический центр города на Неве. Планов и решений было представлено множество: самые «безобидные» предполагали, в частности, вырубку Александровского сада перед Адмиралтейством и устроение на его месте площади «Свободы» с соответствующим памятным знаком. Также был популярен проект возведения монумента на площади перед Казанским собором; определённую поддержку имел план вырубки Таврического сада под мемориал жертвам революции; прозвучала идея убрать и Летний сад всё для тех же «памятных» нужд или перестроить Знаменскую площадь (нынешнюю площадь Восстания).
Однако самым дерзким во всех отношениях был проект по сносу Александровской колонны и организации мемориального кладбища непосредственно на Дворцовой площади. Рассматривали четыре варианта: строительство монумента у Дворцового проезда (ближе к Адмиралтейству); снос колонны, братская могила на её месте и памятник поверх захоронений посреди площади; третья идея — линия могил вдоль фасада Зимнего дворца; четвёртая — монумент во внутреннем дворе бывшей царской резиденции. Популярный журнал «Зодчий» ратовал за второй вариант (с братской могилой на месте Александровской колонны), а видный политик и публицист Владимир Дмитриевич Набоков (отец знаменитого писателя) в мемуарах «Временное правительство» писал: «Исполнительный комитет назначил день, опубликовал церемониал похорон и выбрал местом для братской могилы Дворцовую площадь, где, как известно, даже приступили к рытью могилы».
Похороны были назначены на 10 марта 1917, потому на детальное рассмотрение проектов времени отводилось немного. Однако практически все варианты, продвигаемые партийным руководством, не получили поддержки жителей Петрограда, а в среде «творческой интеллигенции» образовалась особая комиссия во главе с Максимом Горьким, которая раскритиковала все представленные проекты, один за другим спасая памятники архитектуры Северной столицы. Эта же группа, в состав которой вошли Бенуа, Петров-Водкин, Рерих, Шаляпин и другие, составляла различные документы и записки о невозможности разрушения одного объекта или перестройки другого, опираясь на необходимость соблюдения стилистического единства архитектурных ансамблей.
«Любовь» новой власти к Дворцовой площади объяснялась тремя моментами: во-первых, это самый центр столицы; во-вторых, здесь в 1905 году произошёл расстрел рабочей демонстрации царскими войсками («Кровавое воскресенье»); в-третьих, именно Зимний дворец был символом «гидры Дома Романовых», источника всех несчастий трудового народа (по мнению большевиков).
В итоге, точку в дискуссии поставил опытный архитектор Иван Александрович Фомин, который в своём авторитетном докладе разъяснил «начинающим градостроителям», что новый памятник требует особого места, в котором его не будут заслонять памятники прошлого. Более того, значимость событий, которые надлежит увековечить, требует размаха и простора, потому единственным местом в Петрограде, которое удовлетворит всем идейным и эстетическим требованиям, является Марсово поле. К тому же, бывший Царицын луг, который всегда служил то плацем для войсковых смотров и «экзерциций», то площадкой для масленичных и рождественских гуляний, не требовал сноса или перестройки чего-либо, что было несомненным плюсом. Интересно, что изначально Марсово поле, похороны на котором состоялись 5 апреля 1917 года, не пользовалось особой поддержкой в качестве места для памятника жертвам революции: видимо, сама идея предполагала непременное уничтожение чего-либо старого для постройки на его «костях» чего-то нового.
Читать дальше →
ответить
Сегодня у нас интересная задача на битовые манипуляции – 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 ответ
Здесь я приведу все посты, разделенные по тематикам и отсортированные по рейтингу.
Наука
Математика
★4 Почему 1 не является простым числом? - notq
★4 Бывает ли так, что доказательство сложной математической теоремы, проверенное узким кругом учёных, имеет незамеченную ошибку? - notq
★3 В чем причина деления математиков в вопросе принятия количественной бесконечности — в логике, в вере или в самом фундаменте математики? - notq
★2 Тему «События с нулевой вероятностью» на научном форуме "dxdy" пытаются обсудить. Что мы можем добавить ? - notq
★2 Непрофессионалы в математике - notq
★2 Самое большое число в мире. Как изобрести число больше числа ГРЭМА? - notq
★2 В чем суть теоремы Эрроу? Он правда математически доказал, что демократия невозможна? - notq
★2 Что произойдет после доказательства теоремы Ферма? - notq
★2 Есть ли обобщение поля с определенными гипероперациями высших степеней, например, тетрация и т.д? - notq
★2 Какие есть приложения у теории узлов? - notq
★2 Неожиданные математические факты - notq
★1 Можно ли представить, каким было бы современное научное мировосприятие, если бы случай обернулся по-другому и не было бы Ньютона и Эйнштейна? - notq
★1 Какой минимальный набор понятий и концепций статистики стоит освоить для решения прикладных задач? - notq
Читать дальше →
4 ответа
Очередная наша задача - 2593. Find Score of an Array After Marking All Elements. Ну и так как наша цель не просто решать, а показывать имплементацию разных техник, то воспользуемся-ка мы идеей битового множества (его в стандартную библиотеку Rust еще "не подвезли", так что и операции имплементируем сами).
Задача 🧩
Дан массив положительных целых чисел nums. Ваша цель — получить максимальное значение score, выполняя следующие действия:
- Выберите наименьший немаркированный элемент массива (при равенстве — элемент с меньшим индексом).
- Добавьте значение этого элемента к
score.
- Пометьте выбранный элемент и его двух соседей (если они существуют).
- Повторяйте, пока все элементы не будут помечены.
Необходимо вернуть итоговое значение score.
Идея 💡
В данной задаче нужно эффективно следовать указанным правилам. Чтобы сделать это:
- (а) Мы отсортируем индексы массива nums по значениям, чтобы обрабатывать элементы в правильном порядке, начиная с наименьших.
- (б) Используем битовое множество (
Vec<u128>) для компактного представления состояния "помечен" для элементов массива.
Подход 🚀
Читать дальше →
ответить
Сегодня мы решаем задачу 2924. Find Champion II
🏆 Задача:
В турнире n команд представлены как вершины DAG (ориентированного ацикличного графа). Если команда a сильнее команды b, это отображается направленным ребром от a к b. Требуется найти чемпиона турнира — вершину, из которой достижимы все остальные вершины. Если чемпиона нет или их несколько, вернуть −1.
😊 Идея:
В DAG вершина с отсутствующими входящими рёбрами (in_degree = 0) является источником. Если в графе ровно один источник, он становится кандидатом в чемпионы, так как из него достижимы все остальные вершины
(Нетривиальный момент: это утверждение не верно в общем случе, но в случае DAG его несложно доказать).
Если источников больше или ни одного, чемпиона не существует.
Сложность
-
🕒 Временная сложность:
O(m): Обход рёбер для подсчёта входящих рёбер.O(n): Проход по массиву in_degree.- Итого:
O(n+m).
-
🗂️ Пространственная сложность:
O(n): Для хранения массива in_degree.
Исходный код решения
impl Solution {
pub fn find_champion(n: i32, edges: Vec<Vec<i32>>) -> i32 {
let mut in_degree = vec![0; n as usize];
// Calculate in-degrees for each node
for e in &edges {
in_degree[e[1] as usize] += 1;
}
// Identify the potential champion
let mut champion = -1;
let mut n_champions = 0;
for (node, °ree) in in_degree.iter().enumerate() {
if degree == 0 {
champion = node as i32;
n_champions += 1;
}
}
// There must be exactly one node with in-degree 0
if n_champions == 1 {
champion
} else {
-1
}
}
}
Сегодня на очереди задача 2825. Make String a Subsequence Using Cyclic Increments.
Описание задачи 📝
Даны две строки str1 и str2. Нужно определить, можно ли сделать str2 подпоследовательностью строки str1, выполнив не более одной операции циклического увеличения произвольного набора символов в str1.
Циклический сдвиг означает, что 'a' становится 'b', 'b' — 'c', ..., 'z' — 'a'.
Идея решения 💡
Задача почти идентична проверке подпоследовательности в строке. Единственное отличие — сравнение символов становится чуть сложнее из-за необходимости учитывать циклический сдвиг.
Мы выделяем проверку совпадения символов в отдельный метод, а в остальном используем стандартный алгоритм проверки подпоследовательности.
Реализация подхода 🚀
- Используем два итератора для последовательного прохода по символам строк.
- Для сравнения символов применяем отдельную функцию, учитывающую как прямое совпадение, так и циклический сдвиг.
- При совпадении текущего символа строки
str2 с символом из str1, переходим к следующему символу в str2.
- Если все символы
str2 найдены в str1 в правильном порядке, возвращаем true, иначе — false.
Сложность алгоритма 📊
Читать дальше →
ответить
Наша новая задача – 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
}
}
Последняя в уходящем году задача 983. Minimum Cost For Tickets требует от нас несложного сочетания техник динамического программирования и скользящего окна.
📜 Условие задачи
У вас есть запланированные дни поездок в течение года, указанные в массиве days. Билеты можно приобрести по следующим ценам:
- Однодневный билет за
costs[0] долларов.
- Семидневный билет (покрывает любые последовательно идущие 7 дней) за
costs[1] долларов.
- Тридцатидневный билет (покрывает любые последовательно идущие 30 дней) за
costs[2] долларов.
Необходимо определить минимальные затраты, чтобы покрыть все дни из списка days.
💡 Идея
Для минимизации затрат можно использовать динамическое программирование.
Основная идея — поочередно вычислять минимальную стоимость для каждой даты из массива days, учитывая разные виды билетов, а также использовать индексы скользящих окон для эффективного вычисления диапазонов покрытия билетов.
🛠️ Детали подхода
- Создаем массив
dp, где dp[i] хранит минимальную стоимость поездок для первых i дней.
Читать дальше →
ответить
Ответ спасен из Яндекс.Кью
Это, внезапно, одна из лучших научно-популярных книжек из тех, что я читал за последние годы. Тема, казалось бы, узкая (о некотором античном механизме, найденном в останках кораблекрушения, и попытках разгадать, для чего он служил и как был устроен), но автор настолько фантастически и разносторонне образован, и настолько системно мыслит, что за пару абзацев мимоходом меняет читателю представление о целых масштабных областях.
Чтобы не быть голословным: все мы со школы помним про "бронзовый век", да? Не знаю, как вы, а я с тех пор его так и представлял как-то очень упрощенно. Были люди в шкурах и всё такое, потом научились обработке металлов, люди с бронзовыми мечами легко выносили людей с каменными или даже с медными топорами, ну и понеслась. Так вот, как известно, бронза -- сплав меди с оловом. То ли первая, то ли одна из первых цивилизаций бронзового века, Эгейская (3200 до н.э.), выплавляла бронзу на Кипре, где были удобные для разработки месторождения меди, а олово для этого доставлялось, тадам, из Англии. Представьте себе размеры и сложность необходимых для этого торговых путей и общества в целом. Вот вам и пещерные люди.
Отличие хороших книжек от интернета, если кому-то нужно его доказывать, иллюстрируется тем фактом, что из википедии, например, понять это невозможно, даже если читать именно статью "Бронзовый век", просто не поймешь, на что смотреть.
Или вот другой факт: оказывается, императорская Япония вполне себе разрабатывала ядерное оружие и в 1945 году даже приступила к строительству установки по обогащению урана, чуть-чуть не успели, в общем. Как так получается, что я об этом впервые читаю в книжке, вообще совершенно не об этом написанной?!
Ещё очень радует, что автор, когда ему что-то непонятно, в отличие от большинства своих коллег, не стесняется так и писать: непонятно. После распространенного в научпопе сциентистского высокомерия это освежает. Почему античная цивилизация, дойдя до паровой машины и точных механических калькуляторов, вместо вступления в индустриальную эру решила погибнуть, непонятно. Имеющиеся разъяснения выглядят как средневековое "чеснок исцеляет благодаря своей исцелительной силе", исчерпывающего и убедительного объяснения нет.
На всякий случай, передам предупреждение от старших товарищей, увлекающихся историей техники: говорят, что автор местами увлекается сенсационными интерпретациями в ущерб более банальным, так что самые удивляющие фрагменты лучше перепроверять по независимым источникам. Тем не менее, книжку горячо рекомендую, давайте весь тираж срочно скупим, чтобы такое продолжали переводить и издавать.
ответить
Спасибо загадочному пользователю
leetcoder, здесь опять есть какая-то жизнь. По такому случаю попробуем сюда писать в формате классического web log, вдруг получится не бросить?
Прикольная статья про силу воли и выгорание. Как всегда на lesswrong, длинновато и напоминает домашнюю философию, но основная мысль крайне простая и что-то в ней есть.
У каждого человека есть "бюджет" силы воли. Внутренний нарратор-планировщик, он же "Система 2", когда вы хотите сделать что-то неприятное, берёт кредит из этого "бюджета". Когда в вашей жизни происходит что-то приятное (приятное на базовом, бессознательном уровне), связанное с предыдущими решениями планировщика, бюджет пополняется. Если в бюджете нет средств, вы "выгорели", у вас "не хватает силы воли". Важная часть мысли состоит в том, что "приятное" определяется бессознательно, "системой 1". Например, вы очень любите мороженое; съесть мороженое и заработать $1000 могут оказаться одинаково ценными пополнениями бессознательного бюджета, хотя объективно первое примерно в тысячу раз дешевле. Это позволяет управлять "бюджетом" на сознательном уровне, решая оптимизационную задачу, и помогать другим в том же. Например, взрослые люди, как правило, недохвалены: если они делают свою работу профессионально, затратив на это немало усилий, в том числе и волевых, то это "само собой разумеется".
ответить
Следующая задача 407. Trapping Rain Water II даёт возможность потренировать пространственное воображение (по крайней мере на этапе выбора адекватного для её решения алгоритма).
📋 Описание задачи
Дана 3D-сетка, представляющая высоты ячеек. Необходимо вычислить объем воды, который можно удержать после дождя. Вода может заполнять только области, окруженные ячейками с большей высотой.
💡 Идея
Мы рассматриваем каждую ячейку как часть сетки, где вода может стекать только в соседние ячейки с меньшей или равной высотой. Используя структуру данных непересекающихся множеств (Disjoint-Set или Union-Find), мы группируем соединённые ячейки и отслеживаем их связь с границами, чтобы определить, какие ячейки могут удерживать воду.
🛠️ Детали подхода
-
Представление и сортировка:
- Преобразуем все ячейки в список, где каждая ячейка представлена своей высотой и координатами.
- Сортируем ячейки по высоте в порядке возрастания.
-
Структура объединения множеств:
- Создаем дискретное множество для ячеек, добавляя виртуальный узел для границ сетки.
Читать дальше →
ответить
Сегодня мы рассмотрим решение задачи 2116. Check if a Parentheses String Can Be Valid.
🧩 Описание задачи
Дана строка s, состоящая только из символов '(' и ')', и строка locked длины n, состоящая из символов '0' и '1'. Каждая позиция в locked указывает, можно ли изменить символ в s на этой позиции:
- Если
locked[i] == '1', символ s[i] нельзя менять.
- Если
locked[i] == '0', символ s[i] можно изменить на '(' или ')'.
Нужно определить, можно ли сделать строку s корректной скобочной записью.
💡 Идея
Решение основывается на двух проходах по строке:
- Прямой проход: Проверяем баланс открывающих и закрывающих скобок слева направо, учитывая символы, которые можно менять.
- Обратный проход: Инвертируем строку (меняем '(' на ')' и наоборот) и проверяем баланс справа налево.
При каждом проходе используем два счётчика:
- balance для отслеживания текущего баланса скобок.
- free для отслеживания количества символов, которые можно изменить.
Если на любом этапе баланс становится отрицательным, и его нельзя компенсировать изменением свободных символов, строка не может быть сделана валидной.
Читать дальше →
1 ответ
Наверняка у вас были книжки о математике/программированию, которыми вы зачитывались в подростковом возрасте?
Из тех, которые запомнились мне:
"Математические новеллы", Гарднера и "Алиса в стране смекалки" Рэймонда Смаллиана - обе могу порекомендовать как взрослым, так и детям. #books #math
4 ответа
Сегодня у нас еще одна задача на аккуратное манипулирование индексами 2337. Move Pieces to Obtain a String.
Описание задачи
Даны две строки start и target длины n, содержащие символы 'L', 'R' и '_'.
- Символ
'L' может двигаться только влево, если есть пустое место ('_') слева.
- Символ
'R' может двигаться только вправо, если есть пустое место ('_') справа.
- Необходимо определить, можно ли преобразовать строку
start в строку target с соблюдением этих правил.
Идея 🧠
Задача сводится к тому, чтобы проверить, совпадают ли позиции и направления символов 'L' и 'R' в двух строках с учётом их ограничений на движение. Мы используем итерацию по строкам одновременно, отслеживая доступные символы 'L' и 'R' через счётчики.
Подход 🛠️
- Используем метод
as_bytes(), чтобы быстро перебрать символы в виде байтов.
- Одновременно проходим по обеим строкам:
- Если видим
'L' в target, увеличиваем счётчик доступных 'L'.
- Если видим
'L' в start, проверяем, есть ли доступный 'L', и уменьшаем счётчик.
Читать дальше →
ответить
В нашей новой задаче - 1765. Map of Highest Peak продолжим закреплять работу с семейством простых графовых алгоритмов.
📜 Описание задачи
Вам дана матрица isWater размером m×n, где:
isWater[i][j] == 1 указывает, что клетка — это вода.isWater[i][j] == 0 указывает, что клетка — это суша.
Требуется назначить высоты каждой клетке таким образом, чтобы:
- Высота каждой клетки была неотрицательной.
- Высота любой клетки с водой была равна 0.
- Абсолютная разница высот у соседних клеток не превышала 1.
- Максимальная высота в назначенной карте была как можно больше.
💡 Идея
Мы используем поиск в ширину с несколькими источниками (multi-source BFS), начиная с клеток воды (высота 0).
На каждом шаге ближайшие клетки суши получают высоту на 1 больше текущей.
Этот метод гарантирует, что все клетки суши получают наилучшую из возможных высот, что приводит к максимизации самой высокой высоты в матрице.
🛠 Подробности подхода
- Инициализация:
- Создаём очередь и добавляем в неё все клетки воды, помечая их высотой
0.
Читать дальше →
ответить
Итак, я нагло спарсил notq(спасибо @finder за отсутствие антифрода) и решил посмотреть топовые статьи по голосам пользователей. Текущий топ выглядит так:
| rating | link_title |
|---------:|:----------------------------------------------------------------------------------------|
| 45 | Что здесь происходит - notq |
| 31 | Совет молодому руководителю в IT - notq |
| 16 | Планы на будущее - notq |
| 16 | Космическая интуиция - notq |
| 13 | Печенье "Юбилейное" - notq |
| 11 | Глубокая мысль - notq |
| 10 | Как рассчитывать цену производных финансовых инструментов - notq |
| 9 | Performing productivity at Google: It’s All Bullshit - notq |
| 9 | Кардиологи и китайские грабители - notq |
| 8 | Интервью с директором советского продуктового магазина - notq |
Наиболее рейтинговым автором стал(кто бы сомневался) @robot-q-reposter. За ним идут @finder, @notq и @1e9y.
Читать дальше →
2 ответа
Ссылка на задачу – 1261. Find Elements in a Contaminated Binary Tree.
📝 Описание задачи
Дано двоичное дерево, в котором:
- Корень всегда имеет значение
0.
- Для каждого узла со значением
x:
- Если есть левый потомок, то его значение
2 * x + 1.
- Если есть правый потомок, то его значение
2 * x + 2.
Значения всех узлов загрязнены (-1).
Нужно реализовать структуру FindElements, которая:
- Принимает корень «загрязнённого» дерева в конструкторе.
- Реализует
find(target) — метод, проверяющий существует ли узел с таким значением.
💡 Идея
Восстанавливать дерево не требуется!
Вместо этого мы вычисляем путь к узлу target, определяя его родителя и положение.
🔍 Детали подхода
- Поиск родителя (
parent):
Читать дальше →
ответить
Страница
1
2
3
4
