面试常见基础算法题总结
需积分: 23 136 浏览量
2020-04-29
13:50:18
上传
评论 1
收藏 124KB DOCX 举报
算法这一块太过庞大，几乎都有可能，牛油们最好还是去刷剑指 oer（level 1），leetcode（如果能
够刷到最高难度，算法对你来说已经不是什么了，或者说面试对你来说简直就是吃饭喝水的难度），左神
的书《程序源代码面试指南》（字符串，数组，dp，海量数据问题，搞定它们也就搞定面试的一半）。
下面还是简单的列举一些吧（包括一些数据结构题目，只列举简单的，面试的算法一半不会太难，但是现
在一般都是需要比较好的思维，或者曾经接触过这方面的题，建议就是多刷题，做题感觉是刷出来的）
（1） 红黑树 RBTREE 的了解（平衡树，二叉搜索树），使用场景
avl 用于搜索，插入删除次数少场景，用在 win 的内核中很多；
红黑：查找，用在 STL 中 map set，java 中的 tree map，
linux 进程调度公平调度用于管理进程控制块；
B/B++用于文件系统、数据库中做索引，trie 用于前缀匹配，NLP 中常用的数据结构吧
（2） 红黑树在 STL 上的应用
对于 unordered 的结构，红黑树虽然慢，但是比 hash 的方式省内存
（3） 了解并查集吗？（低频）
并查集用于畅通工程算法，亲戚门派问题；pre{}数组用于记录上一级是谁，两个函数 !nd 用于查根，
join 用于当两个人的掌门人不同的时候，将其中一个掌门人归并到另外一个掌门人门下；可以使用路径压
缩算法继续优化
（4） 贪心算法和动态规划的区别：
贪心就是考虑当前，与后面无关；dp 就是考虑所有相关情况，把结果保存起来，然后回溯
（5） 判断一个链表是否有环，
如何找到这个环的起点：如果不考虑空间的话，其实只要把链表节点加入到 hash_set 中去就行，如
果在 set 已经包含了元素，那么就是起点，有环。也可以用双指针快慢来做
（6） 实现一个 strcpy 函数（或者 memcpy），如果内存可能重叠呢
（7） 实现一个循环队列：ring buer
（8） 排序算法（写快排，归并排序，堆排序），算法的时间复杂度，空间复杂度，是否
稳定等
（9） 快排存在的问题，如何优化：
最差情况下不好，比较点的选择使用随机的方式（可以取左中右各自 3 个数取中数，然后得到 3 个
中数再取中数，如果这样的话，后面的 N 可以设为 9）；
三向切分（把相等的数也考虑进来，不让他们再次递归）；
当划分已经小于 N 时，使用插入排序，因为快排会递归自己
资源评论
