p*u
发帖数: 136 | 1 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
注意不是求合法的括号个数。。。
三哥面试官，感觉算三哥里面比较好听懂的发音了
就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
。。
感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
长时间。 | f**********3
发帖数: 295 | 2 这回不是三哥黑你，这是rf常见题
【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
| p*u
发帖数: 136 | 3 感觉比较tough啊，有题解没？
【在 f**********3 的大作中提到】
: 这回不是三哥黑你，这是rf常见题
| w*******s
发帖数: 138 | 4 直接枚举吧？内存不会吃不消，如果数目很大，枚举输出会很长时间。
【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
| l*n
发帖数: 529 | 5 应该类似BackTrack吧，不用都存起来。
【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
| l***z
发帖数: 9 | 6 我面过这题 是让直接打出来 不会存在内存里
用stack做 和leetcode上的generate parenthesis差不多 | p*u
发帖数: 136 | 7 时间复杂度很高啊？
【在 l***z 的大作中提到】
: 我面过这题 是让直接打出来 不会存在内存里
: 用stack做 和leetcode上的generate parenthesis差不多
| f********e
发帖数: 91 | 8 一个比较简单的办法是用递归来逐步添加各种括号 可以用一个stack来判断每次加的括
号是否合理
应该是可以把以上这个递归的过程改称迭代的 逻辑上可能会比较复杂一些 在电话面
试里写这个还是挺不容易的
【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
| p*u
发帖数: 136 | 9 你这个思路挺好！
我当时是写的这种，你看下能过不？。。。空间消耗很大
https://code.stypi.com/b9fzywss
【在 f********e 的大作中提到】
: 一个比较简单的办法是用递归来逐步添加各种括号 可以用一个stack来判断每次加的括
: 号是否合理
: 应该是可以把以上这个递归的过程改称迭代的 逻辑上可能会比较复杂一些 在电话面
: 试里写这个还是挺不容易的
| c********p
发帖数: 1969 | | | | f********e
发帖数: 91 | 11 恩 好的 我看看
【在 p*u 的大作中提到】
: 你这个思路挺好！
: 我当时是写的这种，你看下能过不？。。。空间消耗很大
: https://code.stypi.com/b9fzywss
| f********a
发帖数: 165 | | m*****k
发帖数: 731 | 13 这么做有重复吧，
start with {}{}(),
then
{} ({})
and
{}({})
are actually the same.
【在 p*u 的大作中提到】
: 你这个思路挺好！
: 我当时是写的这种，你看下能过不？。。。空间消耗很大
: https://code.stypi.com/b9fzywss
| B****D
发帖数: 132 | 14 这题的思路是这样的.
首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
不必把所有答案都存起来. 产生一个, 打一个.
这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
.
举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
括号, 每种左括号还各剩一个, 你怎么办?
你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
扩号匹配. 因此, 你需要4个参数.
1. 还剩几个 "("
2. 还剩几个 "["
3. 还剩几个 "{"
4. 当前的结果.
下面是用JAVA写的CODE. 为了方便, 多加了一个参数, 所有目前为止的左括号的STACK.
这是为了不用分析当前结果去找下一个右括号.
public class ListP
{
static int count = 0;
public static void main(String args[])
{
int n1 = 2;
int n2 = 2;
int n3 = 1;
PrintP(n1, n2, n3, "", "");
}
static String rightPart(String left)
{
if (left.equals("(")) return ")";
if (left.equals("[")) return "]";
return "}";
}
static void PrintP(int n1, int n2, int n3, String result, String
leftStack)
{
if (n1 == 0 && n2 ==0 && n3 == 0 && leftStack.length() == 0)
{
count ++;
System.out.println ("" + count + ":" + result + "\r\n");
}
if (leftStack.length() > 0)
{
PrintP(n1, n2, n3, result + rightPart(leftStack.substring(0, 1))
, leftStack.substring(1));
}
if (n1 > 0)
{
PrintP(n1 - 1, n2, n3, result + "(", "(" + leftStack);
}
if (n2 > 0)
{
PrintP(n1, n2-1, n3, result + "[", "[" + leftStack);
}
if (n3 > 0)
{
PrintP(n1, n2, n3-1, result + "{", "{" + leftStack);
}
}
} | z****e
发帖数: 54598 | 15 re一个
【在 B****D 的大作中提到】
: 这题的思路是这样的.
: 首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
: 不必把所有答案都存起来. 产生一个, 打一个.
: 这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
: .
: 举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
: 括号, 每种左括号还各剩一个, 你怎么办?
: 你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
: 扩号匹配. 因此, 你需要4个参数.
: 1. 还剩几个 "("
| c********p
发帖数: 1969 | | f********x
发帖数: 2086 | 17
大神！多谢
【在 B****D 的大作中提到】
: 这题的思路是这样的.
: 首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
: 不必把所有答案都存起来. 产生一个, 打一个.
: 这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
: .
: 举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
: 括号, 每种左括号还各剩一个, 你怎么办?
: 你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
: 扩号匹配. 因此, 你需要4个参数.
: 1. 还剩几个 "("
| k*****o
发帖数: 43 | | S*****o
发帖数: 5 | | l**********a
发帖数: 181 | | | | n*****a
发帖数: 107 | | p*u
发帖数: 136 | 22 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
注意不是求合法的括号个数。。。
三哥面试官，感觉算三哥里面比较好听懂的发音了
就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
。。
感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
长时间。 | f**********3
发帖数: 295 | 23 这回不是三哥黑你，这是rf常见题
【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
| p*u
发帖数: 136 | 24 感觉比较tough啊，有题解没？
【在 f**********3 的大作中提到】
: 这回不是三哥黑你，这是rf常见题
| w*******s
发帖数: 138 | 25 直接枚举吧？内存不会吃不消，如果数目很大，枚举输出会很长时间。
【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
| l*n
发帖数: 529 | 26 应该类似BackTrack吧，不用都存起来。
【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
| l***z
发帖数: 9 | 27 我面过这题 是让直接打出来 不会存在内存里
用stack做 和leetcode上的generate parenthesis差不多 | p*u
发帖数: 136 | 28 时间复杂度很高啊？
【在 l***z 的大作中提到】
: 我面过这题 是让直接打出来 不会存在内存里
: 用stack做 和leetcode上的generate parenthesis差不多
| f********e
发帖数: 91 | 29 一个比较简单的办法是用递归来逐步添加各种括号 可以用一个stack来判断每次加的括
号是否合理
应该是可以把以上这个递归的过程改称迭代的 逻辑上可能会比较复杂一些 在电话面
试里写这个还是挺不容易的
【在 p*u 的大作中提到】
: 有n1个()，n2个[]，n3个{}，枚举出所有的合法括号组合。
: 注意不是求合法的括号个数。。。
: 三哥面试官，感觉算三哥里面比较好听懂的发音了
: 就一个题，跟他纠结了很长时间，也聊了比较长时间的项目。最后面了1小时22分钟。
: 。。
: 感觉三哥出题很坑，枚举出所有的组合的话，内存吃不消吧；而且会跟你解释argue很
: 长时间。
| p*u
发帖数: 136 | 30 你这个思路挺好！
我当时是写的这种，你看下能过不？。。。空间消耗很大
https://code.stypi.com/b9fzywss
【在 f********e 的大作中提到】
: 一个比较简单的办法是用递归来逐步添加各种括号 可以用一个stack来判断每次加的括
: 号是否合理
: 应该是可以把以上这个递归的过程改称迭代的 逻辑上可能会比较复杂一些 在电话面
: 试里写这个还是挺不容易的
| | | c********p
发帖数: 1969 | | f********e
发帖数: 91 | 32 恩 好的 我看看
【在 p*u 的大作中提到】
: 你这个思路挺好！
: 我当时是写的这种，你看下能过不？。。。空间消耗很大
: https://code.stypi.com/b9fzywss
| f********a
发帖数: 165 | | B****D
发帖数: 132 | 34 这题的思路是这样的.
首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
不必把所有答案都存起来. 产生一个, 打一个.
这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
.
举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
括号, 每种左括号还各剩一个, 你怎么办?
你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
扩号匹配. 因此, 你需要4个参数.
1. 还剩几个 "("
2. 还剩几个 "["
3. 还剩几个 "{"
4. 当前的结果.
下面是用JAVA写的CODE. 为了方便, 多加了一个参数, 所有目前为止的左括号的STACK.
这是为了不用分析当前结果去找下一个右括号.
public class ListP
{
static int count = 0;
public static void main(String args[])
{
int n1 = 2;
int n2 = 2;
int n3 = 1;
PrintP(n1, n2, n3, "", "");
}
static String rightPart(String left)
{
if (left.equals("(")) return ")";
if (left.equals("[")) return "]";
return "}";
}
static void PrintP(int n1, int n2, int n3, String result, String
leftStack)
{
if (n1 == 0 && n2 ==0 && n3 == 0 && leftStack.length() == 0)
{
count ++;
System.out.println ("" + count + ":" + result + "\r\n");
}
if (leftStack.length() > 0)
{
PrintP(n1, n2, n3, result + rightPart(leftStack.substring(0, 1))
, leftStack.substring(1));
}
if (n1 > 0)
{
PrintP(n1 - 1, n2, n3, result + "(", "(" + leftStack);
}
if (n2 > 0)
{
PrintP(n1, n2-1, n3, result + "[", "[" + leftStack);
}
if (n3 > 0)
{
PrintP(n1, n2, n3-1, result + "{", "{" + leftStack);
}
}
} | z****e
发帖数: 54598 | 35 re一个
【在 B****D 的大作中提到】
: 这题的思路是这样的.
: 首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
: 不必把所有答案都存起来. 产生一个, 打一个.
: 这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
: .
: 举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
: 括号, 每种左括号还各剩一个, 你怎么办?
: 你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
: 扩号匹配. 因此, 你需要4个参数.
: 1. 还剩几个 "("
| c********p
发帖数: 1969 | | f********x
发帖数: 2086 | 37
大神！多谢
【在 B****D 的大作中提到】
: 这题的思路是这样的.
: 首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
: 不必把所有答案都存起来. 产生一个, 打一个.
: 这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
: .
: 举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
: 括号, 每种左括号还各剩一个, 你怎么办?
: 你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
: 扩号匹配. 因此, 你需要4个参数.
: 1. 还剩几个 "("
| k*****o
发帖数: 43 | | S*****o
发帖数: 5 | | n*****a
发帖数: 107 | | | | l********1
发帖数: 24 | 41 void dfs(int n1, int n2, int n3, string transfer, set &dict){
if(n1 == 0 && n2 == 0 && n3 == 0){
if(dict.find(transfer) == dict.end()){
dict.insert(transfer);
cout<
}
return;
}
if(transfer.size() == 0){
if(n1 > 0){
string temp = "()";
dfs(n1 - 1, n2, n3, temp, dict);
}
if(n2 > 0){
string temp = "[]" ;
dfs(n1, n2 - 1, n3, temp, dict);
}
if(n3 > 0){
string temp = "{}";
dfs(n1, n2, n3 - 1, temp, dict);
}
}
for(int i = 0; i < transfer.size(); ++i){
if(transfer[i] == '(' || transfer[i] == '[' || transfer[i] == '{'){
if(n1 > 0){
string temp = transfer.substr(0, i + 1) + "()" + transfer.
substr(i + 1);
dfs(n1 - 1, n2, n3, temp, dict);
}
if(n2 > 0){
string temp = transfer.substr(0, i + 1) + "[]" + transfer.
substr(i + 1);
dfs(n1, n2 - 1, n3, temp, dict);
}
if(n3 > 0){
string temp = transfer.substr(0, i + 1) + "{}" + transfer.
substr(i + 1);
dfs(n1, n2, n3 - 1, temp, dict);
}
}
}
}
void generateParenthesis(int n1, int n2, int n3) {
set dict;
dfs(n1, n2, n3, "",dict);
} | w****r
发帖数: 69 | 42 来个简单易懂的python版, n1是剩余左括号， n1_是剩余右括号
res = []
def gen(sol, stk, n1, n2, n3, n1_, n2_, n3_):
if n1 == 0 and n2 == 0 and n3 == 0 and n1_ == 0 and n2_ == 0 and n3_ ==
0:
res.append("".join(sol))
return
if n1 > 0:
gen(sol[:] + ["("], stk[:] + [1], n1-1, n2, n3, n1_, n2_, n3_)
if n2 > 0:
gen(sol[:] + ["["], stk[:] + [2], n1, n2-1, n3, n1_, n2_, n3_)
if n3 > 0:
gen(sol[:] + ["{"], stk[:] + [3], n1, n2, n3-1, n1_, n2_, n3_)
if len(stk) > 0 and stk[-1] == 1:
gen(sol[:] + [")"], stk[:-1], n1, n2, n3, n1_-1, n2_, n3_)
if len(stk) > 0 and stk[-1] == 2:
gen(sol[:] + ["]"], stk[:-1], n1, n2, n3, n1_, n2_-1, n3_)
if len(stk) > 0 and stk[-1] == 3:
gen(sol[:] + ["}"], stk[:-1], n1, n2, n3, n1_, n2_, n3_-1)
gen([], [], 2, 2, 1, 2, 2, 1)
for i in res:
print i | w****r
发帖数: 69 | 43 我在想，有没有办法能求出solution的个数? |
|
