Skip to content

Latest commit

 

History

History
 
 

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

主要学习内容

位运算
    利用二进制的特点,在特定场景下直接进行二进制运算,以此提高效率  
    左移 <<,右移 >>,按位或 |,按位与 &,按位取反 ~ ,按位异或 ^  
    指定位置的位运算
        将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