• 学习笔记

  算法题的作业每道题为一个md文件，每道题包含一种或多种解法，每种解法都包含解题思路、代码实现和复杂度分析。

  第16课 位运算

  一、位运算符

  机器里的数字表示方式和存储格式是二进制。

  位运算符包括：左移（<<）、右移（>>）、按位或（|）、按位与（&）、按位取反（~）、按位异或（^）。

  二、逻辑移位与算术移位

  逻辑移位是指逻辑左移和逻辑右移，移出的空位都用0来补。

  算术移位需要分有符号型值和无符号型值。

  对于无符号型值，算术移位等同于逻辑移位。

  而对于有符号型值，算术左移等同于逻辑左移，算术右移补的是符号位，正数补0，负数补1。

  第17课 布隆过滤器和LRU缓存

  一、布隆过滤器

  有时候只需要判断元素是否存在，因此使用一种占用空间小的数据结构。

  布隆过滤器是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。

  布隆过滤器的优点是空间效率和查询时间都远超过一般的算法，缺点是有一定的误识别率和删除困难。

  如果一个元素对应的二进制位都是1，则该元素可能在索引中（不能确定）。如果一个元素对应的二进制位包含0，则该元素一定不在索引中。

  布隆过滤器的作用是在最外层的快速查询的缓存，排除一定不在索引中的元素。如果一个元素可能在索引中，则需要进一步查询判断是否存在（例如在数据库表中查询）。

  二、LRU缓存

  两个要素：大小、替换策略。

  使用哈希表和双向链表实现。

  查询、修改、更新的时间复杂度都是O(1)。

  第18课 排序算法

  一、排序算法分类

  排序算法可以分成两类，比较类排序和非比较类排序。

  1. 比较类排序

  通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(n log n)，因此也称为非线性时间比较类排序。

  比较类排序的例子：交换排序（冒泡排序、快速排序）、插入排序（简单插入排序、希尔排序）、选择排序（简单选择排序、堆排序）、归并排序（二路归并排序、多路归并排序）。

  2. 非比较类排序

  不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

  非比较类排序的例子：计数排序、桶排序、基数排序。

  二、初级排序——O(n^2)

  • 选择排序（Selection Sort）

    每次找最小值，然后放到待排序数组的起始位置。

  • 插入排序（Insertion Sort）

    从前到后逐步构建有序序列；对于未排序数组，在已排序序列中从后向前扫描，找到相应位置并插入。

  • 冒泡排序（Bubble Sort）

    嵌套循环，每次查看相邻的元素，如果逆序，则交换。

  三、高级排序——O(n log n)

  • 快速排序（Quick Sort）

    数组取标杆pivot，将小元素放pivot左边，大元素放pivot右边，然后依次对左边和右边的子数组继续快排，以达到整个序列有序。

  • 归并排序（Merge Sort）

    1. 把长度为n的输入序列分成两个长度为n/2的子序列；
    2. 对这两个子序列分别采用归并排序；
    3. 将两个排序号的子序列合并成一个最终的排序序列。

  • 堆排序（Heap Sort）

    1. 数组元素依次建立小顶堆；
    2. 依次取堆顶元素，并删除。

  四、作业：实现初级排序代码

  此处的代码使用Java。

  #选择排序
  import sort
  def selectionSort(data):
     for i in range(len(data)):
         min_index = i
         for j in range(i,len(data)):
             if data[j] < data[min_index]: min_index = j
         sort.exch(data, i, min_index)
  #出入排序
  def insertionSort(data):
     for i in range(1, len(data)):
         temp = range(i)
         temp.reverse()
         for j in temp:
             if data[j+1] < data[j]:
                 sort.exch(data, j, j+1)
  #冒泡排序
  def bubbleSort(data):
     for i in range(len(data)-1):
         for j in range(len(data)-i-1):
             if data[j] > data[j+1]:
                 sort.exch(data, j, j+1)