《数据结构与算法》编程练习

2016年11月21日1,1406

数据结构与算法(上)

百练2746:约瑟夫问题

 vector模拟操作

多项式加法

百练2980:大整数乘法

百练2702:密码翻译

百练4077:出栈序列统计

卡特兰数

POJ1686.等价表达式(Lazy Math Instructor)

给每个字母一个随机值,对两个式子做表达式计算

用一个数字栈+操作栈来实现

从左往右,将扫到的数字入数字栈,将扫到的操作与操作栈的栈顶对比优先级

如果当前操作优先级高,将其入栈

否则从数字栈中取出两个数字,用栈顶的操作进行运算

优先级次序是右括号和栈内左括号,运算符,未入栈的左括号

百练2121:英语数字转换器

百练1035:拼写检查

poj1961.前缀中的周期(Period)

kmp求出fail数组后,前i个的重复子串就是i-fail(i)

由中根序列和后根序列重建二叉树

后根序列的最后一个元素是树根,在中根序列中找出这个根,划分左右子树递归

实现堆结构

二叉堆模板

百练4080:Huffman编码树

用小根堆实现哈夫曼树

百练4079:二叉搜索树

表达式•表达式树•表达式求值

 

森林的带度数层次序列存储

从左往右扫过带度数层次序列,一个度数为x的结点决定之后x个连续结点的父亲

poj1182:食物链(food chain)

带权并查集

百练4083:我爱北大

floyd求最短路,同时记录最短路上的最后一个结点

百练4084:拓扑排序

用小根堆来实现字典序最小的拓扑序

poj2049:Finding Nemo

建图后01-bfs,由0的边扩展的点放在队首,1的边扩展的点放在队尾

数据结构与算法(下)

距离排序

数据筛选

快速选择函数

数组取数

对每个数\(a_i\),二分查询\(a_i-T\),注意\(T=0\)的情况