全站内容
Calf
这里收录 Calf 在 GoCalf 上的文章、笔记与其他内容。
求二叉树中两结点的最小公共祖先
据说这是微软的一道面试题，谁知道呢。问题描述：找出二叉树上任意两个指定结点的最近共同父结点（LCA，Least Common Ancestor）。
求内积最大的子数组
问题描述：有两个长度均为 n 的整数数组 A 和 B，现在要从这两个数组中各抽出 s 个数字，分别构成两个新的数组 C 和 D，要求数组 C 和 D 的内积最大。
让 11、12、13、14 通过加减乘除运算得到 46
前两天同事的朋友给出了一个怪怪的题目，说是考验我们的智商，结果最后让我们大跌眼镜。题目很简单：怎样让四个不同的数 11、12、13 和 14，通过简单的数学运算得到 46，可以使用加减乘除和括号。同时还给了一条重要提示：不能按照正常的思路思考。
任务调度问题：资源占用与释放
问题描述：有 n 个任务，第 i 个任务运行时需要使用 R[i] 的资源，运行完毕后需要占用 O[i] 的资源（O[i] <= R[i]），假设现在我们总共有 s 的资源，要求设计一个调度算法，能保证所有任务能顺利执行；如果无法执行完，需要说明理由。
时针，分针，相对运动
某人 6 点多从家出发，出门时时针和分针是 110 度角，7 点前回到家，时针和分针还是 110 度角。问这人出门多久？本文以这个简单的问题入手，介绍了利用相对运动解决时针、分针相关问题的方法。
数据仓库分层建模和规范
#仓库分层 =1.1 STG 缓冲层 Staging 将业务数据同步过来，不做任何转换，与业务数据库同构。 主要用于因为特殊原因，无法在 ODS 一步完成业务数据快照的场景。如每天按照 update_time 把 T 日更新的记录同步到 STG 层，但 STG 表中会有重复的记录，无法方便地直接使用，需要做一次去重后写入 ODS 层。 =1.2 ODS 存储层（操作性数据） Operational Data Store 将业务数据快照过来，不做任何转换，与业务数据库同构。 …
水木社区、小百合、饮水思源、日月光华十大博客
gdh 同学利用 Google Blogspot 和 Google Picasa 制作了四个博客，分别收集了清华水木社区、南大小百合、上海交通大学饮水思源和复旦大学日月光华的全站十大，不但保留了文章全文，还存储了图片，几乎是与这几个 BBS 同步更新的，非常方便。欢迎参观，猛烈点击小广告。
算法的复杂度与 Master 定理
平时设计或者阅读一个算法的时候，必然会提到算法的复杂度（包括时间复杂度和空间复杂度）。比如我们说一个二分查找算法的平均时间复杂度为 O(log n)，快速排序可能是 O(n log n)。那这里的 O 是什么意思？这样的表达是否准确呢？今天来复习一下与算法复杂度相关的知识：函数渐进阶；记号 O、Ω、θ和 o；Master 定理。