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

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)

复制代码

大佬解法：

1. class Solution(object):
   
2.     def longestValidParentheses(self, s):
   
3.         """
   
4.         :type s: str
   
5.         :rtype: int
   
6.         """
   
7.         stack = [-1]
   
8.         res = 0
   
9.         for i, x in enumerate(s):
   
10.             if x == "(":
    
11.                 stack.append(i)
    
12.             else:
    
13.                 stack.pop()
    
14.                 if stack:
    
15.                     res = max(res, i - stack[-1])
    
16.                 else:
    
17.                     stack.append(i)
    
18.                     
    
19.         return res

复制代码

panheng

字符串当然用正则啦~
斑竹，最近这些题都没有加入《每日一题：淘专辑》呢

1. import re
   
2. 
   
3. def answer(strs):
   
4.     temp = re.search(r'(\(\))+', strs)
   
5.     start, end = temp.span()
   
6.     result = end - start
   
7.     return result
   
8. 
   
9. print(answer("(()"))
   
10. print(answer(")()())"))

复制代码

zltzlt

panheng 发表于 2019-8-29 22:06
字符串当然用正则啦~
斑竹，最近这些题都没有加入《每日一题：淘专辑》呢

我不是维护员，@新手·ing 又不在线，没法加

zltzlt

panheng 发表于 2019-8-29 22:06
字符串当然用正则啦~
斑竹，最近这些题都没有加入《每日一题：淘专辑》呢

用正则也不错

archlzy

1. import re
   
2. import copy
   
3. 
   
4. test_string = "()()((()))(()())())()((())))(()()()((()(()()())()("
   
5. 
   
6. 
   
7. def fun(string):
   
8.     # test_string = copy.copy(string)   
   
9.     while re.findall(r'\(1*\)',string) != []:
   
10.         old_str_list = set(re.findall(r'\(1*\)',string))
    
11.         for i in old_str_list:
    
12.             string = string.replace(i,'1'*len(i))
    
13.     temp = sorted(re.findall(r'1+',string))[-1]
    
14.     # start, end = re.search(temp, string).span()
    
15.     # print(test_string[start:end])
    
16.     return len(temp)
    
17.    
    
18. print(fun(test_string))

复制代码

lucky邪神

折腾一上午，研究了半天findall，怎么都搞不出来怎么统计‘（）’，参照楼上思路才突然开通了

1. #第一步找出所有的（）
   
2. #将所有的（）替换成*
   
3. #将字符串中的*+分别找出来，放入一个列表
   
4. #统计*最长的项，并输出
   
5. def cal(str1):
   
6.     #list1=re.findall("\(\)",str1)  #搜寻（）
   
7.     str2=str1
   
8.     while re.findall("\(\)",str1) !=[]:   #判断是否有（），如果有就继续
   
9.         str1=str1.replace('()','*')
   
10.     list2=re.findall('\*+',str1)
    
11.     list2.sort()
    
12.     #return len(list2[-1])
    
13.     print("{}的最长有效长度为：{}".format(str2,len(list2[-1])))
    
14.     print('解释：'+"()"*len(list2[-1]))

复制代码

zltzlt

怎么我就没想到用正则呢

panheng

panheng 发表于 2019-8-29 22:06
字符串当然用正则啦~
斑竹，最近这些题都没有加入《每日一题：淘专辑》呢

昨天的答案没有考虑到最长字符串出现在后边，只返回首个子字符串。
修改了下，使用findall非捕获组排序求解。

1. import re
   
2. 
   
3. def answer(strs):
   
4.     result = re.findall(r'(?:\(\))+', strs)
   
5.     result.sort()
   
6.     return len(result[-1])
   
7. 
   
8. 
   
9. print(answer("(()"))
   
10. print(answer(")()())"))
    
11. print(answer("()()((()))(()()()()()())())()((())))(()()()((()(()())()("))

复制代码

FC的注册很坑

中间的if语句是重复的代码，有鱼油有好方法来缩减下代码量吗？

1. def func231(li):
   
2.     stack=[]
   
3.     len_stack=0
   
4.     for i in li:
   
5.         if (i=='(' and len(stack)%2==0) or (i==')' and len(stack)%2==1):
   
6.             stack.append(i)
   
7.             if len(stack)>len_stack:
   
8.                 len_stack=len(stack)
   
9.         else:
   
10.             stack=[]
    
11.             if (i=='(' and len(stack)%2==0) or (i==')' and len(stack)%2==1):
    
12.                 stack.append(i)
    
13.                 if len(stack)>len_stack:
    
14.                     len_stack=len(stack)
    
15.     if len_stack==1:
    
16.         return 0
    
17.     else:
    
18.         return len_stack

复制代码

_2_

FC的注册很坑 发表于 2019-8-30 10:14
中间的if语句是重复的代码，有鱼油有好方法来缩减下代码量吗？

elif考虑一下？

zlj19931010

是兄弟就来砍我！

1. s = input("输入字符串:")
   
2. 
   
3. l = len(s)
   
4. i = 0
   
5. maxlen = 0
   
6. k = 0
   
7. # 是否匹配左边
   
8. left = True
   
9. while i < l:
   
10.     if left:
    
11.         if s[i] == '(':
    
12.             left = False
    
13.         else:
    
14.             left = True
    
15.             # 匹配结束
    
16.             maxlen = k if k>maxlen else maxlen
    
17.             k = 0
    
18.         i+=1
    
19.         continue
    
20. 
    
21.     if not left:
    
22.         if s[i] == ')':
    
23.             left = True
    
24.             k+=2
    
25.             i+=1
    
26.         else:
    
27.             left = True
    
28.             # 匹配结束
    
29.             maxlen = k if k>maxlen else maxlen
    
30.             k = 0
    
31. 
    
32. maxlen = k if k>maxlen else maxlen
    
33. print(maxlen)
    

复制代码

panheng

zltzlt 发表于 2019-8-30 07:44
怎么我就没想到用正则呢

为啥给错误答案加分呀。。
感觉被挂墙了

zltzlt

panheng 发表于 2019-8-30 11:07
为啥给错误答案加分呀。。
感觉被挂墙了

哦，加错了，不好意思

archlzy

panheng 发表于 2019-8-30 08:37
昨天的答案没有考虑到最长字符串出现在后边，只返回首个子字符串。
修改了下，使用findall非捕获组排序 ...

你这个 没有 考虑 这种情况吧 (()())，括号里面套着括号。
不过我也不太懂上述的括号叫做 有效的括号吗

cct

1. def answer(s):
   
2.     t, t['('], t[')'], t['max'] = {}, 0, 0, 0
   
3.     for i in s:
   
4.         t[i]+=1
   
5.         if t[')'] > t['(']:
   
6.             t['max']=t['(']*2 if t['max'] < t['(']*2 else t['max']
   
7.             t['(']=t[')']=0
   
8.     return t[')']*2 if t['max'] < t[')']*2 else t['max']
   
9.    
   
10. print(answer("()()((()))(()())())()((())))(()()()((()(()()())()("))
    
11. print(answer("(()"))
    
12. print(answer(")()())"))
    
13. print(answer(")(())))())"))
    
14. print(answer(")(())())()())"))

复制代码

不用正则也能做吧。

panheng

archlzy 发表于 2019-8-30 11:22
你这个 没有 考虑 这种情况吧 (()())，括号里面套着括号。
不过我也不太懂上述的括号叫做 有效的括号吗

您说的情况应该有考虑到
r'(?:\(\))+'

引号内第一对括号 (?: ……)作用是将括号里边的内容作为一个整体匹配，同数学运算小括号。？:是将此分组设置为非捕获组，否则会返回findall会返回'（）'子组

\(\) 是使用“\”转移匹配一对括号

最后的+紧接第一对括号后，表示括号内容重复次数。

FC的注册很坑

_2_ 发表于 2019-8-30 10:22
elif考虑一下？

代码怎么写呢

archlzy

panheng 发表于 2019-8-30 11:47
您说的情况应该有考虑到
r'(?:\(\))+'

但是你这个 能匹配到 “(())” 这个吗？
我理解的是 你这个 表达式 匹配的是 ()()... 成组出现的  嵌套的就不能 捕获了
我运行了下貌似是这个样子的

zltzlt

archlzy 发表于 2019-8-30 12:24
但是你这个 能匹配到 “(())” 这个吗？
我理解的是 你这个 表达式 匹配的是 ()()... 成组出现的  嵌套 ...

'(())' 不算一个包含有效括号的字符串哦。

tomywow

zlj19931010 发表于 2019-8-30 10:49
是兄弟就来砍我！

厉害，&#128077;&#128077;&#128077;