数据结构与算法

发表于 更新于 分类于

本文介绍常用的数据结构和算法，并给出每种数据结构和算法对应的经典习题，详细的解答可以参考下一篇习题解。本文的目录如下：

  1. 基础的数据结构
  2. 高级数据结构
  3. 排序算法
  4. 递归和回溯算法
  5. 深度优先遍历和广度优先遍历算法
  6. 动态规划
  7. 二分搜索和贪婪算法

基础数据结构

数组、字符串

  • 数组的优点：简单、根据下表查询O(1)
  • 缺点：分配连续空间、查找、添加、删除某个元素时必须遍历
  • 例子：242有效的字母异位词
    思路：由于字母都是小写且只有26个，因此可以用一个长度为26的数组对每个单词中字母出现的顺序计数，判断是否一致。或者第一个单词累加，第二个减，看这个数组的每个字母的计数是否为0.

链表

  • 优点：灵活分配内存，删除、添加元素O(1)

  • 缺点：不能locate

  • 解题技巧：

  • 快慢指针（有时需要用三个指针）：【翻转、倒数k个元素、寻找中间位置元素、判断链表是否有环】

  • 构建虚假的链表头：两个排序链表整合、将链表奇数偶数分离
    例题：k个一组翻转链表
    ##栈###

  • 特点：后进先出LIFO

  • 算法基本思想：用一个单链表实现，只关心上一次操作，处理完上一次的操作后能在O(1)的时间内查找到更前一次的操作。（不用数组的原因：数组的长度变化不好控制）
    例题：20.有效的括号 739.每日温度

    队列

  • 特点：先进先出

  • 算法思想：双链表

  • 常用场景：广度优先遍历
    ###双端队列####

  • 特点：双链表、头尾两端可以在O(1)的时间进行查看、添加和删除

  • 常用场景：实现长度动态变化的窗口或者连续区间

  • 例题：239.滑动窗口的最大值
    ##树###

  • 树的共性：结构直观、通过树的问题考察递归算法

  • 常考的树的形状：普通二叉树、平衡二叉树、完全二叉树、【二叉搜索树】、四叉树、多叉树。（特殊的树：红黑树、自平衡二叉搜索树不必花费太多时间）

  • 操作：遍历：前序（搜索、建立二叉树）、【中序】（二叉搜索树）、后序（需要利用左右子树信息）掌握递归、非递归写法。
    例题：230.二叉搜索中第k小的元素

#高级数据结构##

  • 优先队列：常见考点、面试中可以直接使用
  • 图：广泛运用的数据结构，大数据：社交网络、地图
  • 前缀树：难题、能够熟练实现及运用
  • 线段树和树状数组：应用场合比较明确：在图片中修改像素的颜色、求解任意矩形区间的灰度平均值需要用二位的线段树。

##优先队列###

  • 与普通队列区别：每次取出的元素是队列中优先级最高的，优先级别可以自己定义
    常用场景：从杂乱无章的数据中按照一定的顺序（优先级）筛选数据。例如：找出前k大的数。

  • 本质：二叉堆结构，利用数组实现完全二叉树

  • 特性：

    • 数组里的第一个元素拥有最高优先级，给定一个下标i，那么对于array[i]而言。 父节点下标为(i-1)/2;
    • 左侧子节点为2*i+1;右侧子节点下标为2*i+2;每个元素的优先级必须高于它两侧子节点。

  • 操作：向上筛选；向下筛选；

    • 向上筛选：新的数据加入到优先队列后对数据进行重新筛选，高度为树的高度。复杂度为O(logk)
    • 向下筛选：堆顶元素被取出，将最后一个元素放入堆顶，重新筛选。复杂度为O(logk)
    • 优先队列初始化：O(n)

  • 例题：347. 前k个高频元素

##图###

  • 基础知识：

    • 图的存储和表达：邻接矩阵、邻接表

  • 算法：

    • 图的遍历：深度遍历、广度遍历（重要）
    • 二部图的检测：树的检测、环的检测：有向图、无向图
    • 联合-查找算法（union-find）
    • 拓扑排序
    • 最短路径算法
    • 连通性相关算法
    • 图的着色、旅行商问题等

  • 例题：785.判断二分图
    ##前缀树（字典树）###

  • 前缀树广泛应用于字典查找中

    • 字典查找：方法一：暴力搜索O(MN)；方法二：前缀树O(M)

  • 经典应用：在搜索框输入时，会列出以搜索词开头的相关搜索词；汉语拼音输入法；

  • 重要性质

    • 每个节点至少包含两个属性：children和isEnd；children是数组或者集合，包含每个分支中包含的所有字符串；isEnd表示该节点是否为某个字符串的结尾。
    • 前缀树的根节点是空（只关心根节点的children）
    • 除了根节点，其他所有节点都有可能是单词的结尾，叶子节点一定都是单词的结尾

  • 操作

    • 创建：遍历输入的字符串，对每个字符串的字符进行遍历；从根节点开始，将每个字符加入节点的children字符集中；如果字符集已经包含则跳过；如果当前字符是字符串的最后一个，则isEnd标记为真。
    • 搜索：从根节点出发，逐个匹配输入的前缀字符；如果遇到则向下一层继续搜索；如果没有则返回。

  • 例题

  • 212.单词搜索

##线段树###

  • 线段树出现的原因：对数组数值频繁更新且的任意区间元素求和的时候需要O(N)的时间，而线段树只需要O(logN)
  • 线段树的概念：按照二叉树形式存储数据，每个节点保存的是数组里某一段的总和。
  • 例题：315.计算右侧小于当前元素的个数：将下标设为数值区间，节点设置为在这个区间的数字个数；遍历数组并更新数中节点的数值；查找的时候从根节点向下遍历即可。
  • 题目特征：区间

##树状数组###

  • 树状数组出现原因：对数组频繁更新数组的数值且求前k个元素的总和；线段树O(logN);树状数组也可以在O(logN)时间实现，但是代码实现更简单些。
  • 基本特征：
    • 用数组表示多叉树的结构；优先队列是用数组表示完全二叉树，二树状数组是多叉树。
    • 树状数组的第一个元素是空节点
    • 如果节点tree[y]是tree[x]的父节点，那么需要满足y = x - (x &(-x))
  • 例题：308.二维区域和检索-可变：求动态变化矩阵任意子矩阵里数的总和。

#排序算法#

基本的排序算法【简单直接、要求没有bug】：

  • 冒泡排序
  • 插入排序

常考的排序算法【解决大部分关于排序问题的关键】：

  • 归并排序
  • 快速排序
  • 拓扑排序

其他【掌握好思想，开阔思路】：

  • 堆排序
  • 桶排序

##冒泡排序##

void BubbleSort(int[] nums)
{
    bool hasExchange = true;
    for (int i=0; i<nums.length-1&& hasExchange;i++)
    {
        hasExchange = false;
        for (int j=0;j<nums.length-1-i;j++)
        {
            if (nums[j]>nums[j+1])
            swap(nums,j,j+1);
            hasExchange =  true;
        }
    }
}
  • 空间复杂度O(1)；时间复杂度O(N^2)
  • 算法稳定

##插入排序

void SelectSort(int[] nums)
{
    for(int i = 1,i<nums.lenth;i++)
    {
        current = nums[i];
        for(j = i-1;j>=0&&nums[j]>current;j--)
        {
            nums[j+1] = nums[j];
        }
        nums[j+1] = current;
    }
}

##归并排序##

void MergeSort(int[] A,int low, int high)
{
    if (low>=high) return;
    int mid = (low+high)/2;
    MergeSort(A,low,mid);
    MergeSort(A,mid+1,high);
    merge(A,low,mid,high);
}


void merge(int []nums,int low, int mid, int high)
{
    int[] copy = nums.clone();
    int k=low, i=low, j=mid+1;
    while(k<=high)
    {
        if(i>mid){nums[k++]=copy[j++];}
        else if(j>high){nums[k++]=copy[i++];}
        else if(copy[j]<copy[i]){nums[k++]=copy[j++];}
        else {nums[k++]=copy[i++];}
    }
        
}

空间复杂O(n)

##快速排序##

void QuickSort(int[] nums,int low, int high)
{
    if (low>=high) return;
    int p = partition(nums,low,high);
    QuickSort(nums,low,p-1);
    QuickSort(nums,p+1,high);
}
void partition(int[] nums,int low, int high)//获得基准值
{
    swap(nums,randRange(low,high),high);//随机取一个数作为基准值，放在high
    int i,j;
    for(int i=low,j=low;j<high;j++)//每个数和基准值比较，如果当前值比基准值小，将其放在指针i所在的位置
    {
        if(nums[j]<=nums[high])
        swap(nums,i++,j);
    }//循环完毕之后，i左边的数都比基准值小
    swap(nums,i,j);//将基准值放在i的位置，i之后的数都比基准值大
    return i;//返回基准值的位置
}

空间O(logN)
例题：215

##拓扑排序##
排序前提：有向图、没有环

void TopSort()//图的广度优先搜索
{
    //adj表示图，indegree表示入度
    Queue<Integer> q = new LinkedList();
    for (int v=0; v<V; v++)//将入度为0的顶点加入队列
    {
        if (indegree[v]==0) q.add(v);
    }
    while (!q.isEmpty())
    {
        int v= q.poll();//从队列中取出顶点
        print(v);
        for(int u=0;u<adj[v].length;u++)//将和这个顶点相邻的定点减1
        {
            if(--indegree[u] == 0)//如果相邻的顶点入度为0，则加入队列
            {
                q.add(u);
            }
        }
    }
}

时间复杂度O(N):统计顶点入度，每个顶点遍历一次

#递归、回溯算法#

递归的基本性质：调用函数本身，把大规模问题不断缩小再进行推导
回溯：利用递归的性质，从问题起点出发不断尝试，返回一步甚至多步再做选择，直到抵达终点

##递归算法（自顶向下）##
使看似复杂的问题变得简洁和易于理解
算法思想：

  • 将问题规模变小（把要实现的递归函数看成已经实现好的）

  • 利用小规模问题中得到的结果（解决这个子问题）

  • 结合当前情况得出最终结果（根据子问题的解得到现在问题的答案）
    经典例子：汉诺塔问题

    void hano(char A, char B, char C, int n)
    {
    if (n>0){
    hano(A,C,B,n-1);
    move(A,C);
    hano(B,A,C,n-1);
    }
    }

递归写法结构：

function fn(n)
{
//第一步，判断输入或者状态是否非法
    if(input/state is invalid){
    return;
    }
    
//第二步，判断递归过程是否应该结束
    if(match condition){
    return some_value;
    }
//第三步，缩小问题规模，递归调用
    result1 = fn(n1);
    result2 = fn(n2);
    ...
//第四步，整合结果
return combine(result1,result2);
}

例题：91.解码方法；247.中心对称数II
递归的时间复杂度分析：

  • 迭代法：比如汉诺塔问题，T(n)= 1+2T(n-1)+1= 2T(n-1)+O(n)=…=2*2^n
  • 公式法
    对形如T(n) = aT(n/b) + f(n)的递归方程，算法复杂度如下：
    递归的算法复杂度
    • 举例1:
      T(n) = 2T(n/2) + n,
      a=2,b=2,f(n)=n;
      $n^{log_ba}=n^1=n$, 符合第二种情况，时间复杂度为O(nlogn)
    • 举例2：
      T(n) = 2T(n/4) + 1
      $n^{log_42}=sqrt(n)$
      n>1,sqrt(n)>1, 时间复杂度为O(sqrt(n))
    • 举例3：
      T(n) = 3T(n/2) + $n^2$
      $n^{log_23}=n^{1.48}<n^2$
      故，时间复杂度为$O(n^2)$

回溯算法

回溯算法和暴力算法的区别是，回溯算法一步一步向前试探，对每一步试探的结果进行评估，再决定是否继续。

解决问题的模板：

  1. 判断当前情况是否非法，如果非法就立即返回
  2. 看看当前情况是否已经满足条件？如果是，就将当前结果保存并返回
  3. 在当前情况下遍历所有可能出现的情况，并进行递归
  4. 递归完毕后，立即进行回溯，回溯的方法就是取消前一步进行的尝试

例题：39.组合总和；52.N皇后II

时间复杂度，以N皇后问题为例：

- 假设backtracking函数的执行时间是T(n)
- 首先每次必须遍历所有列，一共有n列，每一列都要对是否冲突进行检查，最多n列，时间复杂度$O(n^2)$
- 然后，递归尝试每种摆放，每次放好一个，规模-1，执行时间为T(n-1)
- 最后，得到表达式$T(n)= n*T(n-1)+O(n^2)$，用迭代法展开即可得到O(T(n))=n!

其他

  • 二叉树的定义和遍历
  • 归并排序、快速排序
  • 动态规划
  • 二分搜索
  • 数学基础：等差数列、等比数列

深度优先和广度优先

DFS

DFS解决的是连通性的问题，即给定起始点和终点，判断两点之间是否连通。连通的路径有很多条，找出一条即可。

例题：走迷宫(在矩阵中设置起点和终点，以及墙)

实现：深度优先有两种实现方法：递归和非递归。非递归方法直接用栈来实现。

复杂度分析：邻接表O(V+E)；邻接矩阵$O(V^2)$

寻找最短路径：暴力法，找出所有路径，比较长短； 优化：一边寻找目的地，一边记录和起始顶点的距离，当发现从某个方向用的步数更少，则更新到这个点的步数，如果步数更多，则不用继续尝试。

BFS

广度优先搜索一般用来解决最短路径问题，从起始点出发，一层一层遍历，每层结点到起始点步数相同，找到目的地即可结束。

双端BFS是同时从起点和终点开始进行的广度优先搜索，可以大大提高搜索的效率。比如，社交网络中判断两个人通过多少人能够认识对方，从认识的人较少的一方开始遍历。

实现：广度优先遍历用队列进行实现。

复杂度分析：邻接表 O(V+E); 邻接矩阵 O(V^2)

例题：迷宫问题中允许打通3堵墙，应该怎么找到最短路径？

  • 暴力法：首先枚举所有的拆墙方法，假设共有K堵墙，最多允许拆3堵，有3种方式，可以不拆、只拆一堵、两堵和三堵。那么一共有C(0,K)+C(1,K)+C(2,K)+C(3,K),约为K^3,若允许拆w堵墙，则共有k^w种方式。在这么多情况下再分别进行BFS，整体复杂度为O(n^2*k^w)。

  • 优化：允许打通一堵墙的情况下，分身为两个人进行BFS搜索，复杂度为2O(n^2);允许打通两堵墙的情况下，分身为3个人，复杂度为3O(n^2)……如果第一个人又遇到一堵墙，不需要再次分身，而是记录下来让第二个人搜索，将这个点放入队列即可。4个分身在各自的平面立面搜索，利用三维矩阵记录每个层面的点即可。