关于前端:算法学习笔记day4

原视频

哈希表的简略介绍（集体了解对于 js 当中就是简略的 map）
1）哈希表在应用层面上能够了解为一种汇合构造
2）如果只有 key，没有随同数握 value，能够应用 HashSet 构造 (C++ 中叫 UnOrderedSet)
3) 如果既有 key，又有随同数据 value，能够应用 HashMap 构造(C++ 中叫 UnOrderedNap)
4）有无随同数据，是 HashMap 和 HashSet 雅一的区别，底层的理论构造是一回事
5) 应用哈希表增 (put)、删(remove)、改(put) 和查(get) 的操作，能够认为工夫复杂度为 O（1)，然而常数工夫比拟大
6）放入哈希表的货色，如果是根底类型，外部按值传递，内存占用就是这个货色的大小
7）放入哈希表的货色，如果不是根底类型，外部按援用传递，内存占用是这个货色內存地址的大小

有序表的简略介绍
1) 有序表在应用层面上能够了解为一种汇合构造
2）如果只有 key，没有随同数据 value，能够应用 TreeSet 构造(C++ 中叫 OrderedSet)
3）如果既有 key，又有随同数据 value，能够应用 Treellep 构造(C++ 中叫 OrderedMap)
4）有无随同数据，是 TreeSet 和 Treelap 惟一的区别，底层的理论构造是一回事
5）有序表和哈希表的区别是，有序表把 key 依照程序組织起来，而哈希表齐全不组织
5) 红黑树、AVL 树、size-balance-tree 和號表等都属于有序表构造，只是底层具体实现
不同
6)放入哈希表的货色，如果是根底类型，外部按值传递，内存占用就是这个货色的大小
7）放入哈希表的货色，如果不是根底类型，必须提供比拟器，外部按援用传递，内存古用是这个货色内存地址的大小
8）不论是什么底层具体实现，只有是有序表，都有以下固定的基本功能和固定的工夫复杂度

单向链表

class Node {
    v value
    Node next
}

双向链表

class Node {
    v value
    Node next
    Node last
}

相干题目: 翻转链表
[打印有序链表的公共局部]

【题目】给定一个单链表的头节点 head，请判断该链表是否为回文结构。
【例子】1->2->1，返回 true；1->2->2->1，返回 true；15->6->15，返回 true；
1->2->3，返回 false。
【思路】：用一个栈把该链表存下，存完之后每次 pop 进去和链表比对
【例子】如果链表长度为 N，工夫复杂度达到 O(N），额定空间复杂度达到 O(1)。
思考应用快慢指针找到中点。而后再遍历到中点后扭转下一个节点的指向改为指向上一个同时记录首位节点。而后通过首位遍历链表，判断是否始终雷同，始终雷同则为回文。额定控件复杂度为 O(1)

在一个单向链表中，如何晓得链表的中点在哪？设置一个快指针一次走两步，慢指针一次走一步，那么快指针走完的时候，慢指针走到的地位就是中点的地位，须要留神的是要依据数据的长度是基数和数据偶数是偶数时候进行特判

快慢指针也能够判断链表是否为有环无环，如果快指针 === 慢指针就是有环，这里还能延长当当快指针和慢指针相遇后，快指针回到原点，慢指针不动，接下来快慢指针都同时走一步，他们终将会在入环节点相遇（）

【题目】给定一个单链表的头节点 head，节点的值类型是整型，再给定一个整数 pivot。实现一个调整链表的西数，将链表调整为左局部都是值小于 pivot 的节点，两头局部都是值等于 pivot 的节点，右局部都是值大于 pivot 的节点。

【进阶】在实现原问题性能的根底上减少如下的要求
【要求】调整后所有小于 pivot 的节点之间的绝对程序和调整前一样
【要求】调整后所有等于 pivot 的节点之间的绝对程序和调整前一样
【要求】调整后所有大于 pivot 的节点之间的绝对程序和调整前一样
【要求】工夫复杂度请达到 0(N)，额定空间复杂度请达到 0(1）。

【题目】一种非凡的单链表节点类形容如下

class Node {
    int value；Node next；Node rand；}

rand 指针是单链表节点构造中新增的指针，rand 可能指向链表中的任意一个节点，也可能指向 null。给定一个由 Node 节点类型组成的无环单链表的头节点 head，请实现一个函数实现这个链表的复制，并返回复制的新链表的头节点。
【要求】工夫复杂度 0(N），额定空间复杂度 0（1）

思路：应用额定空间时，思考应用 map(js 中为 Map 构造不能是 {})，key 为老节点，value 为新节点一个个复制，再遍历一个遍依据 map 一个个拼
不应用额定空间就比拟屌了，1 指向 1 复制同时 1 复制指向 1next，2 指向 2 复制，同时 2 复制指向 2next 而后再遍历一遍拿出新链表
这里为什么不能间接复制是因为你复制 1 的时候，1 的 rand 指向还没生成，你无奈晓得指向哪。

当然也能够应用 hash 表来判断入环节点在哪，遍历的时候顺便放到 hash 中，每次遍历的过程中看下 hashmap 中寸没存，存过了就是入环节点。

【题目】给定两个可能有环也可能无环的单链表，头节点 head1 和 head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回 null

【要求】如果两个链表长度之和为 N，工夫复杂度请达到 O(N），额定空间复杂度
请达到 O(1)。

【思路】因为如果有相交那么前面的节点肯定都雷同（即两个链表肯定是 y 字型）那么咱们就先判断两个链表的尾是否雷同。如果不同返回 null 不同的话求两个链表的长度。而后让长的链表先走出长的间隔，而后遍历

链表这一张了解并不深刻有空还得看看这个 https://zhuanlan.zhihu.com/p/…

关于前端:算法学习笔记day4

哈希表

有序表

链表

判断链表是否为回文链表

快慢指针

将单向链表按某值划分成右边小、两头相等、左边大的模式

复制含有随机指针节点的链表

两个单链表相交的一系列问题

其余