主要学习内容
位运算
利用二进制的特点,在特定场景下直接进行二进制运算,以此提高效率
左移 <<,右移 >>,按位或 |,按位与 &,按位取反 ~ ,按位异或 ^
指定位置的位运算
将x的最右边n位清零:x & ( ~ 0 << n)
获取x的第n位值:(x >> n) & 1
获取x的第n位幂值:x & (1 << n)
仅将第n位设置为1:x | (1 << n)
仅将第n位设置为0:x & ( ~ (1 << n))
将x最高位至第n位(含)清零:x & ((1 << n) - 1)
布隆过滤器
快速检索一个元素是否在一个集合中
优点是空间效率和查询效率都极高,缺点是结果不完全准确(针对存在的情况)及删除困难
通过一个很长的二进制向量及一系列随机映射函数实现
LRU缓存
Least Recently Used Cache,实现近期最少使用算法的缓存。
元素使用频率越高,优先级越高,当容量到达上限后继续添加元素时,最老的元素被移除
通过Hash表及双向链表实现
Java的LindkedHashMap已经进行了实现
排序
具体实现方式有多种,主要掌握效率最高的O(N*LogN)
快速排序:先取pivot,以标杆为界,小元素放左边,大元素放右边。左右两边以此类推进行操作。关键点在于标杆位置的选取。
归并排序:基于分治理念,将数组一分为二,分别进行排序,然后合并两个有序子数组。子数组也以此类推进行操作。关键点在于合并两个有序数组。
堆排序:数组元素依次建立小顶堆,然后依次从堆顶取出元素,关键点在与堆的实现。
特殊排序O(N)
计数排序 Counting Sort
桶排序 Bucket Sort
基数排序 Radix Sort