weixin_39590635
weixin_39590635
2020-11-25 07:54

【336-week 07】课后总结

摘要

  • 位运算
  • 布隆过滤器
  • LRU Cache
  • 排序算法
  • 算法区别

位运算

  • 意义
  • 机器里的数字表示方式和存储格式就是 二进制
  • 算数移位与逻辑移位
  • 左移
    • "<<":0011 => 0110
  • 右移
    • ">>":0110 => 0011
  • 位运算符
  • “|”
    • 按位或
    • 0011,1011 => 1011
  • “ & ”
    • 按位与
    • 0011,1011 => 0011
  • “ ~ ”
    • 按位取反
    • 0011 => 1100
  • “ ^ ”
    • 按位异或(相同为零、不同为一)
    • 0011,1011 => 1000
    • 常用
    • x ^ 0 = x
    • x ^ 1s = ~x (注意 1s = ~)
    • x ^ (~x) = 1s
    • x ^ x = 0
    • c = a ^ b => a ^c = b,b ^c =a(交换两个数)
    • a ^ b ^ c = a ^ (b ^ c) = (a ^ b)^c //associative
  • 指定位置的位运算
  • 将 x 最右边的 n 位清零:x & (~0 <<
  • 获取 x 的第 n 位值(0 或者 1): (x >> n) &
  • 获取 x 的第 n 位的幂值:x & (1 << (n -1))
  • 仅将第 n 位置为 1:x | (1 << n)
  • 仅将第 n 位置为 0:x & (~ (1 << n))
  • 将 x 最高位至第 n 位(含)清零:x & ((1 << n) - 1)
  • 将第 n 位至第 0 位(含)清零:x & (~ ((1 << (n + 1)) - 1))
  • 实战常用
  • x % 2 == 1 —> (x & 1) == 1
  • x % 2 == 0 —> (x & 1) == 0
  • x >> 1 —> x / 2
  • X = X & (X-1) 清零最低位的 1
  • X & -X => 得到最低位的 1
  • X & ~X => 0
  • 转换整数
  • parseInt(string,radix)
  • Math.trunc()
  • ~~n
  • n | n
  • n | 0
  • n << 0
  • n >> 0
  • n & n

布隆过滤器

  • 布隆过滤器可以用于检索一个元素是否在一个集合中。
  • 一个很长的二进制向量
  • 和一系列随机映射函数。
  • 是一个占用空间很小、效率很高的随机数据结构,它由一个bit数组和一组Hash算法构成。
  • 可用于判断一个元素是否在一个集合中,查询效率很高(1-N,最优能逼近于1)
  • 图示
  • 优点
  • 空间效率和查询时间都远远超过一般的算法
  • 缺点
  • 有一定的误识别率和删除困难
  • 实际应用
  • 比特币网络
  • 分布式系统(Map-Reduce) — Hadoop、search engine
  • Redis 缓存
  • 垃圾邮件、评论等的过滤
  • 网页爬虫对URL的去重,避免爬取相同的URL地址(一个网址是否被访问过)
  • 反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱(同理,垃圾短信)
  • 缓存击穿,将已存在的缓存放到布隆中,当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉
  • 字处理软件中,需要检查一个英语单词是否拼写正确
  • 在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上

LRU Cache

  • 缓存手段
  • LFU - least frequently used
  • LRU - least recently used
  • 实现
  • Hash Table + Double LinkedList
  • 时间复杂度
  • O(1) 查询
  • O(1) 修改、更新
  • 实现
  • 146. LRU缓存机制

排序算法

  • 非比较类排序
  • 计数排序
  • 基数排序
  • 桶排序
  • 比较类排序
  • 交换排序
    • 冒泡排序
    • 快速排序
  • 插入排序
    • 简单插入排序
    • 希尔排序
  • 选择排序
    • 简单选择排序
    • 堆排序
  • 归并排序

    • 二路归并排序
    • 多路归并排序
  • 算法稳定性

  • 稳定
    • 相同的两个元素,经过排序后位置顺序没有变化
  • 不稳定
    • 相同的两个元素,经过排序后位置顺序发生变化
  • 以下排序算法所用测试用例
    javascript
        // 生成n个1~scope的随机数字
        let randomArr = (n,scope) => {
            let arr = [];
            for(let i = 0;i < n;i++){
                arr.push(~~(Math.random()*scope) + 1)
            }
            return arr;
        }
        // 交换两个数字[注意是两个数字,且如果自己异或自己,结果为0]
        // 1、位运算
        a ^= b;
        b ^= a;
        a ^= b;
        // 2、中间变量
        let tmp = a;
        a = b;
        b = a;
        // 3、ES6语法糖
        [a,b] = [b,a]
      

+ 初级排序 - O( n^2 ) + 选择排序 - (Selection Sort) + 每次找到最小值,然后放到待排序数组的起始位置 + 找最小值的索引 + 经过n-1趟 + + code

javascript
      let selectionSort = (arr) => {
          let len = arr.length;
          let minIndex;
          for(let i = 0;i < len - 1;i++){
              minIndex = i;
              for(let j = i + 1;j < len;j++){
                  if(arr[j] < arr[minIndex]){
                      minIndex = j;
                  }
              }
              // 自己异或自己 == 0
              if( (minIndex ^ i) !== 0){
                arr[i] ^= arr[minIndex];
                arr[minIndex] ^= arr[i];
                arr[i] ^= arr[minIndex];
              }
          }
          return arr;
      }
      
+ 插入排序 - (Insertion Sort) + 从前到后逐步构建有序序列 + 对于未排序序列,在已排序序列中从后向前扫描,找到相应位置并插入 + + code
javascript
      let insertionSort = (arr) => {
          let len = arr.length;
          let preIndex,current;
          for(let i = 1;i < len;i++){
              preIndex = i - 1;
              current = arr[i];
              while(preIndex >= 0 && arr[preIndex] > current){
                  arr[preIndex+1] = arr[preIndex];
                  preIndex--;
              }
              arr[preIndex+1] = current;
          }
          return arr;
      }
      
  • 冒泡排序 - (Bubble Sort)
    • 嵌套排序,每次查看相邻的元素如果逆序,则交换
    • code
      javascript
        let bubbleSort = (arr) => {
            let n = arr.length - 1;
            for(let i = 0;i < n;i++){
                for(let j = 0;j < n;j++){
                    if(arr[j] > arr[j+1]){
                        arr[j] ^= arr[j+1]; 
                        arr[j+1] ^= arr[j]; 
                        arr[j] ^= arr[j+1]; 
                    }
                }
            }
            return arr;
        }
        
  • 高级排序 - O( N*LogN )
  • 快速排序 - (Quick Sort)

    • 数组取标杆 pivot
    • 将小元素放 pivot 左边,大元素放右侧
    • 然后依次对右边和右边对子数组继续快排
  • 归并排序 - (Merge Sort) ~ 分治

    • 把长度为n的输入序列分成两个长度为n/2的子序列
    • 对这两个子序列分别采用归并排序
    • 将两个排序好的子序列合并成一个最终的排序序列
  • 堆排序 - (Heap Sort)

    • 是一种特殊的树
    • 是一个完全二叉树
      • 除了最后一层,其他层的节点个数都是满的
      • 最后一层的节点都靠左排列
      • 比较适合用数组来存储
    • 堆中每个节点的值大于等于或小于等于其左右子树中(或者说左右子节点)每个节点的值
    • 原地排序
    • 大顶堆:
    • 每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列
    • 小顶堆:
    • 每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列
    • 部分操作时间复杂度
    • 插入:O(logN)
    • 取最大、小值:O(1)
    • 1、数组元素依次建立小顶堆
    • 2、依次取堆顶元素,并删除
  • 特殊排序 - O(n)

  • 计数排序(Counting Sort)
    • 计数排序要求输入的数据必须是有确定范围的整数。
    • 将输入的数据值转化为键存储在额外开辟的数组空间中;
    • 然后依次把计数大于 1 的填充回原数组
  • 桶排序(Bucket Sort)
    • 假设输入数据服从均匀分布,将数据分到有限数量的桶里,
    • 每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)
  • 基数排序(Radix Sort)
    • 按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。
    • 有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。

算法区别

  • 快排与归并
    • 归并:
    • 分治
    • 先排序,数组只剩一个元素即为有序
    • 再合并,双指针比较合并两个子分区数组
    • 快排:
    • 先分区,小的放基准左边,大的放基准右边
    • 再排序,将两个以基准划分的子数组合并成完全有序的一个数组

该提问来源于开源项目:algorithm004-01/algorithm004-01

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

5条回答

  • weixin_39943750 weixin_39943750 5月前

    还有动图,太优秀了吧!

    点赞 评论 复制链接分享
  • weixin_39603613 weixin_39603613 5月前

    请问下lZ 像A+B问题这样,进位运算该怎么解决?

    点赞 评论 复制链接分享
  • weixin_39628339 weixin_39628339 5月前

    动图牛逼

    点赞 评论 复制链接分享
  • weixin_39943750 weixin_39943750 5月前

    大佬请问你用的什么排版的啊?看着好舒服!

    点赞 评论 复制链接分享
  • weixin_39718083 weixin_39718083 5月前

    好全面啊; 位运算的也总结的很好

    点赞 评论 复制链接分享

相关推荐