h****e
发帖数: 928 | 1 原题在这儿：
http://www.careercup.com/question?id=13262681
简单的说，就是二叉树的一个结点如果一个子树为空，就用0表示，
非空用(...)嵌套表示。叶子结点就是(00)。例如
o -> (00)
o
/
o -> ((00)0)
o
/ \
o o -> ((00)(00))
现在给定一个字符串，要判断它是否表示的是一个有效的二叉树。
是的话返回树的深度，不是的话返回-1。
我的想法是用一个堆栈：碰到(00)的话，就压1入栈；碰到0或)
的话就和栈内的元素比较以后化简，如(01)变成2, (12)变成3之类的。
例如((00)(0(00)))的化简过程就是:
((00)(0(00))) -> (1(0(00))) -> (1(01)) -> (12) -> 3
最后返回3-1=2
这样程序写出来差不多要七八十行，而且调试好多次以后才做对。
请问有没有更简洁的办法？ |
p*****2
发帖数: 21240 | |
h****e
发帖数: 928 | 3 看不出可递归的子结构，可以说具体一些吗？
【在 p*****2 的大作中提到】
: recursion。
|
p*****2
发帖数: 21240 | 4 ((00)(00))
可以分为左右子树
左子树
(00),
右子树
(00)
这样可以递归。用个cache，就是O(n)的复杂度。 |
h****e
发帖数: 928 | 5 但是你怎么找出左右子树的分隔点，我觉得这样得先扫描字符串一次，
平均扫描N/2次。找到分隔点以后，左右再分开做，递推公式是:
T(N) = N/2 + 2T(N/2)
复杂度就是O(NlogN)了。
【在 p*****2 的大作中提到】
: ((00)(00))
: 可以分为左右子树
: 左子树
: (00),
: 右子树
: (00)
: 这样可以递归。用个cache，就是O(n)的复杂度。
|
p*****2
发帖数: 21240 | 6
先用一个hashtable存储
key 存 （ 的位置
value 存 ）的位置
这样扫一遍，以后就直接可以得到配对的）的位置了。
【在 h****e 的大作中提到】
: 但是你怎么找出左右子树的分隔点，我觉得这样得先扫描字符串一次，
: 平均扫描N/2次。找到分隔点以后，左右再分开做，递推公式是:
: T(N) = N/2 + 2T(N/2)
: 复杂度就是O(NlogN)了。
|
h****e
发帖数: 928 | 7 还是不明白，找配对的时候还是要扫N/2个左括号。
这样50行之内可以写得出来吗？
【在 p*****2 的大作中提到】
:
: 先用一个hashtable存储
: key 存 （ 的位置
: value 存 ）的位置
: 这样扫一遍，以后就直接可以得到配对的）的位置了。
|
p*****2
发帖数: 21240 | 8
随便写了一个，不过没 怎么调呀。大概这个意思。
HashMap hm = new HashMap();
int isValid(char[] arr)
{
Stack stack = new Stack();
for (int i = 0; i < arr.length; i++)
{
if (arr[i] == '(')
stack.push(i);
else if (arr[i] == ')')
{
if (stack.isEmpty())
return -1;
hm.put(stack.pop(), i);
}
}
if (!stack.isEmpty())
return -1;
return check(arr, 0, arr.length - 1);
}
int check(char[] arr, int start, int end)
{
if (!hm.containsKey(start) || hm.get(start) != end)
return -1;
start++;
end--;
if (start + 1 == end)
if (arr[start] == '0' && arr[end] == '0')
return 1;
else
return -1;
if (!hm.containsKey(start) || hm.get(start) > end)
return -1;
int left = check(arr, start, hm.get(start));
int right = hm.get(start) == end ? 0 : check(arr, hm.get(start) + 1,
end);
if (left == -1 || right == -1)
return -1;
else
return 1 + Math.max(left, right);
}
【在 h****e 的大作中提到】
: 还是不明白，找配对的时候还是要扫N/2个左括号。
: 这样50行之内可以写得出来吗？
|
n****n
发帖数: 117 | 9 只要记录(和)的数量，还有上一个(或者)的位置即可
1,
【在 p*****2 的大作中提到】
:
: 随便写了一个，不过没 怎么调呀。大概这个意思。
: HashMap hm = new HashMap();
: int isValid(char[] arr)
: {
: Stack stack = new Stack();
: for (int i = 0; i < arr.length; i++)
: {
: if (arr[i] == '(')
: stack.push(i);
|
h****e
发帖数: 928 | 10 多谢，大概明白你的意思了。不过复杂度还是O(NlogN)吧，
不知道面试的时候够不够用。
【在 p*****2 的大作中提到】
:
: 随便写了一个，不过没 怎么调呀。大概这个意思。
: HashMap hm = new HashMap();
: int isValid(char[] arr)
: {
: Stack stack = new Stack();
: for (int i = 0; i < arr.length; i++)
: {
: if (arr[i] == '(')
: stack.push(i);
|
|
|
p*****2
发帖数: 21240 | 11
复杂度应该是O(N)吧？
核心代码也就是30多行吧？我一般写代码看着行数多。
【在 h****e 的大作中提到】
: 多谢，大概明白你的意思了。不过复杂度还是O(NlogN)吧，
: 不知道面试的时候够不够用。
|
h****e
发帖数: 928 | 12 哦，是O(N)，我先前想错了。
【在 p*****2 的大作中提到】
:
: 复杂度应该是O(N)吧？
: 核心代码也就是30多行吧？我一般写代码看着行数多。
|
v****c
发帖数: 29 | 13 int f(const std::string& str, int start, int& end)
{
if(start < str.size() && str[start] == '0')
{
end = start;
return 0;
}
else if(start < str.size() && str[start] == '(')
{
int t; // position of last letter in the left subtree
int left = f(str, start + 1, t);
if(left == -1) return -1;
int right = f(str, t + 1, end);
if(right == -1 || ++end == str.size() || str[end] != ')') return -1;
return std::max(left, right) + 1;
}
return -1;
}
main里面调用f(str, 0, end)，然后比较一下end是不是str.size()-1就行了
【在 h****e 的大作中提到】
: 原题在这儿：
: http://www.careercup.com/question?id=13262681
: 简单的说，就是二叉树的一个结点如果一个子树为空，就用0表示，
: 非空用(...)嵌套表示。叶子结点就是(00)。例如
: o -> (00)
: o
: /
: o -> ((00)0)
: o
: / \
|
j********e
发帖数: 1192 | 14 我的做法也是用stack，可能简单些。
从左到右scan一遍，如果是"("或者0，就入栈，如果是“)”就
看栈顶3个元素是否“(00”，是的话，弹出这3个，
压入“0”(也就把子树替换成“0”)。
最后栈里只剩一个“0”就validated。
int validate(char *s, int len) {
if(s == NULL || len == 0 || s[0] != '(')
return -1;
int depth = 0, max_depth = 0;
char *t = new char[len+1];
int tlen = 0;
for(int i=0; i
if(s[i] == '(') {
depth++;
if(depth>max_depth)
max_depth = depth;
}
else if(s[i] == '0')
t[tlen++] = s[i];
else if(s[i] == ')') {
if(tlen>=3 && t[tlen-1] == '0'
&& t[tlen-2] == '0'
&& t[tlen-3] == '(') {
t[tlen-3] = '0';
tlen -= 2;
}
else
return -1;
}
else
return -1;
}
if(tlen == 1 && t[0] == '0')
return max_depth;
else
return -1;
}
【在 h****e 的大作中提到】
: 原题在这儿：
: http://www.careercup.com/question?id=13262681
: 简单的说，就是二叉树的一个结点如果一个子树为空，就用0表示，
: 非空用(...)嵌套表示。叶子结点就是(00)。例如
: o -> (00)
: o
: /
: o -> ((00)0)
: o
: / \
|
z****h
发帖数: 164 | |
w****x
发帖数: 2483 | 16 为啥都那么复杂, 就是递归下降语法分析撒
语法规则
F = ( [N | F] [N | F])
N = (00) | 0
3种token ( | (00) | 0 |
l*********8
发帖数: 4642 | 17 我也写一个，写完才发现和jingoshine的是一样的：）
int BinaryTreeDepth(string & s)
{
int maxDepth(-1), depth(-1);
vector v;
for (int i=0; i
if (s[i] == '(') {
v.push_back(s[i]);
maxDepth = max(maxDepth, ++depth);
} else if (s[i] == '0') {
v.push_back('0');
} else if (s[i] == ')') {
int n=v.size();
if (n<3 || v[n-1]!='0' || v[n-2]!='0' || v[n-3]!='(')
return -1;
v[n-3] = '0';
v.resize(n-2);
--depth;
} else
return -1;
}
return v[0]=='0' && v.size()==1 ? maxDepth : -1;
} |
l*********8
发帖数: 4642 | 18 一个小bug：
if(s[i] == '(') {
的时候没有入栈。
【在 j********e 的大作中提到】
: 我的做法也是用stack，可能简单些。
: 从左到右scan一遍，如果是"("或者0，就入栈，如果是“)”就
: 看栈顶3个元素是否“(00”，是的话，弹出这3个，
: 压入“0”(也就把子树替换成“0”)。
: 最后栈里只剩一个“0”就validated。
: int validate(char *s, int len) {
: if(s == NULL || len == 0 || s[0] != '(')
: return -1;
: int depth = 0, max_depth = 0;
: char *t = new char[len+1];
|
l*********8
发帖数: 4642 | 19 请问怎么编程实现呢？
【在 w****x 的大作中提到】
: 为啥都那么复杂, 就是递归下降语法分析撒
: 语法规则
: F = ( [N | F] [N | F])
: N = (00) | 0
: 3种token ( | (00) | 0
|
h****e
发帖数: 928 | 20 这个vector.resize()用得很巧。这样相当于把
vector当作stack来用，但是功能更强大因为
可以多个元素同时出栈。多谢，又学了一招。
【在 l*********8 的大作中提到】
: 我也写一个，写完才发现和jingoshine的是一样的：）
: int BinaryTreeDepth(string & s)
: {
: int maxDepth(-1), depth(-1);
: vector v;
: for (int i=0; i: if (s[i] == '(') {
: v.push_back(s[i]);
: maxDepth = max(maxDepth, ++depth);
: } else if (s[i] == '0') {
|
|
|
p*****2
发帖数: 21240 | 21
怎么没见你返回－1呢？
【在 l*********8 的大作中提到】
: 我也写一个，写完才发现和jingoshine的是一样的：）
: int BinaryTreeDepth(string & s)
: {
: int maxDepth(-1), depth(-1);
: vector v;
: for (int i=0; i: if (s[i] == '(') {
: v.push_back(s[i]);
: maxDepth = max(maxDepth, ++depth);
: } else if (s[i] == '0') {
|
l*********8
发帖数: 4642 | 22 我理解为：根节点深度为1了。 如果根节点深度为0， 那么我的程序中的一些0要变成-
1.
【在 p*****2 的大作中提到】
:
: 怎么没见你返回－1呢？
|
l*********8
发帖数: 4642 | 23 看了题目要求，根节点深度应该算作0.
根据题目要求我把程序改了一下：）
成-
【在 l*********8 的大作中提到】
: 我理解为：根节点深度为1了。 如果根节点深度为0， 那么我的程序中的一些0要变成-
: 1.
|
p*****2
发帖数: 21240 | 24 } else if (s[i] == ')') {
int n=v.size();
if (n<3 || v[n-1]!='0' || v[n-2]!='0' || v[n-3]!='(')
return -1;
这段没明白
((((((((((00)))))))))) 你返回什么？ |
l*********8
发帖数: 4642 | 25 应该是返回-1， 因为是非法的binary树
简单一点儿的例子
((00)) 是非法的，因为用0代替（00）后变成 (0)
((00)0) 或者 ((00)(00))才是合法的
【在 p*****2 的大作中提到】
: } else if (s[i] == ')') {
: int n=v.size();
: if (n<3 || v[n-1]!='0' || v[n-2]!='0' || v[n-3]!='(')
: return -1;
: 这段没明白
: ((((((((((00)))))))))) 你返回什么？
|
p*****2
发帖数: 21240 | 26
奥。是我理解错了。
【在 l*********8 的大作中提到】
: 应该是返回-1， 因为是非法的binary树
: 简单一点儿的例子
: ((00)) 是非法的，因为用0代替（00）后变成 (0)
: ((00)0) 或者 ((00)(00))才是合法的
|
