11.12打卡

1. 简化路径（70）

返回的 规范路径 必须遵循下述格式：

• 始终以斜杠 '/' 开头。
• 两个目录名之间必须只有一个斜杠 '/' 。
• 最后一个目录名（如果存在）不能 以 '/' 结尾。
• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 

思想： 栈

class Solution {
    public String simplifyPath(String path) {          String[] names =  path.split("/");
        Deque<String> s = new ArrayDeque<>();
        for (String name : names) {
            if("..".equals(name)){
                if(!s.isEmpty()){
                    s.pollLast();
                }
            }else if(name.length()>0&&!".".equals(name)){
                s.offerLast(name);
            }

        }
        StringBuffer res = new StringBuffer();
       
        if(s.isEmpty()){
            res.append('/');
        }else {
            while (!s.isEmpty()) {
                res.append('/').append(s.pollFirst());
            }
        }
        return res.toString();
    }
}

2. 编辑距离（72）

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

思想：动态规划

dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作

以 word1 为 "horse"，word2 为 "ros"，且 dp[5][3] 为例，即要将 word1的前 5 个字符转换为 word2的前 3 个字符，也就是将 horse 转换为 ros，因此有：

(1) dp[i-1][j-1]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro，然后将第五个字符 word1[4]（因为下标基数以 0 开始） 由 e 替换为 s（即替换为 word2 的第三个字符，word2[2]）

(2) dp[i][j-1]，即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro，然后在末尾补充一个 s，即插入操作

(3) dp[i-1][j]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros，然后删除 word1 的第 5 个字符

class Solution {
    public int minDistance(String word1, String word2) {
  int n1 = word1.length();
        int n2  = word2.length();
        int [][] dp = new int[n1+1][n2+1];
          for (int i = 1; i <=n2 ; i++) {
            dp[0][i]=dp[0][i-1]+1;
        }
        for (int i = 1; i <= n1; i++) {
            dp[i][0]=dp[i-1][0]+1;
        }
        for (int i = 1; i <=n1 ; i++) {
            for (int j = 1; j <=n2 ; 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]),dp[i-1][j-1])+1;
                }
            }
        }
        return dp[n1][n2];
    }
}

3. 矩阵置0（73）

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法

class Solution {
    public void setZeroes(int[][] matrix) {
        int[] rows  = new int[matrix.length];
        int[] cols  = new int[matrix[0].length];
        for (int i = 0; i <matrix.length ; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if(matrix[i][j]==0){
                    cols[j] = 1;
                    rows[i]=1;
                }
            }
        }

  for (int i = 0; i < rows.length; i++) {
            for (int j = 0; j < cols.length; j++) {
                if(rows[i]==1||cols[j]==1)
                    matrix[i][j]=0;
            }
        }
    }
}

4. 搜索二维矩阵（74）

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

思想： 将二维数组当作一维进行二分查找

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
   if(matrix == null || matrix.length == 0){
            return false;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int left = 0;
        int right = row*col-1;
        while(left <= right){
            int mid = left + (right - left)/2;
            int val = matrix[mid / col][mid % col];
            if(val == target){
                return true;
            }
            else if(val > target){
                right = mid-1;
            }
            else{
                left = mid + 1;
            }
        }
        return false;

    }
}

5. 颜色分类（75）

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。整数 0、 1 和 2 分别表示红色、白色和蓝色。

思想：双指针，p0标记0 的位置更新，p1标记1 的位置更新

class Solution {
    public void sortColors(int[] nums) {
  int n = nums.length;
        int p0=0;
        int p1=0;
        for (int i = 0; i <n ; i++) {
            if(nums[i]==1){
                swaper(nums,i,p1);
                p1++;
            }else if(nums[i]==0){
                swaper(nums,i,p0);
                if(p0<p1){
                    swaper(nums,p1,i);
                  
                }
                  p0++;
                 p1++;
            }
        }
    }
    public void swaper(int[] nums,int i,int p0){
        int temp = nums[i];
        nums[i] = nums[p0];
        nums[p0] = temp;
    }
    }