帮王老师找了几个题用于研一同学的算法课课堂测试,题目是辛辛苦苦选出来的...原则是尽量全面,简单。提前开了个VJudge (password: ssdut) 和自动发布的Blog(也就是这一篇...),尽量让工作流自动起来,下面是题解和总结

A题,hiho 1103。考察栈的使用,和括号匹配并无二致。细节是,1. 空格, 2. 非<>内的内容可能是代表颜色的词语。可能很多人会忽略第二种情况,出题人都忽略了...所以,纵然通过这题的同学也要思考下自己的代码是否真的没有问题。使用python,可以方便地进行字符替换和切片,并用list来模拟栈。

B题,hiho 1405。考察对堆和树的遍历的理解,先全局最小找树根,然后划分成左右子树变成子问题...写代码的时候会考察分治和递归的思想。题目的表述其实是有瑕疵的,应该想要表达满足堆的性质(即任意节点小于左右子树),却说成了是一个堆(不符合完全二叉树)。使用python,可以体会函数式编程的精髓。

C题,hiho 1086。LRU Cache,数据量是N = 20000M = 5000,标准实现是hashtable + linkedlist,理论下(均摊分析)每次操作花费O(1)。也可以用BST来做,理论上每次操作花费O(logM),搜索树平衡的时候运行性能是很好的。时间考虑到时间10s,最坏也可以使用每次代价为O(M)的链表或数组来做。因而,可能考察到的点有,散列表、链表、二叉搜索树。使用python,可以用有序字典方便地实现解法2.

比赛时通过的提交记录在这里,需要的同学自取。另:王老师让学python是有道理的,这些python代码是一路百度很短时间内写出来的,能用很简洁的语句实现逻辑。除了熟练使用,也应关注这些数据结构底层的实现和原理,嗯,就酱。