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

zltzlt

今天的题目：

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

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

示例 1:

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

示例 2:

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

我的解法：

def longest_valid_par(string):
    result = []
    for i in range(len(string) - 1):
        a = 2
        while True:
            if string[i:i + a] == "()" * (a // 2):
                try:
                    string[i + a - 1]
                except Exception:
                    result.append(a - 2)
                    break
                a += 2
            else:
                result.append(a - 2)
                break
    return max(result, default=0)

大佬解法：

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = [-1]
        res = 0
        for i, x in enumerate(s):
            if x == "(":
                stack.append(i)
            else:
                stack.pop()
                if stack:
                    res = max(res, i - stack[-1])
                else:
                    stack.append(i)
                    
        return res

panheng

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

import re

def answer(strs):
    temp = re.search(r'(\(\))+', strs)
    start, end = temp.span()
    result = end - start
    return result

print(answer("(()"))
print(answer(")()())"))

zltzlt

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

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

zltzlt

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

用正则也不错

archlzy

import re
import copy

test_string = "()()((()))(()())())()((())))(()()()((()(()()())()("


def fun(string):
    # test_string = copy.copy(string)    
    while re.findall(r'\(1*\)',string) != []:
        old_str_list = set(re.findall(r'\(1*\)',string))
        for i in old_str_list:
            string = string.replace(i,'1'*len(i))
    temp = sorted(re.findall(r'1+',string))[-1]
    # start, end = re.search(temp, string).span()
    # print(test_string[start:end])
    return len(temp)
    
print(fun(test_string))

lucky邪神

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

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

zltzlt

怎么我就没想到用正则呢

panheng

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

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

import re

def answer(strs):
    result = re.findall(r'(?:\(\))+', strs)
    result.sort()
    return len(result[-1])


print(answer("(()"))
print(answer(")()())"))
print(answer("()()((()))(()()()()()())())()((())))(()()()((()(()())()("))

FC的注册很坑

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

def func231(li):
    stack=[]
    len_stack=0
    for i in li:
        if (i=='(' and len(stack)%2==0) or (i==')' and len(stack)%2==1):
            stack.append(i)
            if len(stack)>len_stack:
                len_stack=len(stack)
        else:
            stack=[]
            if (i=='(' and len(stack)%2==0) or (i==')' and len(stack)%2==1):
                stack.append(i)
                if len(stack)>len_stack:
                    len_stack=len(stack)
    if len_stack==1:
        return 0
    else:
        return len_stack

_2_

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

elif考虑一下？

zlj19931010

是兄弟就来砍我！

s = input("输入字符串:")

l = len(s)
i = 0
maxlen = 0
k = 0
# 是否匹配左边
left = True
while i < l:
    if left:
        if s[i] == '(':
            left = False
        else:
            left = True
            # 匹配结束
            maxlen = k if k>maxlen else maxlen
            k = 0
        i+=1
        continue

    if not left:
        if s[i] == ')':
            left = True
            k+=2
            i+=1
        else:
            left = True
            # 匹配结束
            maxlen = k if k>maxlen else maxlen
            k = 0

maxlen = k if k>maxlen else maxlen
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

def answer(s):
    t, t['('], t[')'], t['max'] = {}, 0, 0, 0
    for i in s:
        t[i]+=1
        if t[')'] > t['(']: 
            t['max']=t['(']*2 if t['max'] < t['(']*2 else t['max']
            t['(']=t[')']=0
    return t[')']*2 if t['max'] < t[')']*2 else t['max']
    
print(answer("()()((()))(()())())()((())))(()()()((()(()()())()("))
print(answer("(()"))
print(answer(")()())"))
print(answer(")(())))())"))
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
是兄弟就来砍我！

厉害，👍👍👍