All C++ solutions got LTE?


  • 8
    T

    I spent more than 2 hours, and I was mad because all of my solutions got LTE. Then I gave up, and tried to see others' solutions, but they were almost the same as mine. I thought maybe my implementation was bad. However, after I copied and pasted their ACCEPTED code, I still got LTE.

    I tried almost every c++ solution posted by the others. All of them got LTE. (Maybe when the author posted it, it could pass, but after that, something was wrong with the OJ).


  • 2
    T

    Well, finally, found a work solution (1744ms, still very slow comparing with other language).

    Summary based on my experiments: (may not correct)

    1. using unordered set --> LTE
    2. using vector involving push_back/pop_back --> LTE
    3. using stack/queue --> LTE
    4. using array (or vector but don't use push_back/pop_back, as the solusion of @yular ) -->Works
    
    class PhoneDirectory {
    
        vector<int> recycledNums;
        vector<bool> flag;
        int maxNum;
        int nextNum;
        int index;
        
    public:
          
        PhoneDirectory(int maxNumbers) {
            maxNum = maxNumbers;
            nextNum = 0;
            index = 0;
            flag.resize(maxNumbers,true);
            recycledNums.resize(maxNumbers);
        }
        
        int get() {
            if(nextNum==maxNum && index<=0) return -1;
            if(index>0)
            {
                int n = recycledNums[--index];
                flag[n] = false;
                return n;
            }
            flag[nextNum] = false;
            return nextNum++;
        }
        
        bool check(int number) {
            return number>=0 && number<maxNum && flag[number];
        }
        
        void release(int number) {
            if(number>=0 && number<maxNum && !flag[number])
            {
                recycledNums[index++]=number;
                flag[number] = true;
            }
        }
    };
    
    

  • 0

    @TTester said in All C++ solutions got LTE?:

    I tried almost every c++ solution posted by the others.

    I only see two posted c++ solutions. Do you see more?

    They could maybe be made faster by using vector<int> instead of vector<bool> or by even using arrays instead of vectors.

    Anyway, I just tried it myself, pretty optimal I think and it gets accepted almost every time, but still takes around 1700 ms. And not much more seems allowed. So I agree, seems to be a problem with the system. @1337c0d3r ?

    Here's mine:

    class PhoneDirectory {
    public:
        PhoneDirectory(int maxNumbers) {
            n = maxNumbers;
            available = new int[n];
            isAvailable = new bool[n];
            for (int i=0; i<n; i++) {
                available[i] = i;
                isAvailable[i] = true;
            }
        }
        
        ~PhoneDirectory() {
            delete available;
            delete isAvailable;
        }
    
        int get() {
            if (!n)
                return -1;
            int number = available[--n];
            isAvailable[number] = false;
            return number;
        }
        
        bool check(int number) {
            return isAvailable[number];
        }
        
        void release(int number) {
            if (!isAvailable[number]) {
                isAvailable[number] = true;
                available[n++] = number;
            }
        }
    private:
        int n;
        int *available;
        bool *isAvailable;
    };
    

  • 1
    T

    @StefanPochmann

    Thanks for the reply, explanation, and sharing your code.

    I only see two posted c++ solutions. Do you see more?

    No, I also saw two solutions myself. But I am not sure whether under other posts someone will post a c++ variant. I didn't check all posts.

    They could be made faster by using `vector<int>` instead of `vector<bool>`

    Thank you very much! That is new knowledge to me. One short explanation for this I found is here. It makes sense to me. Do you agree?

    Also, one piece of your code:

            delete available;
            delete isAvailable;
    

    I think it should be:

            delete [] available;
            delete [] isAvailable;
    

    That is what I learned, however since c++ syntax is keeping developing all the time, I don't know whether it has been simplified. But if I was wrong, I appreciate very much if you could let me know.


  • 0

    @TTester No, the delete was just me being a C++ noob :-). Looks like it indeed should be delete[]. I'm quite surprised that it compiled... usually the C++ compiler loves bombarding me with pages and pages of cryptic error messages for one tiny mistake like that.

    And yes, vector<bool> often being slow because it's optimized for space at the cost of speed is what I remember and meant.


  • 0
    F

    I tried all C++ solution posted in discussion, all of them failed now with TLE. It seems some problem of the question. @1337c0d3r


  • 0
    T

    @forestwn I retried. In 8 submissions, 4 passed and 4 got TLE. Even one got "Compile time limit exceeded". By changing the vector<bool> to vector<int>, (as suggested by StefanPochmann), 5/6 submissions passed. Additionally StenfanPochmann's answer also passed the test.


  • 0
    F

    @TTester Thanks for the reply! I tried today and it could pass now without any changes. It may because of the system status, or admin has updated it.
    But you are right, vector<int> is faster then vector<bool>


  • 0
    T
    This post is deleted!

  • 0
    P

    I used stack, and it was accepted

    typedef vector<bool> vb;
    class PhoneDirectory {
        int nMax,n;
        vb mark;
        stack<int> s;
    public:
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        PhoneDirectory(int maxNumbers):nMax(maxNumbers),n(0){
            mark = vb(maxNumbers,true);
        }
        
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        int get() {
            if(!s.empty()){
                int ans = s.top();
                s.pop();
                mark[ans] = false;
                return ans;
            }
            if(n<nMax){
                mark[n] = false;
                return n++;
            }
            return -1;
        }
        
        /** Check if a number is available or not. */
        bool check(int number) {
            if(number>=nMax) return false;
            return mark[number];
        }
        
        /** Recycle or release a number. */
        void release(int number) {
            if(!check(number) && number<nMax){
                s.push(number);
                mark[number] = true;
            }
        }
    };
    
    /**
     * Your PhoneDirectory object will be instantiated and called as such:
     * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
     * int param_1 = obj.get();
     * bool param_2 = obj.check(number);
     * obj.release(number);
     */
    

  • 0
    J

    I got the same problem. I was pretty astonished when I found using unordered_set is also TLE, cause in theory every operation except initialization is supposed to be O(1).


  • 0
    A
    This post is deleted!

Log in to reply
 

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