|
1 | | -学习笔记 |
| 1 | +# 第八周学习笔记 |
| 2 | +## 位运算 |
| 3 | +### 位运算符 |
| 4 | +| 含义 | 运算符 | 示例 | |
| 5 | +| :------:| :------: | :------ | |
| 6 | +| 左移 | << | 0011 => 0110 | |
| 7 | +| 右移 | >> | 0110 => 0011 | |
| 8 | +| 按位或 | \| | 0011 <br> ———— =>1001<br>1011 | |
| 9 | +| 按位与 | & | 0011<br> ————=> 0011<br>1011 | |
| 10 | +| 按位取反 | ~ | 0011 => 1100 | |
| 11 | +| 右移 | >> | 0110 => 0011 | |
| 12 | +### 算数移位与逻辑移位 |
| 13 | +### 位运算的应用 |
| 14 | + |
| 15 | +## 布隆过滤器 |
| 16 | +* Bloom Filter vs Hash Table |
| 17 | + 一个很长的二进制向量和一些列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中 |
| 18 | +* 优点：空间效率和查询时间都远远高于一般的算法 |
| 19 | +* 缺点：有一定的误识别率和删除困难 |
| 20 | +* 示意图 |
| 21 | + |
| 22 | +* 案例 |
| 23 | + 1. 比特币网络 |
| 24 | + 2. 分布式系统(Map-Reduce) —— Hadoop、search engine |
| 25 | + 3. Redis缓存 |
| 26 | + 4. 垃圾邮件、评论等的过滤 |
| 27 | + |
| 28 | +## LRU Cache |
| 29 | +* Cache 缓存 |
| 30 | +* 两个要素: 大小， 替换策略 |
| 31 | +* Hash Table + Double LinkedLIst |
| 32 | +* O(1)查询 |
| 33 | + O(1)修改、更新 |
| 34 | +* 代码实现(js) |
| 35 | +``` |
| 36 | +/** |
| 37 | + * @param {number} capacity |
| 38 | + */ |
| 39 | +var LRUCache = function(capacity) { |
| 40 | + this.size = capacity |
| 41 | + this.cache = new Map() |
| 42 | +}; |
| 43 | +
|
| 44 | +/** |
| 45 | + * @param {number} key |
| 46 | + * @return {number} |
| 47 | + */ |
| 48 | +LRUCache.prototype.get = function(key) { |
| 49 | + if (this.cache.has(key)) { |
| 50 | + const temp = this.cache.get(key) |
| 51 | + this.cache.delete(key) |
| 52 | + this.cache.set(key, temp) |
| 53 | + return temp |
| 54 | + } |
| 55 | + return -1 |
| 56 | +}; |
| 57 | +
|
| 58 | +/** |
| 59 | + * @param {number} key |
| 60 | + * @param {number} value |
| 61 | + * @return {void} |
| 62 | + */ |
| 63 | +LRUCache.prototype.put = function(key, value) { |
| 64 | + if(this.cache.has(key)) { |
| 65 | + this.cache.delete(key) |
| 66 | + this.cache.set(key, value) |
| 67 | + } else { |
| 68 | + if (this.cache.size >= this.size) { |
| 69 | + this.cache.delete(this.cache.keys().next().value) |
| 70 | + } |
| 71 | + this.cache.set(key, value) |
| 72 | + } |
| 73 | + |
| 74 | +}; |
| 75 | +
|
| 76 | +/** |
| 77 | + * Your LRUCache object will be instantiated and called as such: |
| 78 | + * var obj = new LRUCache(capacity) |
| 79 | + * var param_1 = obj.get(key) |
| 80 | + * obj.put(key,value) |
| 81 | + */ |
| 82 | +``` |
| 83 | + |
| 84 | +## 排序 |
| 85 | +1. 比较类排序 |
| 86 | + 通过比较来决定元素间的相对排序，由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序 |
| 87 | +2. 非比较类排序 |
| 88 | + 不通过比较来决定元素间的相对次序，他可以突破基于比较排序的时间下限，以线性时间运行，因此也称为线性时间非比较类排序 |
| 89 | + |
| 90 | +* 脑图 |
| 91 | + |
| 92 | + |
| 93 | +### 初级排序 |
| 94 | +1. 选择排序(Selection Sort) |
| 95 | + 每次找最小值，然后放到待排序数组的起始位置 |
| 96 | +2. 插入排序(Insertion Sort) |
| 97 | + 从前到后逐步构建有序序列；对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入 |
| 98 | +3. 冒泡排序(Bubble Sort) |
| 99 | + 嵌套循环，每次查看相邻的元素如果逆序，则交换 |
| 100 | + |
| 101 | +### 高级排序 |
| 102 | +1. 快速排序(Quick Sort) |
| 103 | + 数组取标杆pivot，将小元素放在pivot左边，大元素放在右侧，然后依次对右边和右边的子数组继续快排，以达到整个序列有序 |
| 104 | +2. 归并排序(Merge Sort) —— 分治 |
| 105 | + 1. 把长度为n的输入序列分成两个长度为n/2的子序列 |
| 106 | + 2. 对两个子序列分别采用归并排序 |
| 107 | + 3. 将两个排序好的子序列合并成一个最终的排序序列 |
| 108 | +3. 堆排序(Heap Sort) |
| 109 | + 堆插入O(logN),取最大/最小值O(1) |
| 110 | + 1. 数组元素依次建立小顶堆 |
| 111 | + 2. 依次取堆顶元素，并删除 |
| 112 | + |
| 113 | +总结： 归并和快排具有相似性，但步骤相反 |
| 114 | + 归并：先排序左右子数组，然后合并两个有序子数组 |
| 115 | + 快排：先调配出左右子数组，然后对于左右子数组进行排序 |
| 116 | + |
| 117 | +### 特殊排序 - O(n) |
| 118 | +* 计数排序(Counting Sort) |
| 119 | +* 桶排序(Bucket Sort) |
| 120 | +* 基数排序(Radix Sort) |
0 commit comments