liuxinyu95
- 浏览: 30990 次
- 性别:
- 来自: 北京
-
最新评论
-
liuxinyu95：
中文版已经完成：https://github.com/liux ...
初等算法 -
liuxinyu95：
补充一下Extended Euclidean algorith ...
POJ 1061青蛙的约会题解 -
maakey：
[u]引用引用[img][url][/url][/img][/ ...
Natural merge sort -
liuxinyu95：
PDF放了一份在github:https://github.c ...
AVL tree，比红黑树更朴素 -
liuxinyu95：
公式2的merge部分有错误，已改正。x1=y1的时候，结果为 ...
为什么要学习算法和数据结构
文章列表
经过6年，我终于写完了《初等算法》一书。
这本书完全免费，可以从这里下载电子版：https://github.com/liuxinyu95/AlgoXY/releases/download/v0.618033/elementary-algorithms-zh-cn.pdf
Why
算法书籍汗牛充栋，《算法导论》，《计算机程序设计艺术》 ...
这一章包含如下内容：
- 扫描查找
- 分治查找
- 二维Saddleback search
- 字符串查找
-KMP
-BM
- 解的查找
DFS
BFS
Greedy
DP
详细内容见链接中的PDF
https://dl.dropboxusercontent.com/u/52705490/search-en.pdf
昨天讨论了一些Computing at school的内容。受到Richard Bird在
Pearls of functional algorithm design一书中Saddleback search一章的启示，我这里抛砖引玉，给出一个我心目中的中学计算机课的例子。
教师：
同学们，早上好。想必你们都吃过了营 ...
终于写完了这一章
本章全面地涉及了quick sort和merge sort的方方面面。同其他章节一样，即覆盖传统的imperative算法，也覆盖functional（函数式）算法。
首先展示的是著名的只有2行的Haskell快速排序算法。之后，针对Partition给出了一些小的改进。并且用两种方法严格证明了快速排序的平均性能。此后，我给出了各种著名的工程方法：2路partition, 3路parition (ternary quick sort)，3点中值法，随机快速排序等等，最后通过deforestation给出快速排序和树排序的关系。
为了解决快速排序的worst case问题， ...
POJ 1061青蛙的约会题解
网上似乎有不少此题的解法。我这个post和其他人的相比主要时想说下面几点。
1. 给出一个试图不死记硬背公式的思路;
2. 谈谈暴力解为什么看起来这么诱人，却无法通过;
3. 一些细节及对此题的评价（个人 ...
和插入排序一样，选择排序通常被认为是一种hello world式的排序。通常被用来作为例子向初学者讲解多层循环。它有着特别直观的结构，但是性能却是O(N^2)的。
在这一章中，我将向读者展示，选择排序也可以不断进化：既有简单的改进（诸如cock-tail排序），也有从本质上改进数据结构（使用tournament knock out和heap sort)，从而最终使得基于选择的排序方法也达到比较排序的上限: O(N lg N)
https://github.com/liuxinyu95/AlgoXY/blob/algoxy/preview/ssort-en.pdf?raw=true
相信一定有人问？我们有这么多经典优秀的算法书：
- TAOCP: Donald E. Knuth, The art of computer programming;
- CLRS: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. ``Introduction to Algorithms, Second Edition''
- Robert Sedgewick: 的Algorithms in XXX Language系列
甚至一些讲授计算机体系结构，以及编程的好书也有大量的算法介绍：
...
单向链表是几乎所有函数式编程语言的环境的基石。它的重要性，就如同数组对于imperative编程语言的重要性一样。（有读者可能会质疑：lambda才是函数式编程中最最基础的；作者认为lambda对于函数式编程，如同汇编语言对于imperative一样，是计算模型的基础表达方式。）
经过两个月的持续写作，关于单向链表的内容终于脱稿了。尽管List非常重要，但是作者并不打算把它作为AlgoXY一书的第一章，而是把它作为本书的第一个附录。第一章仍然是：“二叉树——数据结构中的Hello world”。
虽然是附录，但是作者仍然秉着非常严格的态度来写作，丝毫不敢放松。我们遵循CLRS(《算法导论》) ...
经过了14个月锱珠积累，这一章终于脱稿了。
这一章具有里程碑式的意义。这一章写好后，所有的基本数据结构，从易到难：
二叉树，红黑树，AVL树，Trie，Patricia, Suffix tree，B-tree，binary heap，Leftist Heap, Skew Heap, 二项式heap，斐波纳契Heap，队列，序列
就全部给出了函数式实现。
我们面前已经没有任何基本数据结构的阻碍，使得我们无法用纯函数式的基本算法解决问题了！
本章是基本数据结构的最后一章。讲述sequence。
在imperative语言中，通常不用担心random access。原生的数组就可以满足O(1)时 ...
通常我们见到的merge sort的思路是典型的分而治之divide and conquer策略：
1. 如果待排序序列为空，或者只有1个元素，结束
2. 否则，将序列一分为二，将两个子序列分别merge sort，再将两个排好的子序列merge
我们也可以从另外一个角度出发，序列中存在一些已经排好的片段，我们可以把这些排好的片段merge起来，不断重复直到序列排好（只含有一个排好的片段，亦即整个序列）
这种思路叫做natural merge sort。
例如下面的Haskell代码：
mergesort' = foldl merge [] . groupBy' (<=)
其中me ...
题目详情可以参考这里：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3
ZOJ上的判定标准是：
b不服，站出来质疑；
如果a能举证说：你瞧，存在一种合理的解释，a = a[1]*a[2]*…*a[n], b = b[1]*b[2]*…*b[m]; 其中 2<= a[i], b[j] <=100, 且 a[i] !=b[j] if i!=j
就判断a赢，否则b赢
但是，这里会有对b不利的冤案！例如b踩了气球4和8，于是b = 32 而 a吹牛说自己得了44分，
b不服，但是a狡猾的说，你看，a = 4*11 ...
经过近两年的时间，我终于写完了这一章。
正如我在Algoxy第一章描述的，Queue并非想象的那样简单。尤其是提供一个纯函数式的队列，并且满足常数时间的头部和尾部操作并不容易。
本章中，我们给出几种不同的队列的纯函数式实现。
当然，用常见的imperative语言实现队列很容易，尤其是使用双向链表。但是这是一个overkill的解法，我们先用单向链表实现一个头部尾部都是常数时间的队列；然后我们给出一个ring-buffer的实现；
接着我们给出一个简单的纯函数式解法：它能达到amortized常数时间，但是worst case表现一般，接着我们给出一个基于状态机的real time que ...
通常的数据结构和算法教科书介绍的堆，实际上是用数组隐式表达的二叉树堆（binary heap by implicit array），如果将概念扩展为多叉树或者森林，就会得到更多有趣的堆。本章介绍的3种堆，就是其中很有代表性的数据结构。
其中二项式堆把合并的速度提高到了O(lg N)的量级，如果把二项式堆的某些操作延迟进行，就得到了Fibonacci堆，Fibonacci堆的各项指标除了pop外，都达到了O(1)的量级，在理论上的意义特别重大。它使得诸多的图算法，如Dijkstra算法等得以高效实现。
遗憾的是Fibonacci Heap的实现有些复杂，时间常数比较大，理论意义大于实际意义。为 ...
AVL树发明于上世纪60年代，比红黑树早了近十年。
上一章里，我展示了用pattern matching实现的红黑树。本章我展示同样策略实现的AVL tree。相比于传统的基于旋转的解法，这一解法再次展示了简单一致的特点。
本章内容如下：
- 简单介绍；给出AVL树的高度与节点数的证明；
- 类比红黑树的思路；
- 解：
- pattern matching 的形式分析
- 子问题一： 如何更新平衡因子和增加的高度？
- 子问题二； 4个case中的平衡因子如何变化的推导和证明；
- Haskell实现
- 验证
- 删除算法作为习题留给读 ...
红黑树是非常popular的一种self-adjusted的平衡二叉排序树。
通常他给我们的印象是很复杂，有很多case，要小心的旋转。有人说，曾将在某公司的面试时，被要求实现红黑树。他觉得这很没有道理，几乎很少有人能在不参考教科书的情况下，记清楚那么多的case。
在这一章里，我将向你展示目前我所见过的最简洁的红黑树实现。简洁到什么程度呢？我打赌你看过后能轻松通过上面的面试——Wow, 红黑树原来可以这么简单！
这个实现，来自Chris Okasaki在卡耐基梅隆大学(CMU)的博士研究成果。他启发我用同样的方法简洁地实现了AVL tree和Splay tree。
这一章我们讲红黑树， ...