总结一下用python撸codejam时常用的一些库, 并且给一些简单的例子. 发现用python撸codejam非常合适: codejam的时间要求不严格(4/8分钟), 而且程序只要本地运行. 正好可以使用python简洁的语法和丰富的函数库.
collections
py自带的一些好用的数据结构...
https://docs.python.org/2/library/collections.html …
昨天做的一道codejam题目, 这个题目的三种解法都非常有代表性, 特此一记.
题目链接在这里:
https://code.google.com/codejam/contest/8234486/dashboard#s=p2
Elliot's parents speak French and English …
1. Introduction to Intractability
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, ...
1. Brewer-'s Problem
toy example: choose products to maximize profit.
...
feasible region: a convex polygon.
⇒ optimum solution appears at an extreme point.
standard form …
Goal: classify problems according to computational requirements.
bad new: for huge number of pbs we don't know...
1. Introduction to Reductions
shifing gears:
- from individual problems to problem-solving models.
- from linear/quard to polynomial/exponential pbs
- from implementation details to conceptual framwork
suppose we could (not) solve pb X efficiently …
1. Introduction to Data Compression
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 …
1. Regular Expressions
pb: pattern matching.
regular expression
Is a notation to specify a set of strings.
basic operations:
- concatenation
- or
- closure: "0 or more appearances of chars"
- parentheses
additional operations (added for convinence):
ex. [A-C]+ is equivalent to (A|B|C)(A|B|C)*.
吐槽名句:
2 …
今天简单介绍一下优先队列(priority queue, 以下简称PQ)这个数据结构的实现.
PQ又叫"堆"(heap), 但是可能优先队列这个名字更容易记忆它的 …
1. Introduction to substring search
"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.
2. Brute-Force Substring Search
function signature:
public static int search(String pat …
今天总结一下非常有用的快速排序(qsort)算法, 以及由此衍生的一些其他相关算法(Knuth shuffle, quick select, 3-way partition).
快速排序的算法可以用三 …