唉，好无奈的陪伴 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Parenting - 为人父母

唉，好无奈的陪伴

唉，好无奈的陪伴# Parenting - 为人父母

m*a2018-07-12 07:07

1 楼

Given n pairs of parentheses, write a function to generate all combinations
of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
递归很容易
void generateParenthesisRecr(string str,int n,int l,int r,vector&
result){
if (l==n && r==n){
result.push_back(str);
return;
}
if (lif (l>r) generateParenthesisRecr(str+")",n,l,r+1,result);
}
vector generateParenthesis2(int n) {
vectorresult;
generateParenthesisRecr("",n,0,0,result);
return result;
}
但是不递归的我写的方法很慢，无法通过 leetcode
就是第一次插入一对"()"，下一次插入下一对的时候，可以查到
上一对的任何地方就是有三个选择(new)(),((new)),()(new)
然后插入下一对，有5*3=15中可能
插入的可能指数增长
最后去处重复
vector generateParenthesis(int n) {
stack seed;
stack solution;
vectorresult;
if (n==1){
result.push_back("()");
return result;
}
if (n==0) return result;
seed.push("()");
for (int i=2;i<=n;i++){
while (!seed.empty()){
for (int i=0;i<=seed.top().size();i++){
string str=seed.top();
solution.push(str.insert(i,"()"));
}
seed.pop();
}
seed=solution;
while (!solution.empty()) solution.pop();
}
while (!seed.empty()){
int notsame=1;
for (int i=0;iif (seed.top()==result[i]){
seed.pop();
notsame=0;
break;
}
}
if (notsame){
result.push_back(seed.top());
seed.pop();
}
}
return result;
}

b*g2018-07-12 07:07

2 楼

儿子回家住了十天又走了，虽然有点不舍和牵挂，但心里有种轻松自由的舒服，因为不
用每天计划着做什么好吃的给他。我是不是一个很自私的妈妈？有点内疚的感觉，不能
让儿子知道。
孩子回来每一顿饭都希望有营养，孩子吃的不但是美食还有母爱。
给儿子端上一碟炒乌冬面，想坐在边上像小时候一样陪着他看他津津有味地吃面，可是
孩子长大了，他受不了妈妈的眼神和亲近，他更喜欢的是边看新闻边吃面。老妈不能以
自己的私心影响了儿子的心情，选择悄悄地离开，给他自由的空间。
一家人同时用餐的时候，不看电视不玩手机是一直以来的规矩，现在还保持着。
休息的那天想出去逛商场，没指望儿子会跟我们同行，只是随便地问问他的意见。没想
到他居然愿意一起去购物中心，大概是良心发现需要陪陪父母吧。
到了商场他单独行动，到了吃饭点手机联系。儿子根本没有逛商店，就坐在一个咖啡馆
喝咖啡上网。
给他钱让他买几件好看的衣服，还拒绝了。我半开玩笑地说：“你爸你妈穿得那么体面
，而你穿得这么随便，人家会以为你不是我们亲生的呐。”儿子摆摆手耸耸肩，不在乎。
一起在Wagamama用完餐，我还想再逛逛，叫儿子去看一场电影。两个多小时后，我们逛
够了，儿子是从咖啡厅里出来的，他没有去看电影。
唉，儿子无奈的陪伴让我们也很内疚，如果只是应该陪父母而不享受跟父母在一起的快
乐，父母也会有压力的。
老爸送他去火车站的路上问他回家过得怎样，儿子说回家就是休息，很放松。
这一年儿子常回家住几天，只要他觉得家是他可以放松心情的地方，老妈就放心了。
带他去中国餐馆吃点心，尝尝不一样的味道，可是他最喜欢的还是老妈的炒乌冬，晚上
回到家再给他炒一个。

h*e2018-07-12 07:07

3 楼

mark

l*a2018-07-12 07:07

4 楼

没细想，直接BFS就可以吧
你只能start from "("这个算root,
他的子节点可以是(( or ()
下一level可以是 ((( or (() or ()(
以此类推。只要number of "(" <= n, number of ")" <=number of "("
就可以插入Queue
最后...

combinations

【在 m*********a 的大作中提到】

: Given n pairs of parentheses, write a function to generate all combinations
: of well-formed parentheses.
: For example, given n = 3, a solution set is:
: "((()))", "(()())", "(())()", "()(())", "()()()"
: 递归很容易
: void generateParenthesisRecr(string str,int n,int l,int r,vector&
: result){
: if (l==n && r==n){
: result.push_back(str);
: return;

l*e2018-07-12 07:07

5 楼

一样思路改成递推就行了空间是还可以优化的
class Solution {
public:
vector generateParenthesis(int n) {
vector f[n + 1][n + 1];
f[0][0] = vector {""};

for (int left = 0; left <= n; ++left) {
for (int right = 0; right <= left; ++right) {
for (const string& s : f[left][right]) {
if (left < n) {
f[left + 1][right].push_back(s + "(");
}
if (right < left) {
f[left][right + 1].push_back(s + ")");
}
}
}
}
return f[n][n];
}
};

l*e2018-07-12 07:07

6 楼

再上一个空间优化的吧
class Solution {
public:
vector generateParenthesis(int n) {
vector f[2][n + 1];
f[0][0] = vector {""};

for (int left = 0; left <= n; ++left) {
for (int right = 0; right <= left; ++right) {
f[(left + 1) & 1][right].clear();
for (const string& s : f[left & 1][right]) {
if (left < n) {
f[(left + 1) & 1][right].push_back(s + "(");
}
if (right < left) {
f[left & 1][right + 1].push_back(s + ")");
}
}
}
}
return f[n & 1][n];
}
};

l*e2018-07-12 07:07

7 楼

再来更多的空间优化好了
class Solution {
public:
vector generateParenthesis(int n) {
vector f[n + 1];
f[0] = vector {""};

for (int left = 0; left <= n; ++left) {
for (int right = 0; right <= left; ++right) {
for (int i = 0; i < f[right].size(); ++i) {
if (right < left) {
f[right + 1].push_back(f[right][i] + ")");
}
if (left < n) {
f[right][i] += "(";
}
}
}
}
return f[n];
}
};

z*a2018-07-12 07:07

8 楼

好角度，写了个，过了LC，差不多是非递归中序遍历二叉树的思路。
class Solution {
public:
class stack
{
public:
char c;
int flag;
stack(char c, int flag)
{
this->c = c;
this->flag = flag;
}
};
vector generateParenthesis(int n) {
int left = 0;
int right = 0;
vectorrecord;
vectorresult;
stack temp(0,0);
record.push_back(stack('(', 0));
left++;
while (record.size() != 0)
{
temp = record[record.size() - 1];
record.pop_back();
if (temp.c == '(')
{
left--;
}
else
{
right--;
}
if (temp.c == '(')
{
if (temp.flag == 0)
{
record.push_back(stack('(', 1));
left++;
if (left > right)
{
record.push_back(stack(')', 0));
right++;
}
}
else if (temp.flag == 1)
{
if (left < n - 1)
{
record.push_back(stack('(', 2));
left++;
record.push_back(stack('(', 0));
left++;
}
}
}
else if(temp.c == ')')
{
if (temp.flag == 0 && right!=n-1)
{
record.push_back(stack(')', 1));
right++;
if (left{
record.push_back(stack('(', 0));
left++;
}
}
else if (temp.flag == 1)
{
if (right < n-1 && left>=right+2)
{
record.push_back(stack(')', 2));
right++;
record.push_back(stack(')', 0));
right++;
}
}
}
int pos = 0;
string temp_record;
if (right == n && left == n)
{
for (pos = 0; pos < 2*n; pos++)
{
temp_record.push_back(record[pos].c);
}
result.push_back(temp_record);
}
}
return result;
}
};

m*a2018-07-12 07:07

9 楼

大家很牛啊，想得清楚>2可能的非递归的
左右二种选择就比较难了非递归就比较难了

m*e2018-07-12 07:07

10 楼

我来贡献一个用queue的方法。C#写的：
// Iterative approach
public List generateParenthesisIter(int n)
{
Queue queue = new Queue(
);
queue.Enqueue(new ParenthesisWrapper("",0,0));
List result = new List();
while (queue.Count > 0)
{
ParenthesisWrapper curr = queue.Dequeue();
if (curr.left == n)
{
if (curr.right < n)
{
curr.parenthesis += new string(')', n-curr.right);
}
result.Add(curr.parenthesis);
continue;
}
if (curr.left < n)
{
queue.Enqueue(new ParenthesisWrapper(curr.parenthesis +
"(", curr.left + 1, curr.right));
}
if (curr.right < curr.left)
{
queue.Enqueue(new ParenthesisWrapper(curr.parenthesis +
")", curr.left, curr.right + 1));
}
}
return result;
}
public class ParenthesisWrapper
{
public string parenthesis;
public int left;
public int right;
public ParenthesisWrapper(string p, int l, int r)
{
parenthesis = p;
left = l;
right = r;
}
}

combinations

【在 m*********a 的大作中提到】

: 大家很牛啊，想得清楚>2可能的非递归的
: 左右二种选择就比较难了非递归就比较难了

m*k2018-07-12 07:07

11 楼

DP

combinations

【在 m*********a 的大作中提到】

: 大家很牛啊，想得清楚>2可能的非递归的
: 左右二种选择就比较难了非递归就比较难了

l*s2018-07-12 07:07

12 楼

贡献一个 python
class Solution:
# @param an integer
# @return a list of string
def generateParenthesis(self, n):
bs='()'
res=['()']
if n==0:
return ''
elif n==1:
return res
for i in range(2,n+1):
leres=len(res)
for j in range(leres):
base=res[0]
del res[0]
lebase=len(base)
for k in range(lebase+1):
new = base[0:k]+bs+base[k:lebase]
if not (new in res):
res.append(new)
return res