百度举报网站,创意设计小发明,用模块做网站,网站快速收录方法废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【动态规划】#xff0c;使用【数组】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为…废话不多说喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【动态规划】使用【数组】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。
明确目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
编辑距离【HARD】
终于又来到一道看了很久的高频题目这里
题干
搞定了一系列的简单题来个编辑距离练练手
解题思路
原题解地址解决两个字符串的动态规划问题一般都是用两个指针 i, j 分别指向两个字符串的最后然后一步步往前移动缩小问题的规模
设两个字符串分别为 rad 和 apple为了把 s1 变成 s2算法会这样进行
暴力递归
base case 是 i 走完 s1 或 j 走完 s2可以直接返回另一个字符串剩下的长度。对于每对儿字符 s1[i] 和 s2[j]可以有四种操作
if s1[i] s2[j]:啥都别做skipi, j 同时向前移动
else:三选一插入insert删除delete替换replace
有这个框架问题就已经解决了。读者也许会问这个「三选一」到底该怎么选择呢很简单全试一遍哪个操作最后得到的编辑距离最小就选谁
int minDistance(String s1, String s2) {int m s1.length(), n s2.length();// ij 初始化指向最后一个索引return dp(s1, m - 1, s2, n - 1);
}// 定义返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
int dp(String s1, int i, String s2, int j) {// base caseif (i -1) return j 1;if (j -1) return i 1;if (s1.charAt(i) s2.charAt(j)) {return dp(s1, i - 1, s2, j - 1); // 啥都不做}return min(dp(s1, i, s2, j - 1) 1, // 插入dp(s1, i - 1, s2, j) 1, // 删除dp(s1, i - 1, s2, j - 1) 1 // 替换);
}int min(int a, int b, int c) {return Math.min(a, Math.min(b, c));
}
情况一什么都不做
if s1[i] s2[j]:return dp(s1, i - 1, s2, j - 1); # 啥都不做
# 解释
# 本来就相等不需要任何操作
# s1[0..i] 和 s2[0..j] 的最小编辑距离等于
# s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离
# 也就是说 dp(i, j) 等于 dp(i-1, j-1)
如果 s1[i] ! s2[j]就要对三个操作递归了
情况二插入操作
dp(s1, i, s2, j - 1) 1, # 插入
# 解释
# 我直接在 s1[i] 插入一个和 s2[j] 一样的字符
# 那么 s2[j] 就被匹配了前移 j继续跟 i 对比
# 别忘了操作数加一 插入操作
情况三删除操作
dp(s1, i - 1, s2, j) 1, # 删除
# 解释
# 我直接把 s[i] 这个字符删掉
# 前移 i继续跟 j 对比
# 操作数加一 情况四替换操作
dp(s1, i - 1, s2, j - 1) 1 # 替换
# 解释
# 我直接把 s1[i] 替换成 s2[j]这样它俩就匹配了
# 同时前移 ij 继续对比
# 操作数加一a字符被替换为p字符
int dp(i, j) {dp(i - 1, j - 1); // #1dp(i, j - 1); // #2dp(i - 1, j); // #3
}
对于子问题 dp(i-1, j-1)如何通过原问题 dp(i, j) 得到呢有不止一条路径比如 dp(i, j) - #1 和 dp(i, j) - #2 - #3。一旦发现一条重复路径就说明存在巨量重复路径也就是重叠子问题
动态规划
接下来用DP table来优化一下降低重复子问题首先明确 dp 数组的含义dp 数组是一个二维数组长这样 有了之前递归解法的铺垫应该很容易理解。dp[..][0] 和 dp[0][..] 对应 base casedp[i][j] 的含义和之前的 dp 函数类似
替换操作word1的0~i-1位置与word2的0~j-1位置的字符都相同,只是当前位置的字符不匹配,进行替换操作后两者变得相同dp[i-1][j-1] 表示需要进行替换操作才能转到dp[i][j] 所以此时dp[i][j]dp[i-1][j-1]1(这个加1代表执行替换操作)删除操作: 若此时word1的0~i-1位置与word2的0~j位置已经匹配了,此时多出了word1的i位置字符,应把它删除掉,才能使此时word1的0~i(这个i是执行了删除操作后新的i)和word2的0~j位置匹配,因此此时dp[i][j]dp[i-1][j]1(这个加1代表执行删除操作)插入操作:若此时word1的0~i位置只是和word2的0~j-1位置匹配此时只需要在原来的i位置后面插入一个和word2的j位置相同的字符使得此时的word1的0~i(这个i是执行了插入操作后新的i)和word2的0~j匹配得上,所以此时dp[i][j]dp[i][j-1]1(这个加1代表执行插入操作)
有了之前递归解法的铺垫应该很容易理解。dp[..][0] 和 dp[0][..] 对应 base casedp[i][j] 的含义和之前的 dp 函数类似
int dp(String s1, int i, String s2, int j)
// 返回 s1[0..i] 和 s2[0..j] 的最小编辑距离dp 函数的 base case 是 i, j 等于 -1而数组索引至少是 0所以 dp 数组会偏移一位
dp[i-1][j-1]
// 存储 s1[0..i] 和 s2[0..j] 的最小编辑距离既然 dp 数组和递归 dp 函数含义一样也就可以直接套用之前的思路写代码唯一不同的是DP table 是自底向上求解递归解法是自顶向下求解
int minDistance(String s1, String s2) {int m s1.length(), n s2.length();// 定义s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i1][j1]int[][] dp new int[m 1][n 1];// base case for (int i 1; i m; i)dp[i][0] i;for (int j 1; j n; j)dp[0][j] j;// 自底向上求解for (int i 1; i m; i) {for (int j 1; j n; j) {if (s1.charAt(i-1) s2.charAt(j-1)) {dp[i][j] dp[i - 1][j - 1];} else {dp[i][j] min(dp[i - 1][j] 1,dp[i][j - 1] 1,dp[i - 1][j - 1] 1);}}}// 储存着整个 s1 和 s2 的最小编辑距离return dp[m][n];
}int min(int a, int b, int c) {return Math.min(a, Math.min(b, c));
}
代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构无 算法动态规划 技巧无 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Solution
{// 编辑距离返回两个字符串操作的最小距离public int minDistance(String word1, String word2){// 1 入参校验if(word1.length() 1 word2.length() 1){return 0;}// 2 定义行列长度word1作为竖word2作为行int m word1.length();int n word2.length();// 定义s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp[i1][j1]int[][] dp new int[m 1][n 1];// 4 初始化base casefor(int i 1; i m; i){dp[i][0] i;}for(int j 1; j n; j){dp[0][j] j;}// 5 状态转移方程:自底向上求解从头开始比较i0和j0的位置初始化为基本操作数for(int i 1; i m; i){for(int j 1; j n; j){if(word1.charAt(i-1) word2.charAt(j-1)){dp[i][j] dp[i - 1][j - 1];}else{dp[i][j] minCompare(dp[i - 1][j] 1, dp[i][j - 1] 1, dp[i - 1][j - 1] 1);}}}return dp[m][n];}private int minCompare(int a, int b, int c){return Math.min(a, Math.min(b, c));}
}第一行是 word1 为空变成 word2 最少步数就是插入操作第一列是 word2 为空word1要变为word2(也就是空)需要的最少步数就是删除操作
(一)、当word1[i]word2[j]时,由于遍历到了i和j,说明word1的0~i-1和word2的0~j-1的匹配结果已经生成,
由于当前两个字符相同,因此无需做任何操作,dp[i][j]dp[i-1][j-1](二)、当word1[i]!word2[j]时,可以进行的操作有3个:① 替换操作:可能word1的0~i-1位置与word2的0~j-1位置的字符都相同,只是当前位置的字符不匹配,进行替换操作后两者变得相同,所以此时dp[i][j]dp[i-1][j-1]1(这个加1代表执行替换操作)②删除操作:若此时word1的0~i-1位置与word2的0~j位置已经匹配了,此时多出了word1的i位置字符,应把它删除掉,才能使此时word1的0~i(这个i是执行了删除操作后新的i)和word2的0~j位置匹配,因此此时dp[i][j]dp[i-1][j]1(这个加1代表执行删除操作)③插入操作:若此时word1的0~i位置只是和word2的0~j-1位置匹配,此时只需要在原来的i位置后面插入一个和word2的j位置相同的字符使得此时的word1的0~i(这个i是执行了插入操作后新的i)和word2的0~j匹配得上,所以此时dp[i][j]dp[i][j-1]1(这个加1代表执行插入操作)④由于题目所要求的是要最少的操作数:所以当word1[i] ! word2[j] 时,需要在这三个操作中选取一个最小的值赋格当前的dp[i][j]
(三)总结:状态方程为:
if(word1[i] word2[j]):dp[i][j] dp[i-1][j-1]
else:min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])1PS:大佬的代码中word1.charAt(i-1)word2.charAt(j-1)的原因是:初始化DP Table时dp[i][0]和dp[0][j]已经填写完成,所以接下来填表需要从1开始,但是字符的比较需要从0开始,因此才这样子写复杂度分析
时间复杂度O(N^2)这里 N 是数组的长度我们写了两个 for 循环每个 for 循环的时间复杂度都是线性的 空间复杂度O(N)要使用和输入数组长度相等的状态数组因此空间复杂度是 O(N)。
