总结一下用python撸codejam时常用的一些库, 并且给一些简单的例子. 发现用python撸codejam非常合适: codejam的时间要求不严格(4/8分钟), 而且程序只要本地运行. 正好可以使用python简洁的语法和丰富的函数库.
py自带的一些好用的数据结构...
https://docs.python.org/2/library/collections.html
from collections import Counter, deque, defaultdict
主要是用来穷举的时候它里面一些函数很好用...
https://docs.python.org/2/library/itertools.html
>>> from itertools import product, combinations
>>> a = 'ABCD'; b='EFG'
>>> for p in product(a,b):
print ...昨天做的一道codejam题目, 这个题目的三种解法都非常有代表性, 特此一记.
题目链接在这里:
https://code.google.com/codejam/contest/8234486/dashboard#s=p2
Elliot's parents speak French and English to him at home. He has heard a lot of words, but it isn't always clear to him which word comes from which language! Elliot knows one sentence ...
recall model of computation: DFA
a univeral model of computation: turing machine
→ no more powerful model of computation.
Turing machine can compute any function that can be computed by a physically harnessable process of the natural world.
bottom line: turing machine is a simple and universal ...
simplex algo: top 10 algo of the 20th century (ever?).
what is linear programming:
a general problem-solving model that works for:
shortest-path, maxflow, MST, matching, assignment, ...
toy example: choose products to maximize profit.
...
feasible region: a convex polygon.
⇒ optimum solution appears at an extreme point.
standard ...
Goal: classify problems according to computational requirements.
bad new: for huge number of pbs we don't know...
shifing gears:
suppose we could (not) solve pb X ...
pb: reduce the size of a file, to save space/time for storing/transmitting.
applications: generic file compression(gzip), multimedia (mp3), communication(skype).
From binary data B, ⇒ generate a compressed representation C(B).
lossless compression: get exactly B from C(B)
compression ratio: |C(B ...
pb: pattern matching.
Is a notation to specify a set of strings.
basic operations:
additional operations (added for convinence):
ex. [A-C]+ is equivalent to (A|B|C)(A|B|C)*.
吐槽名句:
今天简单介绍一下优先队列(priority queue, 以下简称PQ)这个数据结构的实现.
PQ又叫"堆"(heap), 但是可能优先队列这个名字更容易记忆它的用途: pq是一种队列, 不过不是先进先出(FIFO), 而是每次出队的元素永远是优先级最高的.
个人感觉"堆"这个名字大概源于PQ的(逻辑上的)形状吧: PQ是一种树(tree), 准确的说, 是一种二叉树(binary tree), 说得再准确一点, 它是一种完全二叉树(complete binary tree): 没错, PQ是一种满足某些条件的完全二叉树.
所谓的"完全二叉树", 要满足:
- 除了最后一层, 所有层都排满(没有非空节点)
- 最后一层的所有非空节点都排在左边
一张图可以直观说明, 完全二叉树其实就是长得像这样:
一个完全二叉树能被成为PQ的话, 要满足的条件就是:
对于任何一个节点, 它的优先级都大于左右子节点的优先级.
比如下图 ...
"most ingenious algorithm we've seen so far"
pb. having two strings, pattern and text, len(pattern)=M << len(text)=N, try to find pattern in text.
ex. indexOf method of String in java.
function signature:
public static int search(String ...
今天总结一下非常有用的快速排序(qsort)算法, 以及由此衍生的一些其他相关算法(Knuth shuffle, quick select, 3-way partition).
快速排序的算法可以用三句话描述:
[Algo]
- 选择基准项(pivot element, 一般取第一个元素为pivot)
- 把数组里所有小于pivot的移动到pivot左边, 大于pivot的移动到右边 ⇒ 此时pivot已经位于最终排序时的正确位置
- 对pivot左右两个数组分别递归进行快速排序
由以上描述可见, qsort是一个递归算法, 我们可以把它的函数声明写成: void qsort(int[] a, int lo, int hi), 表示排序a[lo, hi]之间(闭区间)的所有元素.
由上面描述可以见, qsort最关键的是第二步: 把数组元素以pivot分为两部分. 这个操作就是quick partition.
函数声明为: int partition(int[] a, int ...