【每日刷题】Day35

【每日刷题】Day35

🥕个人主页：开敲🍉

🔥所属专栏：每日刷题🍍

🌼文章目录🌼

1. 844. 比较含退格的字符串 - 力扣（LeetCode）

2. 2487. 从链表中移除节点 - 力扣（LeetCode）

3. 225. 用队列实现栈 - 力扣（LeetCode）

1. 844. 比较含退格的字符串 - 力扣（LeetCode）

//0ms  100％思路：栈的基本使用。遍历字符串，遇到字母入栈，遇到'#'出栈，最后判断两个栈中元素是否相同。

typedef char STDataType;

typedef struct Stack

{

    STDataType* arr;

    int top;

    int capacity;

}ST;

//栈的初始化

void StackInit(ST* st)

{

    assert(st);

    st->arr = NULL;

    st->capacity = st->top = 0;

}

//入栈

void StackPush(ST* st, STDataType x)

{

    assert(st);

    if (st->top == st->capacity)

    {

        int newcapacity = st->capacity == 0 ? 4 : 2 * st->capacity;

        STDataType* tmp = (STDataType*)realloc(st->arr,sizeof(STDataType) * newcapacity);

        if (tmp == NULL)

        {

            perror("realloc:");

            exit(-1);

        }

        st->arr = tmp;

        st->capacity = newcapacity;

    }

    st->arr[st->top] = x;

    st->top++;

}

//出栈

void StackPop(ST* st)

{

    assert(st);

    assert(st->top > 0);

    st->top--;

}

//栈顶元素

STDataType StackTop(ST* st)

{

    assert(st);

    assert(st->top > 0);

    return st->arr[st->top - 1];

}

 

bool backspaceCompare(char* s, char* t)

{

    ST st1;

    ST st2;

    StackInit(&st1);

    StackInit(&st2);

    while (*s || *t)

    {

        if (*s && *s != '#')//遇到字母入栈

        {

            StackPush(&st1, *s);

        }

        else if (*s && *s == '#' && st1.top > 0)//否则出栈

        {

            StackPop(&st1);

        }

        if (*t && *t != '#')//同上

        {

            StackPush(&st2, *t);

        }

        else if (*t && *t == '#' && st2.top > 0)

        {

            StackPop(&st2);

        }

        if (*s)

        {

            s++;

        }

        if (*t)

        {

            t++;

        }

    }

    int i = 0;

    while (i < st1.top || i < st2.top)//比较两个栈中元素是否相同

    {

        if (i == st1.top || i == st2.top)

        {

            return false;

        }

        if (st1.arr[i] != st2.arr[i])

        {

            return false;

        }

        i++;

    }

    return true;

}

2. 2487. 从链表中移除节点 - 力扣（LeetCode）

//思路：栈。遍历链表，遇到更大的元素与之前入栈的元素比较，推出比当前元素小的栈中元素，将当前元素入栈。

typedef struct ListNode LN;

 

struct ListNode* removeNodes(struct ListNode* head)

{

    LN* pmove = head->next;

    int sta[100000] = {0};

    sta[0] = head->val;

    int count = 1;

    while(pmove)

    {

        if(count==0)//如果栈中无元素，直接入栈

        {

            sta[count++] = pmove->val;

        }

        while(count>0&&pmove->val>sta[count-1])//循环遍历栈顶元素，推出比当前元素小的

        {

            count--;

        }

        sta[count++] = pmove->val;

        pmove = pmove->next;

    }

    LN* Sentry = (LN*)malloc(sizeof(LN));//将栈中元素存入新链表返回

    Sentry->next = NULL;

    LN* newhead = Sentry;

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

    {

        LN* newnode = (LN*)malloc(sizeof(LN));

        newnode->next = NULL;

        newnode->val = sta[i];

        newhead->next = newnode;

        newhead = newhead->next;

    }

    return Sentry->next;

}

3. 225. 用队列实现栈 - 力扣（LeetCode）

//栈和队列的巩固理解题。本题只用于帮助加深巩固结构体与栈和队列的知识，不具有实际价值。

typedef int QDataType;

 

//队列节点

typedef struct listnode

{

    QDataType val;

    struct listnode* next;

}LN;

 

//队列头尾指针

typedef struct Queque

{

    LN* phead;

    LN* ptail;

    int size;

}QE;

 

//队列初始化

void QueInit(QE* qe)

{

    assert(qe);

    qe->phead = NULL;

    qe->ptail = NULL;

    qe->size = 0;

}

 

//入列

void QuePush(QE* qe, QDataType x)

{

    assert(qe);

    LN* newnode = (LN*)malloc(sizeof(LN));

    if (newnode == NULL)

    {

        perror("malloc:");

        exit(-1);

    }

    newnode->next = NULL;

    newnode->val = x;

    if (qe->phead == NULL)

    {

        qe->phead = qe->ptail = newnode;

    }

    else

    {

        qe->ptail->next = newnode;

        qe->ptail = qe->ptail->next;

    }

    qe->size++;

}

 

//出列

void QuePop(QE* qe)

{

    assert(qe);

    assert(qe->phead!=NULL);

    assert(qe->size > 0);

    if(qe->phead->next==NULL)

    {

        free(qe->phead);

        qe->phead = qe->ptail = NULL;

    }

    else

    {

        LN* tmp = qe->phead->next;

        free(qe->phead);

        qe->phead = tmp;

    }

    qe->size--;

}

 

//获取列头元素

QDataType QueGetHead(QE* qe)

{

    assert(qe);

    assert(qe->phead != NULL);

    return qe->phead->val;

}

 

//获取列尾元素

QDataType QueGetBack(QE* qe)

{

    assert(qe);

    assert(qe->ptail != NULL);

    return qe->ptail->val;

}

 

//获取队列元素个数

int QueSize(QE* qe)

{

    assert(qe);

    return qe->size;

}

 

//判断队列是否为空

bool QueEmpty(QE* qe)

{

    assert(qe);

    return qe->size == 0;

}

 

//释放队列

void QueRelease(QE* qe)

{

    assert(qe);

    LN* del = qe->phead;

    while (del)

    {

        LN* tmp = del->next;

        free(del);

        del = tmp;

    }

    qe->phead = qe->ptail = NULL;

    qe->size = 0;

}

 

typedef struct

{

    QE q1;

    QE q2;

} MyStack;

 

//创建栈

MyStack* myStackCreate()

{

    MyStack* Sta = (MyStack*)malloc(sizeof(MyStack));

    QueInit(&(Sta->q1));

    QueInit(&(Sta->q2));

    return Sta;

}

//入数据

void myStackPush(MyStack* obj, int x)

{

    if(QueEmpty(&(obj->q1)))

    {

        QuePush(&(obj->q1),x);

    }

    else

    {

        QuePush(&(obj->q1),x);

    }

}

//出数据

int myStackPop(MyStack* obj)

{

    QE* Empty = &(obj->q1);

    QE* NotEmpty = &(obj->q2);

    if(!QueEmpty(&(obj->q1)))

    {

        Empty = &(obj->q2);

        NotEmpty = &(obj->q1);

    }

    while(QueSize(NotEmpty)>1)

    {

        QuePush(Empty,QueGetHead(NotEmpty));

        QuePop(NotEmpty);

    }

    int top = QueGetHead(NotEmpty);

    QuePop(NotEmpty);

    return top;

}

//获取栈顶数据

int myStackTop(MyStack* obj)

{

    if(!QueEmpty(&(obj->q1)))

    {

        return QueGetBack(&(obj->q1));

    }

    else

    {

        return QueGetBack(&(obj->q2));

    }

}

//判断空

bool myStackEmpty(MyStack* obj)

{

    return QueEmpty(&(obj->q1))&&QueEmpty(&(obj->q2));

}

//释放栈

void myStackFree(MyStack* obj)

{

    QueRelease(&(obj->q1));

    QueRelease(&(obj->q2));

    free(obj);

    obj = NULL;

}