LC20. 有效的括号

用来熟悉一下栈的应用之括号匹配

题目链接

下面是大致思路
1.初始化:创建一个空栈,用于存储左括号。(LC这题不用,自己写完整的需要)
2.遍历字符串:从左到右依次扫描字符串中的每个字符。
3.处理左括号:如果是左括号,将其压入栈中。
4.处理右括号:如果是右括号,检查找顶元素是否与其匹配:

  • 如果匹配,弹出栈顶元素。
  • 如果不匹配,返回false,表示括号不匹配。

5.检查栈是否为空:

  • 遍历结束后,检查找是否为空。
  • 如果栈为空,表示所有括号匹配;否则,返回false。
    (还有就是一开始可以直接排除掉奇数个的情况,不可能匹配

可运行版

下面就是注意一个地方

pairs函数,在扫描的时候如果发现是左括号,那么会进入后面的else逻辑,让左括号入栈
如果发现是右括号
那么会返回与之匹配的左括号,去和当前栈顶的左括号匹配

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>// 定义一个函数 pairs,用于返回与右括号对应的左括号
char pairs(char a)
{if (a == '}')return '{';if (a == ']')return '[';if (a == ')')return '(';return 0;
}// 检查括号是否匹配的函数
bool isValid(char *s)
{int n = strlen(s); // 获取字符串的长度if (n % 2 == 1){ // 如果字符串长度是奇数,不可能匹配return false;}int *stk = (int *)malloc((n + 1) * sizeof(int)); // 动态分配栈的大小if (stk == NULL){printf("Memory allocation failed\n");return false;}int top = 0; // 初始化栈顶指针int i;       // 将变量声明移到循环外部for (i = 0; i < n; i++){char ch = pairs(s[i]); // 获取与当前字符对应的左括号if (ch){ // 如果当前字符是右括号if (top == 0 || stk[top - 1] != ch){              // 检查栈是否为空或栈顶元素是否匹配free(stk); // 释放动态分配的内存return false;}top--; // 弹出栈顶元素}else{                      // 如果当前字符是左括号stk[top++] = s[i]; // 将左括号压入栈中}}bool result = (top == 0); // 如果栈为空,表示所有括号匹配free(stk);                // 释放动态分配的内存return result;
}// 示例使用
int main()
{printf("%d\n", isValid("()"));     // 输出: 1 (true)printf("%d\n", isValid("()[]{}")); // 输出: 1 (true)printf("%d\n", isValid("(]"));     // 输出: 0 (false)printf("%d\n", isValid("([)]"));   // 输出: 0 (false)printf("%d\n", isValid("{[]}"));   // 输出: 1 (true)// 复杂的例子printf("%d\n", isValid("{[()]}"));       // 输出: 1 (true)printf("%d\n", isValid("{[(])}"));       // 输出: 0 (false)printf("%d\n", isValid("{{[[(())]]}}")); // 输出: 1 (true)return 0;
}

cpp


#include <iostream>
#include <stack>
#include <string>
using namespace std;
class Solution
{
public:bool isMatch(char a, char b){if ((a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}')){return true;}return false;}bool isValid(string s){stack<char> stk; // 定义一个栈,用来存放左括号// stack是一个容器适配器,它提供了一种先进后出的数据结构,即栈。只能在栈顶进行插入和删除操作。if (s.size() % 2 == 1)return false; // 如果字符串长度为奇数则不可能有效,直接返回false;for (int i = 0; i < s.size(); i++){   // 扫描字符串,遇到左括号入栈,遇到右括号则与栈顶元素匹配;if (s[i] == '(' || s[i] == '[' || s[i] == '{')stk.push(s[i]); // 遇到左括号入栈;// 下面的两个else if 和 else都是对右括号情况的处理else if (stk.empty())return false; // 如果遇到了右括号但是栈已经空了,说明不是有效的括号,直接返回false;else if (!isMatch(stk.top(), s[i]))return false; // 如果遇到右括号且栈不为空,但是栈顶不是相匹配的左括号,返回false;elsestk.pop(); // 当前遍历到的右括号与栈顶左括号相匹配,弹出栈顶元素继续遍历;}return stk.empty(); // 遍历结束后,栈为空则为有效,否则无效;}
};int main()
{Solution s;cout << s.isValid("()") << endl;     // 输出: 1 (true)cout << s.isValid("()[]{}") << endl; // 输出: 1 (true)cout << s.isValid("(]") << endl;      // 输出: 0 (false)return 0;
}

LC版

C++版
在这里插入图片描述
注意 两个empty的不同
比如具体的例子如下

在这里插入图片描述

class Solution {
public:bool isMatch(char a,char b){if(a == '(' && b == ')' ||a == '[' && b == ']'||a == '{' && b == '}')return true;elsereturn false;}bool isValid(string s) {int n = s.size();if (n % 2 == 1) {return false;}stack<char> stk;for(int i = 0; i < n ; i++){if(s[i]=='(' || s[i]=='[' || s[i]=='{' )stk.push(s[i]);else if(stk.empty())return false;else if(!isMatch(stk.top(),s[i]))return false;else if(isMatch(stk.top(),s[i]))stk.pop();}return stk.empty(); // 遍历结束后,栈为空则为有效,否则无效;}};

C版

char pairs(char a) {if (a == '}') return '{';if (a == ']') return '[';if (a == ')') return '(';return 0;
}bool isValid(char* s) {int n = strlen(s);if (n % 2 == 1){return false;}int stk[n + 1], top = 0;for (int i = 0; i < n; i++){char ch = pairs(s[i]);if(ch) // 如果是右括号{if ( top == 0 || stk[top - 1] != ch) {// 如果是空栈或者不匹配return false;}top --; // 匹配了就要出栈了(top--指向新的位置)}else  //如果是左括号就入栈{//一开始top是0,那么先赋值再移动指针指向下一个位置stk[top] = s[i];top++;}}return top == 0; //最后应该都出栈了
}//总结:其实就是把哪些不成立的条件先列出来,还有注意各种边界条件,然后理解了算法原理,就能写出代码了

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

8. 性能指标

博客补充&#xff1a;CUDA C 最佳实践指南-CSDN博客https://blog.csdn.net/qq_62704693/article/details/141267262?spm1001.2014.3001.5502 在尝试优化 CUDA 代码时&#xff0c;了解如何准确测量性能并了解带宽在性能测量中的作用是值得的。本章讨论如何使用 CPU 计时器和 C…

【Stable Diffusion - Ai】小白入门必看(涂鸦、涂鸦重绘、局部重绘和重绘蒙版篇)!真材实料!不卖课!!!

【Stable Diffusion - Ai】小白入门必看&#xff08;涂鸦、涂鸦重绘、局部重绘和重绘蒙版篇&#xff09;&#xff01;真材实料&#xff01;不卖课&#xff01;&#xff01;&#xff01; 在上一篇 小白入门必看&#xff08;图生图篇&#xff09;中我们详细的介绍了文生图和图生…

Linux字体更新 使用中文字体

问题描述&#xff0c;处理之前&#xff0c;中文乱码 处理后的结果 压缩需要上传的字体&#xff1a; 上传到LInux的字体目录&#xff0c;上传后解压出来 刷新字体&#xff1a; fc-cache -fv 测试是否正常 fc-list | grep "FontName"如果还不行 可以在代码里面指定字…

信息安全工程师(72)网络安全风险评估概述

前言 网络安全风险评估是一项重要的技术任务&#xff0c;它涉及对网络系统、信息系统和网络基础设施的全面评估&#xff0c;以确定存在的安全风险和威胁&#xff0c;并量化其潜在影响以及可能的发生频率。 一、定义与目的 网络安全风险评估是指对网络系统中存在的潜在威胁和风险…

Kafka 基础入门

文章内容是学习过程中的知识总结&#xff0c;如有纰漏&#xff0c;欢迎指正 文章目录 前言 1. 核心概念 1.1 Producer 1.2 broker 1.3 consumer 1.4 zookeeper 1.5 controller 1.6 Cluster 2. 逻辑组件 2.1 Topic 2.2 Partition 2.3 Replication 2.4 leader & follower 3. …

CH569开发前的测试

为了玩转准备Ch569的开发工作 &#xff0c;准备了如下硬件和软件&#xff1a; 硬件 1.官方的 Ch569 开发板&#xff0c;官方买到的是两块插接在一起的&#xff1b;除了HSPI接口那里的电阻&#xff0c;这两块可以说是一样的。也意味着两块板子的开发也需要烧录两次&#xff1b…

OpenCV基本操作(python开发)——(7)实现图像校正

OpenCV基本操作&#xff08;python开发&#xff09;——&#xff08;1&#xff09; 读取图像、保存图像 OpenCV基本操作&#xff08;python开发&#xff09;——&#xff08;2&#xff09;图像色彩操作 OpenCV基本操作&#xff08;python开发&#xff09;——&#xff08;3&…

ffmpeg视频滤镜:网格-drawgrid

滤镜介绍 drawgrid 官网链接 》 FFmpeg Filters Documentation drawgrid会在视频上画一个网格。 滤镜使用 参数 x <string> ..FV.....T. set horizontal offset (default "0")y <string> ..FV.....T. set…

使用pytorch实现LSTM预测交通流

原始数据&#xff1a; 免费可下载原始参考数据 预测结果图&#xff1a; 根据测试数据test_data的真实值real_flow&#xff0c;与模型根据测试数据得到的输出结果pre_flow 完整源码&#xff1a; #!/usr/bin/env python # _*_ coding: utf-8 _*_import pandas as pd import nu…

Oracle视频基础1.1.3练习

1.1.3 需求&#xff1a; 完整格式查看所有用户进程里的oracle后台进程 查看物理网卡&#xff0c;虚拟网卡的ip地址 ps -ef | grep oracle /sbin/ifconfig要以完整格式查看所有用户进程中的 Oracle 后台进程&#xff0c;并查看物理和虚拟网卡的 IP 地址&#xff0c;可以使用以下…

【数据集】MODIS地表温度数据(MOD11)

【数据集】MODIS地表温度数据(MOD11) 数据概述MYD11A2数据下载MYD11A2 v006MYD11A2 v061参考MODIS(Moderate Resolution Imaging Spectroradiometer)是美国国家航空航天局(NASA)和美国国家海洋和大气管理局(NOAA)联合开发的一种遥感仪器,搭载于Terra和Aqua卫星上。MOD…

SpringBoot最佳实践之 - 项目中统一记录正常和异常日志

1. 前言 此篇博客是本人在实际项目开发工作中的一些总结和感悟。是在特定需求背景下&#xff0c;针对项目中统一记录日志(包括正常和错误日志)需求的实现方式之一&#xff0c;并不是普适的记录日志的解决方案。所以阅读本篇博客的朋友&#xff0c;可以参考此篇博客中记录日志的…

2024年优秀的天气预测API

准确、可操作的天气预报对于许多组织的成功至关重要。 事实上&#xff0c;在整个行业中&#xff0c;天气条件会直接影响日常运营&#xff0c;包括航运、按需、能源和供应链&#xff08;仅举几例&#xff09;。 以公用事业为例。根据麦肯锡的数据&#xff0c;在 1.4 年的时间里…

Tenda路由器 敏感信息泄露

0x01 产品描述&#xff1a; ‌ Tenda路由器‌是由深圳市吉祥腾达科技有限公司&#xff08;Tenda&#xff09;生产的一系列网络通信产品。Tenda路由器以其高性能、高性价比和广泛的应用场景而闻名&#xff0c;适合家庭、办公室和各种网络环境。0x02 漏洞描述&#xff1a…

net mvc中使用vue自定义组件遇到的坑

自定义一个ButtonCounter.js组件 export default {data() {return {count: 0}},template: <van-button type"primary" click"count">You clicked me {{ count }} times.</van-button> }按照官网文档的意思&#xff0c;组件命名需要大写驼峰命…

Python第六次作业

01.求第n项的斐波那契数列值 #求第n项的斐波那契数列值 #1、1、2、3、5、8、13、21、34…… #F(0)0&#xff0c;F(1)1, F(n)F(n - 1)F(n - 2)&#xff08;n ≥ 2&#xff0c;n ∈ N*&#xff09;def shulie ():print("求第n项的斐波那契数列值:",end"")xev…

Vue3 学习笔记(十三)Vue组件详解

1、组件&#xff08;Component&#xff09; 介绍 组件&#xff08;Component&#xff09;是 Vue.js 最强大的功能之一。 组件可以扩展 HTML 元素&#xff0c;封装可重用的代码&#xff0c;可以帮助你将用户界面拆分成独立和可复用的部分。 每个 Vue 组件都是一个独立的 Vue 实…

MySQL基础(二)

目录 一. 数据库命令行基本操作指令 1. 查看当前有哪些数据库——show databases; 2. 创建数据库——create database 数据库名 charset utf8 3. 选中数据库——use 数据库名; 4. 删除数据库——drop database 数据库名; 二. 常用数据类型 2.1 数值类型 2.2. 字符串类型 …

详细解读 CVPR2024:VideoBooth: Diffusion-based Video Generation with Image Prompts

Diffusion Models专栏文章汇总:入门与实战 前言:今天是程序员节,先祝大家节日快乐!文本驱动的视频生成正在迅速取得进展。然而,仅仅使用文本提示并不足以准确反映用户意图,特别是对于定制内容的创建。个性化图片领域已经非常成功了,但是在视频个性化领域才刚刚起步,这篇…

深度学习案例:带有一个隐藏层的平面数据分类

该案例来自吴恩达深度学习系列课程一《神经网络和深度学习》第三周编程作业&#xff0c;作业内容是设计带有一个隐藏层的平面数据分类。作业提供的资料包括测试实例&#xff08;testCases.py&#xff09;和任务功能包&#xff08;planar_utils.py&#xff09;&#xff0c;下载请…