【每日刷题】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;
}
