之前写了两篇 感觉太简单的没什么意思 就一直搁下懒得写了 今天做题的时候碰到了个有意思的 就记录一下吧
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入:"()"输出:true
示例 2:
输入:"()[]{}"输出:true
示例 3:
输入:"(]"输出:false
示例 4:
输入:"([)]"输出:false
示例 5:
输入:"{[]}"输出:true
初看 感觉需要遍历 和一大堆if判断 然后还想到可以用ascii码的值来判断 后来自己写的时候 发现只能满足 (){}()[] 这种依次排列 以及({[]}) 这样规律的嵌套 ({}([])) 这种多级的嵌套无法搞定 以下是我失败的截图
失败尝试
其实还是蛮简洁有意思的,但是我懒得继续想了 感觉挺蠢的 而且本能地想到应该是需要用到栈 因为最早看<<算法>>那本书的时候,提及到了对于栈的一些使用 百度了一下 果然如此 并且自己实现了一种 好像还不错的方法 如下
public class Solution { public bool IsValid(string s) { if (s == null) return true; if (s.Length % 2 == 1) return false; Stacksc=new Stack();
for(int i = 0; i < s.Length; i++)
{
switch (s[i])
{
case '(': sc.Push(s[i]); break;
case '{': sc.Push(s[i]); break;
case '[': sc.Push(s[i]); break;
case ')':if (sc.Count == 0 || sc.Peek() != '(') return false; else sc.Pop(); break;
case '}':if (sc.Count == 0 || sc.Peek() != '{') return false; else sc.Pop(); break;
case ']':if (sc.Count == 0 || sc.Peek() != '[') return false; else sc.Pop(); break;
}
}
return sc.Count == 0;
}
}
思路就是遇到左括号就压进去 遇到右括号就去和栈顶对比 其他的嘛 自己写写思路也就理清啦 不赘述了
然后在我提交了之后 又看到了一种NB的算法
public class Solution{ public bool IsValid(string s) { Stackstack = new Stack();
foreach (char item in s.ToCharArray())
{
if (item == '(')
stack.Push(')');
else if (item == '{')
stack.Push('}');
else if (item == '[')
stack.Push(']');
else if (stack.Count == 0 || stack.Pop() != item)
return false;
}
return stack.Count == 0;
}
}
牛比在哪? emmm自己读读吧 虽然我感觉思路区别不是很大 但是这个用时是之前那个的一半还要少哦
网友评论