leetcode刷题(71-75)

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

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

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

目录

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 ;
    }
}