Day6 25/2/19 WED
【一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵）】https://www.bilibili.com/video/BV13g41157hK?p=4&vd_source=04ee94ad3f2168d7d5252c857a2bf358
目录
4、表
4.1 按存储结构划分
4.1.1 哈希表
4.1.1.1 函数调用
4.1.1.2 增删改查操作
4.1.2 单链表 & 双链表
4.1.2.1 面试时的方法论
4.2 按元素数值大小划分
4.2.1 有序表
笔记：
4、表
哈希表和链表的区别：
哈希表是根据关键码值（Key Value）而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录，以加快查找的速度。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
4.1 按存储结构划分
4.1.1 哈希表
4.1.1.1 函数调用
如果只有key没有value，在java中可以使用HashSet结构。
如果既有key也有value，在java中可以使用HashMap结构。
有无value数据就是set和map的唯一区别。
4.1.1.2 增删改查操作
哈希表增删改查操作的时间复杂度都是常数级别的，但这个常数时间一般较长。
map中的put()方法既是插入操作，也是更新操作，比如：
HashMap<Integer, String> testMap = new HashMap();
testMap.put(1, “abc”);
testMap.put(1, “ghj”);
System.out.print(testMap.get(1)); //会打印出ghj，而非abc。map插入/更新操作：map名.put(键名, 值);
map查询键是否存在的操作：map名.contsinKey(键名); //在则显示true
map查询某个键是否存在值的操作：map名.get(键名); //在则显示值，不在则返回null
map移除操作：map名.remove(键名);
set插入/更新操作：set名.add(键名);
set查询是否存在的操作：set名.contians(键名); //在则显示true
set移除操作：set名.remove(键名);
哈希表中，如果key的类型不是基础类型，是自己定义的Node等类型，存储到key中的就是内存地址；如果key是基础类型，存储的就是值而非地址。
4.1.2 单链表 & 双链表
4.1.2.1 面试时的方法论
所有链表题在做的时候，一律贯彻笔试和面试区别对待的方式。
（1）对于笔试，不用太在乎时间复杂度，一切为了时间复杂度。
（2）对于面试，时间复杂度仍重要，但也要找到空间最省的方法。
（3）重要技巧：额外数据结构记录（哈希表）、快慢指针
例题普通版：判断一个链表是否为回文结构。
笔试的做法：创建一个栈，遍历链表的时候把元素依次放进去。然后再遍历一遍链表，边遍历边弹栈，比较二者是否一样。（栈弹出的顺序是先进后出，也就是链表的逆序）
另一个做法：只把后一半链表压入栈，边遍历前一半链表边弹栈比较二者是否相同，这样空间使用从N变为了N/2。用“快慢指针”可以实现，慢指针s一次走一格，快指针f一次走两格，当快指针遍历到链表末尾的时候，慢指针正好抵达链表中央。把从慢指针指向的元素到链表末尾都压入栈。
补充，快慢指针这块需要根据题目要求去修改具体的代码。当链表为偶数时，慢指针有可能指向中线的左侧或右侧，这是边界问题，需要按题目需求去具体分析快慢指针哪个先走。
例题进阶版：要求时间复杂度O(N)，额外空间复杂度O(1)。
快慢指针中的慢指针遍历到中点的时候，慢指针边往后便利边把元素指向改为指向中点。改完后再用两个指针分别从两端往中间遍历，边遍历边比较，遍历到中点指向的null之后停止。
最后再把链表的指向改回去。
这个方法无实际作用，只是面试时纯粹为了考验编程能力。
4.2 按元素数值大小划分
4.2.1 有序表
如果只有key没有value，java中可用TreeSet结构。
如果既有key也有value，java中可用TreeMap结构。
有序表和哈希表的区别是：哈希表的key是无序的，有序表的key是有序的。
有序表中，如果key的类型不是基础类型，是自己定义的Node等类型，存储到key中的就是内存地址，而且必须设置个比较器来告诉程序如何比较非基础类型；如果key是基础类型，存储的就是值而非地址。
有序表的时间复杂度是O(logN)。