算法是码农的基本功，也是各个大厂必考察的重点，让我们一起坚持写题吧。

遇事不决，可问春风，春风不语，即是本心。

我们在我们能力范围内，做好我们该做的事，然后相信一切都事最好的安排就可以啦，慢慢来，会很快，向前走，别回头。

目录

1、简化路径

2、编辑距离

3、矩阵置零

4、搜索二维矩阵

5、颜色分类

---

1、简化路径

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/simplify-path/description/

思路：利用栈的思想，先按照/划分字符串，然后按照依次进站，遇到..，当前栈顶字符串出栈，全部元素入栈后，依次从栈底出栈拼接。

class Solution {public String simplifyPath(String path) {String [] str = path.split("/");LinkedList<String> stack = new LinkedList<>() ;for(String s : str){if(s.equals("..")){if(!stack.isEmpty()){stack.pop() ;}}else if(s.length() > 0 && !".".equals(s)){stack.push(s) ;}}StringBuilder sb = new StringBuilder("") ;if(stack.isEmpty()){return "/" ;}while(!stack.isEmpty()){sb.append("/") ;sb.append(stack.pollLast()) ;   }return sb.toString() ;}
}

2、编辑距离

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/edit-distance/description/

思路：本质上是动态规划的思想：dp[i][j] 表示将word1从第i位置转换到word2的第j位置需要最少多少步，主要判断有两种场景：一种是word1与word2当前值相等与不等。

相等： dp[i][j] = dp[i-1][j-1]

不等：dp[i][j] = Math.min(dp[i-1][j-1] ,Math.min(dp[i-1][j],dp[i][j-1])) + 1 ;

class Solution {public int minDistance(String word1, String word2) {int n = word1.length(), m = word2.length() ;// dp[i][j] 表示将word1从第i位置转换到word2的第j位置需要最少多少步int [][] dp = new int [n+1][m+1] ;for(int j=1; j<=m; j++){dp[0][j] = j ;}for(int i=1; i<=n; i++){dp[i][0] = i ;}for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(word1.charAt(i-1) == word2.charAt(j-1)){dp[i][j] = dp[i-1][j-1] ;}else{// 插入、删除、替换dp[i][j] = Math.min(dp[i-1][j-1] ,Math.min(dp[i-1][j],dp[i][j-1])) + 1 ;}}}return dp[n][m] ;}
}

3、矩阵置零

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/set-matrix-zeroes/description/

思路：用两个一维数组作为标记数组，标记出现0的行列，然后判断当前元素所在行列是否被标记，被标记的则置0.

class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length, n = matrix[0].length ;boolean [] row = new boolean [m] ;boolean [] col = new boolean [n] ;for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(matrix[i][j] == 0){row[i] = true ;col[j] = true ;}}}for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(row[i] || col[j]){matrix[i][j] = 0 ;}}}}
}

4、搜索二维矩阵

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/search-a-2d-matrix/

思路1:按行循环遍历即可。两层循环。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {for(int i=0; i<matrix.length; i++){for(int j=0; j<matrix[0].length; j++){if(matrix[i][j] == target){return true ;}if(matrix[i][j] > target){return false ;}}}return false ;}
}

思路2:从右上角向左侧和下方遍历，找到满足要求的数字，没找到则返回。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length , n = matrix[0].length ;int i = 0, j = n-1 ;while(i<m && j>=0){if(matrix[i][j]==target){return true ;}else if(matrix[i][j] > target){j -- ;}else{i ++ ;}}return false ;}
}

5、颜色分类

题目链接：. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/sort-colors/description/

思路：比较交换法。依次把0和1交换到最左侧，剩下的就是2在最右侧。

class Solution {public void sortColors(int[] nums) {// Arrays.sort(nums) ;int j = 0 ;for(int i=0; i<nums.length; i++){if(nums[i]==0){swap(nums, i, j) ;j ++ ;}}for(int i=j; i<nums.length; i++){if(nums[i]==1){swap(nums, i, j) ;j ++ ;}}}public void swap(int [] nums, int i, int j){int tmp = nums[i] ;nums[i] = nums[j] ;nums[j] = tmp ;}
}