稳定婚姻问题 Stable Marriage Problem定义 两个集合men、women数量相等，每个人持有对异性的好感度顺序表。现在假定要对这n对进行匹配，如果某种匹配存在同时满足以下三个条件的m-w对(blocking-pair)，则认为此匹配是不稳定的：1)m和w目前没有订婚（意味着它们的订婚对象是别人） 2) 在m的优先级列表中，w的级别比当前订婚对象高 3) 在w的优先级列表中，m的优先级比当前订婚对象优先级高。 反之则称这个匹配是稳定的。在这样一个场景中求解稳定订婚关系的问题，称之为稳定婚姻问题 常见变种 SMI:(SM with Incomplete lists) SMT:(SM with Ties) 按照稳定条件依次减弱 super-stability strong stability weak stability: 总是存在解，并能在多项式时间内解决 SMTI(SM with Ties and Incomplete lists) 三种稳定关系定义，同上 super/strong关系，存在算法可以确定一个问题是否有解，以及求出一个解，super stability时间复杂度O(a), strong stabilityO(na)， a表示所有优先级列表的整体长度（2n^2如果所有优先级列表都是完整的），且所有的解都具有相同的大小 weak stablity，任何情况下都存在一个稳定匹配，并且可以在O(a)时间内找到，但是解的大小可以有多个，求解其中最大的那个是NP-Hard的 经典解法 Gale-Shapley Algorithm algorithm stable_matching is Initialize all m ∈ M and w ∈ W to free while ∃ free man m who still has a woman w to propose to do w := first woman on m's list to whom m has not yet proposed if w is free then (m, w) become engaged else some pair (m', w) already exists if w prefers m to m' then m' becomes free (m, w) become engaged else (m', w) remain engaged end if end if repeat 按轮次进行 ...

Concept A partial reference of a contiguous sequence of elements in a collection. contiguous a data type that does not have ownership Usage String Slices let s = String::from("hello world"); let hello = &s[0..5]; let world = &s[6..11]; Like others languages, we can simpify the syntax if we want to start at the first index(zero) or include the last byte of String #![allow(unused)] fn main() { let s = String::from("hello"); let slice = &s[0..2]; let slice = &s[..2]; } #![allow(unused)] fn main() { let s = String::from("hello"); let len = s.len(); let slice = &s[3..len]; let slice = &s[3..]; } #![allow(unused)] fn main() { let s = String::from("hello"); let len = s.len(); let slice = &s[0..len]; let slice = &s[..]; } Attention String slice range indices must occur at valid UTF-8 character boundaries. String literals are slices Using string slices as parameters usually make our API more general and useful without losing any functionality.

References Something like &String, the concept is similar to a Pointer in C/C++/Golang/… It will not take the ownership, thus we can drop some tuple code to make it simpler. Borrowing having references as function parameters Scope A reference’s scope starts from where it is introduced and continues through the last time that reference is used. let mut s = String::from("hello"); let r1 = &s; // no problem let r2 = &s; // no problem println!("{} and {}", r1, r2); // r1 and r2 are no longer used after this point let r3 = &mut s; // no problem println!("{}", r3); Recapitulation At any given time, you can have either one mutable or any number of immutable references. References must always be valid. (Dangling references will not be allowed in Rust by compiler)

什么是Ownership Ownership是Rust中的一个核心特点，可以理解成是Rust做到内存安全的重要手段。不同于带GC的语言或是C/C++这样显式管理内存的语言，ownership系统实现了在编译期管理内存(但又不需要程序员过分手动介入)从而避免了GC开销。 硬要说的话个人感觉像是C++中的RAII，但是由于带有编译器级别的检查，比C++更不容易出错。 Ownership的规则 Rust中所有的值(value)都有一个作为所有者(owner)的变量(variable) (一个值)同时只能有一个owner(参考Rust中赋值的Move语义和在内存管理中起到的作用) 当owner离开作用域(scope)时，其对应的值(value)就会被释放(dropped)(无论是堆上还是栈上的) 解释 Variable Scope 和其他语言类似，变量离开作用域后，就失效了。当一个变量离开作用域时，Rust会自动调用drop 函数，释放内存 Heap and Stack 和C/C++一样，Rust的内存管理也分为堆和栈，栈上内存由操作系统自动管理，堆上内存需要程序员手动管理（Rust中通过Ownership规则和编译器自动插入释放内存的语句，避免像C/C++那样的显式管理） Move Rust中的简单赋值=大多类似于其他语言中的浅拷贝，仅拷贝栈上内容。在Rust中，这种变量和数据交互(interact)的方式称为Move。当发生Move(我理解为“实际”所有权的转移)后，原变量在离开作用域后，编译器不会插入drop，从而避免内存的重复释放 这里还引出Rust的另一个设计思想：Rust永远不会“自动”(automatically)去“深拷贝”数据。因此，默认赋值行为的运行时代价都可以认为是比较低的 String结构示例 let s1 = String::from("hello") let s2 = s1 Clone 那么如果我们真的需要深拷贝一块数据需要怎么做呢，在Rust中需要显式调用clone。这实际上也是显式提醒程序员，这里有一段特殊的代码要执行，有可能消耗会比较大 fn main() { let s1 = String::from("hello"); let s2 = s1.clone(); println!("s1 = {}, s2 = {}", s1, s2); } Another wrinkle: Stack-Only Data 一些简单数据类型，像整型，我们不调用clone，也不是Move语义，原因在于，这些简单类型在编译期就能确定大小，并且完全存储于栈上，所以拷贝比较快。 Rust中有一种特殊的注解(annotation) Copytrait, 实现了这个trait类型的变量在赋值后依然可以使用。但如果实现了Droptrait，Copy就无法使用 什么样的类型可以实现Copytrait呢？可以参考官方文档，通常来说，没有需要分配资源的类型可以实现。以下是一些实现了Copy的类型 所有整型，如u32 Boolean类型,bool 浮点型, 如f64 字符类型，char 元组(Tuples)，当然只能包含同样实现Copy的类型，如(i32, i32)实现了，但(i32, String)没有 Functions 函数中传参和返回值也一样有ownership的转移问题，传参即赋值，返回值会将ownship move到调用它的函数 ...

树堆的基本概念 树堆（Treap）是二叉排序树（Binary Sort Tree）与堆（Heap）结合产生的一种拥有堆性质的二叉排序树。 但是这里要注意两点，第一点是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap并不一定是；第二点是Treap并不严格满足平衡二叉排序树（AVL树）的要求，即树堆中每个节点的左右子树高度之差的绝对值可能会超过1，只是近似满足平衡二叉排序树的性质。 Treap每个节点记录两个数据，一个是键值，一个是随机附加的优先级，Treap在以关键码构成二叉排序树的同时，又以结点优先级形成最大堆和最小堆。所以Treap必须满足这两个性质，一是二叉排序树的性质，二是堆的性质。如下图，即为一个树堆。 关键步骤 查找 按照正常BST的查找过程即可 插入 给新节点一个随机的权重值，按照普通二叉搜索树，使用key进行插入 为了保证堆的特性，插入完成后要进行旋转操作，保证仍为最大堆或最小堆。以最大堆为例，若插入到右子树，且权重比父结点大，就要实现一次左旋转，使右子树根结点成为新的父节点；反之左旋，直到满足堆的特性为止 删除 按照正常的查找流程找到待删除节点后，有三种情况 待删除结点本身就是叶子结点，直接删除即可 待删除结点只有一个孩子（一棵子树），用这个孩子替换待删除结点，实现删除效果 待删除结点两棵子树均不为空时，先进行旋转。以最大堆为例，找到权重更大的孩子，向相反方向旋转（即若左孩子权重更大，执行右旋），直到待删除结点满足上面两种情况之一，再进行删除 具体实现 参考LeetCode(cn) 第1438题的实现，其中对于旋转的优雅实现值得一学 import "math/rand" type node struct { ch [2]*node priority int key int cnt int } func (o *node) cmp(b int) int { switch { case b < o.key: return 0 case b > o.key: return 1 default: return -1 } } func (o *node) rotate(d int) *node { x := o.ch[d^1] o.ch[d^1] = x.ch[d] x.ch[d] = o return x } type treap struct { root *node } func (t *treap) ins(o *node, key int) *node { if o == nil { return &node{priority: rand.Int(), key: key, cnt: 1} } if d := o.cmp(key); d >= 0 { o.ch[d] = t.ins(o.ch[d], key) if o.ch[d].priority > o.priority { o = o.rotate(d ^ 1) } } else { o.cnt++ } return o } func (t *treap) del(o *node, key int) *node { if o == nil { return nil } if d := o.cmp(key); d >= 0 { o.ch[d] = t.del(o.ch[d], key) } else { if o.cnt > 1 { o.cnt-- } else { if o.ch[1] == nil { return o.ch[0] } if o.ch[0] == nil { return o.ch[1] } d = 0 if o.ch[0].priority > o.ch[1].priority { d = 1 } o = o.rotate(d) o.ch[d] = t.del(o.ch[d], key) } } return o } func (t *treap) insert(key int) { t.root = t.ins(t.root, key) } func (t *treap) delete(key int) { t.root = t.del(t.root, key) } func (t *treap) min() (min *node) { for o := t.root; o != nil; o = o.ch[0] { min = o } return } func (t *treap) max() (max *node) { for o := t.root; o != nil; o = o.ch[1] { max = o } return } func longestSubarray(nums []int, limit int) (ans int) { t := &treap{} left := 0 for right, v := range nums { t.insert(v) for t.max().key-t.min().key > limit { t.delete(nums[left]) left++ } ans = max(ans, right-left+1) } return } func max(a, b int) int { if a > b { return a } return b } 参考 树堆（Treap）图文详解与实现 leecode-cn 1438