关于求职:上岸算法-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 < j; i++, j--) {a += "AEIOUaeiou".indexOf(s.charAt(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<Apple> 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<Apple> 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;
    }
}