23ms C++ DP version, beat 99.09%!


  • 0
    J
    class Solution {
        int max_xor = 0;
    
      public:
        int findMaximumXOR(const vector<int> &nums) {
            vector<bitset<32>> temp(nums.size());
            transform(nums.cbegin(), nums.cend(), temp.begin(),
                      [](const int i) { return bitset<32>((unsigned)i); });
    
            dp(move(temp), {}, 32 - 1, 0);
            return max_xor;
        }
    
      private:
        void dp(const vector<bitset<32>> nums_0, const vector<bitset<32>> nums_1,
                const int nth_bit, bitset<32> prev_val) {
            if (nth_bit == -1) {
                if (max_xor < prev_val.to_ulong()) {
                    max_xor = (int)prev_val.to_ulong();
                }
                return;
            }
    
            if (nums_0.empty() || nums_1.empty()) {
                const auto &ref = nums_0.empty() ? nums_1 : nums_0;
                vector<bitset<32>> new_nums_0;
                vector<bitset<32>> new_nums_1;
    
                for (const auto i : ref) {
                    if (i[nth_bit]) {
                        new_nums_1.push_back(i);
                    } else {
                        new_nums_0.push_back(i);
                    }
                }
    
                if (!new_nums_0.empty() && !new_nums_1.empty()) {
                    prev_val[nth_bit] = 1;
                }
                if (may_beat_max(prev_val, nth_bit))
                    return dp(move(new_nums_0), move(new_nums_1), nth_bit - 1,
                              prev_val);
            } else {
                vector<bitset<32>> new_nums_0_0;
                vector<bitset<32>> new_nums_1_1;
    
                vector<bitset<32>> new_nums_0_1;
                vector<bitset<32>> new_nums_1_0;
    
                for (const auto i : nums_0) {
                    if (i[nth_bit]) {
                        new_nums_0_1.push_back(i);
                    } else {
                        new_nums_0_0.push_back(i);
                    }
                }
                for (const auto i : nums_1) {
                    if (i[nth_bit]) {
                        new_nums_1_1.push_back(i);
                    } else {
                        new_nums_1_0.push_back(i);
                    }
                }
    
                if (!new_nums_0_0.empty() && !new_nums_1_1.empty()) {
                    prev_val[nth_bit] = 1;
                    dp(move(new_nums_0_0), move(new_nums_1_1), nth_bit - 1,
                       prev_val);
                }
    
                if (!new_nums_0_1.empty() && !new_nums_1_0.empty()) {
                    prev_val[nth_bit] = 1;
                    dp(move(new_nums_1_0), move(new_nums_0_1), nth_bit - 1,
                       prev_val);
                }
    
                if (prev_val[nth_bit] == 0) {
                    if (may_beat_max(prev_val, nth_bit))
                        return dp(move(nums_0), move(nums_1), nth_bit - 1,
                                  prev_val);
                }
            }
        }
    
        inline bool may_beat_max(bitset<32> val, int nth) {
            auto a = val.to_ulong() >> nth;
            auto b = max_xor >> nth;
    
            if (a < b) {
                return false;
            } else if (a != b) {
                max_xor = (int)val.to_ulong();
                return true;
            } else {
                return true;
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.