LeetCode 71-75

71. Simplify Path

分析：

此题考查栈的应用。
先用“/”将字符串分割。然后遍历所有的字符串，如果是“..”，说明要出栈。
如果是"." 不需要操作， 如果是""，说明有重复的斜杠，也不用操作。
其余情况都入栈。
最后从栈底往栈顶输出路径即可。

Java：

class Solution {
    public String simplifyPath(String path) {
        Stack<String> stack = new Stack();
        String[] strs = path.split("/");
        for (String str : strs) {
            if ("..".equals(str)) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else if (".".equals(str)) {

            } else {
                if (!"".equals(str)) {
                    stack.push(str);
                }
            }
        }
        if (stack.isEmpty()) {
            return "/";
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < stack.size(); i++) {
            res.append("/" + stack.get(i));
        }
        return res.toString();
    }
}

72. Edit Distance

分析：

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符，删除一个字符
，替换一个字符。
使用动态规划，dp[i][j]代表word1前i个字母和word2前j个字母之间的编辑距离。
边界：dp[0][j] = j ，dp[i][0] = i 。
转移方程 :
当word1.charAt(i - 1) == word2.charAt(j - 1)时，dp[i][j] = dp[i - 1][j - 1];
否则dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;

Java：

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

73. Set Matrix Zeroes

分析：

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为0。
先遍历一遍矩阵，将所有的0的行号和列号分别存入set中。
再遍历一遍矩阵，只要某一行或某一列存在于set中，就将那一行那一列的所有数置0。

Java：

class Solution {
    public void setZeroes(int[][] matrix) {
        Set<Integer> row = new HashSet<>();
        Set<Integer> col = new HashSet<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    row.add(i);
                    col.add(j);
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (row.contains(i) || col.contains(j)) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

74. Search a 2D Matrix

分析：

使用二分查找，把二维数组想象成一维的，lo初始为0，hi初始为行数乘以列数-1。
mid转化成数组中的位置的方法就是 mid/col行，mid%col列。

Java：

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

75. Sort Colors

分析：

方法一：
先遍历一次，统计红色白色蓝色的个数。 再遍历一次，将对应的值重新赋值给数组。
方法二：
一次遍历，用p0,p2,cur来分别追踪0的最右边界，2的最左边界，当前考虑的元素。
初始p0 = 0,p2 = nums.length-1,cur = 0
cur从左往右扫描，当nums[cur]等于0时，与p0位置的元素交换位置，并p0加1。
当nums[cur]等于1时，继续往右扫描。当nums[cur]等于2时，与p2位置的元素交换位置，并p2减1。 直到cur大于p2时就可以停止了。

Java：

class Solution {
    public void sortColors(int[] nums) {
        int red = 0, white = 0, blue = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                red++;
            } else if (nums[i] == 1) {
                white++;
            } else {
                blue++;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (red != 0) {
                nums[i] = 0;
                red--;
                continue;
            }
            if (white != 0) {
                nums[i] = 1;
                white--;
                continue;
            }
            if (blue != 0) {
                nums[i] = 2;
                blue--;
                continue;
            }
        }
    }
}

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0, cur = 0, p2 = nums.length - 1;
        int temp;
        while (cur <= p2) {
            if (nums[cur] == 0) {
                temp = nums[p0];
                nums[p0++] = nums[cur];
                nums[cur++] = temp;
            } else if (nums[cur] == 2) {
                temp = nums[cur];
                nums[cur] = nums[p2];
                nums[p2--] = temp;
            } else {
                cur++;
            }
        }
    }
}