上陸アルゴリズムI LeetCode Weekly Contest 221解題報告

No.1
文字列の半分が似ているかどうかを判断する
問題を解く構想.
母音アルファベットの数を統計すればいいです.
コードディスプレイ

class Solution {
    public boolean halvesAreAlike(String s) {
        int n = s.length();
        int a = 0, b = 0;
        for (int i = 0, j = n - 1; i = 0 ? 1 : 0;
            b += "AEIOUaeiou".indexOf(s.charAt(j)) >= 0 ? 1 : 0;
        }
        return a == b;
    }
}

No.2
りんごを食べる最大数
問題を解く構想.
欲張りな考えで、私たちはいつも残りのりんごの中で最初に腐ってしまった.優先キューを使用すると、残りのアップルが先に腐っているものを維持することができます.
コードディスプレイ

class Solution {
    static class Apple {
        int num;
        int day;

        public Apple(int num, int day) {
            this.num = num;
            this.day = day;
        }
    }

    public int eatenApples(int[] apples, int[] days) {
        PriorityQueue bucket = new PriorityQueue<>(Comparator.comparingInt(a -> a.day));
        int res = 0;
        for (int i = 0; i < apples.length; i++) {
            if (apples[i] > 0) {
                bucket.add(new Apple(apples[i], i + days[i]));
            }
            res += eat(bucket, i);
        }
        //       ，      
        for (int i = apples.length; !bucket.isEmpty(); i++) {
            res += eat(bucket, i);
        }
        return res;
    }

    //    day     ，         (0   1)
    private int eat(PriorityQueue bucket, int day) {
        while (!bucket.isEmpty()) {
            Apple a = bucket.poll();
            if (a.day <= day) {
                continue;
            }
            if ((--a.num) > 0) {
                bucket.add(a);
            }
            return 1;
        }
        return 0;
    }
}

No.3
ボールはどこへ落ちるの
問題を解く構想.
ボールの落下をシミュレートすればいいです.
コードディスプレイ

class Solution {
    public int[] findBall(int[][] grid) {
        int m = grid[0].length;
        int[] res = new int[m];
        for (int i = 0; i < m; i++) {
            res[i] = drop(0, i, grid);
        }
        return res;
    }

    private int drop(int x, int y, int[][] grid) {
        if (x == grid.length) {
            return y;
        }
        if (grid[x][y] == 1 && (y == grid[0].length - 1 || grid[x][y + 1] == -1)) {
            return -1;
        }
        if (grid[x][y] == -1 && (y == 0 || grid[x][y - 1] == 1)) {
            return -1;
        }
        return drop(x + 1, y + grid[x][y], grid);
    }
}

No.4
配列内の要素との最大異種または値
問題を解く構想.
辞書の木.
バイナリ数の異或演算の意味は両者が異なるかどうかを知っています.だから、Trieツリー上でできるだけ現在のビットとは異なるパスを歩けばいいです.
コードディスプレイ

class Solution {
    class TrieNode {
        int min; //          
        TrieNode[] child;

        public TrieNode() {
            min = Integer.MAX_VALUE;
            child = new TrieNode[2];
        }
    }

    public int[] maximizeXor(int[] nums, int[][] queries) {
        int min = Arrays.stream(nums).min().getAsInt();

        //    ，     32    Trie  
        TrieNode root = new TrieNode();
        for (int num : nums) {
            TrieNode cur = root;
            for (int m = 30; m >= 0; m--) {
                cur.min = Math.min(cur.min, num);
                int d = (num >> m) & 1;
                if (cur.child[d] == null) {
                    cur.child[d] = new TrieNode();
                }
                cur = cur.child[d];
                cur.min = Math.min(cur.min, num);
            }
        }

        //   
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            if (queries[i][1] < min) {
                res[i] = -1;
                continue;
            }
            TrieNode cur = root;
            for (int m = 30; m >= 0 && cur != null; m--) {
                int xd = (queries[i][0] >> m) & 1; //     xd ^ 1     
                TrieNode except = cur.child[xd ^ 1];
                if (except == null || except.min > queries[i][1]) {
                    cur = cur.child[xd];
                } else {
                    cur = except;
                }
            }
            res[i] = cur == null || cur.min > queries[i][1] ? -1 : cur.min ^ queries[i][0];
        }
        return res;
    }
}