本文主要是介绍算法进修Day-36,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
算法进修Day-36
71. 简化路径
难度:中等
题目要求:
给你一个字符串 path
,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/'
开头),请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中,一个点(.
)表示当前目录本身;此外,两个点 (..
) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,'//'
)都被视为单个斜杠 '/'
。 对于此问题,任何其他格式的点(例如,'...'
)均被视为文件/目录名称。
请注意,返回的 规范路径 必须遵循下述格式:
- 始终以斜杠
'/'
开头。 - 两个目录名之间必须只有一个斜杠
'/'
。 - 最后一个目录名(如果存在)不能 以
'/'
结尾。 - 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含
'.'
或'..'
)。
返回简化后得到的 规范路径 。
示例1
输入:path = “/home/”
输出:“/home”
示例2
输入:path = “/…/”
输出:“/”
示例3
输入:path = “/home//foo/”
输出:“/home/foo”
示例4
输入:path = “/a/./b/…/…/c/”
输出:“/c”
题解
提供两条API内容解释:
- System.IO.Path.TrimEndingDirectorySeparator(String)
- 剪裁一个超出指定路径根目录的尾随目录分隔符。
- System.IO.Path.GetFullPath(String)
- 返回指定路径字符串的绝对路径。
想法代码
class Solution
{public static void Main(String[] args){string path = "/../";Solution solution = new Solution();string res = solution.SimplifyPath(path);Console.WriteLine(res);}public string SimplifyPath(string path){return Path.TrimEndingDirectorySeparator(Path.GetFullPath(path));}
}
72. 编辑距离
难度:困难
题目要求
给你两个单词 word1
和 word2
, 请返回将 word1
转换成 word2
所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例1
输入:word1 = “horse”, word2 = “ros”
输出:3
示例2
输入:word1 = “intention”, word2 = “execution”
输出:5
题解
利用动态规划,用 m m m 和 n n n 分别表示字符串 w o r d 1 word_1 word1 和 w o r d 2 word_2 word2 的长度,对于满足 1 ≤ i ≤ m 1\leq i\leq m 1≤i≤m 和 1 ≤ j ≤ n 1\leq j\leq n 1≤j≤n 的每个下标对 ( i , j ) (i,j) (i,j),需要分别计算将 w o r d 1 word_1 word1 的前 i i i 个字符转换成 w o r d 2 word_2 word2 的前 j j j 个字符的最小操作数
创建 ( m + 1 ) ∗ ( n + 1 ) (m+1)*(n+1) (m+1)∗(n+1) 的二维数组 d p dp dp,其中 d p [ i ] [ j ] dp[i][j] dp[i][j] 为将 w o r d 1 word_1 word1 的前 i i i 个字符转换成 w o r d 2 word_2 word2 的前 j j j 个字符的最小操作数
如果 i = 0 i=0 i=0,则对于任意 j j j,需要将 w o r d 2 word_2 word2 的前 j j j 个字符全部删除,最少操作数是 j j j,如果 j = 0 j=0 j=0,则对于任意 i i i,需要将 w o r d 1 word_1 word1 的前 i i i 个字符全部删除,最少操作数是 i i i,因此动态规划边界为:对于任意 0 ≤ j ≤ n , d p [ 0 ] [ j ] = j 0\leq j\leq n, dp[0][j]=j 0≤j≤n,dp[0][j]=j,对于任意 0 ≤ i ≤ m , d p [ i ] [ 0 ] = i 0\leq i\leq m, dp[i][0]=i 0≤i≤m,dp[i][0]=i,当然, d p [ 0 ] [ 0 ] = 0 dp[0][0]=0 dp[0][0]=0
当 1 ≤ i ≤ m 1\leq i\leq m 1≤i≤m 且 1 ≤ j ≤ n 1\leq j\leq n 1≤j≤n 时,让 c 1 = w o r d 1 [ i − 1 ] , c 2 = w o r d 2 [ j − 1 ] c_1=word_1[i-1], c_2=word_2[j-1] c1=word1[i−1],c2=word2[j−1],总共分为两种情况
- 当 c 1 = c 2 c_1=c_2 c1=c2,将 c 1 c_1 c1 和 c 2 c_2 c2 成为公共字符,将 w o r d 1 word_1 word1 的前 i − 1 i-1 i−1 个字符的最小操作数是 d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i−1][j−1],所以 d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] dp[i][j]=dp[i-1][j-1] dp[i][j]=dp[i−1][j−1]
- 当 c 1 ≠ c 2 c_1\neq c_2 c1=c2 时,计算将 w o r d 1 word_1 word1 的前 i i i 个字符串转换成 w o r d 2 word_2 word2 的前 j j j 个字符的最少操作数时需要考虑三种可能的操作,取其中的最小操作数作为 d p [ i ] [ j ] dp[i][j] dp[i][j]
- 第一种操作是插入字符 c 1 c_1 c1,操作之前的最少操作数是 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j],操作之后的最少操作数是 d p [ i − 1 ] [ j ] + 1 dp[i-1][j]+1 dp[i−1][j]+1
- 第二种操作是删除字符 c 2 c_2 c2,操作之前的最少操作数是 d p [ i ] [ j − 1 ] dp[i][j-1] dp[i][j−1],操作之后的最少操作数是 d p [ i ] [ j − 1 ] + 1 dp[i][j-1]+1 dp[i][j−1]+1
- 第三种操作是将字符 c 1 c_1 c1 替换为 c 2 c_2 c2,操作之前的最少操作数是 d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i−1][j−1],操作之后的最少操作数是 d p [ i − 1 ] [ j − 1 ] + 1 dp[i-1][j-1]+1 dp[i−1][j−1]+1
动态规划转移方程如下
d p [ i ] [ j ] = { d p [ i − 1 ] [ j − 1 ] , word1[i-1]=word2[j-1] m i n ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j − 1 ] ) + 1 , word1[i-1]!=word2[j-1] dp[i][j]=\begin{cases} dp[i-1][j-1],&\text{word1[i-1]=word2[j-1]}\\min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1,&\text{word1[i-1]!=word2[j-1] } \end{cases} dp[i][j]={dp[i−1][j−1],min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])+1,word1[i-1]=word2[j-1]word1[i-1]!=word2[j-1] 根据动态规划转移方程,计算 d p [ i ] [ j ] dp[i][j] dp[i][j] 的顺序为从小到大遍历每个 i i i,对于每个 i i i 从小到大遍历每个 j j j。最后 d p [ m ] [ n ] dp[m][n] dp[m][n] 即为最少操作数
想法代码
public class Solution
{public static void Main(string[] args){Solution solution = new Solution();string word1 = "horse";string word2 = "ros";Console.WriteLine(solution.MinDistance(word1,word2));}public int MinDistance(string word1, string word2){int m = word1.Length, n = word2.Length;int[][] dp = new int[m + 1][];for (int i = 0; i <= m; i++){dp[i] = new int[n + 1];}for (int j = 1; j <= n; j++){dp[0][j] = j;}for (int i = 1; i <= m; i++){dp[i][0] = i;}for (int i = 1; i <= m; i++){char c1 = word1[i - 1];for (int j = 1; j <= n; j++){char c2 = word2[j - 1];if (c1 == c2){dp[i][j] = dp[i - 1][j - 1];}else{dp[i][j] = Math.Min(Math.Min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;}}}return dp[m][n];}
}
这篇关于算法进修Day-36的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!