Честный разбор с решением, которое не стыдно показать на собеседовании, я всё же сделаю :)
Идея 💡
Задача состоит в том, чтобы разделить массив на максимальное количество блоков, так чтобы сортировка каждого блока и их объединение давали отсортированный массив. Ключевая идея заключается в том, что элементы из одного цикла перестановки
arr1 → arr2 → arr3 → ... → arrn → arr1
обязательно должны находиться в одном блоке, так как они взаимозависимы.
Описание подхода 🛠️
- Создаём массив
chunk_assignment, чтобы отслеживать принадлежность каждого индекса к определённому блоку.
- Используем функцию
assign_chunk для рекурсивного назначения всех индексов, связанных с текущим индексом, в один блок. Она:
- Обновляет максимальный индекс текущего блока.
- Помечает все посещённые индексы текущим номером блока.
- Внешний цикл:
- Перебирает индексы массива.
- Увеличивает счётчик блоков при обнаружении нового блока.
- Завершает обработку текущего блока, когда все его элементы покрыты.
- Возвращаем общее количество блоков
Асимптотика 📊
- Время:
O(n), так как каждый элемент обрабатывается один раз.
- Память:
O(n), для хранения массива chunk_assignment.
Исходный код решения 📜
impl Solution {
pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
let n = arr.len();
let mut chunk_assignment = vec![0; n]; // Tracks which chunk each index belongs to
let mut chunk_count = 0; // Counter for the number of chunks
// Helper function to assign indices to a chunk
let mut assign_chunk = |start_idx: usize, chunk: i32, max_idx: &mut usize| {
let mut current_idx = start_idx;
while chunk_assignment[current_idx] == 0 {
*max_idx = (*max_idx).max(current_idx);
chunk_assignment[current_idx] = chunk;
current_idx = arr[current_idx] as usize;
}
};
let mut start_idx = 0;
while start_idx < n {
chunk_count += 1; // Start a new chunk
let mut max_idx = start_idx;
// Process the current chunk until all related indices are covered
loop {
assign_chunk(start_idx, chunk_count, &mut max_idx);
if start_idx == max_idx {
break; // The current chunk is complete
}
start_idx += 1; // Move to the next index
}
start_idx += 1; // Move to the next unprocessed index
}
chunk_count // Return the total number of chunks
}
}
Кажется что мы разговариваем на сильно разных английских.
По моему опыту:
- slayer вышел из употребления, последние пару раз я видел это слово в названии группы
- triggerman, manslayer вообще ни разу в жизни не встречал
- cutthroat до сегодняшнего дня был уверен что это исключительно прилагательное
- insecurity имхо к ревности имеет крайне опосредованое отношение, оно скорее про низкую самооценку и недостаток признания
- intelligentsia видел только применительно к СССР, в дискуссиях о США это скорее cultural elite/educated class/chattering class
перейти
Я освободил свой разум и понял первое решение. По-моему, его не стыдно и на собесе написать (разве что не в таком стиле, а циклом), оно не эзотерическое.
перейти
Интересно, в каких компаниях такие ужасы спрашивают. У меня платного leetcode нет, не подскажешь, если у тебя есть, конечно?
перейти
- slayer книжное слово, и, мне кажется, ничем в этом смысле не отличается от "душегуба" и "головореза". В GoT кличку Kingslayer не снабжали сноской и не поясняли
- я не знаю, как перевести "он ревнует свою жену ко всем подряд" с сохранением смысла без использования слов insecurity/insecure. Со словом jealousy/jealous получается совсем другое утверждение, что-то вроде "он (думает, что) не получает от своей жены того, что достается всем подряд, и от этого страдает"
- intelligentsia в мемах пример 1, пример 2. Это я сейчас поиском нашел, но вообще на сабстеке периодически натыкался в живой природе
перейти
Согласен, аналогичная история.
Мое доказательство основано на тождестве 0-0=0. Допустим, наше решение не оптимально. Рассмотрим первый несовпадающий чанк в нашем решении и в оптимальном. Оба имеют нулевой баланс. В нашем решении он короче, потому что иначе мы сформировали бы его раньше. Тогда чанк в якобы оптимальном решении можно разбить на два -- наш и остаток. Пришли к противоречию.
перейти
Достаточно просто показать, что при увеличении числа студентов в классе margin gain только падает. А это в свою очередь означает, что любая цепочка добавлений студентов в разные классы может быть отранжирована по убыванию margin gain и корректно применена уже в новом порядке.
перейти
Для максимизации среднего соотношения нужно жадно добавлять студентов
Почему? Это совершенно не очевидное математически утверждение. У нас тут какая-то очень ядреная функция от n переменных, почему жадным методом мы придем в её глобальный минимум, а не в локальный?
перейти
С БАК было более очевидно -- емнип был простой контраргумент, состоящий в том, что энергия столкновения все еще меньше энергии некоторых (редких, но время от времени вполне регистрируемых) космических частиц, входящих в атмосферу Земли. Т.е. аналогичные события в природе происходят "сами собой", нет ничего особенного конкретно в БАК.
В случае с бактерией неправильной хиральности есть небессмысленная модель угроз: в биосфере появляется незамкнутая цепочка переработки (бактерия вряд ли сможет замкнуть все циклы в одиночку). Подобное в реальной истории жизни на Земле уже несколько раз происходило, например, carboniferous period. В результате происходит накопление неиспользуемых веществ и вывод их из активного оборота до тех пор, пока не эволюция не произведет кого-то, кто умеет их перерабатывать, что может занять десятки миллионов лет. Для этого не обязательно, чтобы новая бактерия была "суперхищником", достаточно, чтобы она просто быстро не сдохла.
Ну и в целом соотношения risk-reward тут крайне сомнительные.
перейти
А, я понял.
То есть речь о рисках небыстрого, но полного занятия какой-то биоподобной ниши.
С таким я согласен, возможно.
Но всё же, я также и почти уверен, что заниматься эта ниша будет даже не годами, а тысячелетиями или десятками тысяч лет. Это совсем копейки с точки зрения геологической летописи, но совсем иной уровень угроз, с точки зрения человеческой цивилизации (мы тупо парниковыми газами успеем раньше всё загадить).
перейти
В первом решении - самое сложно на мой взгляд - доказать корректность.
Не то, чтобы это было почти невозможно, возможно и за разумное время.
Но на доказательство, почему он работает (и в том числе безуспешные попытки найти контрпример) у меня ушло больше времени, чем на написание/понимание кода.
перейти