教人做衣服的网站,南京科技网站设计费用,教做糕点的网站,wordpress 媒体分类leetcode题目有效的括号#xff0c;分类是easy#xff0c;但是博主前前后后提交了几十次才通过#xff0c;现在记录一下使用Java语言的写法。
题目链接: 20.有效的括号
题目描述#xff1a;
给定一个只包括 (#xff0c;)#xff0c;{#xff0c;}#xff0c;[分类是easy但是博主前前后后提交了几十次才通过现在记录一下使用Java语言的写法。
题目链接: 20.有效的括号
题目描述
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。有效字符串需满足
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。题目示例
示例 1
输入s ()
输出true示例 2
输入s ()[]{}
输出true示例 3
输入s (]
输出false题目提示
1. s.length 104
2. 仅由括号 ()[]{} 组成题目解读
每个左括号都要有成对的右括号成对的含义是
1属于()、[]、{}中的任意一对
2中间不存在其他字符比如()
3中间存在其他成对的字符比如({[]})示例图
一、 递归
基于以上的理解博主最初选择使用递归消除字符的做法。只要左右相邻的字符成对就将其消除递归至LinkedHashMap的长度为0或不再出现可消除的字符。
思路
1使用LinkedHashMap保存入参用例中的所有字符。
2遍历LinkedHashMap在存在相邻两个元素符合成对匹配条件时将这两个元素记录下来在一次遍历结束后从LinkedHashMap中移除。
3当LinkedHashMap长度为0或者在一次遍历中没有产生新的待删除的元素则跳出循环。
4当最终LinkedHashMap长度为0时说明全部匹配成功。class Solution {public boolean isValid(String s) {boolean res false;char[] charArray s.toCharArray();if (charArray.length % 21) {return res;}HashMapInteger, String linkedHashMap new LinkedHashMap();for (int i 0; i charArray.length; i) {linkedHashMap.put(i, String.valueOf(charArray[i]));}ListString leftList Arrays.asList((, [, {);ListString rightList Arrays.asList(), ], });// 当map中全部消除完或上一轮没有可消除的值时跳出循环int lastIndex 0;ListInteger removeKeys new ArrayList();while (!linkedHashMap.isEmpty()) {removeKeys new ArrayList();for (Integer key : linkedHashMap.keySet()) {int pos new ArrayListInteger(linkedHashMap.keySet()).indexOf(key);// 从第二个开始跟前面的比较前面取最新的linkedMap的第一个不是key0if (pos 0) {if (leftList.contains(linkedHashMap.get(lastIndex)) rightList.contains(linkedHashMap.get(key)) (leftList.indexOf(linkedHashMap.get(lastIndex)) rightList.indexOf(linkedHashMap.get(key)))) {// 删除对应位置removeKeys.add(lastIndex);removeKeys.add(key);linkedHashMap.put(lastIndex, 0);linkedHashMap.put(key, 0);}}// 保存上一个key的值lastIndex key;}if (!removeKeys.isEmpty()) {removeKeys.forEach(linkedHashMap::remove);} else {break;}}if (linkedHashMap.isEmpty()) {res true;}return res;}}该做法可以计算正确但在遇到以下测试用例时惨遭Time Limit Exceeded 。
String s [([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([([()])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])];该测试用例长度为7000以递归消除元素的方法需要递归遍历几千次速度非常的慢。那么提高速度最好的办法就是减少遍历次数。
二、栈
在评论区看了一圈发现大佬们的基本都是用栈来解决。 但是博主平时基本不使用栈这种数据结构对栈的了解仅停留在以下层面。
栈Stack是一种常见的数据结构具有后进先出LIFOLast In First Out的特性即最后入栈的元素最先出栈。所以依然选择使用熟悉的LinkedHashMap去实现LIFO这一行为。在加入LinkedHashMap前先判断是否与末尾的元素匹配再决定后续的操作。仅需要遍历一次就可以完成所有的匹配判断。
思路
1遍历入参的字符数组。
2如果linkedMap长度为空当前字符直接加入作为第一个字符。
3如果linkedMap长度不为空取末尾元素与当前元素进行匹配。匹配成功将末尾元素消除弹出匹配失败将当前元素加入linkedMap压入
4字符数组遍历结束后如果linkedMap为空说明全部匹配。class Solution {public boolean isValid(String s) {boolean res false;char[] charArray s.toCharArray();if (charArray.length % 21) {return res;}ListString leftList Arrays.asList((, [, {);ListString rightList Arrays.asList(), ], });// 栈一个一个往堆栈里填入如果跟前一个匹配就双双丢出HashMapInteger, String linkedHashMap new LinkedHashMap();for (int i 0; i charArray.length; i) {String s1 String.valueOf(charArray[i]);// 当前linkedMap中的排列的第一位if (i 0 || linkedHashMap.isEmpty()) {if (rightList.contains(s1)) {return false;}linkedHashMap.put(i, String.valueOf(charArray[i]));} else {int lastPos new ArrayListInteger(linkedHashMap.keySet()).get(linkedHashMap.size()-1);// 判断跟linkedMap中最新一位元素是否匹配String lastS1 linkedHashMap.get(lastPos);if (leftList.contains(lastS1) rightList.contains(s1) (leftList.indexOf(lastS1) rightList.indexOf(s1))) {// 匹配成功不加入linkedMap并且将前一个元素从map中移除弹出linkedHashMap.remove(lastPos);} else {// 不匹配将该元素加入linkedMap中压入linkedHashMap.put(i, String.valueOf(charArray[i]));}}}// 全部消除完毕才是通过if (linkedHashMap.isEmpty()) {res true;}return res;}
}不过在使用LinkedHashMap时也碰到了一些问题因为元素可以随意移除所以key的排序不是连续的12345等。需要将key转为ArrayList再通过ArrayList.get()方法获取最新一位元素key。
