LeetCode(47) -- 997, 999, 1002

P997. Find the Town Judge (Easy)

找出法官。一个城镇里，所有的人用1~N来编号，其中一个人传说是法官。如果法官存在，那么：

1. 法官不相信任何人
2. 每个人（除了法官自己）都相信法官
3. 如果法官存在，只有一个法官。

trust[i] = [a, b]表示a相信b。

我的思路

如果一个人是法官，那么他不可能是a那个位置，所以我先遍历一次，把所有a那个位置的数标记出来。然后剩下没标记的，就有可能是法官。

在所有有可能是法官的人当中，再遍历一次，查看是不是所有其他人都相信他。

我的代码

class Solution {
    public int findJudge(int N, int[][] trust) {
        boolean[] isNotJudge = new boolean[N + 1];
        for (int[] trustPair : trust) {
            isNotJudge[trustPair[0]] = true;
        }
        possibleJudge:
        for (int i = 1; i < isNotJudge.length; i++) {
            boolean[] trustMe = new boolean[N + 1];
            if (!isNotJudge[i]) { // i is possible a judge
                for (int[] trustPair : trust) {
                    if (trustPair[1] == i) {
                        trustMe[trustPair[0]] = true;
                    }
                }
                for (int j = 1; j < trustMe.length; j++) {
                    if (!trustMe[j] && j != i) {
                        continue possibleJudge;
                    }
                }
                return i;
            }
        }
        return -1;
    }
}

94%

最优解

class Solution {
    public int findJudge(int N, int[][] trust) {
        if (N == 1 && trust.length == 0)
            return 1;

        boolean[] trustsSomeone = new boolean[N + 1];
        int[] numTrusters = new int[N + 1];

        for (int[] t : trust) {
            int truster = t[0];
            int trusted = t[1];

            trustsSomeone[truster] = true;
            numTrusters[trusted]++;
        }

        int judge = -1;
        for (int i = 1; i < N + 1; i++) {
            if (!trustsSomeone[i] && numTrusters[i] == N - 1)
                judge = i;
        }

        return judge;
    }
}

这个逻辑性非常好，值得学习！他用一个整数的数组记录下来相信他的人数，这样只需要一趟就完成了所有的工作。

P999. Available Captures for Rook (Easy)

国际象棋，只有一个白车，可能有白象或黑卒。问白车可以吃到几个黑卒。

我的思路

先找到白车的位置，然后延四个方向检查。只要不是“.”就移动到下一格，直到找到一个字母为止。然后再看这个字母，如果是黑卒，count++

我的代码

代码1：

class Solution {
    public int numRookCaptures(char[][] board) {
        int x = 0, y = 0, count = 0;
        searchRoot:
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
               if (board[i][j] == 'R') {
                   x = i;
                   y = j;
                   break searchRoot;
               }
            }
        }
        // up
        int up = x - 1;
        while (up >= 0 && board[up][y] == '.') {
            up--;
        }
        if (up >= 0 && board[up][y] == 'p') {
            count++;
        }

        // down
        int down = x + 1;
        while (down < 8 && board[down][y] == '.') {
            down++;
        }
        if (down < 8 && board[down][y] == 'p') {
            count++;
        }

        // left
        int left = y - 1;
        while (left >= 0 && board[x][left] == '.') {
            left--;
        }
        if (left >= 0 && board[x][left] == 'p') {
            count++;
        }

        // right
        int right = y + 1;
        while (right < 8 && board[x][right] == '.') {
            right++;
        }
        if (right < 8 && board[x][right] == 'p') {
            count++;
        }

        return count;
    }
}

100%。 延四个方向检查。代码重复比较多，所以重构了一个辅助方法。

代码2：

public class E_999_AvailableCapturesforRook {
    public int numRookCaptures(char[][] board) {
        int x = 0, y = 0, count = 0;
        searchRoot:
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
               if (board[i][j] == 'R') {
                   x = i;
                   y = j;
                   break searchRoot;
               }
            }
        }
        count += checkDirection(board, x, y, 1, 0);
        count += checkDirection(board, x, y, -1, 0);
        count += checkDirection(board, x, y, 0, 1);
        count += checkDirection(board, x, y, 0, -1);
        return count;
    }

    private int checkDirection (char[][] board, int x, int y, int dx, int dy) {
        int newX = x + dx;
        int newY = y + dy;
        while (newX >= 0 && newX < 8 && newY >= 0 && newY < 8 && board[newX][newY] == '.') {
            newX += dx;
            newY += dy;
        }
        if (newX >= 0 && newX < 8 && newY >= 0 && newY < 8 && board[newX][newY] == 'p') {
            return 1;
        }
        return 0;
    }
}

最优解

class Solution {
    public int numRookCaptures(char[][] board) {
        if (board == null) return 0;
        int count = 0;
        for (int i=0; i<board.length; i++) {
            for (int j=0; j<board.length; j++) {
                if (board[i][j] == 'R') {
                    for (int s=i+1; s<board.length; s++) {
                        if (board[s][j] == 'B') {
                            break;
                        } else if (board[s][j] == 'p') {
                            count++;
                            break;
                        }
                    }
                    for (int s=i-1; s>0; s--) {
                        if (board[s][j] == 'B') {
                            break;
                        } else if (board[s][j] == 'p') {
                            count++;
                            break;
                        }
                    }
                    for (int s=j-1; s>0; s--) {
                        if (board[i][s] == 'B') {
                            break;
                        } else if (board[i][s] == 'p') {
                            count++;
                            break;
                        }
                    }
                    for (int s=j+1; s<board.length; s++) {
                        if (board[i][s] == 'B') {
                            break;
                        } else if (board[i][s] == 'p') {
                            count++;
                            break;
                        }
                    }
                }
            }
        }
        return count;
    }
}

没什么大区别。

P1002. Find Common Characters (Easy)

一个字符串数组， 找到所有单词共同的字母，包含重复的。

我的思路

统计每个单词所有字母出现的次数，然后每次跟前面的统计比较，找到最小值。

我的代码

public class E_1002_FindCommonCharacters {
    public List<String> commonChars(String[] A) {
        int[] minLetters = new int[26];
        for (char c : A[0].toCharArray()) {
            minLetters[c - 'a']++;
        }
        for (int i = 1; i < A.length; i++) {
            int[] current = new int[26];
            for (char c : A[i].toCharArray()) {
                current[c - 'a']++;
            }
            for (int j = 0; j < minLetters.length; j++) {
                minLetters[j] = Math.min(minLetters[j], current[j]);
            }
        }
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < minLetters.length; i++) {
            for (int j = 0; j < minLetters[i]; j++) {
                ans.add(String.valueOf((char) (i + 'a')));
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        String[] A = {"cool","lock","cook"};
        List<String> strings = new E_1002_FindCommonCharacters().commonChars(A);
        System.out.println("strings.toString() = " + strings.toString());
    }

}

77%

最优解

class Solution {
    public List<String> commonChars(String[] A) {
        List<String> common = new ArrayList<>();
        int[] h = hash(A[0]);
        for (String a : A) intersect(h, hash(a));
        for (int i = 0; i < h.length; i++) {
            for (int j = 0; j < h[i]; j++) {
                common.add(String.valueOf((char)(i + 'a')));
            }
        }
        return common;
    }

    private int[] hash(String s) {
        int[] h = new int[26];
        for (Character c : s.toCharArray()) h[c - 'a']++;
        return h;
    }

    private int[] intersect(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) a[i] = Math.min(a[i], b[i]);
        return a;
    }
}

基本思路一样，但代码用了两个辅助方法，比较条理清晰。