原视频哈希表哈希表的简单介绍（个人理解是js中的简单映射）1）哈希表在使用层面可以理解为集合结构2）如果只有键，没有伴随数据来保存值，可以使用HashSet结构（C++中称为UnOrderedSet）3）如果既有键又有伴随数据值，可以使用HashMap结构（C++中称为UnOrderedNap）4）是否有伴随数据，是HashMap和HashSet的区别在于底层实际结构是一样的东西。5）利用哈希表进行增（put）、删（remove）、改（put）和查询（get）操作，可以认为时间复杂度为O(1)，但常数时间比较大6)如果放入哈希表的东西是基本类型，则内部按值传递，内存占用就是这个东西的大小7)如果放入哈希表的东西不是基本类型，内部按引用传递，memoryusage就是这个东西内存地址的大小Orderedtableorderedtable简介1）Orderedtable在使用层面可以理解为一个集合结构2）如果只有key，没有伴随数据value，可以使用TreeSet结构（C++中称为OrderedSet）3）如果既有键又有伴随数据值，则可以使用Treellep结构（C++中称为OrderedMap）4）是否有伴随数据是两者之间的唯一区别TreeSet和Treelap，底层实际结构是一样的hing5)有序表和哈希表的区别是有序表是按顺序组织key，而哈希表根本不组织5)红黑树、AVL树、size-balance-tree和numbertable属于有序表结构，但是底层具体实现不一样6）如果是基本类型，内部传值，内存占用就是这个东西的大小7）放到哈希表中如果该表不是基本类型，必须提供比较器，并在内部通过引用传递。使用的内存是这个对象的内存地址的大小。8）不管底层实现是什么，只要是有序表，都有如下固定的基本函数和固定时间复杂度的链表单链表类Node{vvalueNodenext}双链表类Node{vvalueNodenextNodelast}回文链表【题目】给定一个单向链表的头节点head，请判断该链表是否为回文结构。【例子】1->2->1，返回true；1->2->2->1，返回真；15->6->15，返回真；1->2->3，返回false。【思路】：用一个栈来保存链表，然后每次弹出来和链表比较【例子】如果链表的长度为N，时间复杂度达到O(N)，则额外的空间复杂度达到O(1)。考虑使用慢指针和快指针来找到中点。然后，遍历到中点后，改变下一个节点的方向指向上一个，同时记录第一个节点。然后通过第一个bit遍历链表，判断是否始终相同，如果始终相同则为回文。额外的控制复杂度是O(1)快慢指针在一个单向链表中，你怎么知道链表的中点在哪里？设置快指针一次走两步，慢指针一次走一步。那么快指针走完了，慢指针走的位置就是中点位置。需要注意的是，数据的长度是基数，数据的偶数是偶数，当有偶数时，快慢指针也可以判断链表是否有环。如果快指针===慢指针有环，可以在这里扩展。当快指针和慢指针相遇时，快指针回到原点，而慢指针不动，然后快指针和慢指针同时走一步，最终相遇在入口点()将单向链表按照一定的值分成左小，中间相等，右大的形式【题目】给定一个单链表的头节点head，节点的值类型为整数，并给出一个整数主元。实现一个调整链表的西数，调整链表使得左边是所有值小于pivot的节点，中间部分是所有值等于pivot的节点，右边是所有节点其值大于枢轴。【进阶】在实现原问题功能的基础上增加如下需求【需求】调整后，所有小于pivot的节点的相对顺序与调整前相同nodesequaltopivot与调整前相同【要求】调整后，所有大于pivot的节点的相对顺序与调整前相同【要求】时间复杂度请达到0（N），额外空间复杂度请达到0（1）.复制一个包含随机指针节点的链表【题目】一个特殊的单链表节点类描述如下：classNode{intvalue;下一个节点；节点兰特；}rand指针是单链表结点结构中的一个新指针，rand可能指向链表中的任意结点，也可能指向null。给定一个由Node节点类型组成的非循环单向链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。【要求】时间复杂度0(N)，额外空间复杂度0(1)思路：在使用额外空间时，考虑使用map（js中的Map结构不能为{}），key为旧节点，value为就是把新节点一个一个复制，然后一个一个遍历。按照地图，在不占用额外空间的情况下，一个一个打起来比较尴尬。1指向1个copy1个copy指向1next，2个copy2个copy，2个copy指向2next，然后再次遍历取出一个新的链表这里不能直接copy的原因是当你copy1，1的rand点还没有生成，你也不知道它指向哪里。当然也可以使用哈希表来判断入口点在哪里。遍历的时候顺便放到hash里面。在每次遍历过程中，检查hashmap是否未保存。如果它被保存，它就是入口点。关于两个单向链表交集的一系列问题【题目】给定两个可能有环也可能没有环的单向链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，则返回null【需求】如果两个链表的长度之和为N，则时间复杂度为O(N)，追加空间复杂度为O(1)。【思考】因为如果存在相交的无环链表，那么后面的节点一定是相同的（即两个链表的形状一定是y），那么我们先判断两个链表的尾部是否相同是相同的。如果它们不同，则返回null。如果不同，求两个链表的长度。然后让长链表先出去很远的距离，再遍历环上的节点。如果两个链表在进入环之前相交，则与两个无环链表相同。如果交点在入环之后，则为两个链表的任意一个入口点。另一个链表不是很好理解。有时间的话一定要看看这个https://zhuanlan.zhihu.com/p/...
