Some body has all the test cases for this proplem?


  • 0
    L

    the system tells me runtime error in the case when k=1000000000,but I run my code quit well for this case on my computer VS2010 IDE.
    so now i want all the test cases to test whether my code has logical error.
    @Freezen,do you have any?

    typedef struct PAIR{
            int value;
            int p,v;
        }*PPAIR;
        struct PAIR pairbuff[15001];
        PPAIR minheap[15001];
        int flag[27001];
        int linklist[27001][2];
        void HeapAdd(PPAIR heap[],int n,PPAIR e){
            n--;
            heap[n]=e;
            int parent=n>>1;
            while(n>0 && (heap[n]->value < heap[parent]->value)){
                PPAIR tem;
                tem=heap[parent];
                heap[parent]=heap[n];
                heap[n]=tem;
                n=parent;
                parent=n>>1;
            }
        }
        void HeapKeep(PPAIR heap[],int n){
            n--;
            int p=1;
            while(p<=n){
                int parent=p>>1;
                int min=parent;
                if(heap[p]->value < heap[parent]->value)
                    min=p;
                else if(p+1<=n && heap[p+1]->value < heap[min]->value)
                    min=p+1;
                if(min!=parent){
                    PPAIR tem;
                    tem=heap[parent];
                    heap[parent]=heap[min];
                    heap[min]=tem;
                }
                p=(p<<1)+1;
            }
            return;
        }
        
        PPAIR HeapTop(PPAIR heap[]){
            return heap[0];
        }
        int maxProfit(int k, int prices[], int n){
            int transactions=0;
            int v=-1,p=-1;
            int lastv=-1,lastp=-1;
            int maxp=0;
            int heapmaxi=0;
            while(p<n){
                for(v=p+1;v<n-1 && prices[v]>prices[v+1];v++);
                if(v>n-2) break;
                for(p=v+1;p<n-1 && prices[p+1]>prices[p];p++);
                if(p>n-1) break;
                if(p>=0 && v>=0){
                    flag[p]=1;
                    flag[v]=1;
                    heapmaxi++;
                    pairbuff[heapmaxi].value=prices[p]-prices[v];
                    pairbuff[heapmaxi].p=p;
                    pairbuff[heapmaxi].v=v;
                    HeapAdd(minheap,heapmaxi,&pairbuff[heapmaxi]);
                    transactions++;
                    maxp+=pairbuff[heapmaxi].value;
                    if(lastv>=0 && lastp>=0){
                        heapmaxi++;
                        pairbuff[heapmaxi].value=prices[lastp]-prices[v];
                        pairbuff[heapmaxi].p=lastp;
                        pairbuff[heapmaxi].v=v;
                        HeapAdd(minheap,heapmaxi,&pairbuff[heapmaxi]);
                    }
                    linklist[v][0]=lastp;
                    linklist[v][1]=p;
                    linklist[p][0]=v;
                    if(lastp>0)
                        linklist[lastp][1]=v;
                    lastv=v;
                    lastp=p;
                }
            }
            while(transactions>k){
                PPAIR e=HeapTop(minheap);
                if(e!=0){
                    int tem1,tem2;
                    if(e->p>e->v){
                        tem1=e->v;
                        tem2=e->p;
                    }
                    else{
                        tem1=e->p;
                        tem2=e->v;
                    }
                    if(flag[e->p]==1 && flag[e->v]==1)
                        transactions--;
        
                    if(linklist[tem1][0]>=0 && linklist[tem2][1]>=0 && flag[e->p]==1 && flag[e->v]==1){
                        flag[e->p]=0;
                        flag[e->v]=0;
                        maxp-=(prices[e->p]-prices[e->v]);
                        int temp=prices[linklist[tem2][1]]-prices[linklist[tem1][0]];
                        if(temp>0){
                            e->p=linklist[tem2][1];
                            e->v=linklist[tem1][0];
                            e->value=temp;
                        }
                        else{
                            e->p=linklist[tem1][0];
                            e->v=linklist[tem2][1];
                            e->value=-temp;
                        }
                        linklist[linklist[tem1][0]][1]=linklist[tem2][1];
                        linklist[linklist[tem2][1]][0]=linklist[tem1][0];
                    }
                    else{
                        if(linklist[tem1][0]<0 && linklist[tem2][1]>=0 && flag[e->p]==1 && flag[e->v]==1){
                            linklist[linklist[tem2][1]][0]=-1;
                            linklist[tem2][0]=-1;
                            maxp-=(prices[e->p]-prices[e->v]);
                        }
                        else if(linklist[tem1][0]>=0 && linklist[tem2][1]<0 && flag[e->p]==1 && flag[e->v]==1){
                            linklist[tem1][1]=-1;
                            linklist[linklist[tem1][0]][1]=-1;
                            maxp-=(prices[e->p]-prices[e->v]);
                        }
                        e->value=999999;
                    }
                    HeapKeep(minheap,heapmaxi);
                }
            }
            return maxp;
        }

  • 0
    J

    I got the same runtime error for k=1000000000 case. I tested my solution with k=2 case and it all passed.


Log in to reply
 

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