成都商城网站建设地址住房和城乡建设部门户

当前位置： 首页 > news >正文

成都商城网站建设地址,住房和城乡建设部门户,上线了自助建站,网站响应式和电脑手机有效括号问题#xff1a; 题目描述#xff1a; 给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[#xff0c;] 的字符串 s #xff0c;判断字符串是否有效。 有效字符串需满足#xff1a; 左括号必须用相同类型的右括号闭合。左括号必须以正确的…有效括号问题 题目描述 给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 思路 解决此类问题传统的暴力遍历法已经不再适用了暴力遍历无法保证括号的匹配顺序仅能通过统计左右括号的数量进行比较判断但即使是左右括号数量相等也不一定是有效的如“( [ { ] ) }”虽然左右括号数量相同但是它们的顺序不对不能相互匹配所以也是无效的因此暴力遍历的方法是不行的。 此时我们应该从问题本身出发思考一下括号匹配的本质是什么 我们知道一个合法的括号包括两部分左括号和右括号括号匹配就是匹配左右括号并且每次匹配时都是相邻最近的两个左右括号进行匹配。因此我们可以创建一个数组用来储存左括号依次遍历每出现一次左括号就存进这个数组中每次出现右括号时将它与数组中最后一个左括号进行匹配若匹配成功则删除数组最后一个左括号再从下一个开始遍历若匹配不成功则说明是非法括号字符串直接退出程序……直至遍历完括号字符串或者中间出现不匹配的情况直接退出。若正常遍历完括号字符串再看数组中是否为空若为空说明该括号字符串中所有左右括号都匹配成功即该括号字符串合法反之则是非法的。观察这个匹配规律不难发现与栈“先入后出”的特点相符合因此我们可以直接创建一个栈进行实现。 具体代码如下 typedef char STDataType; typedef struct Stack {STDataType* a;int top;//栈顶int capacity;//容量 }ST;//判空 bool STEmpty(ST* ps) {assert(ps);return ps-top 0; } //初始化 void STInit(ST* ps) {assert(ps);ps-a NULL;ps-capacity 0;ps-top 0; } //销毁 void STDestroy(ST* ps) {free(ps-a);ps-a NULL;ps-capacity 0;ps-top 0; } //入栈 void STPush(ST* ps, STDataType x) {assert(ps);if (ps-capacity ps-top){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* p (STDataType*)realloc(ps-a, sizeof(STDataType) * newcapacity);ps-a p;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top; } //出栈 void STPop(ST* ps) {assert(ps);assert(ps-a);assert(!STEmpty(ps));ps-top–; } //取栈顶元素 STDataType STTop(ST* ps) {assert(ps);assert(ps-a);assert(!STEmpty(ps));return ps-a[ps-top - 1]; }bool isValid(char * s) {ST ps;STInit(ps);int i0;for(i0;istrlen(s);i){if(si//左括号入栈{STPush(ps,s[i]);}else//右括号与栈顶元素进行匹配{if(STEmpty(ps))//栈中为空说明括号数量不匹配{return false;}else if((STTop(ps)(s[i]!))||(STTop(ps)[s[i]!])||(STTop(ps){s[i]!}))//栈中不为空但括号样式不匹配{return false;}else//匹配成功栈顶元素出栈{STPop(ps);}}}if(STEmpty(ps))//全部遍历完之后栈中为空说明全部匹配成功{return true;}else//栈中不为空说明数量不匹配{return false;}STDestroy(ps); } 运行结果 用栈实现队列 题目描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty 实现 MyQueue 类 void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false 说明 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 首先要知道栈的特点是“先入后出”因为此特点把栈1中的数据移动到栈2中时数据的顺序会倒过来如下 数据入栈顺序是1、2、3、4此时再从栈2中执行出栈操作数据出栈顺序也是1、2、3、4可以满足队列“先入先出”的功能因此我们不妨把一个栈专门同来进数据push另一个栈专门用来出数据pop。  每次进数据都压入push栈出数据都从pop栈出若pop栈为空则把push栈的数据都压入pop栈后再出数据。 代码如下 typedef int STDataType; typedef struct Stack {STDataType* a;int top;//栈顶int capacity;//容量 }ST; typedef struct {ST push;ST pop; } MyQueue;//初始化 void STInit(ST* ps) {assert(ps);ps-a NULL;ps-capacity 0;ps-top 0; } //判空 bool STEmpty(ST* ps) {assert(ps);return ps-top 0; } //销毁 void STDestroy(ST* ps) {free(ps-a);ps-a NULL;ps-capacity 0;ps-top 0; } //入栈 void STPush(ST* ps, STDataType x) {assert(ps);if (ps-capacity ps-top){int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* p (STDataType*)realloc(ps-a, sizeof(STDataType) * newcapacity);ps-a p;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top; }//出栈 void STPop(ST* ps) {assert(ps);assert(ps-a);assert(!STEmpty(ps));ps-top–; } //取栈顶元素 STDataType STTop(ST* ps) {assert(ps);assert(ps-a);assert(!STEmpty(ps));return ps-a[ps-top - 1]; } //创建我的队列 MyQueue* myQueueCreate() {MyQueue* obj (MyQueue)malloc(sizeof(MyQueue));STInit(obj-push);STInit(obj-pop);return obj; } //入队 void myQueuePush(MyQueue obj, int x) {STPush(obj-push, x); } //出队 int myQueuePop(MyQueue* obj) {if (STEmpty(obj-pop)){while (!STEmpty(obj-push)){STDataType x STTop(obj-push);STPop(obj-push);STPush(obj-pop, x);}}STDataType front STTop(obj-pop);STPop(obj-pop);return front; } //取队头 int myQueuePeek(MyQueue* obj) {if (STEmpty(obj-pop)){while (!STEmpty(obj-push)){STDataType x STTop(obj-push);STPop(obj-push);STPush(obj-pop, x);}}STDataType front STTop(obj-pop);return front; } //我的队列判空 bool myQueueEmpty(MyQueue* obj) {return (STEmpty(obj-push) STEmpty(obj-pop)); } //销毁我的队列 void myQueueFree(MyQueue* obj) {STDestroy(obj-push);STDestroy(obj-pop);free(obj); } 运行结果 用队列实现栈 题目描述 请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。 实现 MyStack 类 void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。 注意 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。 首先要知道队列的特点是“先进先出”因为此特点将队列1中的数据移动到队列2中时数据的顺序不会变如下 数据的从队列1进队顺序是1、2、3、4如直接从队列2出队则出队顺序也是1、2、3、4无法满足栈的“先进后出”的特点。因此想要通过队列实现栈要始终保证至少一个队列为空若两个队列都为空则只能执行判空和压入数据的操作这样在出数据时把不为空队列假设有n个数据的前n-1个数据移动到空队列中再出最后一个数据这样不断在两个队列之间导数据就能实现把后入的数据先出出去而想要压入数据时直接在非空的队列队尾直接插入即可这样就能实现栈“先进后出”的特点。 代码如下 typedef int QDataType; typedef struct QueueNode {struct QueueNode* next;QDataType data; }QNode;typedef struct Queue {QNode* head;QNode* tail;int size; }Que; typedef struct {Que p1;Que p2; } MyStack; //判空 空返回1非空返回0 bool QueueEmpty(Que* pq) {assert(pq);return pq-head NULL; } //初始化 void QueueInit(Que* pq) {assert(pq);pq-head NULL;pq-tail NULL;pq-size 0; } //销毁 void QueueDestroy(Que* pq) {assert(pq);QNode* cur pq-head;while (cur){QNode* p cur-next;free(cur);cur p;}pq-head NULL;pq-tail NULL;pq-size 0; } //入队 void QueuePush(Que* pq, QDataType x) {assert(pq);QNode* newnode (QNode)malloc(sizeof(QNode));if (newnode NULL){perror(malloc failed);exit(-1);}newnode-data x;newnode-next NULL;if (pq-head NULL){pq-head newnode;pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size; } //出队 void QueuePop(Que pq) {assert(pq);assert(!QueueEmpty(pq));//要有数据if (pq-head-next NULL)//只有一个节点{free(pq-head);pq-head NULL;pq-tail NULL;}else{QNode* cur pq-head-next;free(pq-head);pq-head cur;}pq-size–; } //取队头 QDataType QueueFront(Que* pq) {assert(pq);assert(!QueueEmpty(pq));return pq-head-data; } //取队尾 QDataType QueueBack(Que* pq) {assert(pq);assert(!QueueEmpty(pq));return pq-tail-data; } //有效数据 int QueueSize(Que* pq) {assert(pq);return pq-size; } //创建我的栈 MyStack* myStackCreate() {MyStack* obj (MyStack)malloc(sizeof(MyStack));QueueInit(obj-p1);QueueInit(obj-p2);return obj; } //入栈 void myStackPush(MyStack obj, int x) {if (!QueueEmpty(obj-p1)){QueuePush(obj-p1, x);}else{QueuePush(obj-p2, x);} } //出栈 int myStackPop(MyStack* obj) {QDataType top 0;if (!QueueEmpty(obj-p1)){while (QueueSize(obj-p1) 1){QDataType a QueueFront(obj-p1);QueuePop(obj-p1);QueuePush(obj-p2, a);}top QueueFront(obj-p1);QueuePop(obj-p1);}else{while (QueueSize(obj-p2) 1){QDataType a QueueFront(obj-p2);QueuePop(obj-p2);QueuePush(obj-p1, a);}top QueueFront(obj-p2);QueuePop(obj-p2);}return top; } //取栈顶 int myStackTop(MyStack* obj) {if (!QueueEmpty(obj-p1)){return QueueBack(obj-p1);}else{return QueueBack(obj-p2);} } //判空 bool myStackEmpty(MyStack* obj) {return (QueueEmpty(obj-p1) QueueEmpty(obj-p2)); } //销毁我的栈 void myStackFree(MyStack* obj) {QueueDestroy(obj-p1);QueueDestroy(obj-p2);free(obj); } 运行结果