Python：每日一题 234（答题有奖）

zltzlt

今天的题目：

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

这道题已结束，进入奖励阶段。

示例 1：

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2：

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

我的解法（括号不支持嵌套）：

1. def longest_valid_par(string):
   
2.     result = []
   
3.     for i in range(len(string) - 1):
   
4.         a = 2
   
5.         while True:
   
6.             if string[i:i + a] == "()" * (a // 2):
   
7.                 try:
   
8.                     string[i + a - 1]
   
9.                 except Exception:
   
10.                     result.append(a - 2)
    
11.                     break
    
12.                 a += 2
    
13.             else:
    
14.                 result.append(a - 2)
    
15.                 break
    
16.     return max(result, default=0)

复制代码

panheng

和231是不是重复了，感觉做过这题

zltzlt

panheng 发表于 2019-9-1 19:27
和231是不是重复了，感觉做过这题

表面上一样而已。

_2_

以后6点才放学，时间不太充分
@zltzlt

henry2018

重复了～～～，我也学会了黑字了

henry2018

_2_ 发表于 2019-9-1 20:14
以后6点才放学，时间不太充分
@zltzlt

我今天返校，11点就回来了～～～

henry2018

zltzlt 发表于 2019-9-1 19:56
表面上一样而已。

只是更简单了～～～

panheng

zltzlt 发表于 2019-9-1 19:56
表面上一样而已。

我又看了两遍题干，一模一样啊。。。包括实例。

是不是231和232的混合版，支持嵌套的意思？

zltzlt

panheng 发表于 2019-9-1 20:47
我又看了两遍题干，一模一样啊。。。包括实例。

是不是231和232的混合版，支持嵌套的意思？

231 是判断是不是有效的括号字符串，这个是判断最长的有效的括号字符串的长度。

panheng

zltzlt 发表于 2019-9-1 21:52
231 是判断是不是有效的括号字符串，这个是判断最长的有效的括号字符串的长度。

没有啊，231就和这个题一模一样，232是判断是否有效（支持嵌套）

永恒的蓝色梦想

1. def func(string):
   
2.         try:eval(string.replace(')','),'))
   
3.         except:return False
   
4.         return True
   
5. def problem_234(string):
   
6.         length=len(string)
   
7.         return max((j-i for i in range(length)for j in range(i+2,length+1) if func(string[i:j])),default=0)

复制代码

感觉有点投机取巧

angtn

这个题目和上次找(){}[]感觉差不多，可以先用replace把有效的()都替换成一个单独的元素，然后用迭代来统计。希望我的理解没有错误。

1. def echo(sss):
   
2.     count = 0
   
3.     while '()' in sss:
   
4.         sss = sss.replace('()','i')
   
5.     for each in sss:
   
6.         if 'i' == each:
   
7.             count += 1
   
8.     return count
   
9. 
   
10. s = ")()())()()()()())"
    
11. print(echo(s)*2)
    

复制代码

lucky邪神

1. def fma(str1):
   
2.         str2=str1
   
3.         str2=str2.replace('()','A')
   
4.         list1=re.findall('A+',str2)
   
5.         list1.sort()
   
6.         length = 2 * len(list1[-1])
   
7.         return length

复制代码

和前面哪天的很像

jdzzj

1. def fun234(s):
   
2.     s=list(enumerate(s))
   
3.     res=[]  #用于储存左括号
   
4.     stack=[] #用于储存配对的括号
   
5.     for i in range(len(s)):
   
6.         if  s[i][1]=="(" :   #每遇到一个左括号都先储存起来
   
7.             res.append(s[i])
   
8.         else :
   
9.             if len(res)!=0:
   
10.                 stack.append(res.pop()[0])  #遇到右括号后弹出最近的一个左括号，并储存配对的括号的下标
    
11.                 stack.append(s[i][0])
    
12.     if len(stack)==0:
    
13.         return 0
    
14.     #根据返回的下标,找到最长的连续下标
    
15.     stack.sort()
    
16.     lenth=1 #用于计算连续组合的长度
    
17.     result=lenth #用于计算最长的组合
    
18. 
    
19.     for j in range(len(stack)-1):
    
20.         if stack[j+1]-stack[j]==1:
    
21.             lenth+=1
    
22.             if lenth>result:
    
23.                 result=lenth
    
24.         else:
    
25.             lenth=1
    
26. 
    
27.     return result

复制代码

新学

能想到的情况都测试通过了
添加了一些注释，希望各位鱼友能看懂。

1. import unittest
   
2. 
   
3. def q_234(string):
   
4.     length = len(string) #获取字符串长度
   
5.     if length == 0: #什么都没有可以返回0结束吧
   
6.         return 0
   
7.    
   
8.     count = 0 #累计连续的括号对
   
9.     counts = [0] #要是一个括号对都没有，就输出0吧
   
10.     i = 0 #字符串索引
    
11. 
    
12.     while i < length-1: #索引最大为倒数第二个
    
13.         if string[i]=='(' and string[i+1]==')': #出现括号对
    
14.             count += 2 #一对记2个
    
15.             i += 2 #跳过此括号对，下一对要是括号对会再执行这个条件的
    
16.         else: #不是括号对
    
17.             if count: #前面是括号对
    
18.                 counts.append(count) #把括号对长度记下来
    
19.                 count = 0 #再重置计数器
    
20.             i += 1 #这个不是括号对，下一个可能是了。
    
21.    
    
22.     counts.append(count) #如果结尾是括号对，就直接跳出来了，得把括号对长度记下来
    
23.    
    
24.     return max(counts) #把括号对的最大长度返回给主函数
    
25. 
    
26. class q_234TestCase(unittest.TestCase):
    
27.     """一个普通的函数测试"""
    
28.     def setUp(self):
    
29.         #测试用例字典
    
30.         self.strings = {'()()()':6, ')()()()':6, '(()()()':6,
    
31.             '()()()(':6, '()()())':6, '(()()())':6,
    
32.             ')()()())':6, '(()()()(':6, ')()()()(':6,
    
33.             '':0, '()(()())()()':4, '(()())()()())':6
    
34.         }
    
35.    
    
36.     def test_0(self):
    
37.         #遍历整个测试用例字典
    
38.         for string, answer in self.strings.items():
    
39.             q_answer = q_234(string) #看函数怎么弄得
    
40.             print(end='。 ') #检查运行了几个键值对
    
41.             self.assertEqual(q_answer, answer) #看结果是否与预期的一样
    
42.             
    
43. unittest.main()     #运行测试
    
44. 
    
45. # ~ #动手试一试吧
    
46. # ~ answer = q_234(input("请输入括号序列："))            
    
47. # ~ print("输出：", answer)

复制代码

kaohsing

复杂嵌套，不好搞。

Stubborn

1. def fun(x):
   
2.     num,st = 1,'()'
   
3.     while True:
   
4.         if st in x:
   
5.             num +=1
   
6.             st = num * '()'
   
7.         else:
   
8.             return (num-1) * 2

复制代码

tpt

我还不适合看这种问题

kaohsing

1. import re
   
2. NUM=2
   
3. s = ['()()()',             # ()()()       长度6
   
4.      ')()()()(',           # ()()()       长度6
   
5.      '(())(())(())())',    # (())(())(())() 长度  14
   
6.      '(())()(())())',      # (())()(())()  长度12
   
7.      # 有多个符合条件，比较一下，返回最大的
   
8.      '()((()())(())(()',  # (()())(())  >  ()   长度10>2   10
   
9.      '())())())',         # （）=（）=（）      长度2
   
10.      '()()())(()()',      # ()()() >  ()()     长度6
    
11.      '()())()((()()',     # ()()   >  ()  <  ()()   长度4
    
12.      '()())()()())'       # ()()  <(  )()()         长度6
    
13.      ]
    
14. rSub = re.compile(r'\(\)')
    
15. kSub = re.compile(r'(?:k?\(k+\)k?)+')
    
16. sSplit='\(|\)'
    
17. def fun(s):
    
18.     sSub = re.sub(rSub, "k", s)
    
19.     dtemp = re.findall(kSub,sSub)
    
20.     if  dtemp :
    
21.         return  getLen(dtemp)
    
22.     else:
    
23.         i=re.split(sSplit,sSub)
    
24.         return getLen(i)
    
25. def getLen(l):
    
26.     if len(l)>1:
    
27.         return  len(max(l))*NUM
    
28.     else:
    
29.         sDtemp = l[0]
    
30.         return sDtemp.count('k') + len(sDtemp)
    
31. def main():
    
32.     for ele in s:
    
33.         print(ele,'------------>',fun(ele))
    
34. 
    
35. if __name__ == '__main__':
    
36.     main()

复制代码