面试算法学习笔记

算法面试

合理的思考方向和思考路径比较重要
对于问题细节和应用环境可以沟通，完善假设
数据排序：数据特征（是否重复·三路快排，是否有序，是否离他正确位置很近·插入排序，取值范围是否有限-计数排序，排序额外要求·归并排序，数据存储状况，存储状况与内存大小-外排序算法，）
正确的含义包含对于问题的独到见解；优化；代码规范；容错性；
算法面试只是技术面试的一部分

简历中项目经历和项目中遇到的实际问题，具体获得经验和算法难点
印象中的bug处理
将课程设计好好封装 毕业设计
参与实战课程学习（慕课，coursea）
自己做小应用，小网站，自己的技术博客和github
准备好合适的问题去问面试官（项目后续规划，小组工作运行模式，某个问题如何解决，为什么选择某些技术和标准，对某个技术很感兴趣，如何深入学习这个技术）

红黑树，Btree 计算几何 斐波那契 fft 数论概率较低。（高级数据结构）
排序算法，基础数据结构的实现和使用，基础算法，基本算法思想。

选择合适的oj，例如leetcode hackerrank

解决算法面试的整体思路
注意题目中的条件（数据空间，时间，数据规模，是否有序）
当没有思路时，给几个简单的测试用例；暴力解法是起点；
优化算法：遍历常见的算法思路；遍历常见的数据结构；空间和时间点交换（哈希表）；预处理（排序）；在瓶颈处寻找答案；
实际编写：极端条件判断（数组空，指针null，数量0）；变量名有寓意；模块化与复用性）；基本问题能够白板编程。

面试算法的时间复杂度分析（指令正比）
二分查找法 log n
寻找数组中的最大最小On
归并排序Onlogn
选择排序On2
在学术界O(fn)为算法的复杂度上界
O（nlogn+n）=O（nlogn）不完全成立，因为操作步骤数不同

字符串比较是Os消耗
算法复杂度有时和用例相关
插入排序与快速排序算法最差最好情况下显著性差别，不能仅看平均情况
数据规模有一个概念
(在几秒之内解决问题)如果数据规模小可以
空间复杂度
多开了一个数组辅助 On 2个辅助数组On2 常数空间O（1）
递归调用是有空间代价的（前面执行的空间状态压入栈）
logaN=logab*logbN只差一个常数，所以统一复杂度为logn
反转数值编程要考虑是否为负数，是否为0
复杂度实验：每次将数据规模提高两倍，看时间变化，看趋势。
递归算法的复杂度分析
一次递归调用：看递归深度
多次递归调用：计算调用的次数（节点个数）
均摊复杂度分析：动态数组，防止复杂度震荡，元素个数为数字容量1/4时resize，为添加元素留出余地
栈与队列逻辑同上。

数组问题中问题最常见
明确变量的含义，维护循环不变量
小数据量的调试 大数据量测试
对于有序数列才能使用二分查找法
     mid=（r-l）/2+l 防止整型溢出
简单问题同样要在时间空间复杂度上进一步优化
需要考虑到特殊的测试用例
数组去重（先排序再去重，双数组var值去重，对象性质去重）
数组中只有0，1，2排序（计数排序，三路快排）
寻找第k大的元素index，先排序，然后二分发，设立partition
寻找有序数组中两个数组元素和为target的索引：二分法，寻找i和target-nums【i】的索引号
对撞指针的思想
水坑储水问题：https://blog.****.net/u012501459/article/details/14056435
字符串问题注意事项：空字符串如何考虑；字符包含哪些字符；字符大小写问题是否考虑；

 查找set与map的使用，要注意不同语言中容器类具体的使用方式
具体操作有find erase change（map） insert四种操作，有时会用到迭代器
哈希表失去了数据的顺序性

happy number：https://blog.****.net/u011809767/article/details/68059125

word pattern：https://blog.****.net/happyaaaaaaaaaaa/article/details/51357287
即使用hashmap映射pattern和对应单词

Two sums：方法一：排序后双指针碰撞
方法二：定a 查找target-a
https://www.cnblogs.com/grandyang/p/4130379.html

4 sum ||：方法一：将D中元素放入查找表，然后遍历A+B+C和
方法二：C+D和放入查找表，遍历A+B
方法三：A+B与C+D均放入查找表

规模已知可推测解决问题的最差时间复杂度情况

Number ofBoomeranges：令i为枢纽点，计算各个点到i的距离个数，然后分别计数：最后三元组数量为count*（count-1）
注意：防止数组越界可将dis类型设为long
避免浮点数，以平方和代替距离

max points on a line：选定一个点，分别计算其他点和它构成的直线的斜率，斜率相同的点肯定在同一条直线上。计算斜率时，注意重合点和x值相同的两个点（数学上称斜率不存在，此时斜率用int的最大值表示）。https://blog.****.net/ljiabin/article/details/38904757

contains duplicated ll ：运用滑动窗口+查找表去解决问题。固定查找表的长度。！https://blog.****.net/DERRANTCM/article/details/48084061

valid parentheses：栈顶元素反映了在嵌套关系中，需要匹配最近的元素
后序表达式的求解：注意运算符的种类；字符串表达数字的种类。
Simply path：不能回退的情况，是否有多余的符号。
栈和递归的紧密关系：
二叉树的遍历：三种遍历，递归与非递归遍历。
系统栈的模拟实现。
flatten nested list lterator：
https://blog.****.net/qq508618087/article/details/51111355
设置两个栈，遇到整形就放进去，集合的话就放入栈中pop出来
队列：广度优先遍历
应用：树：层序遍历
            图：无权图的最短路径
二叉树的层序遍历：使用数据对，返回level和val
perfect squares：一定有解；
直觉解法：贪心算法（错误）
正确解法：两数之差为完全平方数则连线；然后寻找n到0的路径，找step数量
word ladder：https://blog.****.net/mine_song/article/details/68951974
word ladder2:路长和保存返回路径，使用递归来还原最短路径。

优先队列也是队列：底层实现为堆（最好能够白板编程），寻找数据中最大最小数据优先出队。
学习使用语言中的优先队列容器。默认使用最大堆。可以使用自定义函数
top k frequent element：
最简单思路：map扫描统计频率；排序
思路2:维护优先队列，O（nlogk）
merge k sorted lists：https://blog.****.net/u012985132/article/details/53207892