复习任务
快排：
看一遍 qsort
void myQsort(int s[], int lo, int hi){ //s[lo, hi]
if(lo >= hi) return;
int i = lo, j = hi, key;
swap(s[lo], s[rand() % (hi - lo + 1) + lo]);
key = s[lo];
while(i < j){
while(i < j && s[j] > key){
j --;
}
if(i < j){
s[i ++] = s[j];
}
while(i < j && s[i] < key){
i ++;
}
if(i < j){
s[j --] = s[i];
}
}
s[i] = key;
myQsort(s, lo, i - 1);
myQsort(s, i + 1, hi);
}
int main(){
int s[100], len = 100;
for(int i = 0; i < 100; i ++){
s[i] = rand() % 500;
}
myQsort(s, 0, len - 1);
for(int i = 0; i < len; i ++){
printf("%d ", s[i]);
}
return 0;
}
树：
看AVL树那道题，
- 基本建法
- 左旋/右旋操作
- 四种遍历，递归+迭代版 ##
- 删除有空看一下 ##
图：
- 看一两道做过的 dfs, bfs
- dijkstra, floyd，细节
哈希：
- 看MAP那道题，复习MAP的使用
- quadratic probing 那道题
库函数：
记几个常用函数的签名(memset, memcpy, qsort, strcat）；
动规：
看背包问题帖子+做过的动规题
坑：
看最近日记刷过的题；
刷题
1065. A+B and C 多种方法 溢出
给的是 A, B and C in [-263, 263]，做加减 a + b - c，问符号。可能有溢出。还有人用 long double 给过了的，服气，但我猜是因为给的数都太大了，尾数没存上也不影响正负吧。
很多奇葩方法都出来了，我用的是把数字分成两段，这样 long long 就绰绰有余了，分别做加减，最后再判断（这里有坑）。
1064 满二叉树 遍历
给了一串值，要求输出满二叉树的层次遍历。那岂不是。。。只要数组顺序输出就行了？
"妈妈我再也不要写树啦！" 贼爽。
# include <cstdio>
# include <cstdlib>
# define p(x) ((x - 1) / 2)
# define lc(x) (x * 2 + 1)
# define rc(x) (x * 2 + 2)
int inOrder[1010];
int tree[1010]; //树根为0
int N;
int j = 0;
int compar(const void *a, const void *b) { return *(int*)a - *(int*)b; }
void travIn(int pos) {
if (lc(pos) < N) travIn(lc(pos));
tree[pos] = inOrder[j++];
if (rc(pos) < N) travIn(rc(pos));
}
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", inOrder + i);
}
qsort(inOrder, N, sizeof(int), compar);
travIn(0);
printf("%d", tree[0]);
for (int i = 1; i < N; i++) {
printf(" %d", tree[i]);
}
return 0;
}
1101 简单
对于一串经过 partition 操作之后的序列，找到哪些是可能的 pivot。只要别一个一个找（O(N^2)），就行了。我是遍历了两遍，存下每个数左边的最大值和右边的最小值，然后对比就可以了。。
死在了当没有一个解的时候，输出的格式上。。。有一个case不是格式错误就是输出错误。第二行不输出也不对，输出0也不对，只有第一行也不对，第二行输出一个空格也不对。最后看帖子，哇塞，第二行也是要换行的。。。尼玛我其它case里都没有换行也没说格式错误哇，怎么这里就。。。好迷。。。
1102 Invert a Binary Tree 二叉树 遍历
给了一棵二叉树，以每个节点的左右孩子的形式。求反转的树的层次遍历和中序遍历。太简单不说了。
1103 搜索？
找N = a1 ^ P + a2 ^ P+ ... + ak ^ P。给定了 N, K, P，就是找这个序列 a。但是还要找 a[n]之和最小的，这里面又要找序列字典顺序最大的。
刚开始用了 dp，不是很会写，用了两张表，bug 很多。被人带坏用了 dfs，刚开始一直有小 bug，最后还有个 case超时。我试了一下，这个例子就超时得不要不要的，估计要给它几分钟才行吧。。。
参考一个同学的写法（http://blog.csdn.net/ccDLlyy/article/details/60138173），发现他跟我写的基本差不多，但是我写了很多繁琐的剪枝条件，他则只是不对劲就 return，试了一下，秒出！我觉得自己脑子有坑吧！为什么写这么多剪枝还这么慢！可能是计算反而太复杂了。。。
