KMP算法

字符串匹配问题：字符串 P 是否为字符串 S 的子串？如果是，它出现在 S 的哪些位置？” 其中 S 称为主串；P 称为模式串。如下图：

最容易想到的方法：Brute-Force

暴力法的时间复杂度是$O(|P|*(|S|-|P|+1)) = O(|P|*|S|) = O(mn)$

KMP算法：

kmp算法就是尽量利用残余信息，不用逐个比字符串。其思路下面这个图就解释清楚了：

即我们可以不用一个一个往后挪这比较，而是往后挪好几个身位去比较。这个时候挪多少个位置呢？需要next数组去帮我们。

next数组中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。例如，对于”aba”，它的前缀集合为{”a”, ”ab”}，后缀 集合为{”ba”, ”a”}。两个集合的交集为{”a”}，那么长度最长的元素就是字符串”a”了，长 度为1，所以对于”aba”而言，它在PMT表中对应的值就是1。再比如，对于字符串”ababa”，它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”}，它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}， 两个集合的交集为{”a”, ”aba”}，其中最长的元素为”aba”，长度为3。

手撕LRU算法

LRU(Least Recently Used) 即最近最少使用，属于典型的内存淘汰机制。

根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”，其思路如下图所示：

该算法需要达到两个目的：①可以轻易的更新最新的访问数据。②轻易的找出最近最少未使用的数据。所以要用到哈希表+双向链表实现。利用map，获取key对应的value是O(1)，利用双向链表，实现新增和删除都是O(1)。

传统意义的LRU算法是为每一个Cache对象设置一个计数器，每次Cache命中则给计数器+1，而Cache用完，需要淘汰旧内容，放置新内容时，就查看所有的计数器，并将最少使用的内容替换掉。它的弊端很明显，如果Cache的数量少，问题不会很大， 但是如果Cache的空间过大，达到10W或者100W以上，一旦需要淘汰，则需要遍历所有计数器，其性能与资源消耗是巨大的。效率也就非常的慢了。双链表LRU的原理： 将Cache的所有位置都用双链表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。 这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，则向链表后面移动，链表尾则表示最近最少使用的Cache。当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。

LRU数据结构如下图：

根据上图我们可以分析一下：

1. 如果我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。
2. 对于某一个 key，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 val。
3. 链表显然是支持在任意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到任意一个链表节点，然后进行插入和删除。

• 版本1：自己实现循环链表存储，没有用API

  /********************不用API的版本*************************/
  /********************简单说一下思路*************************/
  //1.首先hash表用的是unordered_map来实现，用来查找key对应的node节点，所以hash表应该是[key,node]形式存储
  //2.LRUCache这个类实现双向链表的添加，删除，更新和遍历
  //3.同时这个类还要实现get和put两个功能
  //4.我这里用的是循环双向链表，因此查找链表尾端的元素为O(1)，正常的双向链表是O(n)
  //总结：最重要的就是hash表中的key对应的不是int而是一个node节点，这个要记住
  #include<unordered_map>
  #include<iostream>
  struct Node{
      int key;
      int value;
      Node* pre;
      Node* next;
      Node(){}
      Node(int k, int v):key(k), value(v), pre(nullptr), next(nullptr){}
  };
  
  class LRUCache{
  private:
      //通过key可以找到位于链表中的节点
      std::unordered_map<int, Node*> hash;
      int capacity;
      Node* head_node;
  public:
      LRUCache(int cap){
          capacity = cap;
          head_node = new Node();
          //初始化dummy_Node,next和pre都指向自己
          head_node->next = head_node->pre = head_node;
      }
      //将新来的插入双向链表头部
      void add_Node(Node* n);
      //将某个节点拿出来重新插入头部
      void update_Node(Node* n);
      //移除链表中最后一个（最久未使用）
      void pop_back();
      //输出LRU结构
      void show();
      int get(int key);
      void put(int key, int value);
  };
  
  //注意，该节点可能是新节点，也可能是已经存在的有重新入链表的节点
  void LRUCache::add_Node(Node* n){
      //表示当前节点n就是dummy的next节点，不用加入
      if(n->pre == head_node){
          return;
      }
      //将节点n插入head_node后面
      n->pre = head_node;
      n->next = head_node->next;
      head_node->next->pre = n;
      head_node->next = n;
  }
  
  void LRUCache::update_Node(Node* n){
      //表示当前节点n就是dummy的next节点，不用断掉
      if(n->pre == head_node){
          return;
      }
      n->next->pre = n->pre;
      n->pre->next = n->next;
      add_Node(n);
  }
  
  //弹出链表的最后一个，由于是循环链表，就是head_node->pre
  void LRUCache::pop_back(){
      Node* tmp = head_node->pre;
      head_node->pre = tmp->pre;
      tmp->pre->next = head_node;
      //删除unordered_map中的key
      hash.erase(tmp->key);
  }
  
  void LRUCache::show(){
      //链表中没有节点，退出
      if(head_node->next = head_node){
          return;
      }
      Node* tmp = head_node->next;
      while(tmp->next != head_node){
          std::cout<<"key:"<<tmp->key<<",vlaue:"<<tmp->value<<std::endl;
      }
  }
  int LRUCache::get(int key){
      auto it = hash.find(key);
      if(it == hash.end()){
          std::cout<<"there is no key"<<std::endl;
          return -1;
      }
      //取出key对应的node节点
      Node* node = it->second;
      update_Node(node);
      return node->value;
  
  }
  void LRUCache::put(int key, int value){
      auto it = hash.find(key);
      if(it == hash.end()){
          Node* node = new Node(key, value);
          add_Node(node);
          hash.insert({key, node});
          if(hash.size() > capacity){
              
              pop_back();
          }
      }else{
          it->second->value = value;
          update_Node(it->second);
      }
  }

• 版本2：使用deque，为什么使用deque说的很清楚

  /****************注意unordered_map的插入************/
  
  #include <iostream>
  #include <deque>
  #include <unordered_map>
  #include <list>
  
  class LRUCache{
  private:
      int capacity;
      //1.之所以用deque不用list是因为移除尾部元素的时候，deque方便
      //2.deque里面可以存储自定的node类型，也可以用pair表示，这里我用pair了
      std::deque<std::pair<int, int>> my_deque;
      //通过key找到对应key在deque中的位置
      std::unordered_map<int, std::deque<std::pair<int, int>>::iterator> hash;
  public:
      LRUCache(int cap):capacity(cap){}
      int get(int key);
      void put(int key, int value);
  };
  
  int LRUCache::get(int key){
      if(hash.find(key) == hash.end()){
          std::cout<<"there is no key"<<std::endl;
          return -1;
      }
      std::pair<int, int> tmp = *hash[key];
      my_deque.erase(hash[key]);
      my_deque.push_front(tmp);
      //更新hash表中对应key位于deque的位置
      hash[key] = my_deque.begin();
      return tmp.second;
  }
  
  void LRUCache::put(int key, int value){
      if(hash.find(key) == hash.end()){
          if(my_deque.size() >= capacity){
              //把hash表中的抹除，然后删除deque中的
              auto it = my_deque.back();
              hash.erase(it.first);
              my_deque.pop_back();
              my_deque.push_front({key, value});
              hash.insert({key, my_deque.begin()});
          }else{
              my_deque.push_front({key, value});
              hash.insert({key, my_deque.begin()});
          }
      }else{
          //更新就行
          my_deque.erase(hash[key]);
          my_deque.push_front({key, value});
          //更新hash表中key的位置
          hash[key] = my_deque.begin();
      }
  }

二分查找

二分查找算法的前提是数组时有序的，同时不能有重复元素。

二分查找难点就在于对区间的定义。区间的定义一般分为两种：左闭右闭[left, right]和左闭右开[left, right)

最重要的一点是：二分查找一般不仅仅用来查找某一个位置上的值，同时更多的是用来查找某一个范围。比如一个有序的重复数组，查找第k个等于target的值，其实本质上都是借用了二分查找的思想，只是变体不同而已，所以把二分查找好好学就行。

在知乎上看到的非常有启发的一句话：

二分查找的过程就是一个 维护 low 的过程：low指针从0开始，只在中位数遇到确定小于目标数时才前进，并且永不后退。low一直在朝着第一个目标数的位置在逼近。直到最终到达。

基本的二分搜索

左闭右闭[left, right]

• 左闭右闭[left, right]即 right = nums.length - 1
• while(left <= right)要使用小于等于，因为left==right是有意义的。
• if(nums[middle] > target)这个时候right=middle-1，因为当前这个nums[middle]一定不是target，所以肯定往左边查。

int binary_search(vector<int>& nums, int target){
    int left = 0;
    int right = nums.size() - 1;
    while(left <= right){
        int middle = left + (right - left) /2;
        if(nums[middle] > target){
            right = middle -1;
        }
        else if(nums[middle] < target){
            left = middle + 1;
        }else{
            return middle;
        }
    }
    return -1;
}

左闭右开[left, right)

• 左闭右开[left, right)即right = nums.length
• while(left < right) 因为left=right是没有意义的
• if(nums[middle] > target 的时候应该去左边找，由于是左闭右开的，因此right=middle

 int search(vector<int>& nums, int target) {
     int left = 0;
     int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
     while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
         int middle = left + ((right - left) >> 1);
         if (nums[middle] > target) {
             right = middle; // target 在左区间，在[left, middle)中
         } else if (nums[middle] < target) {
            left = middle + 1; // target 在右区间，在[middle + 1, right)中
         } else { // nums[middle] == target
            return middle; // 数组中找到目标值，直接返回下标
         }
     }
     // 未找到目标值
     return -1;
 }

边界的二分搜索

之前的都是在数组中找到一个数要与目标相等，如果不存在则返回-1。我们也可以用二分查找法找寻边界值，也就是说在有序数组中找到“正好大于（小于）目标数”的那个数。

比如说给有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。

最直观的方法就是找到target然后线性向左向右搜索，但是当数据量很大的时候，很难保证二分查找的复杂度，

因此总结了左侧和右侧边界的二分搜索

对于边界搜索的话使用左闭右开比较普遍

左侧边界

左侧边界又可以理解为小于某个数有几个

• 左闭右开写法

  int left_bound(vector<int>& nums, int target) {
      if (nums.length == 0) return -1;
      int left = 0;
      int right = nums.length(); // 注意
      
      while (left < right) { // 注意
          int mid = left + (right -left) / 2;
          if (nums[mid] < target) {
              left = mid + 1; //没问题
          } else{
              right = mid;  //这个有点意思，找到target不返回而是继续缩小边界，不断锁定左侧，最终会出现left=right
          }
      }
      //检查出界情况
      if (left >= nums.length || nums[left] != target)
          return -1;
      return left;
  }

• 左闭右闭写法

  int left_bound(int[] nums, int target) {
      int left = 0, right = nums.length - 1;
      // 搜索区间为 [left, right]
      while (left <= right) {
          int mid = left + (right - left) / 2;
          if (nums[mid] < target) {
              // 搜索区间变为 [mid+1, right]
              left = mid + 1;
          } else if (nums[mid] > target) {
              // 搜索区间变为 [left, mid-1]
              right = mid - 1;
          } else if (nums[mid] == target) {
              // 收缩右侧边界
              right = mid - 1;
          }
      }
      // 检查出界情况
      if (left >= nums.length || nums[left] != target)
          return -1;
      return left;
  }

可以看到当nums[mid] == target的时候，让mid这个位置变成了right重新开始查找。

数组越界的判断条件是指当left大于数组长度时候，肯定是错的。或者逼近的left位置上的值不等于target，说明就没有。

右侧边界

同理右侧边界可以理解为大于某个数有几个

• 左闭右开

  int right_bound(vector<int>& nums, int target) {
      if (nums.length == 0) return -1;
      int left = 0;
      int right = nums.length(); // 注意
      
      while (left < right) { // 注意
          int mid = left + (right -left) / 2;
          if (nums[mid] < target) {
              left = mid ; //没问题
          } else{
              right = mid - 1;  
          }
      }
      //检查出界情况
      if (right >= nums.length || nums[left] != target)
          return -1;
      return right;
  }

c++二分查找API

二分查找的函数有3个：

int lower_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个等于某元素 的位置。

int upper_bound(起始地址，结束地址，要查找的数值) 返回的是数值 第一个大于某个元素 的位置。

bool binary_search(起始地址，结束地址，要查找的数值) 返回的是 是否存在 这么一个数，是一个bool值。

• 函数lower_bound()

  功能：函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，因为是前闭后开因此这个时候的last会越界，要注意。

• 函数upper_bound()

  功能：函数upper_bound()返回的在前闭后开区间查找的关键字的上界，返回大于val的第一个元素位置。注意：返回查找元素的最后一个可安插位置，也就是“元素值>查找值”的第一个元素的位置。同样，如果val大于数组中全部元素，返回的是last。(注意：数组下标越界)

• 函数binary_search()

  功能： 在数组中以二分法检索的方式查找，若在数组(要求数组元素非递减)中查找到indx元素则真，若查找不到则返回值为假。

Topk两种方法

快排

快排的思路：首先看是求前k个最大的还是前k个最小的值，然后去找flag的左边或者右边。然后呢前k个，则数组的下标和k对比，如果不相等就看下标和k哪个大哪个小。如果index<k，则说明要往右边找，否则网往边找。

算法的平均复杂度是O(n)，最坏的情况是O($n^2$)，这种情况是集合已经排好序了。

时间复杂度计算方法：每次分割后的数组大小近似为原数组大小的一半，因此这种方法的时间复杂度实际上是O(N)+O(N/2)+O(N/4)+……＜O(2N)，因此时间复杂度为O(N)，但是这种方法需要提前将N个数读入，对于海量数据来说，对空间开销很大（缺点）

private int[] quickSearch(int[] nums, int lo, int hi, int k) {
    // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
    int j = partition(nums, lo, hi);
    if (j == k) {
        //返回一个数组。
        return Arrays.copyOf(nums, j + 1);
    }
    // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
    return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
}

// 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
private int partition(int[] nums, int lo, int hi) {
    int v = nums[lo];
    int i = lo, j = hi + 1;
    while (true) {
        while (++i <= hi && nums[i] < v);
        while (--j >= lo && nums[j] > v);
        if (i >= j) {
            break;
        }
        int t = nums[j];
        nums[j] = nums[i];
        nums[i] = t;
    }
    nums[lo] = nums[j];
    nums[j] = v;
    return j;
}

堆

小顶堆，最上面是最小的，求前k个最大的

大顶堆，最上面是最大的，求前k个最小的

构建思路：先随机取出N个数中的K个数，将这N个数构造为小顶堆，那么堆顶的数肯定就是这K个数中最小的数了。然后再将剩下的N-K个数与堆顶进行比较，如果大于堆顶，那么说明该数有机会成为TopK，就更新堆顶为该数，此时由于小顶堆的性质可能被破坏，就还需要调整堆

复杂度分析： 首先需要对K个元素进行建堆，时间复杂度为O(k)，然后要遍历数组,最坏的情况是，每个元素都与堆顶比较并排序，需要堆化n次 所以是O(nlog(k))，因此总复杂度是O(nlog(k));

堆排序的优势：通过对比可以发现，堆排的优势是只需读入K个数据即可，可以实现来一个数据更新一次，能够很好的实现数据动态读入并找出

海量数据情况下

比如：10亿个数中找出最大的10000个数，因为数据太大没办法全部装入内存，所以需要别的办法。

基本：最小堆，10000个数建堆，然后一次添加剩余元素，如果大于堆顶的数（10000中最小的），将这个数替换堆顶，并调整结构使之仍然是一个最小堆，这样，遍历完后，堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O（nlogn），算法的时间复杂度为O（nklogn）（n为10亿，k为10000）。

优化的方法：可以把所有10亿个数据分组存放，比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数，合并到一起在再找出最终的结果。

哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度（以时间换空间的思想）。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。

常见的常见的散列函数

• 直接寻址法

  取关键字或关键字的某个线性函数值为散列地址

• 平方取中法

  当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址

• 随机数法

  择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不等的场合

• 除留余数法

  取余，取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key % p, p <= m

怎么解决哈希冲突

一、 开放寻址法

核心思想：当发生冲突时，通过某种探测策略在哈希表中寻找下一个空闲的槽位，直到找到为止。

常用的探测方法：

1. 线性探测

   • 方法：当冲突发生时，顺序地查看哈希表中的下一个槽位（即索引值依次加1），直到找到一个空槽。
   • 公式：h(k, i) = (h'(k) + i) mod m，其中 i 是尝试次数（从0开始），m 是表大小。
   • 优点：实现简单。
   • 缺点：容易产生聚集现象。即连续出现多个被占用的槽位，导致后续插入和查找的效率下降。

2. 平方探测

   • 方法：为了解决线性探测的聚集问题，探测的步长是尝试次数的平方。即依次检查 h'(k) + 0², h'(k) + 1², h'(k) - 1², h'(k) + 2², h'(k) - 2²... 等位置。
   • 公式：h(k, i) = (h'(k) + c₁*i + c₂*i²) mod m （常见形式）
   • 优点：避免了线性探测的聚集问题，是一种折中较好的方法。
   • 缺点：不一定能探测到哈希表的所有槽位（取决于表大小m和公式选择）。

3. 双重散列

   • 方法：使用两个哈希函数。当第一个哈希函数 h1(k) 发生冲突时，使用第二个哈希函数 h2(k) 来计算探测的步长。
   • 公式：h(k, i) = (h₁(k) + i * h₂(k)) mod m
   • 优点：提供了最好的探测序列，不容易产生聚集，是开放寻址法中最好的方法之一。
   • 缺点：计算量稍大，需要设计第二个哈希函数。

开放寻址法的共同特点：

• 负载因子：开放寻址法的负载因子 α = n/m（n是元素数，m是槽位数）不能超过1，并且当负载因子较高时（例如 > 0.7），性能会急剧下降，必须进行扩容。
• 删除操作：删除元素比较麻烦。不能直接置空，通常要做“懒惰删除”的标记（标记为已删除），否则会中断后续的查找链。

二、 链地址法

核心思想：将哈希到同一槽位的所有元素存储在一个链表中。哈希表的每个槽位都是一个链表头指针。

• 方法：插入时，计算哈希值找到对应槽位，然后将新元素插入到该槽位对应的链表头部（或尾部）。查找和删除时，也是先找到槽位，然后在链表中进行遍历操作。

• 优点：

  • 实现简单，有效。
  • 负载因子可以大于1（即元素数可以超过槽位数）。
  • 是许多编程语言（如Java的HashMap，Python的dict）的标准实现方式。

• 缺点：

  • 需要额外的空间存储指针。
  • 如果某个链表变得非常长，性能会退化为O(n)。需要通过好的哈希函数或扩容来缓解。
  • 对缓存不友好，因为链表节点在内存中不是连续存储的。

优化：当链表过长时，可以将其转换为更高效的数据结构，如红黑树（Java 8的HashMap就是这么做的），以防止最坏情况下的性能恶化。

三、 其他方法

1. 再哈希法

   • 准备一组多个哈希函数。当使用第一个哈希函数发生冲突时，立即换用第二个、第三个...直到找到空位。
   • 这种方法计算成本较高，不如双重散列常用。

2. 建立公共溢出区

   • 将哈希表分为两部分：主表和溢出区。
   • 所有发生冲突的元素都被放入溢出区中。
   • 查找时，先到主表中查找，如果没找到，再到溢出区中顺序查找。
   • 这种方法实现简单，但当溢出区元素较多时，性能会下降。

Hash表的扩容

什么时候扩容？

当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值(即当前数组的长度乘以加载因子的值的时候)，就要自动扩容了。

扩容

在hash表的实现中，我们一般会控制一个装载因子，当装载因子过大的时候，会考虑扩容（resize）

如果一个hash表中桶的个数为 size , 存储的元素个数为used .则我们称 used / size 为负载因子loadFactor . 一般的情况下，当loadFactor<=1时，hash表查找的期望复杂度为O(1). 因此。每次往hash表中加入元素时。我们必须保证是在loadFactor <1的情况下，才可以加入。

当我们加入一个新元素时。一旦loadFactor大于等于1了，我们不能单纯的往hash表里边加入元素。Hash表中每次发现loadFactor==1时，就开辟一个原来桶数组的两倍空间（称为新桶数组），然后把原来的桶数组中元素所有转移过来到新的桶数组中。注意这里转移是须要元素一个个又一次哈希到新桶中的。

缺点：容量扩张是一次完毕的，期间要花非常长时间一次转移hash表中的全部元素。这样在hash表中loadFactor==1时。往里边插入一个元素将会等候非常长的时间。

redis中的dict.c中的设计思路是用两个hash表来进行进行扩容和转移的工作：当从第一个hash表的loadFactor=1时，假设要往字典里插入一个元素。首先为第二个hash表开辟2倍第一个hash表的容量。同一时候将第一个hash表的一个非空桶中元素所有转移到第二个hash表中。然后把待插入元素存储到第二个hash表里。继续往字典里插入第二个元素，又会将第一个hash表的一个非空桶中元素所有转移到第二个hash表中，然后把元素存储到第二个hash表里……直到第一个hash表为空。