外卖网站开发能多少钱,网站建设费用分类,国内便宜的vps,网页浏览器缩写目录
目录
题目描述
题目分析解析
解决代码
写题感悟#xff1a; 题目描述 还有实例 题目分析解析
对于这个题目#xff0c;我们首先有效字符串需要满足什么#xff0c;第一个左右括号使用相同类型的括号#xff0c;这好理解#xff0c;无非就是小括号和小括号大括号…目录
目录
题目描述
题目分析解析
解决代码
写题感悟 题目描述 还有实例 题目分析解析
对于这个题目我们首先有效字符串需要满足什么第一个左右括号使用相同类型的括号这好理解无非就是小括号和小括号大括号和大括号一起匹配。其次第二个就是左括号必须以正确顺序来匹配注意了是顺序大家以为就是左括号小括号遇到左括号中括号然后遇到了右括号(小括号)和右括号中括号然而恰恰相反而是小括号左、中括号右和中括号右小括号右相依匹配大致就是遇到第一个右括号时然后与自己最近的左括号进行匹配假设匹配成功消除第二个右括号继续匹配最近的括号。最后就是第三个和我们将的第一个差不多就是和对应的左括号匹配但是这里主要是限制只有右括号的情况。
接下来就是如何解决问题了。
这里我们根据第二个要求可以知道当遇到右括号时需要找到与之最近的左括号匹配通过这个我们就能想到当遇到右括号时把后进的左括号与之对比看是否满足相同类型括号。这个后进先出就和我们学过的数据结构栈有关系所以我们这里需要数据结构栈来写。将遇到的左括号存入栈中直到遇到右括号这里还得考虑是否右括号判断是否匹配成功只要有一个匹配失败就说明这个字符串不符合有效字符以上都符合后最后判断栈是否还有左括号如果没有则符号题目要求。
解决代码
//栈结构
typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;
//初始化
void StackInit(ST* Stack)
{Stack-arr NULL;Stack-capacity Stack-top 0;
}//入栈
void StackPush(ST* Stack, STDataType x)
{assert(Stack);//空间不够if (Stack-capacity Stack-top){//扩容int newcapacity Stack-capacity 0 ? 4 : 2 * Stack-capacity;STDataType* tmp (STDataType*)realloc(Stack-arr, newcapacity * sizeof(STDataType));if (tmp NULL){perror(realloc);exit(1);}Stack-arr tmp;Stack-capacity newcapacity;}//空间够Stack-arr[Stack-top] x;
}//判断
bool StackEmpty(ST* Stack)
{assert(Stack);return Stack-arrNULL;
}//出栈
void StackPop(ST* Stack)
{assert(!StackEmpty(Stack));--Stack-top;
}//获取栈中元素
STDataType StackTop(ST* Stack)
{assert(!StackEmpty(Stack));return Stack-arr[Stack-top - 1];
}//获取栈中元素个数
int StackSize(ST* Stack)
{assert(!StackEmpty(Stack));return Stack-top;
}//销毁栈
void StackDestory(ST* Stack)
{if (Stack-arr)free(Stack-arr);Stack-arr NULL;Stack-capacity Stack-top 0;
}bool isValid(char* s) {ST st;
StackInit(st);
char* cur s;
while (*cur ! \0)
{//遇到左括号存入栈if (*cur (|| *cur [|| *cur {){StackPush(st, *cur);}//遇到右括号取栈顶元素进行对比else{//内部栈为空时只有右括号时if(st.top 0){return false; }char top StackTop(st);if (*cur ) top ! (|| *cur ] top ! [|| *cur } top ! {){StackDestory(st);return false;}StackPop(st);}cur;
}
if (!StackSize(st))
{return true;
}
else
{return false;
}
}
写题感悟 这道题对于初学者的我很难想到尽然会用到数据结构栈这说明数据结构在刷题过程中发挥着不可磨灭的作用。因此我觉得思路和知识都很重要当然知识是的重要占大头没有知识就没有这个思路就算给你一个思路也很难实现。我觉得在前期的刷题过程需要刻意取练习到后面就需要综合去刷利用自己学到的知识去解决问题这个题目告诉我如果遇到先进后出或者后进需要先出类似的题目首先可以考虑栈。
