java算法,问题如下?
问:假设有一字符串长度无穷大,内容只有
{} 六个。
结果:返回Boolean
规则: 必须成对出现,可以嵌套,但不能错位。如:
A = "{[()()[]{}]
}...({[]}{}())" True
B = "
{]
{(){}[]}()}()}...((((){}[]" False 因:红色部分出现错位
要求:利用JAVA或JavaScript算法实现
我看了电视
10 years, 2 months ago
Answers
Leetcode 原题:
https://leetcode.com/problems/valid-parentheses/
答案在
https://leetcode.com/discuss/questions/oj/valid-parentheses
里找
https://leetcode.com/discuss/11196/my-solution-one-stack-case-statemen...
smeagol
answered 10 years, 2 months ago
更新3:谢@brayden同学提醒,已经改正并简化了代码。
更新2:发现自己怎么这么热心,顺便把JavaScript版本也写了吧,放在最后。
更新1:下班回家重新整理了一下格式,原理正如楼下@DerrickChan同学所说,利用了栈的数据结构。
最近比较忙,如果需要JavaScript版本的话请告知。
来个Java的吧,提供个思路,想翻译成JavaScript也不难,就先不写了。
代码如下:
UnitTest.java
public class UnitTest {
public static void main(String[] args) {
Checker checker = new Checker();
String s1 = "{[()()[]{}]}({[]}{}())";
String s2 = "{]{(){}[]}()}()}((((){}[]";
System.out.println(checker.check(s1));
System.out.println(checker.check(s2));
}
}
Checker.java
public class Checker {
private char[][] css = { { '(', ')' }, { '[', ']' }, { '{', '}' } };
private char[] cs = null;
private char[] stack = null;
private int index = 0;
public boolean check(String s) {
cs = s.toCharArray();
stack = new char[cs.length];
for (char c : cs)
if (!isEndding(c))
push(c);
else if (!isPair(pop(), c))
return false;
if (index == 0)
return true;
index = 0;
return false;
}
public void push(char c) {
stack[index++] = c;
}
private char pop() {
return index == 0 ? '\0' : stack[--index];
}
private boolean isEndding(char c) {
for (int i = 0; i != css.length; ++i)
if (c == css[i][1])
return true;
return false;
}
private boolean isPair(char c1, char c2) {
for (int i = 0; i != css.length; ++i)
if (c1 == css[i][0] && c2 == css[i][1])
return true;
return false;
}
}
UnitTest.js
var s1 = "{[()()[]{}]}({[]}{}())";
var s2 = "{]{(){}[]}()}()}((((){}[]";
var css = "()[]{}";
var stack = {};
var index = 0;
console.log(check(s1));
console.log(check(s2));
function check(cs) {
for (var i = 0; i != cs.length; ++i) {
var c = cs[i]
if (!isEndding(c))
push(c);
else if (!isPair(pop(), c))
return false;
}
if (index == 0)
return true;
index = 0;
return false;
}
function push(c) {
stack[index++] = c;
}
function pop() {
return index == 0 ? '\0' : stack[--index];
}
function isEndding(c) {
console.log();
for (var i = 0; i != css.length; i = i + 2)
if (c == css[i + 1])
return true;
return false;
}
function isPair(c1, c2) {
for (var i = 0; i != css.length; i = i + 2)
if (c1 == css[i] && c2 == css[i + 1])
return true;
return false;
}
clouder
answered 10 years, 2 months ago