- 浏览: 173288 次
- 性别:
- 来自: 济南
文章分类
最新评论
这篇文章总结leetcode中有关括号的问题,最简单的是判断输入的括号是否有效,例如“))”就不属于有效的括号,括号的题目无非是添加,删除,找到最长有效括号等。最长有效括号是一道DP问题,我们在DP总结中结合最长回文子串一起列出。下面列举几个基本的题目。
1,Valid Parentheses
给定一个字符串序列,它包含'(', ')', '{', '}', '[' , ']',判断字符串是否是有效括号组成的。
例如:"()" 和 "()[]{}" 是有效字符串;而 "(]" 和 "([)]" 就不是合法字符串。
我们用堆栈解决这道题,从第一个字符开始遍历,遇到‘(’ , '{' 或‘{’时,我们就把它压入到堆栈中,如果遇到‘)' , ']' 和‘}’时我们将字符出栈,并且与当前字符比较,如果匹配就继续查找,如果不匹配返回false。在遍历完之后,我们要检查堆栈是否为空,如果不为空,也返回false。
例如“((())”就会导致遍历结束后,栈中还有一个字符‘(’,而它是无效的字符串。代码如下:
2,Generate Parentheses
给定n对括号,列出所有可能的有效组合。
例如:n = 3
输出 :"((()))", "(()())", "(())()", "()(())", "()()()"
看到组合问题我们就想到用回溯法,回溯的条件是字符串的长度为2n时,我们就把它记录下来,然后回溯找其它的答案。当查找的时候,我们设定两个变量left和right,分别代表左括号的数量和右括号的数量,当左括号不为零时,我们可以继续添加左括号;而对于右括号,我们要保证再往下查找的时,右括号的数量大于左括号的数量(right > left), 否则就会生成错误结果。
代码如下:
3,Different Ways to Add Parentheses
给定一个字符串,字符串由数字和操作符组成,通过添加不同的括号列出所有可能的计算结果。
例如:输入:"2*3-4*5"
输出:[-34, -14, -10, -10, 10]
结果是由以下的方式计算出来的:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
这道题我们用递归来解决,遍历字符串,当遇到操作符号时,我们就分别递归当前操作符的左边部分和右边部分,最终得到结果。代码如下:
1,Valid Parentheses
给定一个字符串序列,它包含'(', ')', '{', '}', '[' , ']',判断字符串是否是有效括号组成的。
例如:"()" 和 "()[]{}" 是有效字符串;而 "(]" 和 "([)]" 就不是合法字符串。
我们用堆栈解决这道题,从第一个字符开始遍历,遇到‘(’ , '{' 或‘{’时,我们就把它压入到堆栈中,如果遇到‘)' , ']' 和‘}’时我们将字符出栈,并且与当前字符比较,如果匹配就继续查找,如果不匹配返回false。在遍历完之后,我们要检查堆栈是否为空,如果不为空,也返回false。
例如“((())”就会导致遍历结束后,栈中还有一个字符‘(’,而它是无效的字符串。代码如下:
public class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<Character>(); for(int i = 0; i < s.length(); i++) { char c = s.charAt(i); if(c == '[' || c == '(' || c == '{') { stack.push(c); } else { if(stack.isEmpty()) return false; char cs = stack.pop(); if((c == ')' && cs == '(') || (c == ']' && cs == '[') || (c == '}' && cs == '{')) continue; else return false; } } if(!stack.isEmpty()) return false; return true; } }
2,Generate Parentheses
给定n对括号,列出所有可能的有效组合。
例如:n = 3
输出 :"((()))", "(()())", "(())()", "()(())", "()()()"
看到组合问题我们就想到用回溯法,回溯的条件是字符串的长度为2n时,我们就把它记录下来,然后回溯找其它的答案。当查找的时候,我们设定两个变量left和right,分别代表左括号的数量和右括号的数量,当左括号不为零时,我们可以继续添加左括号;而对于右括号,我们要保证再往下查找的时,右括号的数量大于左括号的数量(right > left), 否则就会生成错误结果。
代码如下:
public class Solution { public List<String> generateParenthesis(int n) { LinkedList<String> list = new LinkedList<String>(); int left = n; int right = n; String result = ""; generateParent(n, left, right, result, list); return list; } public void generateParent(int n, int left, int right, String result, LinkedList<String> list) { if(result.length() == 2 * n) { list.add(result); } if(left > 0) generateParent(n, left - 1, right, result + "(", list); if(right > left) generateParent(n, left, right - 1, result + ")", list); } }
3,Different Ways to Add Parentheses
给定一个字符串,字符串由数字和操作符组成,通过添加不同的括号列出所有可能的计算结果。
例如:输入:"2*3-4*5"
输出:[-34, -14, -10, -10, 10]
结果是由以下的方式计算出来的:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
这道题我们用递归来解决,遍历字符串,当遇到操作符号时,我们就分别递归当前操作符的左边部分和右边部分,最终得到结果。代码如下:
public class Solution { public List<Integer> diffWaysToCompute(String input) { List<Integer> list = new LinkedList<Integer>(); if(!input.contains("+") && !input.contains("-") && !input.contains("*")) { list.add(Integer.valueOf(input)); return list; } for(int i = 0; i < input.length(); i++) { char c = input.charAt(i); if(c == '+' || c == '*' || c == '-') { List<Integer> leftlist = diffWaysToCompute(input.substring(0, i)); List<Integer> rightlist = diffWaysToCompute(input.substring(i + 1, input.length())); for(int leftvalue : leftlist) for(int rightvalue : rightlist) { switch (c) { case '+': list.add(leftvalue + rightvalue); break; case '-': list.add(leftvalue - rightvalue); break; case '*': list.add(leftvalue * rightvalue); break; } } } } return list; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 226Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 224You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 340Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 331Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 450Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 509Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 429Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 618Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 427The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 386Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 516Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 529Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 367All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 860Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 880Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 553Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 600Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 762Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 732You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 627For a undirected graph with tre ...
相关推荐
用C语言编写的,括号匹配的检验能够让人轻易的学会C语言和数据结构的使用。
parentheses:如何通过放置括号来给出最大数量
leetcode 2 有效括号 给定一个只包含字符'(' , ')' , '{' , '}' , '['和']'的字符串,确定输入字符串是否有效。 输入字符串在以下情况下有效: * 左括号必须由相同类型的括号封闭。...类别:堆栈、序列处理
此项目已移至来源: ://sr.ht/~tsdh/highlight-parentheses.el/
括号分类器采用一组括号的内容,并将其分类为几个类别之一。 它包括一个带括号的数据提取器和分类器。
括弧 编码练习 给定一串左括号和右括号,检查它是否平衡。 我们有 3 种类型的括号:圆括号:()、方括号:[] 和大括号:{}。 假设字符串不包含除这些之外的任何其他字符,没有空格单词或数字。 提醒一下,平衡括号...
语言:English (United States) 输入一个括号,使其自动关闭。 现在,每当您在网络中输入括号时,扩展程序都会自动完成它。 此扩展还包含实验性的和有缺陷的Wolfram | Alpha集成。 您可以单击一个方程,W | A将尝试...
语言:English (United States) 检查您的WeBWorK答案以正确使用括号。 可在任何学校的WeBWorK安装中使用。 在您为数学或物理课程的WeBWorK作业中输入冗长而又复杂的解决方案(带括号)而感到沮丧吗?...
SP-6667 : Parentheses settings aren't working right for OUTER APPLY. SP-6807 : Maintains a space between close parentheses on RAISERROR and WITH clause. SP-6836 : Parentheses are not consistent in ...
2017湘潭大学邀请赛题目
The right-left rule: Start reading the declaration from the innermost parentheses, go right, and then go left. When you encounter parentheses, the direction should be reversed. Once everything in the...
The right-left rule: Start reading the declaration from the innermost parentheses, go right, and then go left. When you encounter parentheses, the direction should be reversed. Once everything in the ...
第四章 Leetcode 题解 ...20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli
检查你的WeBWorK答案,正确使用括号。可用于任何学校的WeBWorK安装。 在你的数学或物理课上为你的WeBWorK家庭作业输入冗长而复杂的解答并输入大量的括号而感到沮丧? 此扩展名显示您需要添加圆括号的位置,或者您在...
输入一个paren,让它自动关闭。 现在,只要您在网络中输入一个括号,扩展程序就会自动完成它。 此扩展还包含实验性的和有缺陷的Wolfram | Alpha集成。 您可以单击一个方程,W | A将尝试显示它。...
假设一个算数表达式中可包含三种括号:圆括号,方括号和花括号且这三种括号可以按任意次序嵌套使用。试利用栈的运算,编写判别表达式中所含括号是否正确配对出现的算法
Option added to change CREATE/ALTER parentheses separately from the global parentheses options Option added to insert an empty line between JOIN clauses Ole db provider names are now suggested for ...
日圆括号 没有维护- lighttable 很漂亮,但它不是 vim。 主题,旨在与括号一起使用以使代码可读。 目前仅包括轻型变体。 需要彩虹插件的彩虹括号。 包含粗体和浅色变体的字体(例如 )使括号正确突出。
Shouldn t crash on regexps with many nested parentheses.
SP-6887 : Add space between function parentheses and NOT IN. SP-6903 : Rule MI006 no longer detects issue if the parameter is used in function calls. See the full release notes for more information.