Leetcode刷题之有效的括号

这篇具有很好参考价值的文章主要介绍了Leetcode刷题之有效的括号。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

我们的内心和心智,是决定我们未来命运的最强劲的力量。         -- 奥普拉·温弗瑞
目录

🍁一.有效的括号

🍍1.使用栈实现

🍒2.完整代码:


题目描述:
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"
输出:true

示例 2:

输入:s = "()[]{}"
输出:true

示例 3:​​​​​​​

输入:s = "(]"
输出:false

做题链接:有效的括号

前言:
在5月13号晚上写了一篇白嫖chatgpt的Edge插件,很难不爱啊的文章,只是随便写写,只想把这个好用的插件分享给大家,但是出乎我的意料,居然上热榜了,这也是我第一次上热榜,浏览量居然高达9000,收藏也达到了惊人的400多。可给我高兴坏了,非常感谢各位CSDN人的支持。未来我将更加努力,把自己学习的历程的分享出来,和大家一起进步。一起加油,再次感谢。

🍁一.有效的括号

这题的意思就是,给你一串字符串括号,让你判断这个字符串里面的括号是否匹配,如果匹配,就返回true,否则返回false。这题我们就可以使用栈来实现。
我们来回忆一下,之前学习的栈是怎么样的。
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除操作,进行数据的插入和删除操作的一端称为栈顶。另一端称为栈底。栈中数据元素遵循后进先出LIFO(last in first out)。

🍍1.使用栈实现

思路:
1.
我们从头开始遍历字符串,当遇到左括号也就是{,[,(的其中一个时,直接把这个左括号入栈。2.然后继续遍历字符串,只要遇到左括号就入栈,遇到右括号也就是},],)的其中一个时,直接把栈顶的左括号出栈。
3.然后判断这两个字符是否括号匹配,如果不匹配,直接返回false,如果匹配,就继续遍历字符串,直到遍历到字符串的尾,如果都匹配,那么就返回true。
老样子我们还是画图来理解一下:
Leetcode刷题之有效的括号

Leetcode刷题之有效的括号

Leetcode刷题之有效的括号 

Leetcode刷题之有效的括号Leetcode刷题之有效的括号 

接着最后三个字符和明显和栈内的字符是匹配的,所以我们返回true。

思路是有了,那我们就可以直接写代码了。
注意细节:容易犯的错误。
1.最后返回true时,栈必须为空,才能保证括号的匹配成功了的。
2.第一个字符如果是右括号,那么肯定就不匹配了,直接返回false。

🍒2.完整代码:

typedef char STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int Capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType x);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

// 初始化栈 
void StackInit(Stack * ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);//动态的开辟空间
	if (ps->a == NULL)
	{
		perror("malloc\n");
		return;
	}
	ps->top = 0;
	ps->Capacity = 4;
}

// 入栈 
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->Capacity)
	{
		STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->Capacity * 2);
		if (temp==NULL)
		{
			perror("realloc\n");
			return;
		}
			ps->Capacity *= 2;//每次增容尾上一次的二倍
			ps->a = temp;
	}
		ps->a[ps->top] = x;
		ps->top++;//栈内入一个数据,top就要往上面走一步
}

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;
}

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	return ps->a[ps->top-1];
}

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->Capacity = 0;
}


// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps) {
	assert(ps);
	return ps->top==0;
}
//上面调用实现栈的函数
bool isValid(char * s){
    Stack ps;
    StackInit(&ps);
    while(*s)//遍历字符串
    {
        if(*s=='{'||*s=='('||*s=='[')//如果是左括号就直接入栈
        {
            StackPush(&ps,*s);
        }
        else
        {
            if(StackEmpty(&ps))
            {//当第一个字符为右括号时,即没有入栈,栈为空,直接返回false即可。
                StackDestroy(&ps);
                return false;
            }
            char top=StackTop(&ps);
            StackPop(&ps);
            if((*s=='}'&&top!='{')
            ||(*s==')'&&top!='(')
            ||(*s==']'&&top!='['))
            {
                StackDestroy(&ps);
                return false;//if语句只要有不匹配的,直接返回false
            }
        }
        ++s;
    }
    bool ret=StackEmpty(&ps);//栈为空,那么ret就为真,反之,为假。
    StackDestroy(&ps);
    return ret;
}

 文章来源地址https://www.toymoban.com/news/detail-448303.html

 

 

到了这里,关于Leetcode刷题之有效的括号的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode 20.有效的括号

    🌟 leetcode链接: 有效的括号 1️⃣ 代码与思路: 栈问题: 左括号进栈,如果是右括号则拿出栈顶元素比较,相同弹出栈顶元素,接着继续比较,不相同返回 false ,还要考虑一些特殊情况,具体看如下代码。 注:由于C语言没有接口,所以手写了一套栈来使用。或者也可以使

    2024年02月13日
    浏览(46)
  • LeetCode——有效的括号

    这里,我提供一种用栈来解决的方法: 思路:栈的结构是先进后出,这样我们就可以模拟栈结构了,如果是‘(’、‘{’、‘[’任何一种,直接push进栈就可以了,如果是‘}’、‘)’、‘]’任何一种就开始判断,看栈pop的是否和对应的字符匹配。    下面是源码:    

    2024年02月11日
    浏览(42)
  • leetcode刷题之回文链表

    目录 做题思路 代码实现 1.找到链表的中间节点 2.反转中间节点之后的链表 3.判断倒置的后半部分的链表是否等于前半部分的链表 整体代码展示 总结: 这里是题目链接。234. 回文链表 - 力扣(Leetcode)  这道题目的意思是:判断该链表中后半部分倒置是否跟前半部分相同,如

    2023年04月10日
    浏览(76)
  • 刷题之Leetcode209题(超级详细)

    力扣题目链接(opens new window) https://leetcode.cn/problems/minimum-size-subarray-sum/ 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。 示例: 输入:s = 7, nums = [2,3,1,2,4,3] 输

    2024年04月11日
    浏览(42)
  • Leetcode刷题之环形链表

    莫等闲,白了少年头,空悲切。                                            --岳飞 目录 1.环形链表 2.环形链表Ⅱ 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中

    2023年04月19日
    浏览(40)
  • leetcode刷题之背包问题(01背包)

    01 背包 概念:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是 w e i g h t [ i ] weight[i] w e i g h t [ i ] ,得到的价值是 v a l u e [ i ] value[i] v a l u e [ i ] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。 方法1:暴力回溯法 方法2:动态规划 三个

    2024年02月02日
    浏览(45)
  • Leetcode刷题之反转链表Ⅱ

    业精于勤而荒于嬉,行成于思而毁于随。                      ——韩愈 目录 前言: 🍁一.反转链表Ⅱ 🍒1.left和right中间链表反转,再把反转链表和剩下的链接起来 🗼2.left和right中间链表头插  题目描述: 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left =

    2024年02月04日
    浏览(41)
  • LeetCode刷题之分隔链表(图解➕代码)

            首先直接进入主题,题目链接🔗力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 源代码在最后,有更优解的朋友欢迎在评论里指导我一番! 通过题目分析得出结论:         1. 将链表分为 k个子链表         2. 用一个数组存放这k个子链表, 数组的长度就是k

    2024年02月06日
    浏览(35)
  • Leetcode 678. 有效的括号字符串

    有效的括号字符串 【问题描述】 给你一个只包含三种字符的字符串,支持的字符类型分别是 ‘(’、‘)’ 和 ‘*’。请你检验这个字符串是否为有效字符串,如果是有效字符串返回 true 。 有效字符串符合如下规则: 示例 1: 输入:s = “()” 输出:true 示例 2: 输入:s = “

    2024年02月13日
    浏览(42)
  • LeetCode:20. 有效的括号——栈和队列

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正

    2023年04月26日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包