##第八周学习总结 #XOR异或 x^0 = x x^1s = ~x x^(~x) = 1s x^x = 0
#判断奇偶： x % 2 == 1 —> (x & 1) == 1 x % 2 == 0 —> (x & 1) == 0
x >> 1 —> x / 2. 即： x = x / 2; —> x = x >> 1; mid = (left + right) / 2; —> mid = (left + right) >> 1;
X = X & (X-1) 清零最低位的 1 X & -X => 得到最低位的 1
X & ~X => 0
#布隆过滤器
- 一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索 一个元素是否在一个集合中。
- 优点是空间效率和查询时间都远远超过一般的算法， 缺点是有一定的误识别率和删除困难。
#LRU Cache 两个要素： 大小 、替换策略
Hash Table + Double LinkedList
#高级排序
- 快速排序（Quick Sort）
- 数组取标杆 pivot，将小元素放 pivot左边，大元素放右侧，然后依次
- 对右边和右边的子数组继续快排；以达到整个序列有序
- 归并排序（Merge Sort）— 分治
- 把长度为n的输入序列分成两个长度为n/2的子序列
- 对这两个子序列分别采用归并排序
- 将两个排序好的子序列合并成一个最终的排序序列
- 堆排序（Heap Sort）
- 堆插入 O(logN)，取最大/小值 O(1)
- 数组元素依次建立小顶堆
- 依次取堆顶元素，并删除
- 计数排序（Counting Sort）
- 计数排序要求输入的数据必须是有确定范围的整数。将输入的数据值转化为键存 储在额外开辟的数组空间中；然后依次把计数大于 1 的填充回原数组
- 桶排序（Bucket Sort）
- 桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有 限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式 继续使用桶排序进行排）
- 基数排序（Radix Sort）
- 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类 推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按 高优先级排序