2020-07-23

一、hashMap

数组加链表形式的哈希表，时间复杂度O(1)

二、双向指针问题

1. 快慢指针

a. 判断链表是否有环

答：快慢指针,前进一步和前进两步

image.png

b. 链表中有环，返回环的起始节点

答：当快慢指针相遇时，让其中任一个指针重新指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

image.png

c. 寻找链表中点

image.png

当链表的长度是奇数时，slow 恰巧停在中点位置；如果长度是偶数，slow 最终的位置是中间偏右：

寻找链表中点的一个重要作用是对链表进行归并排序。

回想数组的归并排序：求中点索引递归地把数组二分，最后合并两个有序数组。对于链表，合并两个有序链表是很简单的，难点就在于二分。

d. 寻找链表的倒数第k个元素

答：让快指针先走k步

image.png

2.左右指针

左右指针在数组中实际是指两个索引值，一般初始化为 left = 0, right = nums.length - 1 。

可解决问题：
a.二分查找
b.两数之和
c.反转数组
//d.滑动窗口？？？（待解决）

三、算法的特性

输入、输出、可行、有穷、确定

四、并行和并发的区别

image.png

并发:同一时间段，多个任务都在执行（单位时间内不一定执行）
并行:单位时间内多个任务同时执行

五、三山五岳

三山：安徽黄山、江西庐山、浙江雁荡山
五岳：东岳山东泰山、西岳陕西华山、南岳湖南衡山、北岳山西恒山、中岳河南嵩山

六、队列判断满和空的条件是什么？

空：

单链表空：头结点指针域next==NULL

静态链表空（就是用数组来实现链式存储结构）：数组最后一个元素值为0

循环链表空：头结点的指针域指向它本身（循环查找时以p->next !=头结点作为遍历结束条件）

栈空 顺序存储时：top==-1 链式存储时：top==NULL

队列（队头出队、队尾入队）
①顺序存储队列 front==rear循环队列 front==rear
②链式存储链队列 front、rear均指向头结点

满：
单链表、循环链表：不存在
静态链表：根据数组长度来判断
栈 顺序存储时：top==数组大小-1 链式存储时：不存在
队列
①顺序存储队列 可能假溢出循环队列 （rear+1）% QueueSize == front
②链式存储链队列 不存在

七、折半查找过程 5，13，19，21，37，56，64，75，80，88，92查找21
56，21