amarao

Всё-таки match в Rust - это киллер-фича. Язык должен был называться Match.

Задача на общую занимаемую площадь двумя прямоугольниками, которые могут перекрываться любым образом.

https://leetcode.com/problems/rectangle-area

Общее решение задачи: сумма площадей минус площадь пересечения. То есть задача на самом деле сводится к площади пересечения двух прямоугольников (я когда решал даже забыл про "общую площадь" и писал только пересечение).

Сначала компактный код решения, в котором "всё понятно".

use std::cmp;

impl Solution {
    pub fn compute_area(ax1: i32, ay1: i32, ax2: i32, ay2: i32, bx1: i32, by1: i32, bx2: i32, by2: i32) -> i32 {        
        let mut combined = (cmp::min(ay2, by2) - cmp::max(ay1, by1)) * (cmp::min(ax2, bx2) - cmp::max(ax1, bx1));
        if by2 < ay1 || ay2 < by1 || bx2 < ax1 || ax2 < bx1 {
            combined = 0;
        }
        (ay2-ay1) * (ax2-ax1) + (by2-by1) * (bx2-bx1) - combined
        
    }
}

А вот моё решение. Оно сильно больше строк занимает, но, надеюсь, оно лучше объясняет суть решения:

#[derive (Copy, Clone, Debug, PartialEq, Eq)]
enum Color {
    Pink,
    Violet
}

#[derive (Copy, Clone, Debug)]
enum State{
    No,
    One(Color), //Single color zone
    Intersection(i32) // two color zone
}


use State::*;
use Color::*;

impl Solution {
    pub fn compute_area(ax1: i32, ay1: i32, ax2: i32, ay2: i32, bx1: i32, by1: i32, bx2: i32, by2: i32) -> i32 {
        fn intersection(a1: i32, a2: i32, b1: i32, b2: i32) -> i32{
            let mut colored_dots = [(a1, Violet), (a2, Violet), (b1, Pink), (b2, Pink)];
            colored_dots.sort_by(|a, b| a.0.cmp(&b.0));
            let mut state = No;
            for dot in colored_dots{
                match (state, dot) {
                    (No, (_, color))  => {
                        state = One(color);
                    },
                    (One(color), (start, new_color)) if color != new_color => {
                        state = Intersection(start);
                    },
                    (Intersection(start), (end, _)) => {
                        return end-start;
                    }
                    _ => { // no intersection
                        return 0;
                    }
                }
            }
            0
        }
        fn area(x1:i32, x2:i32, y1:i32, y2:i32) -> i32 {
            (x2-x1)*(y2-y1)
        }
        let intersection = intersection(ax1, ax2, bx1, bx2) * intersection(ay1, ay2, by1, by2);
        let rect1 = area(ax1, ax2, ay1, ay2);
        let rect2 = area(bx1, bx2, by1, by2);
        rect1 + rect2 - intersection
    }
}

Когда я написал match, это было ощущение "хорошей презентации". Вместо каких-то странных cmp/min/max, я объясняю алгоритм.

Назначим обоим прямоугольникам цвет. Отсортируем точки для оси, сохраняя цвет.

Идя по всем точкам: для первой точки (state=No), нам важен только цвет. Запомним его.
Далее, для следующей точки, если у нас цвет уже известен, и цвет поменялся, запомним начало пересечения.
Если у нас уже есть пересечение, на следующей точке, вне зависимости от её цвета, находится конец пересечения.

Если нам не удалось найти пересечения, то его нет.

Вот это "вне зависимости от цвета" или "нам важен только цвет первой точки" - это же явно написано. "Оставшееся выбросить". И при написании мы точно знаем, что покрыли все-все варианты, потому что match исчерпывающий.

А вот задачу инвертирования списка я считаю очень и очень полезной для понимания Rust'а. Ощупывание границ того, что можно делать с deconstructed structs - это очень и очень важно.

Об алгоритме.
Есть два алгоритма:

1) Сложить всё в стек и собрать обратно список в другом порядке. При том, что алгоритмически это такой же уровень сложности, на практике - это ~30-кратное замедление из-за необходимости иметь дополнительные аллокации и копирования.

2) Пройти по списку и поменять направление ссылок. Было (val1, Link_to_2) -> (val2, Link_to_2) -> (val3, None), должно стать (val1, None) <- (val2, Link_to_1) <- (val3, Link_to_2).

В условиях указателей (си-подобный язык) эта задача довольно простая, потому что мы казуально допускаем, что в какой-то момент у нас "всё висит" или есть два указателя на одно и то же место. (ну и чё такого?).

В Rust же всё куда более интригующе. Список - это

pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

При этом настоящий тип списка - это

Option<Box<ListNode>>

Проговорим это:

Список это:

Либо None
Либо enum, который владеет smart pointer'ом на heap, у которого тип Box, внутри которого находится структура ListNode.

Структура ListNode владеет val и next, который и есть остаток списка.

Чувствуете, как всё нюасно стало? Не ссылки, а есть владение. Чтобы взять содержимое val или next мы должны:
1. Деконструировать Option.
2. Деконструировать ListNode.

После того, как мы деконструировали или Option, или ListNode, мы больше не можем передать его куда-то дальше!

То есть наивное: something.next = cur мы не можем сделать! У нас cur больше не существует.

В целом, эта задача была бы не решаема, если бы не возможность "реконструировать" ListNode. Если мы для каждого поля, из которого мы "взяли" значения положим назад значения (move, передадим владение туда), то мы получим "реконтструированную" структуру, которую мы можем передавать дальше.

Деконструированный же Option невозможно реконструировать (его больше нет), вместо этого мы можем создать новый. Что такое "новый Option" и чем он отличается от старого? В целом, ни чем. Я даже не уверен, что это создаст какие-то машинные инструкции, но с точки зрения компилятора новый Some и старый Some (который мы деконструировали) - две совершенно разные вещи.

Вот решение:

pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    while let Some(mut node) = head{
        head = node.next;
        node.next = prev;
        prev = Some(node);
    }
    prev
}

Проговариваю его по шагам:

Мы деконструируем head (если есть что деконструировать), и создаём переменную node, которая получает владением над содержимым head. Option<Box<ListNode>> → Box<ListNode>.

node имеет тип Box - это умный указатель на кучу, который (за вычетом кучи) просто владеет ListNode.

К этому моменту у нас head не имеет значения (мы делали move из него в строчке while let).
Мы передаём в head значение поля node.next. В этот момент node становится частично деконструированной. next из неё забрали, а value всё ещё принадлежит node.

После этого мы перемещаем в node.next значение из prev. prev перестаёт иметь какое-либо значение (т.к. отдал владение значением). Зато node теперь полностью сконструирован, потому что он владеет всеми своими значениями.
Мы создаём новое значение Some(node), забирая значение из переменной node, node перестаёт иметь какое-либо значение (т.к. отдал владение значением в Some), после чего мы отдаём владение Some(node) переменной prev.

К концу цикла у нас: prev - содержит в себе Some(node), next содержит в себе либо None, либо Some со следующим элементом списка, то есть содержит остаток списка), node - не определён. Цикл заканчивается, у node заканчивается область видимости и она (он? оно?) уничтожается. Т.к. значение уже было move, то ничего делать не надо. Начинается следующая итерация.

В конце мы отдаём владение prev, внутри которого владение prev.next, внутри которого prev.next.next и т.д., то есть инвертированный список.

Вот, примерно так устроен процесс думания о Rust программе. Где-то тут был пропущен вопрос, как мы сквозь Box<ListNode> получаем поля ListNode. Я тщательно этот вопрос не продумывал, но насколько я понимаю, это неявно вызываемые функции deref и deref_mut, реализованные через трейты Deref и DeferMut.

Все эти возни на leetcode привели к тому, что я нашёл минималистичную конструкцию для обхода их странного Rc RefCell дерева.

pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    fn dive(t: &Option<Rc<RefCell<TreeNode>>>, acc: &mut Vec<i32>){
        if let Some(rc) = t{
            let node = rc.borrow();
            dive(&node.left, acc);
            dive(&node.right, acc);
            acc.push(node.val);
        }
    }
    let mut acc = Vec::new();
    dive(&root, &mut acc);
    acc
}

Ключевое открытие тут: с любым Rc надо работать только через ref/mut ref. Как только появляется владение Rc, начинаются массовые проблемы, потому что rc.as_ref() создаёт короткоживущий референс и начинаются всякие выкрутасы. А c ref всё очень хорошо. Во-первых &option<T> автоматом конвертируется в & T после `if let Some...`. После того, как у нас появляется &T, простой .borrow() даёт нам правильную сущность с lifetime блока Some. Дальше мы можем обращаться к содержимому по точке, потому что там Deref реализован (насколько я понимаю, это именно Deref).

Вторая штука, которую я подглядел у соседей по решению: вложенные функции очень удобны, потому что находятся внутри Solution и их легко рекурсивно вызывать без Solution:: и т.д. Вложенные функции в Rust довольно банальны и всего лишь "записаны локально". В отличие от питона у них нет никаких признаков захвата замыкания (в питоне вложенные функции - метод создания замыканий), т.е. это исключительно кнопкодавное удобство.

Одна из простых задач, которые сложны в Rust'е: даны числа в виде списка чисел (десятичные знаки в i32), список в обратном порядке
(то есть head списка - самое крупное число). Надо в таком же виде (списка) вернуть сумму этих чисел.

https://leetcode.com/problems/add-two-numbers

Rust'овые проблемы:

1. Чтобы в том же порядке сложить числа, их нужно засовывать в хвост по мере складывания. В Rust значительно проще было бы делать это в обратном порядке, но увы. Засовывание в хвост чревато тем, что мы должны иметь значение головы для возврата, то есть по списку по мере построения мы двигаемся с помощью &mut, что приводит к тому, что нам надо менять head по & mut, а это означает чёрную магию mem::swap. (Магия хоть и чёрная, но safe, ура).

2. Когда мы ползём по списку, мы не можем казуально заглядывать в tail полученного списка несколько раз, т.к. происходит move (передача владения), в момент заглядывания. Обходные пути через ссылки не очень работают, потому что компилятор не понимает, можно ли нам верить с сроком жизни полученных ссылок (точнее, он знает, что верить нельзя).

Получается такое:

    pub fn add_two_numbers(
        mut l1: Option<Box<ListNode>>,
        mut l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut carry = 0;
        let mut result = None;
        let mut tail = &mut result;
        while l1.is_some() || l2.is_some() || carry > 0 {
            let (n1, next_l1) = l1.map_or((0, None), |n| (n.val, n.next));
            let (n2, next_l2) = l2.map_or((0, None), |n| (n.val, n.next));
            let sum = n1 + n2 + carry;
            let mut new_node = Some(Box::new(ListNode {
                next: None,
                val: sum % 10,
            }));
            std::mem::swap(tail, &mut new_node);
            tail = &mut (tail.as_mut().unwrap().next);
            carry = sum / 10;
            l1 = next_l1;
            l2 = next_l2;
        }
        result
    }

трюки:

1. mem::swap для того, чтобы поменять &mut (ведущий на None) на новое значение.
2. синхронное выковыривание val & next в одну строчку.

Алготримическое:

While зависит от обоих цифр и carry. Это позволяет элегантно решать проблему последнего символа.

Я думал, что это у меня кривые руки и задача решается проще, но не нашёл ни одного соседнего решения, которое было бы элегантным. Пока что основное, что я видел, то предсоздание в качестве result '0' вместо None (что, соотственно, IRL ломает инвариант для add_two_numbers(None, None), который должен сделать None, хотя тут задача становится мутной, потому что 1 + None - это сколько?).

За что мне при этом дали 31мс решения я не понял, кажется, это флуктуации.

В рамках гольфа: Если гоняться за оптимизацией памяти, то мы можем переиспользовать полученные l1/l2 для новых нод, таким образом, экономя на аллокациях.

В рамках экономии строк: если n1/n2 декларировать над циклом, то можно будет делать n1, l1 = ...., без временных переменных и let.

Upd: могу, но не могу. Моя версия Rust это уже умеет, leetcode'овская утверждает, что destructuring assignments are unstable.

А вот я думал, что задачу symmetric tree я решу в пол-пинка. (Задача: по заданному дереву сказать, симметричное ли оно).

Теоретическое решение: pre_walk() == post_walk().

Практические проблемы: наивные методы обхода дерева используют рекурсию, а использовать рекурсию при параллельном обходе дерева двумя разными способами - себе дороже.

Выгрузка обоих деревьев в список и сравнение - уровень сложности алгоритма `o(позор)`.

Правильное решение: реализовать стеки из вектора и обходить в цикле. Но два обхода в одной функции уродливо, так что идиоматический подход должен реализовать итератор pre_walk(), итератор post_walk(), и потом просто сравнить их. (то есть решение будет `pre_walk(&tree) == post_walk(&tree)`).

А вот над реализацией нерекурсивного обхода дерева я сейчас буду думать. Теоретически, ничего сложного, но масса эргономических нюансиков (например, как хранить направление движения (влево или вправо)? Надо ли его хранить или оно само получится?).

Плюс rust'овая машинерия для итераторов, которая выглядит ясной и простой, пока туда lifetimes для захваченных ref не появятся.

Короче, задача сводится к pre_order walk через итератор. Решу её, дальше тривиально. Традиционно, сначала решаю, потом читаю умные тексты.

Я научился из списка leetcode'а делать дерево! Это было невероятно тяжело, и Rust в этом месте показал learning curve в районе over 60°. Зато к финалу я стал много лучше чувствовать ownership/borrow, особенно, в контексте Rc/RefCell.

Примерно через три часа размышлений о том, как совместить VecDeqeue.get и VecDequeue.pop_front, я понял, что я не могу решать проблему, игнория существование и свойства Rc<RefCell<TreeNode>>. До этого момента я пытался обойтись голым Option, не используя свойства Rc.

Потом я написал функцию mktreefull, которая не умеет несбалансированные деревья (то есть у каждой ноды заполнены оба потомка). В этот момент я почувствовал свет истины.

Потом я ушёл писать walk, чтобы проверить, что я написал правильно, и опять застрял в "получении значения из Rc<RefCell> без .borrow()". И вот тут-то на меня снизошло понимание, что нельзя их использовать без borrow, и все мои выкрутасы тут - фигня.

Я на 99% уверен, что мой алгоритм настолько далёк от компактного, насколько можно, но вот он в двух словах.

У нас есть тип (дерева):

pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

type Tree = Option<Rc<RefCell<TreeNode>>>;

Нам надо читая список вида

Some(1),
Some(2), Some(3),
Some(4), None, None, Some(7),
Some(8),

Собрать дерево. Вот такое:

1
2 3
4 None None 7
8 None None None
None None

(каждая строка - уровень дерева) Можно заметить, что вывод похож на вход, хотя None больше, потому что в компактном вводе "оставшиеся None" не указываются.

Идея, которая у меня не взлетела - класть в VecDeque left и right ноды (None) и заменять из с помощью mem::swap.
Новая идея, которая сработала: вместо сохранения потомков у узла, сохранять сам узел, и обрабатывать его дважды (для левой и правой части). Грубо говоря, для левой части мы делаем push_back(cur.left), push_front(cur). А когда делаем push_back(curl.right), то не делать push_front(cur). Когда мы обрабатываем новое значение, мы смотрим на текущее значение curl.left, и если оно пустое, то это обработка левого поддерва, если не пустое - правого.

Это работало для сбалансированного дерева. Для несбалансированного дерева мы, обрабатывая значения можем получить None, то есть "левый лист не нужен". В этой ситуации, если мы сделаем в следующю итерацию проверку на cur.left.is_none, то получим, что left is none, то есть надо идти на лево, хотя надо было на право.

Чтобы решить эту проблему я сделал enum для состояния узла в VecDeque:

enum NodeState {
    Left(Tree),
    Right(Tree),
}

impl NodeState {
    fn new(t: &Tree) -> Self {
        NodeState::Left(t.as_ref().cloned())
    }
}

Заметим, тут же происходит магия Rc/RefCell, я использую t.as_ref.cloned.

напоминаю, что

type Tree = Option<Rc<RefCell<TreeNode>>>;

то есть t.as_ref превращает &Option<Rc<RefCell<TreeNode>>> в Option<&Rc<RefCell<TreeNode>>>.
Потом мы дёргаем cloned, что проходит в Rc (сквозь Option за счёт трейта Deref, насколько я понимаю) и это делает магию Rc, то есть приводит к появлению +1 на счётчике и ещё одной ссылки (вместо клонирования содержимого). Я вытащил этот самый as_ref().cloned() в реализацию NodeState просто, чтобы сэкономить нажатие кнопок в основной функции.

Дальше у нас простая state machine:

let cur = buff.pop_front().unwrap();
match cur {
NodeState::Left(Some(node)) => {...},
NodeState::Right(Some(node)) => {...},
  _ => {panic!();}
}
 
 

В которой у нас разное поведение для left и right. Если мы в left, то мы кладём в конец новый узел, а в голову возвращаем текущую ноду, но в состоянии 'Right'.
В Right мы кладём новый узел в голову, а текущий узел уже никуда не добавляем.

Ну, и, разумеется, в текущей ноде поддеревья попадают в разные стороны.

Процесс модификации текущей ноды целиком зависит от магии Rc (мы делаем borrow_mut из немутабельной ссылки):

node.borrow_mut().left = subtree;

Повторю, я на 100% уверен, что есть более элегантные решения, но у этого есть неоспоримое достоинство - я его сам думал целиком, а заодно учился жить с Rc/RefCell.

Код: https://github.com/amarao/leetcode-tree-build/blob/master/src/main.rs#L41

А вот теперь, я пойду читать как эту проблему решают взрослые мальчики.

Моя hard task свелась к проблеме поиска структуры, которая есть в стандартной библиотеке, и которая даёт мне возможность вставлять, удалять и находить максимум быстрее, чем o(n). Кроме того, структура должна поддерживать дубликаты. Rust пока не даёт 'first/last' для BTree, так что приходится думать самому.

Правильный ответ - binary search tree, но у меня не хватает сейчас мозгов его хорошо написать, и я не хочу туда коммититься.

Вот что я придумал "их того что было и палок".

объём данных: n
k = sqrt(n) (квадратный корень из n)

Создадим Vec (массив) и VecDeque (double ended queue) - такие есть в в стандартной библиотеке. Всего будет k (напоминаю, sqrt(n)) Vec'ов при ожидаемом размере каждого элемента - k. Получается sqrt(n) * sqrt(n) = n.

Все элементы хранятся упорядоченно. Каждый VecDeque упорядочен от младшего к старшему, каждый элемент Vec содержит в себе VecDeque, которые так же полностью упорядочены.

Вставка:

Найти двоичным поиском в Vec нужный элемент (VecDeque). o(log(k))
Найти двоичным поиском в VecDeque нужную позицию, либо дописать слева/справа. o(log(k))
Вставить элемент в указанный индекс. Сложность o(k/2), с поправкой на облечение "вставки в начало" (т.к. VecDeque).
После этого произойдёт переполнение VecDeque (размер станет больше k), и надо будет перекинуть элемент вверх или вниз. Возможно, в худшем случае вставка потребует перекидывать элементы между каждой "строкой" (VecDeque), так что худший случай - o(k) pop_back, o(k) push_front. в среднем o(k) операций.

Сложность: log(k) + log(k) + o(k/2) + o(k/2) + k + k =~= k

Удаление:

Найти двоичным поиском в Vec нужный элемент (VecDeque). o(log(k))
Найти двоичным поиском в VecDeque нужную позицию o(log(k))
Перенормировать длины: 2*o(k)

Сложность: o(k)

Поиск максимума o(1) - последний элемент последней строки.

Теперь, вспомним, что k - это sqrt(n), и получаем, что сложность вставки/удаления - sqrt(n), что лучше, чем n.

При использовании внутри алгоритма со сложностью n*log(n), получаем n*log(n)*sqrt(n), ~n^1.5, что лучше, чем o(n).

Не фонтан, но...

Вопрос: не могу ли я расширить этот подход на более чем одно измерение? Теоретически, в пределе должно получиться как раз log(n).

Фактически, я хочу сделать дерево, в котором у меня в векторе хранятся вектора, внутри которых хранятся вектора... и так пока я не дойду до самого дна, то есть до leaf'а. Одним из интересных улучшений в рамках задачи является то, что я знаю максимальный размер (n) заранее и могу посчитать оптимальную глубину в момент создания, то есть мне не нужно пересчитывать глубины.

"дерево на векторах" мне кажется куда интереснее, чем обычный struct с left/right (как обычно дерево описывается).

Я сейчас попробую изобрести такое дерево, если не получится, попробую штурмовать задачу с n^(1.5) сложностью решения. Цена вопроса - для 10000 элементов квадратичное решение - это 100 миллионов операций, а 1.5 - это миллион. 100-кратное ускорение. Для 100k элементов - 100 миллиардов против 31 миллиона, 300-кратное ускорение.

Итак, как будет устроено DQTree? По аналогии с btree, я хочу ограничить глубину сканирования эффективным коэфицентом. Допустим, я выбираю коэфицент B (16).

У меня N элементов, и мне нужно посчитать, сколько слоёв нужно в дереве. log₁₆N, округлённый вверх. Допустим, у меня 333333 элементов. Это 5 слоёв (из значения логарифма 4.58..)

В первом слое у меня B элементов (Vec), во втором слое у меня B элементов (тоже Vec), в третьем слое у меня B элементов, в четвёртом у меня B элементов, в пятом у меня Deque... А нужно ли оно тут? Если у меня там up to 16 элементов, то любой insert в него будет константным. Так что просто Vec. Все слои, кроме нижнего, содержат в себе только Vec следующего уровня. Нижний Vec содержит в себе числа.

Переименовываем стуктуру в VecTree.

Создание: Аллоцирвать все Vec'и. WUT? Это же o(n) операций. Нет.

Вместо Vec у нас появляется Option... При создании VecTree мы ничего не аллоцируем.

Вставка:

Дойти до нижнего элемента за o(log n), вставиться в него за o(B) времени (то есть за o(1)).
Каким образом я знаю, в какой элемент вставляться? Если это первый элемент, то понятно, самая левая ветка.

А если, допустим, у нас целиком уровень забит Vec'ами? Как нам понять, в какой Vec ходить?

Допустим, мы будем хранить min/max для обслуживаемого диапазона.

Итак, пройтись по элементам, выбрать подходящий диапазон. Если слишком маленький - расширить диапазон левого значения, если слишком большой - правого.

Спуститься на уровень ниже. Повторить.

Пока не прийдём к нижнему слою.

Двоичным поиском найти нужное место, вставиться.

После вставки мы проверяем размер Vec'а и думаем, что с этим делать. Если размер меньше B, то "и пофигу".

Если размер больше B, то надо вынуть элемент в ставить "куда" следует:

Если у нас нет соседа слева, то надо убирать правый элемент.
Если у нас нет соседа справа, то надо убирать левый элемент.

А если есть оба соседа? Как понять в какую сторону значение надо двигать? По-идее надо двигать в ту сторону, в которой меньше всего элементов.

Для этого мы записываем число элементов для каджого Vec'а. (не число элементов в Vec, а число элементов в Vec в Vec в Vec ... до самого дна).

То есть обычная (не leaf) нода выглядит так:

min
max
count

При спуске на слой ниже мы смотрим на предпочтения по перекидыванию значений. Для этого мы считаем число элементов в остальных элементах слоя (кроме того, в который мы погружаемся) и вычисляем left_count и right_count, который и известен следующему слою.

Когда слой решает, какой элемент удалять при переполнении, он смотрит какой меньше и с той стороны удаляет элемент. (Будет обидно, если удаляют элемент, который только что был вставлен... не создаст ли это бесконечный цикл? Удалённый элемент при ребалансировке надо вставлять... Это особый случай и нам надо проверять, к какому потомку мы посылаем элемент, если элемент на границе диапазона - к тому, у которого это будет "левое" значение или правое). Мы на эти вопросы всё равно смотрим, потому что двигаем min/max у элемента. У кого count меньше, того и элемент.

(возвращаемся к ребалансировке "лишнего" значения с нижнего слоя 'leaf'ов').

Итак, мы знаем с какой стороны удаляем лишнее значение. Мы его удаляем (размер становится B), после чего мы возвращаемся на уровень выше и вставляем значение в элемент с соотв стороны.

Это может вызвать ребалансировку в следующий элемент. Можно представить себе крайне неприятную ситуацию, при которой мы проходим все N/B-1 элементы, то есть получаем ребалансировку за o(n). Плохо-плохо.

А как мы к такой беде пришли? Потому что в старом коде с k=sqrt(n) нужно было не более чем 2*k операций на Dequeue, чтобы ребалансировать всё. Почему так? Потому что при ребалансировке у меня 2 операции на "псевдолиф" (pop_front/push_back).

А в VTree у меня мало того, что на каждый leaf B операций на вставку, то ещё и надо потенциально пройтись по всем значенниям. И переходов o(n). А было o(sqrt(n)), потому что я променял sqrt n на B, когда делал размер leaf'а снизу. Почему я это сделал? Чтобы сделать вставку дешевле. у старого кода вставка была дорогой o(k), и ребалансировка тоже дорогой. o(k). Получалось, что две условно дорогие операции дешевле, чем, казалось бы, быстрая вставка за o(log(n)), но очень дорогая ребалансировка за n.

Мы так не договаривались.

Окей, шаг назад. У нас есть sqrt(n). Там есть Vec>. Если мы сделаем Vec

( Error: Irreparable invalid markup in entry. Raw contents behind the cut. )

Я почти-почти-почти решил задачу, но... У BinaryHeap нет remove. pop убирает только самый большой элемент.

Практически, эпик фейл. Теоретически, BST решает проблему, но в стандартной библиотке нет BST, а есть только "просто дерево" (и BTree).

Я пока не готов коммититься на написание дерева (кроме того, я знаю, что растовая реализация BTree на много голов выше любой моей наивной реализации).

Видимо, я пока признаю своё поражение, и использую внешний крейт с binary_search_tree.

(обидно, потому что first/last для BTreeMap/Set уже стабилизировано, но ещё не зарелижено. Увы).

UPD: его стабилизируют в 1.66, 1.65 выходит послезавтра, а сколько ждать до 1.66 - даже не известно. Увы, binary_search_tree.

UPD2: на leetcode нет крейта binary_search_tree. Либо писать своё дерево (конкретно binary search tree), либо писать всю структуру с нуля.

Мой хак состоял в том, чтобы переопределить Ord таким образом, чтобы точка была равна range в который она попадает. Это позволяло извлекать range по точке из range'а. Если писать свою структуру, хак тут не нужен.

Пока что сохраняю для истории версию с (unstable) BTreeSet.first(): https://gist.github.com/amarao/9126e51f9587186fc95a79e3339bf884

и пойду ваять дерево. Совершенно отдельная дисциплина.

Некоторые задачи на leetcode доставляют трушное настоящее удовольствие.

https://leetcode.com/problems/break-a-palindrome/

Given a palindromic string of lowercase English letters palindrome, replace exactly one character with any lowercase English letter so that the resulting string is not a palindrome and that it is the lexicographically smallest one possible.

Return the resulting string. If there is no way to replace a character to make it not a palindrome, return an empty string.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, a has a character strictly smaller than the corresponding character in b. For example, "abcc" is lexicographically smaller than "abcd" because the first position they differ is at the fourth character, and 'c' is smaller than 'd'.

тесткейсы:

"" => ""
"a" => ""
"aa" => "ab"
"zz" => "az"
"aba" => "abb" (самый сложный случай, на котором я сначала попался).

Я получил реальное неиллюзорное удовольствие от языка и от задачи. Я не уверен, что на питоне у меня бы получилось компактнее и выразительнее

    pub fn break_palindrome(palindrome: String) -> String {
        let mut bytes = palindrome.into_bytes();
        let len = bytes.len();
        if len < 2 {
            String::from("")
        } else {
            let mid = len / 2;
            let odd = (len % 2) == 1;
            let last = len - 1;
            for (idx, c) in bytes.iter_mut().enumerate() {
                match c {
                    b'a' if idx == last => *c = b'b',
                    b'a' => {}
                    _ if odd && idx == mid => {} // mid char, can't change
                    _ => {
                        *c = b'a';
                        break;
                    }
                }
            }
            String::from_utf8(bytes).unwrap()
        }
    }

Усилиями r/rust с Реддита (note: реддит живее, чем SO, причём не только в программировании) проблема quick fail была решена, причём идиоматически. Исчезли две аллокации (из четырёх), и как мне кажется, алгоритмически его быстрее уже не сделать. (Да, я понимаю про идею использовать буквы из шаблона как индексы, но на практике это потребует аллокации вектора букв, и врят ли будет лучше).

Задача: https://leetcode.com/problems/word-pattern/submissions/

В двух словах: дана строка из букв и из слов, надо ответить, эквивалентны ли они друг другу в режиме "шаблона" : "aab" эвивалентна "dog dog cat", "abca" эвивалентна "foo bar baz foo".

(предыдущее обсуждение и текст полный задачи: https://amarao.dreamwidth.org/45539.html)

К предыдущему решению претензия была в отсутствии quick fail, то есть если с самого начала строки различаются, старый алгоритм продолжал "варить" до упора. (aaaaaaaaaaa и "foo bar bar bar bar bar"). Плюс, две аллокации для output.

r/rust был более чем любезен указать на две важные детали:

1. Можно возвращать итераторы вместо векторов.
2. Итераторы лего сравнить.

Кроме того, можно требовать не Iterator, а IntoIterator, так что можно передать любой "итрабельный" объект без вызова его iter(), хотя в конкретном этом случае это не работает, потому что итераторы у строки и шаблона разные и странные (split_whitespace и chars).

Получившийся код для меня находится чуть выше моего свободного понимания Rust: я его могу прочитать, но второй такой же не напишу (или уже напишу после этой истории?):

use std::hash::Hash;
use std::collections::HashMap;

impl Solution {
    fn abstract_iterator(input: impl IntoIterator<Item = impl Hash + Eq>) -> impl Iterator<Item = usize> 
    {
        let mut dict = HashMap::new();
        input
            .into_iter()
            .map(move |elem| {
                let id = dict.len();
                *dict.entry(elem).or_insert(id)
        })
    }

    pub fn word_pattern(pattern: String, s: String) -> bool {
        Self::abstract_iterator(pattern.chars()).eq(
            Self::abstract_iterator(s.split_whitespace())
        )
    }
}

Глядя на этот код, мне немного не нравится word_pattern своей некрасивостью.

Наверное, лучше было бы написать свой трейт, чтобы функция стала такой:

        pattern
            .chars()
            .abstract_iterator()
            .eq(
               s
                .split_whitespace()
                .abstract_iterator()
             )

Но в целом - это огонь. Это совсем не похоже на "низкоуровневый язык,
соревнующийся С++ за системность и поглядывающий на лавры С".

Один из нескольких разов, когда rust взрывает мозг и офигенен.

Задача:

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true

Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

Constraints:

1 <= pattern.length <= 300
pattern contains only lower-case English letters.
1 <= s.length <= 3000
s contains only lowercase English letters and spaces ' '.
s does not contain any leading or trailing spaces.
All the words in s are separated by a single space.

Решение:

impl Solution {
    fn abstract_list<T, G>(input: T) -> Vec<usize>
    where
        T: Iterator<Item = G>,
        G: std::hash::Hash + std::cmp::Eq,
    {
        let mut dict = HashMap::new();
        let mut output = Vec::new();
        for elem in input {
            let id = dict.len();
            output.push(*dict.entry(elem).or_insert(id));
        }
        output
    }
    pub fn word_pattern(pattern: String, s: String) -> bool {
        Self::abstract_list(pattern.chars()) == Self::abstract_list(s.split_whitespace())
    }
}

Я чертовски горжусь abstract_list. Это функция, которую я осмысленно написал
generic'ом, причём с generic'ом для Item.

Я, конечно, подозреваю, что дело в удаче (на таких скоростях как Rust, обычно загрузка ноды больше влияет, чем алгоритм), но всё равно приятно.

Задача: https://leetcode.com/problems/number-of-islands/

Profile

amarao

August 2025

S	M	T	W	T	F	S
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

Syndicate

Style Credit

Style: Pink Panther for Lefty by sarken

Expand Cut Tags

No cut tags

Page generated Aug. 7th, 2025 11:39 pm

Entries tagged with leetcode

Navigation

magical match

list inversion

tree traversal

add two numbers

обходы дерева

Древесные истории

Rust hard task sqrt(n)

hard-Rust'овое

I f.. love it

The программирование, часть вторая

The программирование

leetcode рекорд?