can someone help me,why mle?


  • 0
    Y

    the following is my solution, the problem is just the problem at cf,http://codeforces.com/problemset/problem/282/E, i think they are same, sorry for my bad english.

    struct node{
            int next[2];
            node() {
                next[0] = next[1] = 0;
            }
        };
    class Solution {
    public:
       
        void add(vector<node*> &v, int x) {
            int u = 0;
            for (int i = 31; i >= 0; i--) {
                int cur = (x & (1 << i)) > 0;
                if(!v[u]->next[cur]) {
                    node *t = new node;
                    v[u]->next[cur] = v.size();
                    v.push_back(t);
                }
                u = v[u]->next[cur];
            }
        }
        int work(vector<node*> &v, int x) {
            int res = 0;
            int u = 0;
            for (int i = 31; i >= 0; i--) {
                int cur = (x & (1 << i)) > 0;
                if(v[u]->next[cur ^ 1]) {
                    u = v[u]->next[cur ^ 1];
                    res |= (1 << i);
                } else {
                    u = v[u]->next[cur];
                }
            }
            return res;
        }
        int findMaximumXOR(vector<int>& nums) {
            int num = 0;
            vector<node*> v;
            node *root = new node;
            v.push_back(root);
            int n = nums.size();
            for (int i = 0; i < n; i++) add(v, nums[i]);
            int res = 0;
            for (int i = 0; i < n; i++) {
                res = max(res, work(v, nums[i]));
            }
            return res;
        }
    };
    

  • 0
    P

    I think the key is that you do not release the memory. You can allocate node[1<<20] at the first line of findMaximumXOR, and release them at the end.


  • 0
    K

    I wrote an independent solution using only shared_ptr and got the same "Memory Limit Exceeded" with tests: https://gist.github.com/KirillLykov/d427a8d6fa84482f87ad3317cf4a1d49
    So it doesn't look like that the problem is new without delete.


  • 0

    All your solutions are accepted now after removing some large test cases.


Log in to reply
 

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