[已解决]Python：每日一题 297

zltzlt

今天的题目：

给定整数 n，表示有 n 对括号，生成所有 n 对括号的组合并返回组合结果。

示例 1：

输入：3
输出：["((()))", "(()())", "(())()", "()(())", "()()()"]

示例 2：

输入：2
输出：["()()", "(())"]

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

塔利班

2019-12-31 20:25:05

1. def f295(n):
   
2.     res=[]
   
3.     def dp(base,l,r):
   
4.         if l==0:
   
5.             res.append(base+')'*r)
   
6.         else:
   
7.             dp(base+'(',l-1,r)
   
8.             if l<r:
   
9.                 dp(base+')',l,r-1)
   
10.     dp('',n,n)
    
11.     return res
    

复制代码

跳转到最佳答案楼层

Unicorn#

1. def solve(n):
   
2.     if n <= 0:
   
3.         return ''
   
4.     def find(father):
   
5.         if len(father) == n:
   
6.             return [sorted(father)]
   
7.         else:
   
8.             res = []
   
9.             for i in range(-1, len(father)):
   
10.                 res.extend(find(father + [i]))
    
11.             return res
    
12.     father_list = []
    
13.     for i in find([-1]):
    
14.         if i not in father_list:
    
15.             father_list.append(i)
    
16.     def transfer(father):
    
17.         def draw(p, res):
    
18.             for i in range(len(father)):
    
19.                 if father[i] == p:
    
20.                     res = draw(i, res+'(')+')'
    
21.             return res
    
22.         return draw(-1, '')
    
23.     return list(map(transfer, father_list))

复制代码

塔利班

1. def f295(n):
   
2.     res=[]
   
3.     def dp(base,l,r):
   
4.         if l==0:
   
5.             res.append(base+')'*r)
   
6.         else:
   
7.             dp(base+'(',l-1,r)
   
8.             if l<r:
   
9.                 dp(base+')',l,r-1)
   
10.     dp('',n,n)
    
11.     return res
    

复制代码

阴阳神万物主

抢地板
代码：

1. def solve(n):
   
2.     res = []
   
3.     if n:
   
4.         pos = list(range(n))
   
5.         def add():
   
6.             nonlocal pos
   
7.             for i in range(n-1,-1,-1):
   
8.                 if pos[i] < 2*i:
   
9.                     pos[i] += 1
   
10.                     break
    
11.             for j in range(i+1,n):
    
12.                 pos[j] = pos[j-1]+1
    
13.         m = [2*x for x in range(n)]
    
14.         while True:
    
15.             each = []
    
16.             for i in pos:
    
17.                 each.insert(i,')')
    
18.                 each.insert(i,'(')
    
19.             res.append(''.join(each))
    
20.             if pos < m:
    
21.                 add()
    
22.             else:
    
23.                 break
    
24.     return res
    
25. 
    
26. if __name__ == '__main__':
    
27.     print('示例1 输出：',solve(3))
    
28.     print('示例2 输出：',solve(2))
    
29.     print('自测 输出：',solve(4))
    

复制代码

可能浪费了一部分时间处理坐标……心塞塞
用生成器可能会用时少点

1. def solve(n):
   
2.     res = []
   
3.     if n:
   
4.         def get_pos(n):
   
5.             pos = list(range(n))
   
6.             m = [2*x for x in range(n)]
   
7.             while pos < m:
   
8.                 yield pos
   
9.                 for i in range(n-1,-1,-1):
   
10.                     if pos[i] < 2*i:
    
11.                         pos[i] += 1
    
12.                         break
    
13.                 for j in range(i+1,n):
    
14.                     pos[j] = pos[j-1]+1
    
15.             yield pos
    
16.         for pos in get_pos(n):
    
17.             each = []
    
18.             for i in pos:
    
19.                 each.insert(i,')')
    
20.                 each.insert(i,'(')
    
21.             res.append(''.join(each))
    
22.     return res
    
23. 
    
24. if __name__ == '__main__':
    
25.     print('示例1 输出：',solve(3))
    
26.     print('示例2 输出：',solve(2))
    
27.     print('自测 输出：',solve(4))
    

复制代码

本来想以"对"为单位作平移的，结果没想出来怎样直接在字符串上做更改，然后就设计了个多余的坐标来表示

Croper

1. def func297_1(n:int)->list:
   
2.     ret=[[0]]
   
3.     for i in range(2*n):
   
4.         temp=[]
   
5.         for l in ret:
   
6.             if l[-1]>0:
   
7.                 temp.append(l+[l[-1]-1])
   
8.             if l[-1]<2*n-i:
   
9.                 temp.append(l+[l[-1]+1])
   
10.         ret=temp
    
11.     ret2=[]
    
12.     for l in ret:
    
13.         ret2.append("".join(["(" if l[i+1]>l[i] else ")" for i in range(2*n)]))
    
14.     return ret2

复制代码

Croper

改良版

1. def func297_2(n:int)->list:
   
2.     ret=[(0,"")]
   
3.     for i in range(2*n):
   
4.         temp=[]
   
5.         for l in ret:
   
6.             if l[0]>0:
   
7.                 temp.append((l[0]-1,l[1]+")"))
   
8.             if l[0]<2*n-i:
   
9.                 temp.append((l[0]+1,l[1]+"("))
   
10.         ret=temp
    
11.     return [i[1] for i in ret]

复制代码

平推就行，每一位保证左括号不大于n，右括号不大于左括号的数目。

TJBEST

抢地板，下午发

塔利班

Croper 发表于 2019-12-31 20:53
改良版

平推就行，每一位保证左括号不大于n，右括号不大于左括号的数目。

为嘛我测试n数量大了感觉2种方法都没有我的快呢，，- -

Croper

塔利班 发表于 2020-1-1 11:34
为嘛我测试n数量大了感觉2种方法都没有我的快呢，，- -

我试了一下

这是我计算运行时间的修饰器：

1. import time
   
2. 
   
3. class TimeFunc:
   
4.     def __init__(self,Func):
   
5.         self.Func=Func
   
6.         self.sumRunTime=0.0
   
7.         self.countRun=0
   
8. 
   
9.     def __call__(self,*args,**kwargs):
   
10.         t1=time.clock()*1000
    
11.         ret=self.Func(*args,**kwargs)
    
12.         t2=time.clock()*1000
    
13.         self.countRun+=1
    
14.         self.sumRunTime+=t2-t1
    
15.         return ret
    
16. 
    
17.     def clear(self):
    
18.         self.sumRunTime=0
    
19.         self.countRun=0
    
20.     def GetAveRunTime(self):
    
21.         if self.countRun==0:
    
22.             return -1
    
23.         return self.sumRunTime/self.countRun

复制代码

这是测试代码

1. from module1 import TimeFunc
   
2. import math
   
3. 
   
4. @TimeFunc
   
5. def f295(n):
   
6.     res=[]
   
7.     def dp(base,l,r):
   
8.         if l==0:
   
9.             res.append(base+')'*r)
   
10.         else:
    
11.             dp(base+'(',l-1,r)
    
12.             if l<r:
    
13.                 dp(base+')',l,r-1)
    
14.     dp('',n,n)
    
15.     return res
    
16. 
    
17. @TimeFunc
    
18. def func297_2(n:int)->list:
    
19.     ret=[(0,"")]
    
20.     for i in range(2*n):
    
21.         temp=[]
    
22.         for l in ret:
    
23.             if l[0]>0:
    
24.                 temp.append((l[0]-1,l[1]+")"))
    
25.             if l[0]<2*n-i:
    
26.                 temp.append((l[0]+1,l[1]+"("))
    
27.         ret=temp
    
28.     return [i[1] for i in ret]
    
29. 
    
30. for i in range(1,20):
    
31.     f295(i)
    
32.     func297_2(i)
    
33.     print("%d\t%f\t%f"%(i,f295.GetAveRunTime(),func297_2.GetAveRunTime()))
    
34.     f295.clear()
    
35.     func297_2.clear()

复制代码

测试结果：

1. 1       0.021900        0.020900
   
2. 2       0.028100        0.027100
   
3. 3       0.055200        0.033600
   
4. 4       0.092900        0.074800
   
5. 5       0.259200        0.201000
   
6. 6       0.766200        0.622900
   
7. 7       2.486100        2.004500
   
8. 8       8.053500        7.573700
   
9. 9       27.519100       24.749500
   
10. 10      96.716700       91.843300
    
11. 11      331.920700      301.414800
    
12. 12      1161.430700     1098.966200
    
13. 13      4146.963900     3979.403900
    
14. 14      14975.798600    14503.480000
    
15. 15      54112.200300    52794.922200

复制代码

Croper

Croper 发表于 2020-1-1 12:00
我试了一下

这是我计算运行时间的修饰器：

你的额外时间主要花费在递归过程中函数的调用，进栈和出栈。
我的主要花费在列表的重新连接。
其实大家的思路都差不多，时间复杂度都一样。最后谁快就看电脑处理哪个快了呗。。

塔利班

Croper 发表于 2020-1-1 12:04
你的额外时间主要花费在递归过程中函数的调用，进栈和出栈。
我的主要花费在列表的重新连接。
其实大 ...

1. 1        0.003800        0.004600
   
2. 2        0.006400        0.007500
   
3. 3        0.016400        0.029900
   
4. 4        0.015300        0.025500
   
5. 5        0.034300        0.060400
   
6. 6        0.095600        0.178300
   
7. 7        0.306400        0.672400
   
8. 8        0.883500        2.976600
   
9. 9        2.949600        6.544400
   
10. 10        9.835800        28.778100
    
11. 11        33.952200        97.857100
    
12. 12        128.145800        370.189000
    
13. 13        485.154900        1362.962500
    
14. 14        1614.351900        4911.807300
    
15. 15        5773.216100        18165.848400

复制代码

嗯，这是我跑的，不过也差不多，我主要是好奇bz的测时机制

TJBEST

版主，我用了两个方法，其中一个用到了itertools 不知道 符不符合规矩，确实快了很多我将代码给您，您看看。
（1）用到了itertools

1. import itertools
   
2. def fun297(n):
   
3.     def isOK(com):
   
4.         tempIndex = 0
   
5.         left = 0
   
6.         result = ''
   
7.         for each in com:
   
8.             left = left + (2 - (each - tempIndex))
   
9.             if left < 0:
   
10.                 return False
    
11.             else:
    
12.                 result = result + ')'*(each - tempIndex - 1) + '('
    
13.             tempIndex = each
    
14.         result = result + ')'*(2*n - 1 - tempIndex - 1)
    
15.         return result
    
16.     List = []   
    
17.     for eachCom in itertools.combinations(range(1,2*n-1),n-1):
    
18.         temp = isOK(eachCom)
    
19.         if temp == False:
    
20.             pass
    
21.         else:
    
22.             result = '(' + temp + ')'
    
23.             List.append(result)
    
24.     return List

复制代码

（2）没有用到itertools

1. def fun297(n):
   
2.     def integer2bin(num,n):
   
3.         result = ''
   
4.         right = 0
   
5.         div = num
   
6.         for each in range(1,2 * n + 1):
   
7.             res = div % 2
   
8.             div = div // 2
   
9.             if res == 1:
   
10.                 right = right + 1
    
11.                 result = ')' + result
    
12.             else:
    
13.                 right = right - 1
    
14.                 result = '(' + result
    
15.             if right < 0 or right > n:
    
16.                 return None
    
17.         if right == 0:
    
18.             return result
    
19.         else:
    
20.             return None
    
21.     result = []
    
22.     start = (2**n) - 1
    
23.     end = ((2**(2*n))-1)//3
    
24.     for num in range(start,end + 1,2):
    
25.         if integer2bin(num,n)!=None:
    
26.             result.append(integer2bin(num,n))
    
27.     return result

复制代码

549491637

1. def fun297(num):
   
2.     result = [""]
   
3.     cache = []
   
4.     for i in range(num*2):
   
5.         for j in result:
   
6.             if j.count("(") < num:
   
7.                 cache.append(j + "(")
   
8.             if j.count(")") < num and j.count("(") > j.count(")"):
   
9.                 cache.append(j + ")")
   
10.         result = cache.copy()
    
11.         cache.clear()
    
12.     return result
    
13. 
    
14. while 1:
    
15.     print(fun297(int(input("请输入一个数字："))))
    

复制代码

ouyunfu

def f295(n):
    L=[]
    def dp(base,l,r):
        if l==0:
            L.append("("+base+")"*r+")")
        elif l>r:
            dp(base+"(",l-1,r)
        else:
            dp(base+")",l,r-1)
            dp(base+"(",l-1,r)      
    dp('',n-1,n-1)
    return L
print(len(f295(5)))