C语言每日一题(35)有效的括号

力扣网 20 有效的括号

题目描述

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

有效字符串需满足:

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

示例 1:

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

示例 2:

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

示例 3:

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

思路分析

如果这里再用所谓的遍历字符串寻找进行匹配的话,时间复杂度高且不说,还麻烦,但如果我们学习栈了以后,这道题会变得异常轻松。

我们将所有的左括号入栈,在字符串里找右括号,同时出栈左括号进行匹配,如果匹配成功就返回true,否则返回false。

注意的问题:

这里除了括号类型的匹配问题,同时还有数量问题,会存在左括号多于右括号或者反过来的情况,这里如果数量不匹配的话也返回false。

判断数量的问题,再寻找右括号时,先判断栈是否为空,这是判断右括号多余左括号的情况,

在遍历一遍字符串后,如果栈里面还有括号,说明左括号多于右括号,也返回false。

完整代码

力扣环境下是不提供栈的,这里我们需要自己定义。

栈定义和常用接口

头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int _top;
	int _capacity;
}Stack;

// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);

 接口实现文件

#include"Stack.h"

// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}

// 入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//检查是否栈满
	if (ps->_top == ps->_capacity)
	{
		int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		Stack* ptr = realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (ptr == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = ptr;
		ps->_capacity = newcapacity;
		
	}
	//入栈
	ps->a[ps->_top] = data;
	ps->_top++;
}

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

// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);

	return ps->a[ps->_top-1];
}

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->_top == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

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

题目所需代码

bool isValid(char* s) {
    Stack st;
    StackInit(&st);//初始化栈
    while (*s)
    {
        if (*s == '{' || *s == '(' || *s == '[')//为左括号进栈
        {
            StackPush(&st, *s);
        }
        else
        {
            if (StackEmpty(&st))//如果为右括号,先判断栈是否为空
            {
                StackDestroy(&st);
                return false;
            }
            char top = StackTop(&st);//出栈栈顶括号
            StackPop(&st);
            if (*s == ']' && top != '[' ||//两者进行匹配,如果存在不等情况,返回false
                *s == '}' && top != '{' ||
                *s == ')' && top != '(')
            {
                StackDestroy(&st);
                return false;
            }

        }
        ++s;
    }
    bool ret = StackEmpty(&st);//最后再判断栈是否为空(左括号多余右括号情况),布尔值,如果栈为空返回真,否则返回假
    StackDestroy(&st);
    return ret;
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/178026.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

黑马React18: Redux

黑马React: Redux Date: November 19, 2023 Sum: Redux基础、Redux工具、调试、美团案例 Redux介绍 Redux 是React最常用的集中状态管理工具&#xff0c;类似于Vue中的Pinia&#xff08;Vuex&#xff09;&#xff0c;可以独立于框架运行 作用&#xff1a;通过集中管理的方式管…

Vue生成二维码并进行二维码图片下载

1、安包 npm install vue-qr --save2、引入 // vue2.0 import VueQr from vue-qr // vue3.0 import VueQr from vue-qr/src/packages/vue-qr.vue new Vue({components: {VueQr} })<!-- 设备二维码 对话框 270px--><el-dialog title"点位二维码" :visible.…

【Java 进阶篇】Redis:打开缓存之门

介绍 Redis&#xff08;Remote Dictionary Server&#xff09;是一个高性能的键值对存储系统&#xff0c;被广泛用作缓存、消息中间件和数据库。它以其快速的读写能力、支持多种数据结构和丰富的功能而闻名。在这篇博客中&#xff0c;我们将深入了解Redis的概念、安装以及基本…

阿里云 ACK 新升级,打造智算时代的现代化应用平台

云布道师 今天&#xff0c;能想到的或是想不到的领域&#xff0c;对容器和 Kubernetes 的需求都居高不减&#xff0c;使这项技术正在真正走向无处不在。 在 2023 云栖大会上&#xff0c;阿里云云原生产品线容器服务负责人易立关于容器服务 ACK 在本届亚运会上应用的介绍&#…

系列七、ThreadLocal为什么会导致内存泄漏

一、ThreadLocal为什么会导致内存泄露 1.1、ThreadLocalMap的基本结构 ThreadLocalMap是ThreadLocal的内部类&#xff0c;没有实现Map接口&#xff0c;用独立的方式实现了Map的功能&#xff0c;其内部的Entry也是独立实现的。源码如下&#xff1a; 1.2、ThreadLocal引用示意图…

ChinaSoft 论坛巡礼 | 高可信嵌入式软件智能化开发与测试论坛

2023年CCF中国软件大会&#xff08;CCF ChinaSoft 2023&#xff09;由CCF主办&#xff0c;CCF系统软件专委会、形式化方法专委会、软件工程专委会以及复旦大学联合承办&#xff0c;将于2023年12月1-3日在上海国际会议中心举行。 本次大会主题是“智能化软件创新推动数字经济与社…

MS9708/MS9710/MS9714高速、低功耗数模转换器,可替代ADI的

产品简述 MS9708/MS9710/MS9714 是一个 8-Bit/10-Bit/14-Bit 高速、低功耗 D/A 转换器。当采样速率达到 125MSPS 时&#xff0c; MS9708/MS9710/MS9714 也能提供优越的 AC 和 DC 性能。 MS9708/MS9710/MS9714 的正常工作电压范围为 2.7V 到 5.5V &#xff0c;…

每日一题 2304. 网格中的最小路径代价(中等,动态规划)

由于他每一行的每一个值都可以到下一行的所有节点&#xff0c;且路径的代价没有什么相关性&#xff0c;所以只能用 O(mn2) 的动态规划求解 class Solution:def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:m, n len(grid), len(grid[0])…

Attention is All You Need:Transformer各模块详解

Transformer encoder-decoder架构 Encoder&#xff1a;将输入序列转换为一个连续向量空间中的表示。Encoder通常是一个循环神经网络&#xff08;RNN&#xff09;或者卷积神经网络&#xff08;CNN&#xff09;&#xff0c;通过对输入序列中的每个元素进行编码&#xff0c;得到…

51单片机按键控制LED灯亮灭的N个玩法

51单片机按键控制LED灯亮灭的N个玩法 1.概述 这篇文章介绍按键的使用&#xff0c;以及通过控制LED灯的小实验&#xff0c;发现按键中存在的问题&#xff0c;然后思考并解决这些问题。达到熟练使用按键控制元器件。 2.搭建硬件环境 1.硬件准备 名称型号数量单片机STC12C205…

3d标签云实现过程(tagcloud.js)同步原生和 vue

写在前面 本来是没有准备写这个知识点&#xff0c;但是下载这个 js 的时候发现很多都是要钱或者是积分的&#xff0c;我就不明白了一个开源了这么久的 js 怎么还有人拿来挣钱的&#xff0c;同时还有一些只有原生 html 的例子&#xff0c;但是现在都是 框架主导的一些项目&#…

Find My音箱|苹果Find My技术与音箱结合,智能防丢,全球定位

音箱市场规模正在不断扩大。随着人们生活品质的提高&#xff0c;对音乐体验的需求也在不断升级。消费者对于蓝牙音箱的需求&#xff0c;已经从单纯的音质扩展到了功能、设计和价格等多个方面。随着移动化、即时化的视听娱乐需求的增长&#xff0c;蓝牙音箱性能、质量、外观设计…

嵌入式主板购买需要考虑哪些内容?

众所周知&#xff0c;各种先进电子器件和计算机处理技术在我国自动化工业生产中的应用&#xff0c;极大地提高了发展的效率和发展水平。而嵌入式主板以其多元化的设计特点在我国工业系统的控制中表现得越来越明显&#xff0c;消费者在选择这种嵌入式主板时必须注意以下几点考虑…

2023 年 亚太赛 APMCM 国际大学生数学建模挑战赛 |数学建模完整代码+建模过程全解全析

当大家面临着复杂的数学建模问题时&#xff0c;你是否曾经感到茫然无措&#xff1f;作为2022年美国大学生数学建模比赛的O奖得主&#xff0c;我为大家提供了一套优秀的解题思路&#xff0c;让你轻松应对各种难题。 cs数模团队在亚太赛 APMCM前为大家提供了许多资料的内容呀&…

数学建模之拟合及其代码

发现新天地&#xff0c;欢迎访问Cr不是铬的个人网站 引言 与插值问题不同&#xff0c;在拟合问题中不需要曲线一定经过给定的点。拟合问题的目标是寻求一个函数&#xff08;曲线&#xff09;&#xff0c;使得该曲线在某种准则下与所有的数据点最为接近&#xff0c;即曲线拟合…

JSP:Javabean

起初&#xff0c;JavaBean的目的是为了将可以重复使用的代码进行打包&#xff0c;在传统的应用中&#xff0c;JavaBean主要用于实现一些可视化界面&#xff0c;如一个窗体、按钮、文本框等&#xff0c;这样的JavaBean称之可视化的JavaBean。 随着技术的不断发展与项目的需求&am…

【前端】vue中合并表格行

做平台功能时&#xff0c;遇到一个需求是需要将表格某列有相同值时进行合并展示&#xff0c;比如 1、通过在Element中得知需要在表格中增加span-method方法 <el-table:data"tableData":span-method"cellMerge"borderstyle"width: 100%; margin-to…

Linux操作系统使用及C高级编程-D14共用体和枚举

共用体 不同数据类型可以使用共同的存储区域。和结构体的本质区别是&#xff1a;使用内存方式&#xff0c;其中共用体是使用同一块内存 1、 选择最大成员的大小 2、要能够整除成员大小&#xff0c;下图中un1中char s[7]是7个字节&#xff0c;但要遵循能整除int&#xff0c;所以…