网站制作报价表,做网站上海公司,优化官方网站设计,什么是网络设计制作算法进修Day-36
71. 简化路径
难度#xff1a;中等 题目要求#xff1a; 给你一个字符串 path #xff0c;表示指向某一文件或目录的 Unix 风格 绝对路径 #xff08;以 / 开头#xff09;#xff0c;请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中中等 题目要求 给你一个字符串 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 ) (m1)*(n1) (m1)∗(n1) 的二维数组 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 i0 i0则对于任意 j j j需要将 w o r d 2 word_2 word2 的前 j j j 个字符全部删除最少操作数是 j j j如果 j 0 j0 j0则对于任意 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_1word_1[i-1], c_2word_2[j-1] c1word1[i−1],c2word2[j−1]总共分为两种情况 当 c 1 c 2 c_1c_2 c1c2将 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 c1c2 时计算将 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];}
}
