华科大的 湖南大学面试算法讲座综合ppt.ppt

2014年4月29日 华科大 第5次面试算法讲座2014年4月30日 湖大 第6次面试 算法讲座 主讲人：July 致谢： 武汉光电国家实验室就业实践部 湖南大学CSDN高校俱乐部 本次讲座内容提纲 笔试面试考什么 语言、操作系统、数据库、网络协议、概率统计 数据结构、算法 面试中常考哪些算法 实战演练 一步步，不断优化 如何学习、备战算法 对比 联系 追本溯源，以红黑树 B树为例 海量数据处理面试题解决之道 六种解决方法 准备工作 简历 一页纸最好，简洁精练 会什么，做了什么 项目 or paper 刷题 leetcode 笔试偏基础 语言基础 int hope; int* hope; double(*p) [3]; void (*func) (); 操作系统 线程与进程的区别 产生死锁的条件 如何规避死锁 C++内存分配 堆、栈、自由存储区、全局/静态存储区，常量存储区 网络协议 TCP建立连接的三次握手 数据库 概率论与数理统计 基础不够 补基础 语言 C ： 《C 和指针》 《征服C 指针》 《C++ primer》 C++： 《深度探索C++ 对象模型》 《Effective C++》 数理 《数理统计学简史》 面试偏算法 数据结构上的增删改查 查找、遍历、排序 算法 分治、递归、回溯 贪心、动态规划 海量数据处理 基于各种数据结构上的增删改查 字符串 字符串库函数的编写 字符串查找、翻转、匹配 数组 查找（如二分查找、杨氏矩阵查找） 链表 翻转、遍历、查找、删除、合并 Hash表 查找 树 遍历（前序、中序、后序） set、map 高级树的查找（红黑树、B树、R树） 图 遍历 查找（DFS、BFS） 最短路径算法 面试常用算法总结 穷举（递归回溯）——“万能的” 求n个数的全排列 8皇后（N皇后问题） 分治 分而治之，然后归并 空间换时间 hashtable 巧用数据结构 堆 能排序，考虑排序 前后两个指针往中间扫 若已经排好序，想想有无必要二分 不能排序 贪心 最小生成树Prim, Krusal 最短路dijkstra 动态规划 如 01背包问题，每一步都在决策 细节处理 注意边界条件 实战演练 字符串翻转 翻转 定义字符串左旋转操作：把字符串前面的若干个字符移动到字符串尾部,如把字符串 abcdef 左旋转 2 位得到字符串 cdefab。 时间复杂度为 O(n)，空间复杂度为 O(1)。 解法一： 暴力移位 解法二： 三步翻转（字符串 abcdef - defabc） X：abc，Y：def； X-X^T，得：abc-cba；Y-Y^T，得：def-fed X^TY^T，得到：cbafed-defabc，即(X^TY^T)^T=YX 字符串处理 还是字符串翻转 翻转句子中单词的顺序，例如输入“I am a student.”，则输出“student. a am I”。 字符串的左旋转操作，如把字符串abcdef左旋转2位得到字符串cdefab，要求时间O(n)，空间O(1)。 在原字符串中把尾部m个字符移动到字符串的头部，如原字符串为”Ilovebaofeng”，m=7，输出结果：”baofengIlove”。 设计一个反转字符串的函数 char *reverse_str(char *str),不使用系统函数。 字符串包含 1/2 包含 假设这有两个分别由字母组成的字符串A另外字符串B，字符串B的字母数较字符串A少一些。什么方法能最快地查出字符串B所有字母是不是都在字符串A里？也就是说判断字符串B是不是字符串A的真子集 为了简化，姑且认为两个集合都不是空集，即字符串都不为空，且我们规定输入的字符串只包含大写英文字母。 实现函数bool compare(string A,string B) 比如，如果是下面两个字符串： String 1: ABCDEFGHLMNOPQRS String 2: DCGSRQPO 答案是true，即String2里的字母在String1里也都有，或者说String2是String1的真子集。 如果是下面两个字符串： String 1: ABCDEFGHLMNOPQRS String 2: DCGSRQPZ 答案是false，因为字符串String2里的Z字母不在字符串String1里。 字符串包含 2/2 多种思路 暴力轮询：针对string2中每一个字符，一一与string1中每个字符依次轮询比较，看它是否在String1中，O（n*m） 先对这两个字符串的字母进行排序，然后同时对两个字串依次轮询 hashtable，空间换时间 素数相乘，缺点：可能导