Leetcode 周赛题解 221

输入：s = "book"
输出：true
解释：a = "bo" 且 b = "ok" 。a 中有 1 个元音，b 也有 1 个元音。所以，a 和 b 相似。

class Solution {
public:
    bool halvesAreAlike(string s) {
        int cnt = 0, ret = 0;
        string tmp = "aeiou";
        int n = s.length() / 2;
        for(char c: s) {
            for(char d: tmp) {
                if(c == d || c == d - 'a' + 'A') {
                    ++ cnt;
                    c = -1;
                }
            }
            -- n;
            if(n == 0) ret = cnt;
        }
        return cnt == ret * 2;
    }
};

输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
输出：7
解释：你可以吃掉 7 个苹果：
- 第一天，你吃掉第一天长出来的苹果。
- 第二天，你吃掉一个第二天长出来的苹果。
- 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
- 第四天到第七天，你吃的都是第四天长出来的苹果。

class Solution {
public:
    struct node {
        int ed, num;
        //ed 表示苹果截止日期
        //num 表示苹果个数
        bool operator <(const node &b) const {
            return ed < b.ed;
        }
    };
    const int MXN = 4e4 + 5;
    int eatenApples(vector<int>& apples, vector<int>& days) {
        set<node> st;
        int n = apples.size(), cnt = 0;
        for(int i = 1; i < MXN; ++i) {
            if(i <= n && apples[i - 1] != 0 && days[i - 1] != 0) st.insert(node{i - 1 + days[i - 1], apples[i - 1]});
            if(st.empty()) continue;
            node p = *st.begin();
            st.erase(st.begin());
            if(i <= p.ed) {//可以吃苹果就吃
                -- p.num;
                ++ cnt;
                if(p.num) st.insert(p);//还有剩的就继续放进去
            }
            else -- i;//可能set中还有苹果没用到，所以第i天至少还要判断一次
        }
        return cnt;
    }
};

输入：grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
输出：[1,-1,-1,-1,-1]
解释：示例如图：
b0 球开始放在第 0 列上，最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。
b2 球开始放在第 2 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b3 球开始放在第 3 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b4 球开始放在第 4 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。

class Solution {
public:
    vector<int> findBall(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> ans(n, -1);
        for(int i = 0; i < n; ++i) {//第i列球
            int now = i, flag = 1;//当前在第now列
            for(int j = 0; j < m; ++j) {//当前在第j行
                if(grid[j][now] == 1) {//向右滑
                    if(now + 1 == n || grid[j][now + 1] == -1) flag = 0;
                    ++ now;
                }else {
                    if(now == 0 || grid[j][now - 1] == 1) flag = 0;
                    -- now;
                }
                if(flag == 0) break;
            }
            if(flag) ans[i] = now;
        }
        return ans;
    }
};

输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.

const int INF = 0x3f3f3f3f;
const int MXN = 1e5 * 32 + 11;
class Solution {
public:
    int trie[MXN][2], siz, Min[MXN];
    int newNode() {
        ++ siz;
        trie[siz][0] = trie[siz][1] = -1;
        Min[siz] = INF;
        return siz;
    }
    void add(int x) {
        int rt = 0;
        for(int i = 31; i >= 0; --i) {
            Min[rt] = min(Min[rt], x);
            int now = (x >> i) & 1;
            if(trie[rt][now] == -1) trie[rt][now] = newNode();
            rt = trie[rt][now];
        }
        Min[rt] = x;
    }
    int check(int x, int m) {
        int rt = 0, ans = -1;
        for(int i = 31; i >= 0; --i) {
            int now = (x >> i) & 1;
            int vis[2] = {0, 0};
            if(trie[rt][0] != -1 && Min[trie[rt][0]] <= m) vis[0] = 1;
            if(trie[rt][1] != -1 && Min[trie[rt][1]] <= m) vis[1] = 1;
            if(vis[!now]) {
                if(ans == -1) ans = 0;
                ans += (1 << i);
                rt = trie[rt][!now];
            }else if(vis[now]) {
                if(ans == -1) ans = 0;
                rt = trie[rt][now];
            }else {
                ans = -1;
                break;
            }
        }
        return ans;
    }
    vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size(), m = queries.size();
        vector<int> ans(m, -1);
        siz = 0;
        trie[siz][0] = trie[siz][1] = -1;
        Min[siz] = INF;
        for(int i = 0; i < n; ++i) add(nums[i]);
        for(int i = 0; i < m; ++i) {
            ans[i] = check(queries[i][0], queries[i][1]);
        }
        return ans;
    }
};