基础算法笔记

7/5/2026

基本概念
插入排序
各种问题
求两个整数集合的交集
一个二进制，去掉最低位的1
计算32位无符号整数二进制中1的个数：
编辑距离
和最大的连续子序列：
最长递增子序列：
最长公共子串&最长公共子序列
计算一个正整数各位相加，一直到只有一位时的值：
基于比较的排序算法下界的证明
图
概念

基本概念

插入排序

除了直接的插入排序外，还可以将二分查找应用在插入排序里面，可以在寻找新元素该插入的位置时，减少查找的次数。

希尔排序，利用插入排序在有序的情况下O(n)的特性，将列表分组进行排序，保证列表的元素越来越有序，可以达到O(nlogn)的时间复杂度

各种问题

p问题: 存在多项式时间算法的问题 (P：polynominal，多项式), 例如冒泡排序，时间复杂度为 $O(n^2)$ , 是多项式时间的复杂度- np问题: 能在多项式时间内验证(猜)得出一个正确解的问题(NP: Nondeterministic polynominal，非确定性多项式)，不知道这个问题是不是存在多项式时间内的算法，所以叫non-deterministic非确定性，但是我们可以在多项式时间内验证并得出这个问题的一个正确解- npc问题: 它是一个np问题，所有np问题都能在多项式时间内转化为他，则称该np问题为npc问题 (NPC: Nondeterministic polynominal complete), 又叫NP完全问题- nph问题: 它不是一个np问题，所有np问题都能在多项式时间内转化为他NP Hard问题## 案例

求两个整数集合的交集

遍历，对于集合A中的每个元素，去集合B中找，找到就把该元素取出来，并在两个集合中去掉。这样做，时间复杂度为O(N^2)，很慢，但是是最容易想到的先排序，然后从头开始比较，找到相同的元素，作为交集的元素定义一个大数组，集合中的整数作为数组的下标，值为该整数的个数，没有则为0，从头扫两个数组，值不为0的下标则为交集。改进一下，可用HASH，key为集合中的整数，VALUE为该整数的个数### 判断某字符串的所有字符是否都不同先清楚，是不是ASCII码，如果是，顶多256个字符直接双重循环。O(n^2)用二分查找树。不断地插入，遇到相同的，则说明有相同，否则继续插入，O(logN)开辟一个数组。按照编码，如果是ASCII码，长度为256即可，初始化为0，字符减去’a’的值作为下标，标为1，如果有相同，则会多次标为1使用位图。如果字符串全是小写字母，则只需要使用一个32位整数，将字符减去’a’的值所在的位，置为1，如果有相同，则会多次标为1### 摩尔投票法应用于选出投票数最多的一个或多个元素。例如，找出数组中出现次数最多的元素（众数）。把每个元素的出现，都看作是对目前假设的众数的投票，如果相同则投票数加1，否则减1，如果假设的众数投票数为0，当前元素又和众数不同，则把当前元素看成是众数，最后找到众数。

一个二进制，去掉最低位的1

n = n & (n - 1)

计算32位无符号整数二进制中1的个数：

平行算法：将相邻两位中1的个数相加 217（11011001）

int BitCount4(unsigned int n) 
{ 
    // 每1位之间对1的个数相加
    n = (n &amp; 0x55555555) + ((n &gt;&gt; 1) &amp; 0x55555555) ; 
    // 上面计算出来的n，第2位保存了1的个数，下面每两位之间对1的个数相加
    n = (n &amp; 0x33333333) + ((n &gt;&gt; 2) &amp; 0x33333333) ; 
    // 每四位之间对1的个数相加
    n = (n &amp; 0x0f0f0f0f) + ((n &gt;&gt; 4) &amp; 0x0f0f0f0f) ; 
    // 每8位之间对1的个数相加
    n = (n &amp; 0x00ff00ff) + ((n &gt;&gt; 8) &amp; 0x00ff00ff) ; 
    // 每16位之间对1的个数相加
    n = (n &amp; 0x0000ffff) + ((n &gt;&gt; 16) &amp; 0x0000ffff) ; return n ; }

编辑距离

三种距离消耗：插入一个字符删除一个字符替换一个字符用一个矩阵来记忆各个子状态的三种距离消耗。如ab和ccab两个字符串，矩阵的演变为： 0 1 2 3 4 1 2 a和c不等，替换距离（对角）为0 + 1 = 1，插入距离（上面）为1 + 1 = 2，删除距离（下面）为1 + 1 = 2，3个距离最小为1，变成下面 0 1 2 3 4 1 1 2 a和c又不等，替换距离为1 + 1 = 2，插入距离为2 + 1 = 3，删除距离为1 + 1 = 2，最小为2，变成下面 0 1 2 3 4 1 1 2 2 a和a相等，替换距离为2 + 0 = 2，插入距离为3 + 1 = 4，删除距离为2 + 1 = 3，最小为2，变成下面 0 1 2 3 4 1 1 2 2 2 一直到最后为 0 1 2 3 4 1 1 2 2 3 2 2 2 3 2 所以最小的编辑距离为2，即在前面插入2个字符

//
// 计算字符串距离
// 使用编辑距离算法
//
int get_dist(const std::string&amp; a, const std::string&amp; b) {
  int a_len = a.size();
  int b_len = b.size();
  if (a_len == 0) {
    return b_len;
  }
  if (b_len == 0) {
    return a_len;
  }
  std::vector&lt;std::vector&lt;int&gt;&gt; dist(a_len + 1,
      std::vector&lt;int&gt;(b_len + 1, 0));
  for (int i = 0; i &lt; dist.size(); ++i) {
    dist[i][0] = i;
  }
  for (int i = 0; i &lt; dist[0].size(); ++i) {
    dist[0][i] = i; 
  }
  for (int i = 1; i &lt; dist.size(); ++i) {
    for (int j = 1; j &lt; dist[i].size(); ++j) {
      int cost = 0;
      if (a[i - 1] != b[j - 1]) {
        cost = 1;
      }
      int replace_cost = dist[i - 1][j - 1] + cost;
      int insert_cost = dist[i - 1][j] + 1;
      int delete_cost = dist[i][j - 1] + 1;
      dist[i][j] = get_min(replace_cost, insert_cost, delete_cost);
    }
  }
  return dist[a_len][b_len];
}
// 
// 计算3个整数中最小值
//
inline int get_min(int a, int b, int c) {
  int min = a &lt; b ? a : b;
  return c &lt; min ? c : min;
}

和最大的连续子序列：

例如：5, -6, 4, 2 用一个变量maxSum记住当前和最大的连续子序列的和，用两个变量begin和end记住当前和最大的连续子序列的起始位置和截止位置。用一个变量next_begin记住下一个和最大的子序列的起始位置。从头扫这个序列，用一个变量记住当前sum，如果比maxSum要大，那说明目前的状态下的子序列的和是最大的，更新maxSum，更新起始位置为next_begin和截止位置为当前位置。如果当前sum小于0，说明当前sum对后面求的子序列是拖后腿作用，这种情况下，把当前sum更新为0，并记录下一个可能是和最大的子序列的起始位置next_begin为当前位置加1，等到真正发现下一个子序列的和是最大的时候，再更新到begin。扫到最后一个元素，最后maxSum就是最大的和，begin和end就是这个子序列的起始位置和截止位置。

最长递增子序列：

方法1：O（N^2）复杂度的动态规则比如1，5，8，2，3，4 用一个数组len保存以某个元素为末尾元素时递增子序列的长度，用一个数组preindex保存某个元素为递增子序列的末尾元素时前一个元素的下标。对于每个元素，从第一个元素开始和它做比较，如果比它小，则len数组中当前元素的值加1，其实就是长度加1，前一个元素的下标更新为当前和它比较的那个元素的下标。上面的处理完成后，找出作为末尾元素最大的那个元素的下标，然后利用下标数组，一个一个打印出来前面的元素

最长公共子串&最长公共子序列

比如acd和abcd，用一个矩阵来记忆： “” a b c d “” 0 0 0 0 0 a 0 1 0 0 0 c 0 0 0 1 0 d 0 0 0 0 2 要求acd和abcd的最长公共子串，只需要知道ac和abc的最长公共子串，如果d和d不等，因为要连续，所以，目前扫到现在，公共子串长度为0，如果相等，则加1，但是不一定是最长的，所以需要记忆最长的长度和下标。同样的两个字符串，如果是最长公共子序列，矩阵为： “” a b c d “” 0 0 0 0 0 a 0 1 1 1 1 c 0 1 1 2 2 d 0 1 1 2 3 要求acd和abcd的最长公共子序列，如果d和d相等，则为ac和abc的最长公共子序列的长度加1，如果不等，则要看acd和abc的，或者ac和abcd的，取两者中最长的一个，但是不一定是所有的最长的，所以需要记忆最长的长度和下标，以及用的哪种情况，因此还需要另外一个矩阵来记忆使用的是哪种情况。

计算一个正整数各位相加，一直到只有一位时的值：

38 => 3 + 8 = 11 => 1 + 1 => 2 假设输入的数字是一个5位数字num，则num的各位分别为a、b、c、d、e。有如下关系：num = a * 10000 + b * 1000 + c * 100 + d * 10 + e 即：num = (a + b + c + d + e) + (a * 9999 + b * 999 + c * 99 + d * 9) 因为 a * 9999 + b * 999 + c * 99 + d * 9 一定可以被9整除，因此num模除9的结果与 a + b + c + d + e 模除9的结果是一样的。对数字 a + b + c + d + e 反复执行同类操作，最后的结果就是一个 1-9 的数字加上一串数字，最左边的数字是 1-9 之间的，右侧的数字永远都是可以被9整除的。

基于比较的排序算法下界的证明

n个元素排序，n个元素的全排列为n!种
排序的过程中，每确定一个元素在另外一个元素的左边，就把排列的种数去掉了一半，变成 n! / 2
排序结束时，排列的种数就变成了1，所以经过k个步骤之后，排列变成了1, n! / 2^k = 1
所以，n! = 2^k, log(n!) = k, k = log(n^n) = nlog(n)

图

概念

简单路径

是一条没有重复顶点的路径

简单环除了起点和终点重复，整个环不含重复边和顶点
连通图

如果任意一个顶点都存在一条路径到达另一个任意顶点，这幅图就称为连通图

生成树

连通图的生成树是它的子图，含有图中的所有顶点，并且是一棵树

拓扑排序

给定一幅有向图，将所有的顶点排序，使得所有的有向边均从前面的元素指向后面的元素

Hash解决冲突的方法：拉链法。每个hash(key)为数组的下标，数组的值为一个指针，指向一个链表，链表的节点有两个元素，一个是key，一个是value。当不同的key经过hash函数计算后，res = hash(key)，得到相同的res时，则从res为下标指向的链表中寻找，找到那个key值相同的节点，取出里面的value，找不到返回默认值，这就完成了哈希的get操作。set操作，一样寻找，找到一样的key，则更新value，没找到，则往后面加一个节点。线性探测法。使用两个数组，长度都为n，下标都为哈希函数hash(key)的结果，一个存key，一个存value。对于get操作，res = hash(key)后，如果用res定位到的key数组的key值一样，则定位到的value就是返回的value，如果不一样，则res = (res + 1) % n, 按下标往下找，直到找到为止，如果遍历完整个数组都找不到，则返回默认值。对于set操作，经hash函数计算后，如果没有冲突，直接给两个数组赋值，如果有，则res = (res + 1) % n, 往下查，找到空的地方插入。线性探测法是开放地址法的一种，如果不是每次加1，而是1^2, (-1)^2, 2^2, (-2)^2……这种，则是二次探测法，另外，还有伪随机数探测法，每次加的是一个伪随机数。公共溢出表法。建立另外一个哈希表，发生冲突的都放到这个溢出表中，最坏情况下，原表只有一个元素，溢出表堆满了，而且不断要扩展空间。

树的前序遍历对应二叉树的前序遍历，树的后序遍历和二叉树的中序遍历一致

稀疏矩阵，使用三元组存储，会节省大量内存空间。它就是一个一维数组，元素的类型是一个结构体，结构体有3个成员：行，列，值。

hash里面的装填因子概念：装填因子a = 要放进去的对象个数 / 准备的位置个数

满二叉树：一棵深度为 k，且有 2k - 1 个节点称之为满二叉树

完全二叉树：深度为 k，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中序号为 1 至 n 的节点对应时，称之为完全二叉树