洛谷P2803:带权中位数的思考

带权中位数是CSP(NOIP)的一个常见问题。利用动态规划的方法寻找最佳落址。其中模板为邮局选址问题(_post-office location problem_)。这类问题有各种各样的衍生。这里我们讨论一道简单的变形:洛谷2803,小学生与小学选址。

阅读更多

LeetCode - 二分查找

“90%的程序员不能写出正确的二分查找” – 不是我说的

二分查找及其变种有很多种形式,例如查找第一个出现的、查找出现的区间,等。但都不能脱离一个宗旨:每次查找都要有下标的更迭。

阅读更多

LeetCode T17 - Phone Number

刷LeetCode的时候发现一个道理。用go语言写:“哇塞,我挺厉害的嘛”;用c++写:“哇靠,垃圾程序的典范!😭”

第17题是一个典型选择问题,要求从给定的数字中选择几个需要的字母。解法存在优化,但基本上就是DFS。leetcode 17 题的一个解法如下。

阅读更多

LeetCode T15 - 3Sum

LeetCode T 15: 3Sum是一个比较普通的问题,考验一定的思维和编程能力。

描述:给定一个长为$n$的数组nums,请问数组中是否包含三个元素a, b, c, 使得 a + b + c = 0? 找到数组中所有这类元素的三元组。

阅读更多

CLRS滑稽导论 (1) : AVL树

  在二叉树的学习中,我们会接触到很多不同的树。其中,用得最为普遍的,是二叉搜索树。而为提升二叉树搜索的效率,又引入自平衡二叉树的概念。自平衡二叉搜索树是指通过处理可以实现子树相对平衡,即不极端地偏向一边的二叉搜索树。由于相对平衡的特性,树可以实现查询、插入、删除操作在时间上的优化。

阅读更多

Red Black Tree (Draft)

本文处于草稿中。。。

  1. 定义:红黑树利用特征标记决定高度的自平衡二叉搜索树,具有额外的数据决定其节点为黑或红节点。每一条从单一节点到叶子结点的路径都有相同数目的黑色节点。利用此特性,保持树高为$O(lg\ n)$。

    pre:平衡树:空树或其左右两个子树高度差相对小的二叉搜索树。

    正确性特性:

    1. 节点是红色或黑色。
    2. 根是黑色。
    3. 所有叶子都是黑色(叶子是NIL节点)。
    4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
    5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×