Kiml's Blog
面试-数据结构和算法
Kiml Lv5
  2024-04-22 21:36:05   2024-07-16 17:51:27    7.7k 字  27 分钟  

  • 前言
    根据刷题记录，整理各个类型的特点

  • 更新

1
2
3
4
5
6
24.04.22 初始记录 数组的总结
24.05.23 链表的总结
24.05.24 哈希表的总结
24.05.29 字符串的总结（KMP）
24.06.09 二叉树总结
24.07.10 动态规划总结

数据结构

数组

基础理论

1、数组是存放在连续内存空间上的相同类型数据的集合。

  • 数组下标从 0 开始

  • 数组的内存空间地址连续

2、因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

3、数组的元素是不能删的，只能覆盖。

4、二维数组在内存的空间地址不连续

经典题目

二分法

需要遵循循环不变量原则。这里的循环不变量原则在二分法中的表现就是，循环过程中左闭右开，这个规则是不变的。

双指针法

快慢指针法：通过一个快指针和慢指针在一个 for 循环下完成两个 for 循环的工作。

双向指针法：一个指针从左向右一个指针从右向左。从左向右的找等于目标值的位置，从右向左找不等于目标的位置，每次找到一个用不等于覆盖等于。（就是自己第一次题解时的做法）

滑动窗口

动态更新窗口的大小，找到最优解。

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将 O(n^2) 的暴力解法降为 O(n)。

模拟行为

目前遇到的题型是螺旋矩阵。

这类题目只要模拟数组需要执行的操作就行，需要注意边界值，遵循循环不变量原则。

链表

基础理论

分类

  1. 单链表
    指针域只能指向节点的下一个节点。

  2. 双链表
    每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

  3. 循环链表
    链表首尾相连。

存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义
1
2
3
4
5
6
7
8
9
10
11
public class ListNode {  
    public int val;  
    public ListNode next;  
  
    public ListNode() {  
    }  
  
    public ListNode(int val) {  
        this.val = val;  
    }  
}
链表操作
删除节点

将该节点跳过，前一节点指向后一节点。

添加节点

前一节点指向该节点，该节点指向后一节点。

性能分析
插入/删除（时间复杂度） 查询（时间复杂度） 适用场景
数组 O(n) O(1) 数据量固定，频繁查询，较少增删
链表 O(1) O(n) 数据量不固定，频繁增删，较少查询

经典题目

虚拟头节点

链表中的增删操作，都是需要操作前一个节点进行指向。但是对于头节点的操作，由于没有前一个节点，每次都需要单独处理。因此使用虚拟头结点的技巧。（基本上做题都是加上虚拟节点比较方便）

链表的基本操作

  • 获取链表第 index 个节点的数值

  • 在链表的最前面插入一个节点

  • 在链表的最后面插入一个节点

  • 在链表第 index 个节点前面插入一个节点

  • 删除链表的第 index 个节点的数值

反转链表

  1. 迭代法用双指针，改变两个节点之间的指针方向

  2. 递归法和迭代法的思路基本一样，把移动下一步的操作放到递归里进行。

两两交换链表中的节点

这题也用到了虚拟头节点的方法。

  1. 需要交换的两个节点的前一个节点，指向需要交换的第二个节点

  2. 节点交换

删除倒数第N个节点

运用虚拟头节点 + 双指针。

思路是，一个指针先走 N 步，然后两个指针一起向后。当快指针指向末尾时，慢指针的位置正好是倒数第 N 个节点。然后完成删除操作。

链表相交

这里的相交指的是引用完全相同，即：内存地址完全相同的交点

环形链表

  1. 判断是否有环

  2. 判断交点位置这是一道数学题，具体解析在对应的文章中给出。

哈希表

基础理论

定义
哈希表是根据关键码的值而直接进行访问的数据结构。
一般使用

一般哈希表都是用来快速判断一个元素是否出现集合里。

哈希函数/哈希碰撞

哈希函数是把传入的 key 映射到符号表的索引上。

哈希碰撞处理有多个 key 映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。

常见的三种哈希结构

  1. 数组

  2. set（集合）

  3. map（映射）

哈希表经典题目

数组作为哈希表

一般题目中出现规定 map 大小（比如明说都是小写字母），就可以使用数组。这些题用 map 确实可以，但使用 map 的空间消耗要比数组大一些，因为 map 要维护红黑树或者符号表，而且还要做哈希函数的运算。所以数组更加简单直接有效！

关联题目：

有效的字母异位词

赎金信

set 作为哈希表

如果题目没有限制大小，就无法使用数组。

主要因为：

  1. 数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。

  2. 如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

关联题目：

两个数组的交集

快乐数

map作为哈希表

set 是一个集合，里面放的元素只能是一个 key，但是遇到 key 与 value 都要保存时，就需要使用 map。

字符串

基础理论

定义

字符串是若干字符组成的有限序列，也可以理解为是一个字符数组。

字符串经典题目

双指针

双指针法在数组，链表和字符串中很常用。

关联题目：

反转字符串：只是简单使用 temp 作为中间变量。

替换字符：数组填充类的问题，可以先预先给数组扩容带填充后的大小，然后再从后向前进行操作。

与移除操作有关的双指针操作：

翻转字符串内的单词 中的移除空格部分。

之前数组部分中 移除数组元素

反转系列

反转就是双指针（头尾指针一起向中间移动，然后交换数组元素）

关联题目：

反转字符串II

翻转字符串内的单词：这题的反转用了两次，先整体反转，再分段反转。

右旋转字符串：和上题一样需要先局部反转再整体反转。（这种题笔试遇到直接 API 快一点）

KMP

KMP 算法是字符串查找最重要的算法。
KMP 的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

关联题目：

实现 strStr() 、重复的子字符串

前缀表

作用：前缀表是用来回退的，它记录了模式串与主串 (文本串) 不匹配的时候，模式串应该从哪里开始重新匹配。

常见的基础题目是在文本串中查找一个模式串，例：在 aabaabaafa 中查找 aabaaf。这个查找是文本串指针顺序后移（不变），活动模式串进行匹配。

前缀表用于记录查找失败后，模式串下一次返回查找的点。例：文本串指针到第二个 b 时，查找失败，这时模式串从 b 这个位置重新查询。

什么是前缀表？

记录下标 i 之前（包括 i）的字符串中，有多大长度的相同前缀后缀。

最长公共前后缀

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。这个部分暂时是比较好理解的。

为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配？

image

这张图是教程内的图，下标 5 之前这部分的字符串（也就是字符串 aabaa）的最长相等的前缀 和 后缀字符串是 子字符串 aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。

如何找到一张前缀表

不是很能理解，但是背下来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 需要找到前缀表的字符串
String s;
// 初始化
int j = 0;
int[] next = new int[s.length];
for(int i = 1; i < s.length, i++) {
	// 不相同的情况
	while(j != 0 && s.charAt[i] != s.charAt[j]) {
		j = next[j - 1];
	}
	if(s.charAt[i] == s.charAt[j]) {
		j++;
	}
	next[i] = j;
}

栈与队列

基础理论

队列是先进先出，栈是先进后出。
栈与队列的基础可以通过下面两题回忆。

用栈实现队列

用队列实现栈

栈经典题目

有效的括号：括号匹配是使用栈解决的经典问题。

删除字符串中的所有相邻重复项：思路就是可以把字符串顺序放到一个栈中，然后如果相同的话 栈就弹出，这样最后栈里剩下的元素都是相邻不相同的元素了。

逆波兰表达式求值：这题主要在于题目中给出的百度链接，其中描述了逆波兰式子的意思。计算方式就是遍历式子，遇到数字入栈，遇到运算符出栈两个数字进行计算，计算结果再入栈。直到式子循环完毕。

队列经典题目

滑动窗口最大值：这题需要用到单调队列，即单调递减或单调递增的队列（需要自己定义数据结构）

前 K 个高频元素：这题需要用到优先级队列，其实就是堆（堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。）

二叉树

基础理论

二叉树的种类
满二叉树

满二叉树：如果一棵二叉树只有度为 0 的结点和度为 2 的结点，并且度为 0 的结点在同一层上，则这棵二叉树为满二叉树。

这棵二叉树为满二叉树，也可以说深度为 k，有 2^k-1 个节点的二叉树。

完全二叉树

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h 从 1 开始），则该层包含 1~ 2^(h-1) 个节点。

优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树

二叉搜索树是一个有序树

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

  • 它的左、右子树也分别为二叉排序树

平衡二叉搜索树

平衡二叉搜索树：又被称为 AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

二叉树的存储方式

二叉树可以链式存储，也可以顺序存储。
那么链式存储方式就用指针， 顺序存储的方式就是用数组。

用数组来存储二叉树如何遍历？如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树的遍历方式

二叉树主要有两种遍历方式：

  1. 深度优先遍历：先往深走，遇到叶子节点再往回走。

  2. 广度优先遍历：一层一层的去遍历。
    这两种遍历是图论中最基本的两种遍历方式
    从深度优先遍历和广度优先遍历进一步拓展：

  • 深度优先遍历

    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）

  • 广度优先遍历

    • 层次遍历（迭代法）
      这里前中后，其实指的就是中间节点的遍历顺序，前中后序指的就是中间节点的位置。

❗二叉树的递归遍历、二叉树的迭代遍历、二叉树的统一迭代法：(https://kiml.site/posts/a297f438/)

二叉树的层序遍历

❗递归算法的三要素

  1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

  2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

  3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

二叉树的定义
1
2
3
4
5
6
7
8
9
10
11
12
13
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

经典题目

遍历方式

❗二叉树的递归遍历、二叉树的迭代遍历、二叉树的统一迭代法：(https://kiml.site/posts/a297f438/)

二叉树的层序遍历

层序遍历相关的题目比较多，没有写到笔记里面。（一个模板可以做十道题，部分在 github 上提交了，部分没有做。）

二叉树的属性

  1. 是否对称、相同

对称二叉树

递归：后序遍历。判断左右子树：左右中、右左中是否相等。

迭代：使用队列/栈将两个节点顺序放入容器中进行比较。

  1. 求最大深度

二叉树的最大深度

递归：后序遍历，求根节点最大高度就是最大深度，通过递归函数的返回值做计算树的高度。

  1. 求最小深度

二叉树的最小深度

递归：后序遍历，右节点为空，向左递归；左节点为空，向右递归。

  1. 求节点数

完全二叉树的节点个数

普通二叉树的节点个数：层序遍历

完全二叉树：

分两种情况：满二叉树/最后一层节点没有满。但是这两种情况可以简化为一种，即孩子节点必定为满二叉树（按满二叉树算节点）

于是就变成判断子树是否是满二叉树：向左递归的深度等于向右递归的深度

  1. 是否平衡

平衡二叉树

递归：后序遍历。判断子树是否平衡并把结果向上传递。

  1. 找所有路径

二叉树的所有路径

递归：前序遍历。涉及回溯。

  1. 求左叶子之和

左叶子之和

递归：后序遍历。

  1. 求左下角的值。

找树左下角的值

递归：顺序没有关系。找深度最大的左叶子节点（优先左遍历）。

迭代：感觉层序遍历更简单一点。

  1. 求路径总和

路径总和、路径总和ii

递归：需要回溯。

二叉树的修改与构造

  1. 翻转二叉树

翻转二叉树

递归：中序不行。左右两数交换指针。

  1. 构造二叉树

从中序与后序遍历序列构造二叉树、从前序与中序遍历序列构造二叉树

最大二叉树

递归：思路就是根据后序/前序的遍历结果。切割中序，再递归构造。

  1. 合并二叉树

合并二叉树

递归：前序遍历。

最近公共祖先

二叉树的最近公共祖先：从底层向上传递信息（只能用后序）。找到一个节点的左子树含 p，右子树含 q（可以先交换两个数的大小顺序）

二叉搜索树的最近公共祖先：遍历顺序随便。重点在当我们从上向下去递归遍历，第一次遇到 cur 节点是数值在 [q, p] 区间中，那么 cur 就是 q 和 p 的最近公共祖先。

二叉搜索树的属性

  1. 遍历

二叉搜索树中的搜索：二叉搜索树的遍历是有方向的。

  1. 中序遍历下，输出的二叉搜索树节点的数值是有序序列。

验证二叉搜索树

易错点：左子树所有节点小于中间节点，右子树所有节点大于中间节点

  1. pre 标记前节点的双指针用法

验证二叉搜索树

二叉搜索树的最小绝对差

二叉搜索树中的众数

把二叉搜索树转换为累加树

二叉搜索树的修改与构造

  1. 插入操作

二叉搜索树中的插入操作：找到位置直接插入

  1. 删除操作

删除二叉搜索树中的节点：删除非叶子节点：用右子树顶位（比较好理解）。

修剪二叉搜索树：需要注意修剪情况。

  1. 构造二叉树

将有序数组转换为二叉搜索树：与构造二叉树基本一致。找到中间节点后切割。

总结

  • 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。

  • 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。

  • 求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。

算法

回溯算法

理论基础

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯法解决的问题都可以抽象为树形结构。因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

效率：回溯法并不是什么高效的算法。因为回溯的本质是穷举

能解决的问题：组合问题、切割问题、子集问题、排列问题、棋盘问题。

回溯法模板

for 循环横向遍历，递归纵向遍历，回溯不断调整结果集。

  • 回溯函数模板返回值以及参数回溯算法中函数返回值一般为 void。

  • 回溯函数终止条件

  • 回溯搜索的遍历过程

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
❗剪枝

剪枝精髓是：for 循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够 题目要求的 k 个元素了，就没有必要搜索了。

❗去重

image

去重包括 “树枝去重”和“树层去重”。如图所示：在 candidates[i] == candidates[i - 1] 相同的情况下：

  • used[i - 1] == true，说明同一树枝 candidates[i - 1] 使用过

  • used[i - 1] == false，说明同一树层 candidates[i - 1] 使用过

经典题目

回溯算法能解决如下题目：

  • 组合问题：N 个数里面按一定规则找出 k 个数的集合

  • 排列问题：N 个数按一定规则全排列，有几种排列方式

  • 切割问题：一个字符串按一定规则有几种切割方式

  • 子集问题：一个 N 个数的集合里有多少符合条件的子集

  • 棋盘问题：N 皇后，解数独等等

组合问题

回溯算法的精髓在于：for 循环横向遍历，递归纵向遍历，回溯不断调整结果集，优化回溯算法只有剪枝一种方法。做题前可以先把题目抽象成树，这样剪枝操作也比较好理解。

组合

组合总和III：相当于组合问题加了一个元素总和的限制。（大于元素总和需要剪枝）

组合总和：给出的集合是不重复的，但是元素可以。

组合总和II：给出的集合元素是有重复的，但是要求解集不重复。难点在去重

电话号码的字母组合：多个集合求组合的问题。

切割问题

分割回文串：类似组合问题，但是求值处为一个范围截取。

复原IP地址

子集问题

子集：树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。

子集II：在子集问题的基础上加上了去重。

递增子序列：层去重。

排列问题

全排列：排列每层都需要从 0 开始搜索。

[全排列 II]：在排列的基础上加上去重。

图论额外拓展

重新安排行程

棋盘问题

N皇后

解数独

性能分析

这段直接抄的 (https://programmercarl.com/回溯总结.html)

子集问题分析：

  • 时间复杂度：O(2^n)，因为每一个元素的状态无外乎取与不取，所以时间复杂度为 O(2^n)

  • 空间复杂度：O(n)，递归深度为 n，所以系统栈所用空间为 O(n)，每一层递归所用的空间都是常数级别，注意代码里的 result 和 path 都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为 O(n)
    排列问题分析：

  • 时间复杂度：O(n!)，这个可以从排列的树形图中很明显发现，每一层节点为 n，第二层每一个分支都延伸了 n-1 个分支，再往下又是 n-2 个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * …… 1 = n!。

  • 空间复杂度：O(n)，和子集问题同理。组合问题分析：

  • 时间复杂度：O(2^n)，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。

  • 空间复杂度：O(n)，和子集问题同理。
    N 皇后问题分析：

  • 时间复杂度：O(n!) ，其实如果看树形图的话，直觉上是 O(n^n)，但皇后之间不能见面所以在搜索的过程中是有剪枝的，最差也就是 O（n!），n!表示 n * (n-1) * …. * 1。

  • 空间复杂度：O(n)，和子集问题同理。解数独问题分析：

  • 时间复杂度：O(9^m) , m 是 ‘.’ 的数目。

  • 空间复杂度：O(n^2)，递归的深度是 n^2

贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

一般解题步骤（不一定能用）

  • 将问题分解为若干个子问题

  • 找出适合的贪心策略

  • 求解每一个子问题的最优解

  • 将局部最优解堆叠成全局最优解

经典题目

因为贪心算法没有什么套路，所以刷题很难分类。

简单题

分发饼干

K次取反后最大化的数组和

柠檬水找零

中等题

摆动序列

单调递增的数字

贪心解决股票问题

买卖股票的最佳时机II

两个维度权衡问题

分发糖果

根据身高重建队列

难题

区间问题

跳跃游戏

跳跃游戏II

用最少数量的箭引爆气球

无重叠区间

划分字母区间

合并区间

其他难题

最大子序和

加油站

监控二叉树

动态规划

动态规划，英文：Dynamic Programming，简称 DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

解题步骤

  1. 确定 dp 数组（dp table）以及下标的含义

  2. 确定递推公式

  3. dp 数组如何初始化

  4. 确定遍历顺序

  5. 举例推导 dp 数组
    如何 Debug : 找问题的最好方式就是把 dp 数组打印出来，看看究竟是不是按照自己思路推导的！

经典题目

动态规划基础

斐波那契数

爬楼梯

使用最小花费爬楼梯

不同路径

不同路径 II

整数拆分

背包问题

image

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

分割等和子集：01 背包

最后一块石头的重量 II：01 背包

问装满背包有几种方法：dp[j] += dp[j - nums[i]]

目标和：01 背包

零钱兑换 II：完全背包、组合

组合总和 Ⅳ：完全背包、排列

爬楼梯 （进阶）：完全背包、排列

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

一和零：01 背包

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j])

零钱兑换：完全背包。求最小数（for 循环先后顺序无所谓）

完全平方数：完全背包。求最小数（for 循环先后顺序无所谓）

遍历顺序

  • 01 背包

    • 二维 dp 数组：先遍历背包/先遍历物品都可以
    • 一维 dp 数组：只能先遍历物品再遍历背包容量，第二层 for 循环需要从大到小遍历

  • 完全背包

    • 一维 dp 数组：第二层 for 循环从小到大遍历。如果求组合数就是外层 for 循环遍历物品，内层 for 遍历背包。如果求排列数就是外层 for 遍历背包，内层 for 循环遍历物品。如果是求最小数，那么两层 for 循环排列的先后顺序无所谓。
打家劫舍

打家劫舍

打家劫舍 II

打家劫舍 III

递推公式
一般都是要求相邻格子要跳过，所以公式从前前个获取（因此初始化数组需要 0，1 位置）：dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])

股票问题

买卖股票的最佳时机

买卖股票的最佳时机 II

买卖股票的最佳时机 III

买卖股票的最佳时机 IV

最佳买卖股票时机含冷冻期

买卖股票的最佳时机含手续费

递推公式
dp 数组的定义为二维数组（可以塌缩，但是二维比较好理解）：不同状态计入数组。当天状态一般为持有/不持有两种；如果加入天数，状态需要增加第一天持有/不持有，第二天持有/不持有……。持有的状态递推为上一次不持有 - 当天买入股票价格；不持有的状态递推为上一次持有 + 当天卖出股票的价格。

1
2
3
4
5
6
7
if (j % 2 == 0) {    
    // 偶数买入    
    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);    
} else {    
    // 奇数卖出    
    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);    
}
编辑距离

判断子序列

不同的子序列

两个字符串的删除操作

编辑距离

递推公式
dp 数组的定义为二维数组，可以塌缩。定义：第一个参数到 i - 1；第二个参数到 j - 1 位置的所求量（为什么记为 i - 1？：为了初始化方便）。循环从左向右从上到下（此步可以画图模拟）。根据两个数组当前位置的字符是否相同，分别写出 dp 公式。

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1; i <= word1.length(); i++) {    
    for (int j = 1; j <= word2.length(); j++) {    
        // 当前指针位置相同，dp[i][j] = dp[i - 1][j - 1] + 1    
        if (word1.charAt(i - 1) == word2.charAt(j - 1)) {    
	        // 此处需要具体公式具体分析，一般相同时，状态由左上角推出。
            dp[i][j] = dp[i - 1][j - 1];    
        } else { 
	        // 此处需要具体公式具体分析，根据数组元素是否能改变，可以有三种不同的情况。
            dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);    
        }    
    }    
}
子序列

连续：

最长递增子序列

最长公共子序列

不相交的线

不连续：

最长连续递增序列

最长重复子数组

最大子序和

编辑距离：详见 编辑距离模块

回文：

回文子串

最长回文子序列

单调栈

一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时可以用单调栈。

使用单调栈主要有三个判断条件。

  • 当前遍历的元素 T[i] 小于栈顶元素 T[st.top()] 的情况

  • 当前遍历的元素 T[i] 等于栈顶元素 T[st.top()] 的情况

  • 当前遍历的元素 T[i] 大于栈顶元素 T[st.top()] 的情况

每日温度

下一个更大元素 I

下一个更大元素 II

接雨水

柱状图中最大的矩形

面试-数据结构和算法
posts/1b906b1a/
作者
Kiml
发布于
2024-04-22 21:36
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 数据结构
    1. 数组
      1. 基础理论
      2. 经典题目
        1. 二分法
        2. 双指针法
        3. 滑动窗口
        4. 模拟行为
    2. 链表
      1. 基础理论
        1. 分类
        2. 存储方式
        3. 链表的定义
        4. 链表操作
          1. 删除节点
          2. 添加节点
        5. 性能分析
      2. 经典题目
        1. 虚拟头节点
        2. 链表的基本操作
        3. 反转链表
        4. 两两交换链表中的节点
        5. 删除倒数第N个节点
        6. 链表相交
        7. 环形链表
    3. 哈希表
      1. 基础理论
        1. 定义
        2. 一般使用
        3. 哈希函数/哈希碰撞
        4. 常见的三种哈希结构
      2. 哈希表经典题目
        1. 数组作为哈希表
        2. set 作为哈希表
        3. map作为哈希表
    4. 字符串
      1. 基础理论
        1. 定义
      2. 字符串经典题目
        1. 双指针
        2. 反转系列
        3. KMP
          1. 前缀表
          2. 最长公共前后缀
          3. 为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配？
          4. 如何找到一张前缀表
    5. 栈与队列
      1. 基础理论
      2. 栈经典题目
      3. 队列经典题目
    6. 二叉树
      1. 基础理论
        1. 二叉树的种类
          1. 满二叉树
          2. 完全二叉树
          3. 二叉搜索树
          4. 平衡二叉搜索树
        2. 二叉树的存储方式
        3. 二叉树的遍历方式
          1. ❗递归算法的三要素
        4. 二叉树的定义
      2. 经典题目
        1. 遍历方式
        2. 二叉树的属性
        3. 二叉树的修改与构造
        4. 最近公共祖先
        5. 二叉搜索树的属性
        6. 二叉搜索树的修改与构造
      3. 总结
  2. 算法
    1. 回溯算法
      1. 理论基础
        1. 回溯法模板
        2. ❗剪枝
        3. ❗去重
      2. 经典题目
        1. 组合问题
        2. 切割问题
        3. 子集问题
        4. 排列问题
        5. 图论额外拓展
        6. 棋盘问题
      3. 性能分析
    2. 贪心算法
      1. 一般解题步骤（不一定能用）
      2. 经典题目
        1. 简单题
        2. 中等题
        3. 难题
    3. 动态规划
      1. 解题步骤
      2. 经典题目
        1. 动态规划基础
        2. 背包问题
        3. 打家劫舍
        4. 股票问题
        5. 编辑距离
        6. 子序列
    4. 单调栈
© 2022 - 2025    Kiml
由 Hexo 驱动 & 主题 Keep
访客数 访问量
  1. 数据结构
    1. 数组
      1. 基础理论
      2. 经典题目
        1. 二分法
        2. 双指针法
        3. 滑动窗口
        4. 模拟行为
    2. 链表
      1. 基础理论
        1. 分类
        2. 存储方式
        3. 链表的定义
        4. 链表操作
          1. 删除节点
          2. 添加节点
        5. 性能分析
      2. 经典题目
        1. 虚拟头节点
        2. 链表的基本操作
        3. 反转链表
        4. 两两交换链表中的节点
        5. 删除倒数第N个节点
        6. 链表相交
        7. 环形链表
    3. 哈希表
      1. 基础理论
        1. 定义
        2. 一般使用
        3. 哈希函数/哈希碰撞
        4. 常见的三种哈希结构
      2. 哈希表经典题目
        1. 数组作为哈希表
        2. set 作为哈希表
        3. map作为哈希表
    4. 字符串
      1. 基础理论
        1. 定义
      2. 字符串经典题目
        1. 双指针
        2. 反转系列
        3. KMP
          1. 前缀表
          2. 最长公共前后缀
          3. 为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配？
          4. 如何找到一张前缀表
    5. 栈与队列
      1. 基础理论
      2. 栈经典题目
      3. 队列经典题目
    6. 二叉树
      1. 基础理论
        1. 二叉树的种类
          1. 满二叉树
          2. 完全二叉树
          3. 二叉搜索树
          4. 平衡二叉搜索树
        2. 二叉树的存储方式
        3. 二叉树的遍历方式
          1. ❗递归算法的三要素
        4. 二叉树的定义
      2. 经典题目
        1. 遍历方式
        2. 二叉树的属性
        3. 二叉树的修改与构造
        4. 最近公共祖先
        5. 二叉搜索树的属性
        6. 二叉搜索树的修改与构造
      3. 总结
  2. 算法
    1. 回溯算法
      1. 理论基础
        1. 回溯法模板
        2. ❗剪枝
        3. ❗去重
      2. 经典题目
        1. 组合问题
        2. 切割问题
        3. 子集问题
        4. 排列问题
        5. 图论额外拓展
        6. 棋盘问题
      3. 性能分析
    2. 贪心算法
      1. 一般解题步骤（不一定能用）
      2. 经典题目
        1. 简单题
        2. 中等题
        3. 难题
    3. 动态规划
      1. 解题步骤
      2. 经典题目
        1. 动态规划基础
        2. 背包问题
        3. 打家劫舍
        4. 股票问题
        5. 编辑距离
        6. 子序列
    4. 单调栈