LeetCode 76-80

76. Minimum Window Substring

分析：

以后再做。

Java：

77. Combinations

分析：

使用回溯+剪枝。

Java：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    void dfs(int index, int n, int k) {
        if (temp.size() == k) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i <= n; i++) {
            temp.add(i);
            dfs(i + 1, n, k);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        dfs(1, n, k);
        return res;
    }
}

78. Subsets

分析：

回溯。使用index代表当前要访问的数组元素的下标。
当index等于数组长度时，结束递归。
回溯的过程中可以选第index号元素，也可以不选第index号元素。

Java：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public void dfs(int index, int[] nums) {
        if (index == nums.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        temp.add(nums[index]);
        dfs(index + 1, nums);
        temp.remove(temp.size() - 1);
        dfs(index + 1, nums);
    }

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        return res;
    }
}

79. Word Search

分析：

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
使用深度优先遍历。在遍历过程中判断字符串是否存在，如果不存在直接返回false。

Java：

class Solution {

    boolean[][] isVisit;
    int[] X = {0, 0, -1, 1};//上下左右
    int[] Y = {-1, 1, 0, 0};

    //对所有规则进行判断
    boolean check(char[][] board, int i, int j, int k, String word) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return false;
        }
        if (isVisit[i][j] == true) {
            return false;
        }
        if (board[i][j] == word.charAt(k)) {
            return true;
        } else {
            return false;
        }
    }


    boolean dfs(char[][] board, int i, int j, int k, String word) {
        if (k == word.length()) {
            return true;
        }
        if (check(board, i, j, k, word) == true) {
            isVisit[i][j] = true;
            for (int z = 0; z < 4; z++) {
                int newI = i + X[z];
                int newJ = j + Y[z];
                if (dfs(board, newI, newJ, k + 1, word) == true) {
                    return true;
                }
            }
            //如果某一点四个方向都不满足条件，改回false
            isVisit[i][j] = false;
        } else {
            return false;
        }
        return false;
    }

    public boolean exist(char[][] board, String word) {
        isVisit = new boolean[board.length][board[0].length];
        //从每一个字母开始出发进行DFS
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                boolean res = dfs(board, i, j, 0, word);
                if (res == true) {
                    return true;
                } else {
                    continue;
                }
            }
        }
        return false;
    }
}

80. Remove Duplicates from Sorted Array II

分析：

使用双指针，i为数组中要访问的元素位置，j为下一个要覆盖的元素的位置。使用count记录重复的个数，count值小于等于2时，覆盖掉j位置的元素。

Java：

class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 1, count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                count++;
            } else {
                count = 1;
            }
            if (count <= 2) {
                nums[j++] = nums[i];
            }
        }
        return j;
    }
}