38. Count and Say
题目：1、11、21、1211、111221、……
思路：从1到n依次获得
public class Solution { public String countAndSay(int n) { String ret = new String("1"); for(int i = 1; i < n; i++){ String pre = new String(ret); StringBuilder sb = new StringBuilder(); int j = pre.length()-1; while(j >= 0){ int count = 1; while(j > 0 && pre.charAt(j) == pre.charAt(j-1)){ count++; j--; } sb.insert(0,pre.charAt(j--)); sb.insert(0,count); } ret = sb.toString(); } return ret; } }58. Length of Last Word
题目：找到给定字符串最后一个单词的长度
思路：倒着做，很简单
public class Solution { public int lengthOfLastWord(String s) { if(s.length() == 0) return 0; int count = 0; int i = s.length()-1; while(i >= 0 && s.charAt(i) == ' ') { i--; } while(i >= 0 && s.charAt(i) != ' '){ count++; i--; } return count; } }71. Simplify Path
题目：对输入路径进行简化
思路：栈——注意要讨论所有情况
public class Solution { public String simplifyPath(String path) { Stack<String> stack = new Stack<>(); int len = path.length(); int i = 0; while(i < path.length()){ if(path.charAt(i) =='/'){ String sub = path.substring(i+1, len); int j = sub.indexOf('/'); if(j == -1){ if(!sub.equals("") && !sub.equals(".") && !sub.equals("..")) stack.push(sub); if(sub.equals("..") && !stack.isEmpty()) stack.pop(); break; } else{ String s = path.substring(i+1, i+1+j); if(!s.equals("") && !s.equals(".")){ if(s.equals("..")){ if(!stack.isEmpty()) stack.pop(); } else stack.push(s); } i = i+1+j; } } } String ret = new String(); if(stack.isEmpty()) return "/"; while(!stack.isEmpty()){ ret = "/"+stack.pop()+ret; } return ret; } } 利用split来划分会更简单 public String simplifyPath(String path) { Deque<String> stack = new LinkedList<>(); Set<String> skip = new HashSet<>(Arrays.asList("..",".","")); for (String dir : path.split("/")) { if (dir.equals("..") && !stack.isEmpty()) stack.pop(); else if (!skip.contains(dir)) stack.push(dir); } String res = ""; for (String dir : stack) res = "/" + dir + res; return res.isEmpty() ? "/" : res; }72. Edit Distance
题目：找到使两个字符串相同的最小步数（通过增删改）
思路：动态规划，想清楚状态就很简单了
public class Solution { public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); int[][] dp = new int[m+1][n+1]; dp[0][0] = 0; for(int i = 1; i < m+1; i++){ dp[i][0] = i; } for(int j = 1; j < n+1; j++){ dp[0][j] = j; } for(int i = 1; i < m+1; i++){ for(int j = 1; j < n+1; j++){ if(word1.charAt(j-1) != word2.charAt(i-1)){ dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1; } else{ dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1])+1, dp[i-1][j-1]); } } } return dp[m][n]; } }583. Delete Operation for Two Strings
题目：只通过删除操作使两个字符串相等
思路：与72题方法完全一致，只是当字符相等时，简化了判断过程，因为只能通过删除操作。
public class Solution { public int minDistance(String word1, String word2) { int m = word1.length(); int n = word2.length(); int[][] dp = new int[m+1][n+1]; dp[0][0] = 0; 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(word1.charAt(i-1) == word2.charAt(j-1)){ dp[i][j] = dp[i-1][j-1]; } else{ dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1])+1, dp[i-1][j-1]+2); } } } return dp[m][n]; } }