LeetCode 126-130

126. 单词接龙 II

先使用bfs记录每个结点的前驱，然后使用dfs获得所有最短路径。

class Solution {
    Map<String, Set<String>> pre = new HashMap<>();//存放每个单词的前驱
    List<List<String>> res = new ArrayList<>();//最终结果
    List<String> temp = new ArrayList<>();//临时路径

    public void dfs(String endWord, String beginWord) {
        if (endWord.equals(beginWord)) {
            Collections.reverse(temp);
            res.add(new ArrayList<>(temp));
            Collections.reverse(temp);//还得转回来，不然会影响后面的结果
            return;
        }
        Set<String> set = pre.get(endWord);
        for (String s : set) {
            temp.add(s);
            dfs(s, beginWord);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);//使用set加快搜索
        if (set.isEmpty() || !set.contains(endWord)) {
            return new ArrayList<>();
        }
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        q.offer(beginWord);
        visited.add(beginWord);
        set.add(beginWord);
        boolean finish = false;
        while (!q.isEmpty()) {
            int size = q.size();
            Set<String> s = new HashSet<>();//关键点，每一层遍历完之后才能把这一层加到已访问中
            for (int i = 0; i < size; i++) {
                String front = q.poll();
                char[] array = front.toCharArray();
                for (int j = 0; j < array.length; j++) {
                    char temp = array[j];
                    for (char k = 'a'; k <= 'z'; k++) {
                        array[j] = k;
                        String word = String.valueOf(array);
                        if (word.equals(endWord)) {
                            finish = true;
                        }
                        if (!visited.contains(word) && set.contains(word)) {
                            if (pre.containsKey(word)) {
                                Set<String> se = pre.get(word);
                                se.add(front);
                                pre.put(word, se);
                            } else {
                                Set<String> se = new HashSet<>();
                                se.add(front);
                                pre.put(word, se);
                            }
                            s.add(word);
                            q.add(word);
                        }
                        array[j] = temp;
                    }
                }
            }
            visited.addAll(s);
            if (finish == true) {
                break;
            }
        }
        if (pre.isEmpty()) {
            return new ArrayList<>();
        }
        temp.add(endWord);
        dfs(endWord, beginWord);
        return res;
    }
}

127. 单词接龙

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        if (set.size() == 0 || !set.contains(endWord)) {
            return 0;
        }
        set.remove(beginWord);
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        int step = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String front = q.poll();
                char[] charArray = front.toCharArray();
                for (int j = 0; j < charArray.length; j++) {
                    char temp = charArray[j];
                    for (char k = 'a'; k <= 'z'; k++) {
                        if (k == charArray[j]) {
                            continue;
                        }
                        charArray[j] = k;
                        String word = String.valueOf(charArray);
                        if (word.equals(endWord)) {
                            return step + 1;
                        }
                        if (set.contains(word) && !visited.contains(word)) {
                            q.add(word);
                            visited.add(word);
                        }
                    }
                    charArray[j] = temp;
                }
            }
            step++;
        }
        return 0;
    }
}

128. 最长连续序列

class Solution {
    int[] father, size;
    int res = 1;

    public void init() {
        for (int i = 0; i < father.length; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }
    //没有写路径压缩
    public int findFather(int x) {
        while (father[x] != x) {
            x = father[x];
        }
        return x;
    }

    public void merge(int a, int b) {
        int faA = findFather(a), faB = findFather(b);
        if (faA != faB) {
            father[faA] = faB;
            size[faB] += size[faA];
            res = Math.max(res, size[faB]);
        }
    }

    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        father = new int[nums.length];
        size = new int[nums.length];
        init();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (Integer key : map.keySet()) {
            if (map.containsKey(key + 1)) {
                merge(map.get(key), map.get(key + 1));
            }
        }
        return res;
    }
}

129. 求根到叶子节点数字之和

class Solution {
    int res = 0;

    public void dfs(TreeNode root, int num) {
        if (root == null) {
            return;
        }
        num *= 10;
        num += root.val;
        if (root.left == null && root.right == null) {
            res += num;
        }
        dfs(root.left, num);
        dfs(root.right, num);
    }

    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return res;
    }
}

class Solution {
    public int sumNumbers(TreeNode root) {
        return helper(root, 0);
    }

    public int helper(TreeNode root, int i) {
        if (root == null) return 0;
        int temp = i * 10 + root.val;
        if (root.left == null && root.right == null)
            return temp;
        return helper(root.left, temp) + helper(root.right, temp);
    }
}

130. 被围绕的区域

首先对边界上每一个'O'做深度优先搜索，将与其相连的所有'O'改为'-'。然后遍历矩阵，将矩阵中所有'O'改为'X',将矩阵中所有'-'变为'O'

class Solution {
    int row, col;

    public void dfs(char[][] board, int i, int j) {
        if (i < 0 || j < 0 || i >= row || j >= col || board[i][j] != 'O') {
            return;
        }
        board[i][j] = '-';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    }

    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        row = board.length;
        col = board[0].length;
        for (int i = 0; i < row; i++) {
            dfs(board, i, 0);
            dfs(board, i, col - 1);
        }
        for (int j = 0; j < col; j++) {
            dfs(board, 0, j);
            dfs(board, row - 1, j);
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '-') {
                    board[i][j] = 'O';
                }
            }
        }
    }
}