问个括号问题的迭代解法# JobHunting - 待字闺中
I*e
1 楼
问题：
左“{”，右”}"括号各N个，请打印出所有正确的组合，比如当N=3,{}{}{},{{{}}},等
为正确的组合。
recursive方法careercup有，不知iterative方法怎么写？
左“{”，右”}"括号各N个，请打印出所有正确的组合，比如当N=3,{}{}{},{{{}}},等
为正确的组合。
recursive方法careercup有，不知iterative方法怎么写？
g*e
2 楼
use stack
【在 I*********e 的大作中提到】
: 问题：
: 左“{”，右”}"括号各N个，请打印出所有正确的组合，比如当N=3,{}{}{},{{{}}},等
: 为正确的组合。
: recursive方法careercup有，不知iterative方法怎么写？
【在 I*********e 的大作中提到】
: 问题：
: 左“{”，右”}"括号各N个，请打印出所有正确的组合，比如当N=3,{}{}{},{{{}}},等
: 为正确的组合。
: recursive方法careercup有，不知iterative方法怎么写？
I*e
3 楼
对，但就是不知道如何处理一个函数call自己两次的这种recursive怎么用stack来替换
。
。
d*e
4 楼
call第一次后先pop再call第二次
【在 I*********e 的大作中提到】
: 对，但就是不知道如何处理一个函数call自己两次的这种recursive怎么用stack来替换
: 。
【在 I*********e 的大作中提到】
: 对，但就是不知道如何处理一个函数call自己两次的这种recursive怎么用stack来替换
: 。
S*t
5 楼
FYI, a good candidate, after solving this particular problem, should also
figure out how to convert any recursive code into non-recursive code (via
explicit stack) in general
【在 I*********e 的大作中提到】
: 问题：
: 左“{”，右”}"括号各N个，请打印出所有正确的组合，比如当N=3,{}{}{},{{{}}},等
: 为正确的组合。
: recursive方法careercup有，不知iterative方法怎么写？
figure out how to convert any recursive code into non-recursive code (via
explicit stack) in general
【在 I*********e 的大作中提到】
: 问题：
: 左“{”，右”}"括号各N个，请打印出所有正确的组合，比如当N=3,{}{}{},{{{}}},等
: 为正确的组合。
: recursive方法careercup有，不知iterative方法怎么写？
l*c
6 楼
没有用non-recursive的方法做过，
可不可以用DFS类似的方法，建立树，访问过的，或是illegal(右括号数量多)的就不走
了，走到每个叶子打印path。
【在 I*********e 的大作中提到】
: 问题：
: 左“{”，右”}"括号各N个，请打印出所有正确的组合，比如当N=3,{}{}{},{{{}}},等
: 为正确的组合。
: recursive方法careercup有，不知iterative方法怎么写？
可不可以用DFS类似的方法，建立树，访问过的，或是illegal(右括号数量多)的就不走
了，走到每个叶子打印path。
【在 I*********e 的大作中提到】
: 问题：
: 左“{”，右”}"括号各N个，请打印出所有正确的组合，比如当N=3,{}{}{},{{{}}},等
: 为正确的组合。
: recursive方法careercup有，不知iterative方法怎么写？
s*0
7 楼
#include
#include
#include
#include
#include
using namespace std;
class ProcessParen
{
public:
ProcessParen(){};
void processString(string& inString)
{
stack charStack;
for (int i = 0; i< inString.length(); ++i)
{
if(inString[i] == '{')
{
mResult += "{";
charStack.push('{');
}
if(inString[i] == '}')
{
mResult += "}";
if (charStack.empty())
{
string currentResult = mResult;
mResult = "";
throw runtime_error("UnMatched right Parenthesis, " +
currentResult);
}
else if (charStack.top() == '}')
{
string currentResult = mResult;
mResult = "";
throw runtime_error("UnMatched right Parenthesis, " +
currentResult);
}
charStack.pop();
}
}
// check to see if there stack is empty.
if (!charStack.empty())
{
string currentResult = mResult;
mResult = "";
throw runtime_error("Unmatched left Parenthesis, " +
currentResult);
}
outputResult();
}
void outputResult()
{
cout << "matched, String stripped of brackets: " << mResult << endl;
mResult = "";
}
private:
string mResult;
};
int main()
{
string paren1 = "{}{{{}}}{}";
string paren2 = "{{}";
string paren3 = "{}}";
vector allStr;
vector::iterator sIt;
allStr.push_back(paren1);
allStr.push_back(paren2);
allStr.push_back(paren3);
ProcessParen processParen;
for (sIt = allStr.begin(); sIt < allStr.end(); ++sIt)
{
try
{
processParen.processString(*sIt);
}
catch ( exception &e)
{
cout << "exception : " << e.what() << endl;
continue;
}
}
}
#include
#include
#include
#include
using namespace std;
class ProcessParen
{
public:
ProcessParen(){};
void processString(string& inString)
{
stack
for (int i = 0; i< inString.length(); ++i)
{
if(inString[i] == '{')
{
mResult += "{";
charStack.push('{');
}
if(inString[i] == '}')
{
mResult += "}";
if (charStack.empty())
{
string currentResult = mResult;
mResult = "";
throw runtime_error("UnMatched right Parenthesis, " +
currentResult);
}
else if (charStack.top() == '}')
{
string currentResult = mResult;
mResult = "";
throw runtime_error("UnMatched right Parenthesis, " +
currentResult);
}
charStack.pop();
}
}
// check to see if there stack is empty.
if (!charStack.empty())
{
string currentResult = mResult;
mResult = "";
throw runtime_error("Unmatched left Parenthesis, " +
currentResult);
}
outputResult();
}
void outputResult()
{
cout << "matched, String stripped of brackets: " << mResult << endl;
mResult = "";
}
private:
string mResult;
};
int main()
{
string paren1 = "{}{{{}}}{}";
string paren2 = "{{}";
string paren3 = "{}}";
vector
vector
allStr.push_back(paren1);
allStr.push_back(paren2);
allStr.push_back(paren3);
ProcessParen processParen;
for (sIt = allStr.begin(); sIt < allStr.end(); ++sIt)
{
try
{
processParen.processString(*sIt);
}
catch ( exception &e)
{
cout << "exception : " << e.what() << endl;
continue;
}
}
}
a*y
8 楼
最简单的，你要想在任何情况下左的总要大于等于右的，这样就好办了
s*0
9 楼
First variant, what if you have {, [, (
is {[}] a match?
it's a match with counting.
【在 a*******y 的大作中提到】
: 最简单的，你要想在任何情况下左的总要大于等于右的，这样就好办了
is {[}] a match?
it's a match with counting.
【在 a*******y 的大作中提到】
: 最简单的，你要想在任何情况下左的总要大于等于右的，这样就好办了
I*e
10 楼
大家说得很有道理，不知谁能写个比较clear的code?
sky80 的code是在判断输入的括号是否匹配吗？
sky80 的code是在判断输入的括号是否匹配吗？
g*y
11 楼
def print_valid_parenthese_iterative(n):
stack = []
result = [] # current result
# each tuple in the stack contains three items:
# first item: number of left parenthesis remaining
# second item: number of right parenthesis remaing
# third item: the parenthesis that should add to the
# result when this tuple is popped
stack.append((n - 1, n, '('))
while stack:
left, right, parenthesis = stack.pop()
result.append(parenthesis)
# if no more parenthesis left, print the result
if left == 0 and right == 0:
print("".join(result))
# here we should restore the result to the last valid state
# by checking the current top element in the stack.
if stack:
left, right, parenthesis = stack[-1]
result = result[: 2 * n - left - right - 1]
else:
if left > 0:
stack.append((left - 1, right, '('))
if left < right:
stack.append((left, right - 1, ')'))
【在 I*********e 的大作中提到】
: 大家说得很有道理，不知谁能写个比较clear的code?
: sky80 的code是在判断输入的括号是否匹配吗？
stack = []
result = [] # current result
# each tuple in the stack contains three items:
# first item: number of left parenthesis remaining
# second item: number of right parenthesis remaing
# third item: the parenthesis that should add to the
# result when this tuple is popped
stack.append((n - 1, n, '('))
while stack:
left, right, parenthesis = stack.pop()
result.append(parenthesis)
# if no more parenthesis left, print the result
if left == 0 and right == 0:
print("".join(result))
# here we should restore the result to the last valid state
# by checking the current top element in the stack.
if stack:
left, right, parenthesis = stack[-1]
result = result[: 2 * n - left - right - 1]
else:
if left > 0:
stack.append((left - 1, right, '('))
if left < right:
stack.append((left, right - 1, ')'))
【在 I*********e 的大作中提到】
: 大家说得很有道理，不知谁能写个比较clear的code?
: sky80 的code是在判断输入的括号是否匹配吗？
I*e
12 楼
感激，但下面沒看懂：
# if no more parenthesis left, print the result
if left == 0 and right == 0:
print("".join(result))
# here we should restore the result to the last valid state
# by checking the current top element in the stack.
if stack:
left, right, parenthesis = stack[-1]
result = result[: 2 * n - left - right - 1]
如何理解？
【在 g****y 的大作中提到】
: def print_valid_parenthese_iterative(n):
: stack = []
: result = [] # current result
: # each tuple in the stack contains three items:
: # first item: number of left parenthesis remaining
: # second item: number of right parenthesis remaing
: # third item: the parenthesis that should add to the
: # result when this tuple is popped
: stack.append((n - 1, n, '('))
: while stack:
# if no more parenthesis left, print the result
if left == 0 and right == 0:
print("".join(result))
# here we should restore the result to the last valid state
# by checking the current top element in the stack.
if stack:
left, right, parenthesis = stack[-1]
result = result[: 2 * n - left - right - 1]
如何理解？
【在 g****y 的大作中提到】
: def print_valid_parenthese_iterative(n):
: stack = []
: result = [] # current result
: # each tuple in the stack contains three items:
: # first item: number of left parenthesis remaining
: # second item: number of right parenthesis remaing
: # third item: the parenthesis that should add to the
: # result when this tuple is popped
: stack.append((n - 1, n, '('))
: while stack:
g*y
13 楼
左括号，右括号都没有剩余的时候，说明我们已经得到了一个解，直接输出这个解。例
如N = 2，那么result = ()()就是一个解。对于stack中的下一个tuple，我们应该把
result恢复到符合现在这个tuple的状态。也就是说我们要从result的后面去掉一些括
号。这个可以通过left，right来计算需要去掉多少。比如stack top的tuple是（1，1
，'('）,这说明我们还剩下一个左括号，一个右括号，还有一个'('将要加到result中
去，所以我们要从result中去掉三个。也就是result 从'()()'=>'（'
不知道解释清楚了没有。
【在 I*********e 的大作中提到】
: 感激，但下面沒看懂：
: # if no more parenthesis left, print the result
: if left == 0 and right == 0:
: print("".join(result))
: # here we should restore the result to the last valid state
: # by checking the current top element in the stack.
: if stack:
: left, right, parenthesis = stack[-1]
: result = result[: 2 * n - left - right - 1]
: 如何理解？
如N = 2，那么result = ()()就是一个解。对于stack中的下一个tuple，我们应该把
result恢复到符合现在这个tuple的状态。也就是说我们要从result的后面去掉一些括
号。这个可以通过left，right来计算需要去掉多少。比如stack top的tuple是（1，1
，'('）,这说明我们还剩下一个左括号，一个右括号，还有一个'('将要加到result中
去，所以我们要从result中去掉三个。也就是result 从'()()'=>'（'
不知道解释清楚了没有。
【在 I*********e 的大作中提到】
: 感激，但下面沒看懂：
: # if no more parenthesis left, print the result
: if left == 0 and right == 0:
: print("".join(result))
: # here we should restore the result to the last valid state
: # by checking the current top element in the stack.
: if stack:
: left, right, parenthesis = stack[-1]
: result = result[: 2 * n - left - right - 1]
: 如何理解？
l*a
14 楼
You are talking about another question "validate the parentheses".
【在 s***0 的大作中提到】
: First variant, what if you have {, [, (
: is {[}] a match?
: it's a match with counting.
【在 s***0 的大作中提到】
: First variant, what if you have {, [, (
: is {[}] a match?
: it's a match with counting.
f*m
15 楼
非常感谢。
是不是有些backtracking的意思？或者树生长的意思？
result恢复到以前的某个状态（对应stack最后一个元素的内容所指的前一个配置），
然后根据stack最后一个元素的内容继续生长树（继续配置）？
1
【在 g****y 的大作中提到】
: 左括号，右括号都没有剩余的时候，说明我们已经得到了一个解，直接输出这个解。例
: 如N = 2，那么result = ()()就是一个解。对于stack中的下一个tuple，我们应该把
: result恢复到符合现在这个tuple的状态。也就是说我们要从result的后面去掉一些括
: 号。这个可以通过left，right来计算需要去掉多少。比如stack top的tuple是（1，1
: ，'('）,这说明我们还剩下一个左括号，一个右括号，还有一个'('将要加到result中
: 去，所以我们要从result中去掉三个。也就是result 从'()()'=>'（'
: 不知道解释清楚了没有。
是不是有些backtracking的意思？或者树生长的意思？
result恢复到以前的某个状态（对应stack最后一个元素的内容所指的前一个配置），
然后根据stack最后一个元素的内容继续生长树（继续配置）？
1
【在 g****y 的大作中提到】
: 左括号，右括号都没有剩余的时候，说明我们已经得到了一个解，直接输出这个解。例
: 如N = 2，那么result = ()()就是一个解。对于stack中的下一个tuple，我们应该把
: result恢复到符合现在这个tuple的状态。也就是说我们要从result的后面去掉一些括
: 号。这个可以通过left，right来计算需要去掉多少。比如stack top的tuple是（1，1
: ，'('）,这说明我们还剩下一个左括号，一个右括号，还有一个'('将要加到result中
: 去，所以我们要从result中去掉三个。也就是result 从'()()'=>'（'
: 不知道解释清楚了没有。
g*y
16 楼
是的，有点backtracking的意思。回复到某个状态就绪生长。
【在 f*********m 的大作中提到】
: 非常感谢。
: 是不是有些backtracking的意思？或者树生长的意思？
: result恢复到以前的某个状态（对应stack最后一个元素的内容所指的前一个配置），
: 然后根据stack最后一个元素的内容继续生长树（继续配置）？
:
: 1
【在 f*********m 的大作中提到】
: 非常感谢。
: 是不是有些backtracking的意思？或者树生长的意思？
: result恢复到以前的某个状态（对应stack最后一个元素的内容所指的前一个配置），
: 然后根据stack最后一个元素的内容继续生长树（继续配置）？
:
: 1
I*e
17 楼
感激
i*y
18 楼
每次不是只能去掉一个最上面的么？怎么去掉的三个呢？还有下一次循环不还是先进到
左边了吗？
左边了吗？
r*n
19 楼
use map
【在 s***0 的大作中提到】
: First variant, what if you have {, [, (
: is {[}] a match?
: it's a match with counting.
【在 s***0 的大作中提到】
: First variant, what if you have {, [, (
: is {[}] a match?
: it's a match with counting.
p*2
20 楼
class Element{
String str;
int left;
int right;
public Element(String s, int l, int r){
str=s;
left=l;
right=r;
}
}
void print(int n){
Queue q=new LinkedList();
q.add(new Element("",0,0));
while(!q.isEmpty()){
Element e=q.poll();
if(e.left==n && e.right==n){
System.out.println(e.str);
}
else{
if(e.left
if(e.left>e.right)
q.add(new Element(e.str+"}",e.left,e.right+1));
}
}
}
String str;
int left;
int right;
public Element(String s, int l, int r){
str=s;
left=l;
right=r;
}
}
void print(int n){
Queue
q.add(new Element("",0,0));
while(!q.isEmpty()){
Element e=q.poll();
if(e.left==n && e.right==n){
System.out.println(e.str);
}
else{
if(e.left
if(e.left>e.right)
q.add(new Element(e.str+"}",e.left,e.right+1));
}
}
}
c*p
21 楼
mark
m*k
22 楼
let f(k) be the set of all possible valid arrangement of k pairs of (),
for example,
f(0) = { "" }, "" means empty string
f(1) = { () }
f(2) = { ()(), (()) }
Dynamic programming
迭代：
f(0)={""}
f(k) = ( f(0) ) * f(k-1) + ( f(1) ) * f(k-1) + ... + ( f(k-1) )
所以,
f(1) = ( f(0) ) * f(0) = () => { () }
f(2) = ( f(0) )*f(1) + ( f(1) ) * f(0) = ( ) * { () } + ( { () } )
= ()() + (()) => { ()(), (()) }
f(3) = ( f(0) ) * f(2) + ( f(1) ) *f(1) + ( f(2) )*f(0)
= ()*{ ()(), (()) } + (()) () + ( { ()(), (()) } )
=()()() + ()(()) + (()) () + (()()) + ( (()) )
= { ()()() , ()(()), (()) () , (()()) , ( (()) ) }
.....
.....
for example,
f(0) = { "" }, "" means empty string
f(1) = { () }
f(2) = { ()(), (()) }
Dynamic programming
迭代：
f(0)={""}
f(k) = ( f(0) ) * f(k-1) + ( f(1) ) * f(k-1) + ... + ( f(k-1) )
所以,
f(1) = ( f(0) ) * f(0) = () => { () }
f(2) = ( f(0) )*f(1) + ( f(1) ) * f(0) = ( ) * { () } + ( { () } )
= ()() + (()) => { ()(), (()) }
f(3) = ( f(0) ) * f(2) + ( f(1) ) *f(1) + ( f(2) )*f(0)
= ()*{ ()(), (()) } + (()) () + ( { ()(), (()) } )
=()()() + ()(()) + (()) () + (()()) + ( (()) )
= { ()()() , ()(()), (()) () , (()()) , ( (()) ) }
.....
.....
c*d
23 楼
是leetcode的generateParenthesis吗？
写了个dp的
public class Solution {
public ArrayList generateParenthesis(int n) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList one = new ArrayList();
if (n < 1) return one;
HashMap> dp = new HashMap>();
ArrayList empty = new ArrayList();
empty.add(new String(""));
one.add("()");
dp.put(0, empty);
dp.put(1, one);
for (int i = 2; i <= n; i++) {
dp.put(i, build(i, dp));
}
return dp.get(n);
}
private ArrayList build(int n, HashMap
ArrayList res = new ArrayList();
for (int i = n - 1; i >= 0; i--) {
ArrayList left = dp.get(i);
ArrayList right = dp.get(n-1-i);
for (int x = 0; x < left.size(); x++) {
for (int y= 0; y < right.size(); y++) {
res.add("(" + left.get(x) + ")" + right.get(y));
}
}
}
return res;
}
}
【在 I*********e 的大作中提到】
: 问题：
: 左“{”，右”}"括号各N个，请打印出所有正确的组合，比如当N=3,{}{}{},{{{}}},等
: 为正确的组合。
: recursive方法careercup有，不知iterative方法怎么写？
写了个dp的
public class Solution {
public ArrayList
// Start typing your Java solution below
// DO NOT write main() function
ArrayList
if (n < 1) return one;
HashMap
ArrayList
empty.add(new String(""));
one.add("()");
dp.put(0, empty);
dp.put(1, one);
for (int i = 2; i <= n; i++) {
dp.put(i, build(i, dp));
}
return dp.get(n);
}
private ArrayList
ArrayList
for (int i = n - 1; i >= 0; i--) {
ArrayList
ArrayList
for (int x = 0; x < left.size(); x++) {
for (int y= 0; y < right.size(); y++) {
res.add("(" + left.get(x) + ")" + right.get(y));
}
}
}
return res;
}
}
【在 I*********e 的大作中提到】
: 问题：
: 左“{”，右”}"括号各N个，请打印出所有正确的组合，比如当N=3,{}{}{},{{{}}},等
: 为正确的组合。
: recursive方法careercup有，不知iterative方法怎么写？
m*k
24 楼
2爷出品， 必属精品！
【在 p*****2 的大作中提到】
: class Element{
: String str;
: int left;
: int right;
:
: public Element(String s, int l, int r){
: str=s;
: left=l;
: right=r;
: }
【在 p*****2 的大作中提到】
: class Element{
: String str;
: int left;
: int right;
:
: public Element(String s, int l, int r){
: str=s;
: left=l;
: right=r;
: }
相关阅读
求问阿里的等级路在何方？求指教西雅图，弯曲选哪个啊？Retail巨头找marketing analyst为什么其他外国人貌似找工作并不困难？为什么感觉现在工作比几年前更加难找？北上广深百万年薪最尴尬现在CS没有两年前那么好找工作了吧请问用过HAProxy前辈一个forward resquest的问题真是焦虑，口头offer之后一周Re: 明天是捞还是割肉？ (转载)G 什么情况下offer会保留两年？抽中H1B，但到今天还没批准，正常吗？Uber onsite的设计题H1B工作离职回国，再回美国，还需要抽签吗今天清空了所有基金阿弥陀佛buy buy buy加hr、recuriter的linkedin有什么好处？无人机公司(Autel)招聘computer vision 和image processing 相关职位为什么CS这么容易转？