lc421

贪心+hash，从最高位到最低位逐位确定最大异或值，利用掩码保留高位、异或配对验证的方式高效求解数组中两数的最大异或结果

 

反复询问 下一位能不能是1

 class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int high_bit = __lg(ranges::max(nums));
        int ans = 0, mask = 0;
        unordered_set<int> seen;
        for (int i = high_bit; i >= 0; i--) {

// 从最高位开始枚举
            seen.clear();
            mask |= 1 << i;
            int new_ans = ans | (1 << i); // 这个比特位可以是 1 吗？
            for (int x : nums) {
                x &= mask; // 低于 i 的比特位置为 0
                if (seen.contains(new_ans ^ x)) {
                    ans = new_ans;

    // 这个比特位可以是 1
                    break;
                }
                seen.insert(x);
            }
        }
        return ans;
    }
};

lc2225

hash统计每个选手的输场数

筛选出输场数为0和1的选手，分别排序后返回由这两类选手组成的二维数组。

class Solution {
public:
    vector<vector<int>> findWinners(vector<vector<int>>& matches) 
    {
        unordered_map<int,int> hash;
        for(auto& m:matches)
        {
            if(!hash.count(m[0]))
                hash[m[0]]=0;
            hash[m[1]]++;
        }
        vector<vector<int>> ret(2);
        for(auto& [a,b]:hash)
        {
            if(b==0) ret[0].push_back(a);
            if(b==1) ret[1].push_back(a);
        }
        ranges::sort(ret[0]);
        ranges::sort(ret[1]);
        return ret;
    }
};

lcp3
模拟机器人执行一次指令的路径

将路径坐标编码存入集合，计算目标点在指令循环后的剩余坐标，验证其是否在单次路径中；

再逐一校验障碍物坐标，若障碍物坐标在机器人到达目标点前的路径中则返回false，否则返回true

 

压缩tricks

st.insert(((long)cx << 30) | cy);

int cir = min(x / cx, y / cy);

class Solution {
public:
    bool robot(string cmd, vector<vector<int>>& obs, int x, int y)

  {
        unordered_set<long> st;
        int cx = 0, cy = 0;
        st.insert(0);
        for (char c : cmd) {
            if (c == 'U') cy++;
            else if (c == 'R') cx++;
            st.insert(((long)cx << 30) | cy);
        }

        int cir = min(x / cx, y / cy);
        if (!st.count(((long)(x - cir * cx) << 30) | (y - cir * cy)))

               return false; //圈数位置 无法抵达

        for (auto& v : obs) {
            if (v.size() != 2) continue;
            if (v[0] > x || v[1] > y) continue;
            cir = min(v[0] / cx, v[1] / cy);
            if (st.count(((long)(v[0] - cir * cx) << 30) | (v[1] - cir * cy)))

                  return false;

                // 障碍物位置 在移动集合中
        }
        return true;
    }
};