给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
示例 1:
输入:s = "()" 输出:true
示例 2:
输入:s = "()[]{}" 输出:true
示例 3:
输入:s = "(]" 输出:false
思路:左括号进栈,遇到与栈顶元素相互匹配的右括号就出栈,最后如果栈空,则为有效的括号
- class Solution {
- public:
- bool isValid(string s) {
- stack<char> st;
- for(char c:s)
- {
- if(c== '(' || c== '[' || c== '{')//左括号入栈
- {
- st.push(c);
- }
- else
- {
- char changeTo=right(c);//将右括号转换成左括号
- //当st为空时,st.top()会报错,所以需要先判断st不为空,再用st.top()
- if(!st.empty()&&changeTo==st.top())//栈不为空且右括号和栈顶的左括号相匹配
- {
- st.pop();
- }
- else//不匹配
- {
- return false;
- }
- }
- }
- //若最后栈内的左括号全部出栈,则是有效的括号组合
- return st.empty();
- }
- char right(char c)
- {
- if(c==')')
- return '(';
- else if(c==']')
- return '[';
- else
- return '{';
- }
- };
只有满足下面几点之一,括号字符串才是有效的:
AB
(A
与 B
连接), 其中 A
和 B
都是有效字符串,或者(A)
,其中 A
是有效字符串。给定一个括号字符串 s
,移动N次,你就可以在字符串的任何位置插入一个括号。
s = "()))"
,你可以插入一个开始括号为 "(()))"
或结束括号为 "())))"
。返回 为使结果字符串 s
有效而必须添加的最少括号数。
示例 1:
输入:s = "())" 输出:1
示例 2:
输入:s = "(((" 输出:3
思路:栈+用need表示需要插入的左括号数
- class Solution {
- public:
- int minAddToMakeValid(string s) {
- stack<int> st;
- int need=0;
- for(char c:s)
- {
- if(c=='(')
- {
- st.push(c);
- }
- else
- {
- if(!st.empty())
- {
- st.pop();
- }
- else
- {
- //插入一个左括号
- need++;
- }
- }
- }
- //左括号+右括号
- return need+st.size();
- }
- };
这里不用栈也行,从左往右遍历s,遇到(时,leftCount加一,遇到)时,如果leftCount大于 0, 说明有左括号与之对应,leftCount减一;如果leftCount等于0,说明没有左括号对应了
需要添加一个左括号,need加一;遍历结束后,如果leftCount还是大于0,说明缺少)
与之对应,所以总共需要添加的括号数为leftCount+need。
- class Solution {
- public:
- int minAddToMakeValid(string s) {
- int leftCount=0;
- int need=0;
- for(char c:s)
- {
- if(c=='(')
- {
- leftCount++;
- }
- else
- {
- if(leftCount>0)
- {
- leftCount--;
- }
- else
- {
- need++;
- }
- }
- }
- return need+leftCount;
- }
- };
labuladong 题解思路
给你一个括号字符串 s
,它只包含字符 '('
和 ')'
。一个括号字符串被称为平衡的当它满足:
'('
必须对应两个连续的右括号 '))'
。'('
必须在对应的连续两个右括号 '))'
之前。比方说 "())"
, "())(())))"
和 "(())())))"
都是平衡的, ")()"
, "()))"
和 "(()))"
都是不平衡的。
你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。
请你返回让 s
平衡的最少插入次数。
示例 1:
输入:s = "(()))" 输出:1 解释:第二个左括号有与之匹配的两个右括号,但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。
思路:need代表对右括号的需求,res代表对左右括号配平的需求
- class Solution {
- public:
- int minInsertions(string s) {
- int need=0;//对右括号的需求
- int res=0;//对左、右括号配平的需求
- for(int i=0;i
size();i++) - {
- if(s[i]=='(')
- {
- //需要两个右括号
- need+=2;
- if(need%2==1)//需要的右括号数是奇数
- {
- //插入一个右括号,让它变成偶数
- res++;
- //对右括号的需求减一
- need--;
- }
- }
- else
- {
- need--;
- if(need==-1)//右括号不足(例:s=")")
- {
- //对右括号的需求为1
- need=1;
- //插入一个左括号
- res++;
- }
- }
- }
- return res+need;
- }
- };
给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度。
示例 1:
输入:s = "(()"
输出:2
解释:最长有效括号子串是 "()"
示例 2:
输入:s = ")()())"
输出:4
解释:最长有效括号子串是 "()()"
示例 3:
输入:s = ""
输出:0
dp[i] 表示以s[i] 结尾的最长合法括号子串的长度。
用栈来记录左括号的下标,这样遍历到右括号时,就能弹出栈顶元素,进行匹配。
- class Solution {
- public:
- int longestValidParentheses(string s) {
- int n=s.size();
- //dp[i]表示以s[i]结尾的最长合法括号子串的长度
- vector<int> dp(n);
- stack<int> st;
- for(int i=0;i
- {
- if(s[i]=='(')//以'('结尾的子串,必定不是合法括号
- {
- st.push(i);//左括号入栈
- dp[i]=0;
- }
- else//s[i]==')'
- {
- if(!st.empty())
- {
- int left=st.top();
- st.pop();
- if(left>0)
- dp[i]=dp[left-1]+i-left+1;//连续的有效括号
- else//left==0
- dp[i]=i-left+1;
- }
- else//没有匹配的左括号
- dp[i]=0;
- }
- }
- int res=0;
- for(int i=0;i
- res=max(res,dp[i]);
- return res;
- }
- };
-
相关阅读:
Games101笔记-计算机图形学概述
分页文件pagefile.sys引出的疑问
计算机图形学(七)-深度缓存、着色shadding、着色模型、着色频率、渲染管线
Vue路由及Node.js环境搭建
[21天学习挑战赛——内核笔记](六)——在debugfs中添加一个调试目录
React中组件通信02——消息订阅与发布、取消订阅以及卸载组件时取消订阅
面试:聊一聊 Java 数组默认的排序算法,我懵了
通过竞品分析来挖掘产品卖点
一个免杀项目分享
Elasticsearch的使用
-
原文地址:https://blog.csdn.net/weixin_50437588/article/details/126821660