Go after
0%

数据结构和算法

发表于 更新于 分类于 ， 阅读次数：
本文字数： 6.6k 阅读时长 ≈ 6 分钟

数据结构和算法

数据结构和算法

背景

代码效率-时间复杂度与空间复杂度

代码运行效率用复杂度衡量。

代码运行消耗时间和空间。

现实中的例子：

  • 汽车在有红绿灯的十字路口通行。红绿灯时汽车等待，消耗时间。
  • 汽车在建有立交桥的十字路口通行，不用等待，立交桥消耗空间。

时间、空间消耗和输入量密切相关，无法直接定量衡量。为了更客观的评判时间消耗和空间消耗，我们关注输入量与时间、空间的关系。即时间复杂度、空间复杂度。

时间复杂度与代码结构密切相关，空间复杂度与数据结构密切相关。

不同时间复杂度的计算次数例子：100万条数据的处理

  • O(n²)，10的十二次方
  • O(n)，10的六次方
  • O(log n)，20次

时间无价，空间有价。

数据结构：连接时间和空间复杂度

代码优化：

  1. 暴力解法
  2. 剔除无效计算、无效存储。（递归、回溯、分治（包括二分法）、排序算法、查找算法、贪婪、动态规划）
  3. 使用数据结构，将时间复杂度向空间复杂度转移

代码的时间复杂度和常量系数无关，代码的执行时间与常量系数有关。

复杂度估算

复杂度是关于输入数据量n的函数。

  • 我们假定输入量为n，代码执行n次，复杂度为O(n)；

  • 我们假定输入量为n，代码执行k常数次，与输入量无关，则复杂度为O(1)；

  • 不同数量级的多项复杂度相加时，去数量级高的值。O(n²)+O(n) = O(n²)

常见的复杂度：

  • 顺序执行，O(1);
  • 一层for循环，O(n);
  • 两个顺序执行for循环，O(n);
  • 两层嵌套for循环，O(n²);
  • 二分查找，即二分分而治之，O(log n);

数据操作

  • 遍历

  • 增

    • 中间增加，元素位置顺序改变
    • 末尾增加

  • 删

    • 中间删除，元素位置顺序改变
    • 末尾删除

  • 查

    能否在数据结构中找到此元素。

    • 基于位置查询（索引、下标）
    • 基于数值特征查询（数值相等）

算法分析

算法：递归、分治（二分是重点）、回溯、贪婪、动态规划

数据结构选择

分析数据处理顺序、数据操作，选择不同的数据结构。

不同数据结构特点[参考，按住Control点我](# 各类数据结构对比)

Java 数据结构API

数组

1
2
3
4
5
6
7
8
9
10
// 复制数组
int[] arr = new int[]{1,2};
int[] ints = Arrays.copyOf(arr, arr.length);

// 字符串转字符数组
String word = "abc";
char[] wordChars = word.toCharArray();

// 输出数组内容
Arrays.toString(arr);

Map

1
2
3
4
5
6
7
8
9
10
Map<String,String> map = new HashMap();
map.put("a","1");
map.get("a");
map.size();
map.containsKey("a");
map.remove("a");
// 遍历
for (Map.Entry<String,String> entry : map.entrySet()) {
	System.out.println(entry.getKey()+ map.get(entry.getKey()));
}

双端队列-链表

LinkedList

第一个（头） 最后一个（尾）
插入 offerFirst(e) offerLast(e)
删除 pollFirst() pollLast()
获取元素 peekFirst() peekLast()
入队 出队（拿最大元素
数组线性结构 O(1) O(n)
链式线性结构 O(n) O(1)
二叉堆 O(logn) O(logn)

优先队列（二叉堆）PriorityQueue

1
2
3
4
5
6
7
8
// 初始化大小为k的元素为int[]的小根堆（顶为堆中数组元素int[1]最小）
PriorityQueue<int[]> priorityQueue = new PriorityQueue(k, new Comparator<int[]>() {
    @Override
    public int compare(int[] newValue, int[] pileTop) {// 小值放到堆顶
    	return newValue[1] - pileTop[1];
    }
});

数据结构

数据的组织形式。对数据组织成一定的结构。

1.线性表-链表

介绍

n 个相同特性数据元素的有限序列。

在链表中存储的数据元素也叫作结点，一个结点存储的就是一条数据记录。每个结点的结构包括两个部分：

  • 第一是具体的数据值；
  • 第二是指向下一个结点的指针。

在链表的最前面，通常会有个头指针用来指向第一个结点。对于链表的最后一个结点，由于在它之后没有下一个结点，因此它的指针是个空指针。

存储结构

数据操作

新增

有一个链表，它存储了 10 个同学的考试成绩。现在将一个同学的成绩插入到第4个位置。

链表在执行数据新增的时候非常容易，只需要把待插入结点的指针指向原指针的目标，把原来的指针指向待插入的结点，就可以了。

p s(带插入) t

1
2
s.next = p.next;
p.next = s;

复杂度：O(1)

删除
1
p.next = p.next.next;

复杂度：O(1)

查找

  • 按照位置序号来查找

    一个一个地遍历去查找。

    复杂度：O(n)

  • 按照具体的成绩来查找

    一个一个地遍历去查找。

    复杂度：O(n)

总结

如果处理数据时有顺序，数据的元素个数不确定，且需要经常进行数据的新增和删除时，那么链表会比较合适。

  • 数据按照顺序存储，可以有序遍历数据。
  • 按照数值的条件进行查找时，需要遍历，时间复杂度O(n)。
  • 新增数据，复杂度是O(1)。伴随查找的动作，新增复杂度变为了O(n)
  • 删除数据时，复杂度是O(1)。伴随查找的动作，新增复杂度变为了O(n)

链表算法题

  1. 链表的翻转。给定一个链表，输出翻转后的链表。例如，输入1 ->2 -> 3 -> 4 ->5，输出 5 -> 4 -> 3 -> 2 -> 1。

    分析：单向链表，它的指针结构造成了它的数据通路有去无回，一旦修改了某个指针，后面的数据就会造成失联的状态。为了解决这个问题，我们需要构造三个指针 prev、curr 和 next，对当前结点、以及它之前和之后的结点进行缓存，再完成翻转动作。

  2. 求奇数结点链表的中间结点的数据

    分析：未知长度的数据，获取总长度的一半。利用快慢指针，快指针是慢指针的前进速度的两倍，循环次数是数组长度的一半。

  3. 链表是否有环

    快慢指针，有环时，慢指针循环一圈必定与快指针相遇一次。

2.线性表-栈

介绍

线性表的变种，元素先进后出。栈的数据新增操作只能在末端进行，不允许在栈的中间某个结点后新增数据。

数组或者链表的操作过于灵活，过多暴露了可操作的接口。这些没有意义的接口过多，当数据量很大的时候就会出现一些隐藏的风险。

存储结构

同链表，有表头和表尾

数据操作

新增

  • 顺序栈

    java中使用List实现栈。

    栈的顺序存储可以借助数组来实现。一般来说，会把数组的首元素存在栈底，最后一个元素放在栈顶。然后定义一个 top 指针来指示栈顶元素在数组中的位置。假设栈中只有一个数据元素，则 top = 0。一般以 top 是否为 -1 来判定是否为空栈。当定义了栈的最大容量为 StackSize 时，则栈顶 top 必须小于 StackSize。

    只在栈顶操作，时间复杂度O(1)

  • 链栈

    用链表的方式实现栈。

    通常，可以把栈顶放在单链表的头部，如下图所示。由于链栈的后进先出，原来的头指针就毫无作用了。因此，对于链栈来说，是不需要头指针的。相反，它需要增加指向栈顶的 top 指针，这是压栈和出栈操作的重要支持。

    只在栈顶操作，时间复杂度O(1)

删除

同新增

查找

同链表

总结

  • 数据有序
  • 新增时间复杂度O(1)，但只能在栈顶操作
  • 删除时间复杂度O(1)，但只能在栈顶操作
  • 查询时间复杂度O(n)

栈算法题

  1. 给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须与相同类型的右括号匹配，左括号必须以正确的顺序匹配。
  2. 链表每k个元素翻转，如：链表：123456，k=3，则结果 321654

应用场景

  1. 浏览器回退页面效果。

3.线性表-队列

介绍

线性表的变种，元素先进先出。

队列的数据新增操作只能在末端进行，不允许在队列的中间某个结点后新增数据;

队列的数据删除操作只能在始端进行，不允许在队列的中间某个结点后删除数据。

存储结构

数据操作

总结

  • 数据有序
  • 新增时间复杂度O(1)，但只能在队尾操作
  • 删除时间复杂度O(1)，但只能在队头操作
  • 查询时间复杂度O(n)

队列算法题

  1. 约瑟夫环问题。已知 n 个人（以编号 1，2，3…n 分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出列；他的下一个人又从 1 开始报数，数到 m 的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

应用场景

面对数据处理顺序非常敏感的问题时，使用队列。

  • 可以确定队列长度最大值时，建议使用循环队列。

  • 无法确定队列长度时，应考虑使用链式队列。

双端队列

LinkedList

第一个（头） 最后一个（尾）
插入 offerFirst(e) offerLast(e)
删除 pollFirst() pollLast()
获取元素 peekFirst() peekLast()

优先队列

普通队列：先进先出；后进先出

优先队列：出队顺序和入队顺序无关；和优先级相关。优先级最高的在队首

底层可以使用不同的数据结构：

入队 出队（拿最大元素
数组线性结构 O(1) O(n)
链式线性结构 O(n) O(1)
二叉堆 O(logn) O(logn)

PriorityQueue

1
2
3
4
5
6
7
// 初始化大小为k的元素为int[]的小根堆（顶为堆中数组元素int[1]最小）
PriorityQueue<int[]> priorityQueue = new PriorityQueue(k, new Comparator<int[]>() {
    @Override
    public int compare(int[] newValue, int[] pileTop) {// 小值放到堆顶
    	return newValue[1] - pileTop[1];
    }
});

4.线性表衍生-数组

介绍

存储一个固定大小的相同类型元素的顺序集合。

存储结构

数组在内存中是连续存放的，数组内的数据，可以通过索引值直接取出得到。

数据操作

新增

  • 数组的最后增加一个新的元素

    对原数据产生没有任何影响。时间复杂度是 O(1)。

  • 数组中间的某个位置新增数据

    原数据的位置需要依次向后挪动 1 个位置。时间复杂度是 O(n)。

删除

同新增

查询
  • 根据位置值查找，时间复杂度是 O(1)。
  • 根据数值查找，时间复杂度是 O(n)。

数组算法题

总结

  • 数据有序存储，遍历有序。
  • 根据索引查找快，时间复杂度O(1)
  • 根据数值查找，时间复杂度O(n)
  • 中间位置删除数据，时间复杂度O(n)；末尾删除，时间复杂度O(1)。
  • 中间位置新增数据，时间复杂度O(n)；末尾新增，时间复杂度O(1)。

应用场景

5.字符串

介绍

字符串（string） 是由 n 个字符组成的一个有序整体（ n >= 0 ）。

特殊字符串：

  • 空串，指含有零个字符的串。例如，s = “”

  • 空格串，只包含空格的串。例如，s = “ “

  • 子串，串中任意连续字符组成的字符串叫作该串的子串。

  • 原串通常也称为主串。

    例如：a = “BEI”，b = “BEIJING”，c = “BJINGEI” 。

    • 对于字符串 a 和 b 来说，由于 b 中含有字符串 a ，所以可以称 a 是 b 的子串，b 是 a 的主串；
    • 对于 c 和 a 而言，虽然 c 中也含有 a 的全部字符，但不是连续的 “BEI” ，所以串 c 和 a 没有任何关系。

存储结构

有顺序存储和链式存储两种。

  • 顺序存储

    用一组地址连续的存储单元来存储串中的字符序列，一般是用定长数组来实现。

  • 链式存储

    由于串结构的特殊性（结构中的每个元素数据都是一个字符），如果也简单地将每个链结点存储为一个字符，就会造成很大的空间浪费。因此，一个结点可以考虑存放多个字符，如果最后一个结点未被占满时，可以使用 “#” 或其他非串值字符补全。

数据操作

字符串的数据操作与线性表有很大差别。线性表更关注的是单个元素的操作，比如增删查一个元素，而字符串中更多关注的是查找子串的位置、替换等操作。

新增

  • 顺序存储

    字符串的新增操作和数组相似，都牵涉对插入字符串之后字符的挪移操作，时间复杂度是 O(n)。

删除

和新增相似

查找

需要做的是子串查找或字符串匹配。

在主串n中找模式串m，时间复杂度是 n 和 m 的函数。O(nm)

假设要从主串 s = “goodgoogle” 中找到 t = “google” 子串。

算法题

  1. 两个字符串的最大公共字串。如：a = “13452439”， b = “123456”。输出字符串”345”

6.树（二叉树、红黑树、堆、前缀树、线段树）

博客 TODO

7.哈希表

介绍

实现 “地址 = f (关键字)” 的映射关系

存储结构

特点：

  • 数据没有顺序。

  • 数据存储与数据数值（关键字）有关。

数据操作

总结

  • 数据没有顺序。
  • 根据数值查找，时间复杂度O(1)
  • 新增时间复杂度O(1)
  • 删除时间复杂度O(1)

算法题

应用场景

满足以下：

  • 不需要有序遍历数据
  • n次查询
  • 可以提前预测数据量的大小。

8.图

知识点 TODO

图的存储和表达方式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List）

图的遍历：深度优先、广度优先

二部图的检测（Bipartite）（785）、树的检测、环的检测：有向图、无向图

拓扑排序

联合-查找算法（Union-Find）

最短路径：Dijkstra、Bellman-Ford

各类数据结构对比

链表 数组 字符串 栈 普通队列 优先队列（二叉堆） 二叉搜索树 前缀树 哈希表
数据有序性 有 无
查询时间复杂度 按位置 O(n) O(1) O(1) O(n) O(n) - - -
按数值 O(n) O(n) O(mn) O(n) O(n) ？ O(logn) O(1)
新增时间复杂度 中间 O(1) O(n) O(n) - - O(logn) O(logn) O(1)
末尾 O(1) O(1) O(1) O(1) O(1) - - -
删除时间复杂度 中间 O(1) O(n) O(n) - - O(logn) O(logn) O(1)
末尾 O(1) O(1) O(1) O(1) O(1) - - -

算法

1.递归

介绍

某个函数自己调用自己。

递归的使用条件需满足以下两个条件：

  • 可以拆解为除了数据规模以外，求解思路与原问题完全相同的子问题；

  • 存在终止条件。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function fn(n) {
    // 第一步：判断输入合理性？
    if (input is invalid) {
        return;
    }

    // 第二步：递归结束条件?
    if (match condition) {
        return some value;
    }

    // 第三步：缩小问题规模
    result1 = fn(n1)
    result2 = fn(n2)
    ...

    // 第四步: 获取结果
    return combine(result1, result2)
}

递归算法题

  1. 二叉树中序遍历
  2. 汉诺塔
  3. 斐波那契数列

2.分治

介绍

定义：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

特征：

  1. 该问题的规模缩小到一定的程度就可以容易地解决
  2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
  3. 利用该问题分解出的子问题的解可以合并为该问题的解；
  4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

应用场景

分治算法题

  1. 二分搜索
  2. 大整数乘法
  3. 快速排序
  4. 归并排序
  5. 汉诺塔

3.回溯

4.排序算法

冒泡

归并

快排

5.查找算法

二分查找

满足以下两点：

  • 时间复杂度O(logn)
  • 数据有序

二叉搜索树

深度优先搜索DFS

介绍

从起点出发，从规定的方向中选择其中一个不断地向前走，直到无法继续为止，然后尝试另外一种方向，直到最后走到终点。

解决连通性问题，从起点能不能到终点。

依赖栈，后进先出。

例子

给定一个二维矩阵代表一个迷宫，迷宫里面有通道，也有墙壁，通道由数字 0 表示，而墙壁由 -1 表示，有墙壁的地方不能通过，那么，能不能从 A 点走到 B 点。image-20210829203111589

广度优先搜索BFS

6.贪婪

7.动态规划