C++ DFS search with path cut 136ms


  • 0
    S
    class Solution {
    public:
        void divide(vector<int> &a, vector<int> &a0, vector<int> &a1, int bitPos) {
            if (bitPos > 31 || bitPos < 0) return;
            for (int i = 0; i < a.size(); i++) {
                if ((a[i] & (1<<bitPos)) == 0) {
                    a0.push_back(a[i]);
                } else {
                    a1.push_back(a[i]);
                }
            }
        }
        //a0 and a1 are divided by bitPos, you want to see if there is a possibility
        int dfs(vector<int> &a0, vector<int> &a1, int bitPos, int cur_val, int cur_max) {
            if (bitPos == 0) {
                if (a0.size() && a1.size()) {
                    cur_val |= (1<<bitPos);
                    cur_max = max(cur_val, cur_max);
                }
                return cur_max;
            }
            
            if (!a0.size() || !a1.size()) {
                vector<int> &c = a0.size() ?a0 :a1;
                vector<int> c0, c1;
                divide(c, c0, c1, bitPos-1);
                return dfs(c0, c1, bitPos-1, cur_val, cur_max);
            }
            
            cur_val |= (1<<bitPos);
            cur_max = max(cur_val, cur_max);
            //cout << bitPos << "_" << cur_max << endl;
            
            vector<int> a00, a01, a10, a11;
            divide(a0, a00, a01, bitPos-1);
            divide(a1, a10, a11, bitPos-1);
            
            int a0011 = 0, a0110 = 0;
            if (a00.size() && a11.size()) {
                a0011 = dfs(a00, a11, bitPos-1, cur_val, cur_max);
            }
            // else parts of the elements will be dropped
            if (a01.size() && a10.size()) {
                a0110 = dfs(a01, a10, bitPos-1, cur_val, cur_max);
            }
          
            if (a0011 || a0110) {
                cur_max = max(max(a0011, a0110), cur_max);
                return cur_max;
            }
            //can't divide by this bit; then merge
            a0.insert(a0.end(), a1.begin(), a1.end());
            a1.clear();
            return dfs(a0, a1, bitPos-1, cur_val, cur_max);
        }
        
        int findMaximumXOR(vector<int>& nums) {
            vector<int> nums1;
            int cur_val = 0, cur_max = 0;
            return dfs(nums, nums1, 31, cur_val, cur_max);
        }
    };
    

Log in to reply
 

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