wordpress静态资源加载不,快速优化官网,太原要做网站的公司,专业团队海报一、有效的括号
20.有效的括号#xff08;题目链接#xff09; 思路#xff1a; 1#xff09;括号的顺序匹配#xff1a;用栈实现#xff0c;遇到左括号入#xff0c;遇到右括号出#xff08;保证所出的左括号与右括号对应#xff09;#xff0c;否则顺序不匹配。 2…一、有效的括号
20.有效的括号题目链接 思路 1括号的顺序匹配用栈实现遇到左括号入遇到右括号出保证所出的左括号与右括号对应否则顺序不匹配。 2括号的数量匹配 1左括号大于右括号用栈实现遇到左括号入遇到右括号出遍历完字符数组此时栈不为空则说明左括号数量大于右括号 2右括号大于左括号遇到右括号出时判断栈是否为空若此时栈为空说明右括号数量大于左括号 typedef char SDateType;
typedef struct Stack
{SDateType* a;int top;int capacity;}Stack;
//初始化栈和销毁栈
void InitStack(Stack* ps)
{assert(ps);ps-a NULL;ps-capacity ps-top 0;
}
void DestoryStack(Stack* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-top 0;}//出栈和入栈
void StackPush(Stack* ps, SDateType x)
{assert(ps);//扩容if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;SDateType* tmp (SDateType*)realloc( ps-a,newcapacity * sizeof(SDateType));if (tmp NULL){perror(realloc fail:);return;}ps-a tmp;ps-capacity newcapacity;}//尾插ps-a[ps-top] x;ps-top;
}
void StackPop(Stack* ps)
{assert(ps);assert(ps-top 0);//只少有一个元素才能删除ps-top--;
}//栈的有效个数和栈顶元素
int StackSize(Stack* ps)
{assert(ps);return ps-top;
}
int StackTop(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}//栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
}
int isValid(char* s) {Stack ps;InitStack(ps);while (*s){if (*s [ || *s ( || *s {){StackPush(ps, *s);s;}else{if (StackEmpty(ps)){return false;}char tmp StackTop(ps);StackPop(ps);if ((*s ] tmp ! [) ||(*s } tmp ! {) ||(*s ) tmp ! ()){return false;}s;}}if (!StackEmpty(ps)){return false;}else {return true;}DestoryStack(ps);
}
二、用队列实现栈
225. 用队列复制栈题目链接 思路 栈是后进先出队列是先进先出。 用俩队列实现栈 1入栈时选择有数据的队列入数据 2出栈时将有数据队列中前k-1个数据出队列并入到空队列中返回并出有数据队列的最后一个数据 typedef int QDateType;
typedef struct QueueNode
{QDateType val;struct QueueNode * next;
}QueueNode;
typedef struct Queue
{QueueNode *head;QueueNode *tail;QDateType size;
}Queue;// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDateType x)
{assert(pq);QueueNode* node (QueueNode*)malloc(sizeof(QueueNode));node-val x;node-next NULL;if (pq-tail NULL){pq-head pq-tail node;pq-size;}else{pq-tail-next node;pq-tail node;pq-size;}
}
void QueuePop(Queue* pq)
{assert(pq);assert(pq-head ! NULL);//只少保证一个节点QueueNode* del pq-head;pq-head pq-head-next;free(del);del NULL;pq-size--;if (pq-head NULL)//只有一个节点处理{pq-tail NULL;}
}// 返回队头和队尾
QDateType QueueFront(Queue* pq)
{assert(pq);return pq-head-val;
}
QDateType QueueBack(Queue* pq)
{assert(pq);return pq-tail-val;
}// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-headNULL;
}void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* cur pq-head;while (cur){QueueNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;}
typedef struct {Queue q1;Queue q2;} MyStack;MyStack* myStackCreate() {MyStack* obj(MyStack*)malloc(sizeof(MyStack));QueueInit(obj-q1);QueueInit(obj-q2);return obj;}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}
bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1)QueueEmpty(obj-q2);
}int myStackPop(MyStack* obj) {assert(!myStackEmpty(obj));Queue * emptyobj-q1;Queue * nonemptyobj-q2;if(!QueueEmpty(empty)){emptyobj-q2;nonemptyobj-q1;}while(QueueSize(nonempty)!1){int tmp QueueFront(nonempty);QueuePush(empty,tmp);QueuePop(nonempty);}int tmp QueueFront(nonempty);QueuePop(nonempty);return tmp;
}int myStackTop(MyStack* obj) {assert(!myStackEmpty(obj));Queue * emptyobj-q1;Queue * nonemptyobj-q2;if(!QueueEmpty(empty)){emptyobj-q2;nonemptyobj-q1;}return QueueBack(nonempty);
}void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);}三、用栈实现队列
225. 用栈实现队列题目链接 思路 栈是后进先出队列是先进先出。 1入队列s1栈用来在栈顶入数据 2出队列s2栈用来出栈顶数据如果s2为空则从s1出数据入到s2中去比如;s1中的数据为123入到s2变为321再出s2的栈顶数据这样就满足队列的性质了 typedef int SDateType;
typedef struct Stack
{SDateType* a;int top;int capacity;}Stack;
//初始化栈和销毁栈
void InitStack(Stack* ps)
{assert(ps);ps-a NULL;ps-capacity ps-top 0;
}
void DestoryStack(Stack* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-capacity ps-top 0;}//出栈和入栈
void StackPush(Stack* ps, SDateType x)
{assert(ps);//扩容if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;SDateType* tmp (SDateType*)realloc( ps-a,newcapacity * sizeof(SDateType));if (tmp NULL){perror(realloc fail:);return;}ps-a tmp;ps-capacity newcapacity;}//尾插ps-a[ps-top] x;ps-top;
}
void StackPop(Stack* ps)
{assert(ps);assert(ps-top 0);//只少有一个元素才能删除ps-top--;
}//栈的有效个数和栈顶元素
int StackSize(Stack* ps)
{assert(ps);return ps-top;
}
int StackTop(Stack* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}//栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
}typedef struct {Stack s1;Stack s2;} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj(MyQueue* )malloc(sizeof(MyQueue));InitStack(obj-s1);InitStack(obj-s2);return obj;}void myQueuePush(MyQueue* obj, int x) {StackPush(obj-s1,x);
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(obj-s1)StackEmpty(obj-s2);
}int myQueuePop(MyQueue* obj) {assert(!myQueueEmpty(obj));if(StackEmpty(obj-s2)){while(!StackEmpty(obj-s1)){int tmp StackTop(obj-s1);StackPush(obj-s2,tmp);StackPop(obj-s1);}}int tmp StackTop(obj-s2);StackPop(obj-s2);return tmp;
}int myQueuePeek(MyQueue* obj) {assert(!myQueueEmpty(obj));if(StackEmpty(obj-s2)){while(!StackEmpty(obj-s1)){int tmp StackTop(obj-s1);StackPush(obj-s2,tmp);StackPop(obj-s1);}}return StackTop(obj-s2);
}void myQueueFree(MyQueue* obj) {DestoryStack(obj-s1);DestoryStack(obj-s2);free(obj);}四、设计循环队列
622.设计循环队列题目链接 思路一数组 以front为队列头下标tail为队列尾下一个元素下标一共k个数据开辟k1个整型大小空间方便区分队列为空、为满以及一个元素的情况 1队列为空fronttail 2队列为1个元素front1tail 3) 队列为满tail1)%(k1)front typedef struct {int *a;int front;int rear;int n;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));int * tmp(int *)malloc(sizeof(int)*(k1));obj-atmp;obj-front0;obj-rear0;obj-nk;return obj;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if((obj-rear1)%(obj-n1)obj-front){return true;}return false;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull( obj)){return false;}obj-a[obj-rear]value;obj-rear;obj-rearobj-rear%(obj-n1);return true;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj-frontobj-rear){return true;}return false;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty( obj)){return false;}obj-front;obj-frontobj-front%(obj-n1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty( obj)){return -1;}return obj-a[obj-front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty( obj)){return -1;}return obj-a[(obj-rear-1obj-n1)%(obj-n1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj-a);free(obj);
}思路二单向循环链表 以head为队列头节点tail为队列尾尾节点的下一个节点一共k个数据开辟k1个节点的循环单向链表方便区分队列为空、为满以及一个元素的情况 1队列为空headtail 2队列为1个元素head-nexttail 3) 队列为满tail-nexthead typedef struct QueueNode
{int val;struct QueueNode * next;
}QueueNode;QueueNode* BuyNode(int x)
{QueueNode* node(QueueNode*)malloc(sizeof(QueueNode));node-valx;node-nextNULL;return node;
}
typedef struct MyCircularQueue{QueueNode *head;QueueNode *tail;QueueNode * pretail;int n;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj(MyCircularQueue*)malloc(sizeof(MyCircularQueue));QueueNode* nodeBuyNode(0);obj-pretailNULL;obj-headobj-tailnode;obj-n(k1);QueueNode* curobj-tail;while(k--){QueueNode* nodeBuyNode(0);cur-nextnode;cur cur-next;}cur-nextobj-head;return obj;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if(obj-tail-nextobj-head){return true;}return false;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull( obj)){return false;}obj-tail-valvalue;obj-pretailobj-tail;obj-tailobj-tail-next;return true;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj-headobj-tail){return true;}return false;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty( obj)){return false;}obj-headobj-head-next;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty( obj)){return -1;}return obj-head-val;
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty( obj)){return -1;}return obj-pretail-val;
}void myCircularQueueFree(MyCircularQueue* obj) {while(obj-n--){QueueNode*nextobj-head-next;free(obj-head);obj-headnext;}obj-headNULL;free(obj);
}
