[946] Validate Stack Sequences

寫出了一個垃圾...我替我自己感到難過...(痛哭)

但是沒有掙扎很久就寫出來了, 某種程度上還是算有進步吧XD

只是把題目想的太難了啊啊啊啊啊（抱頭)

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) {

int *push_idx = calloc (10001, sizeof(int));

memset(push_idx, -1, sizeof(int)*(pushedSize+1));

int *stack = calloc (pushedSize , sizeof(int));

int i=0,j=0;

int head = -1;

for (int i=0; i<pushedSize;i++)

{

push_idx [pushed[i]]= i;

}

for (j=0; j<poppedSize; j++)

{

int pivot = popped[j];

int idx = push_idx[pivot];

if (idx < 0) // something wrong , which should not happen

return false;

if (pushed[idx] >=0) // not poped yet , do push

{

while (pushed[i] != pivot && i< pushedSize )

{

stack[++head] = pushed[i];

pushed[i++]= -1; //marked as pushed

}

if (i==pushedSize)

return false;

// push pivot then pop it

{

pushed[i++]= -1; //marked as pushed

push_idx[pivot] = -1;

}

}

else // poped already,

{

while (stack[head] != pivot && head >=0)

{

push_idx[stack[head--]]=-1;//marked as poped

}

if (head < 0 && j < pushedSize )

return false;

}

}

return true;

}

過兩天再來更新版吧(?) 

更一版～完全可以看出各種漏洞XD

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) {

    int *stack= calloc(pushedSize, sizeof(int));

    int head = -1;

    int j=0;

    for (int i=0; i<pushedSize; i++)

    {

        //push

        stack[++head] = pushed[i];

        while (stack[head]==popped[j])

        {

            stack[head--]= -1;

            j++;

            if (head < 0 || j==poppedSize)

                break;

        }

    }    

    if (j== poppedSize && head <0)

        return true;

    else

        return false;

}

更二版～別人的最佳解

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) {

int *stack= calloc(pushedSize, sizeof(int));

int head = -1;

int j=0;

for (int i=0; i<pushedSize; i++)

{

//push

stack[++head] = pushed[i];

while (head >=0 && stack[head]==popped[j])

{

stack[head--]= -1; //其實可以head-- 就好！！！

j++;

}

}

return (head == -1);

}