LeetCode 70爬楼梯&71简化路径&72编辑距离(dp)

新人公众号(求支持)：bigsai 专注于Java、数据结构与算法，一起进大厂不迷路！
算法文章题解全部收录在github仓库bigsai-algorithm,求star！
关注这个潇洒青年一起飞，回复进群即可加入力扣打卡群，欢迎划水。近期打卡：
跟我打卡LeetCode 61旋转链表&62不同路径&63不同路径 II
打卡LeetCode 65有效数字&66加一 &67二进制求和
LeetCode 67二进制求和&68文本左右对齐&69x的平方根
如有帮助，记得对本文一键三连！

LeetCode 70爬楼梯

题目描述：

分析：
入门dp，状态转移方程为：初始赋值好后，dp[i]=dp[i-1]+dp[i-2];

 public int climbStairs(int n) { if(n<3)return n;
	 int dp[]=new int[n+1];
	 dp[1]=1;
	 dp[2]=2;
	 for(int i=3;i<n+1;i++)
	 { dp[i]=dp[i-1]+dp[i-2];
	 }
	 return dp[n];
 }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

另外，本题还可以使用两个变量替代数组去优化空间

LeetCode 71 简化路径

题目描述

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径

请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

示例 1：

输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

  

 

  
1
  
2
  
3
 

示例 2：

输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。

  

 

  
1
  
2
  
3
 

示例 3：

输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

  

 

  
1
  
2
  
3
 

示例 4：

输入："/a/./b/../../c/"
输出："/c"

  

 

  
1
  
2
 

示例 5：

输入："/a/../../b/../c//.//"
输出："/c"

  

 

  
1
  
2
 

示例 6：

输入："/a//bc/d//././/.."
输出："/a/b/c"

  

 

  
1
  
2
 

分析

这题就是栈的应用，通过栈遍历放入目录，在遍历字符串的同时如果遇到/ 那么就考虑进行操作。逻辑如下：

具体编写代码的时候，需要注意是否为最后一个字符和一些特殊情况(栈为空则别抛出)。

具体代码为：

public String simplifyPath(String path) {
  Stack<String>stack=new Stack<String>();
  char ch[]=path.toCharArray();
  StringBuilder sBuilder=new StringBuilder(); for(int i=0;i<ch.length;i++)
  { if(ch[i]=='/'||i==ch.length-1) { if(i==ch.length-1&&ch[i]!='/') { sBuilder.append(ch[i]); } if(sBuilder.length()==0||sBuilder.toString().equals(".")) {} else if (sBuilder.toString().equals("..")) { if(!stack.isEmpty()) stack.pop(); } else if(sBuilder.length()>0){ stack.push(sBuilder.toString()); } sBuilder=new StringBuilder(); } else { sBuilder.append(ch[i]); }
  } sBuilder=new StringBuilder("");
  for(String s:stack)
  { sBuilder.append('/'); sBuilder.append(s);
  }
  if(stack.isEmpty()) return "/";
  return sBuilder.toString();

}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
 

LeetCode 72编辑距离(dp)

题目描述

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

  

 

  
1
  
2
 

分析
这题其实是有难度，笔者刚开始做的时候以为是最小公众子序列(LCS),但是后来发现并不是但是还是有点联系的，dp的思想很相似。

分析一下目的：

• word1字符串转成word2字符串

分析一下操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

即很可能两个字符向上或者向下可能转换成三种状态(有三种方式至少)。如果从递归的思路思考这道题，从后往前递推。

• 如果两个字符相等，操作的次数直接向前推。
• 如果不相等，分别递归取最小的(修改，插入，删除)

但是这样明显有很多次重复计算，超时，你可以使用记忆化：即用数组将对应递归编号的值记录下来，如果数组有值，那么不需要递归重复计算，否则计算完将值赋值到该位置。这样可以避免大量重复计算。

但是我们这题可以使用动态规划的思路，从前往后看。用dp[i][j]表示word1的前i个转成word2的前j个需要转动的次数。动态规划的核心就是初始化和状态方程。

• 对于初始化，如果一个串串长度为0，编程另一个串串，那么肯定只有插入和删除这两种操作。并且初始化次数和字符串的长度一致。

• 对于状态转移方程

  如果a[i]==b[j]那么说明这个字符相等不需要操作，总次数还是前面a[0-(i-1)]和b[0-(j-1)]串操作的次数。

  如果a[i]！=b[j]那么就有三种可能取最小的啦并且加一 dp[i][j]=Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]))+1;

具体可以参考下图：

实现代码：

public int minDistance(String word1, String word2) {
  char ch1[]=word1.toCharArray();
  char ch2[]=word2.toCharArray();
  if(word1.length()==0)return word2.length();
  if(word2.length()==0)return word1.length();
  int dp[][]=new int[ch1.length+1][ch2.length+1];
  for(int i=1;i<ch1.length+1;i++)
  { dp[i][0]=i;
  }
  for(int j=1;j<ch2.length+1;j++)
  { dp[0][j]=j;
  }
  for(int i=1;i<ch1.length+1;i++)
  { for(int j=1;j<ch2.length+1;j++) { if(ch1[i-1]==ch2[j-1]) { dp[i][j]=dp[i-1][j-1]; } else { dp[i][j]=Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]))+1; } }
  }
  return dp[ch1.length][ch2.length];	
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
 

结语

原创不易，bigsai请你帮两件事帮忙一下:

1. star支持一下， 您的肯定是我在平台创作的源源动力。

2. 微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/110285461