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]; }
另外，本题还可以使用两个变量替代数组去优化空间
LeetCode 71 简化路径
题目描述
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1：
输入："/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。
示例 2：
输入："/../" 输出："/" 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3：
输入："/home//foo/" 输出："/home/foo" 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入："/a/./b/../../c/" 输出："/c"
示例 5：
输入："/a/../../b/../c//.//" 输出："/c"
示例 6：
输入："/a//bc/d//././/.." 输出："/a/b/c"
分析
这题就是栈的应用，通过栈遍历放入目录，在遍历字符串的同时如果遇到/ 那么就考虑进行操作。逻辑如下：
具体编写代码的时候，需要注意是否为最后一个字符和一些特殊情况(栈为空则别抛出)。
具体代码为：
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(); }
LeetCode 72编辑距离(dp)
题目描述
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500 word1 和 word2 由小写英文字母组成
分析
这题其实是有难度，笔者刚开始做的时候以为是最小公众子序列(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]; }
结语
原创不易，bigsai请你帮两件事帮忙一下:
- star支持一下， 您的肯定是我在平台创作的源源动力。
- 微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见！
