记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步目录9/28 1614. 括号的最大嵌套深度9/29 2267. 检查是否有合法括号字符串路径9/30 1111. 有效括号的嵌套深度10/1 20. 有效的括号10/2 22. 括号生成10/3 32. 最长有效括号10/4 678. 有效的括号字符串9/28 1614. 括号的最大嵌套深度遇到一个左括号嵌套深度1 一个右括号深度-1记录最大嵌套深度defmaxDepth(s): :type s: str :rtype: int ans0cur0forcins:ifc(:cur1ansmax(ans,cur)elifc):cur-1returnans9/29 2267. 检查是否有合法括号字符串路径只能往下或往右从左上走到右下沿途格子拼成的括号串必须合法。合法括号走的过程中右括号不能比左括号多走到终点时两者要一样多。路径长度固定是 mn-1长度是奇数、起点是右括号、或终点是左括号直接不可能。记「走到 (i,j) 时左括号比右括号多几个」多出来的变成负数就失败剩下格子就算全是右括号也填不完也失败。用记忆化避免重复搜索同一格子同一差值。defhasValidPath(grid): :type grid: List[List[str]] :rtype: bool m,nlen(grid),len(grid[0])if(mn)%20orgrid[0][0])orgrid[m-1][n-1](:returnFalsevis[[[False]*(mn)for_inrange(n)]for_inrange(m)]defdfs(i,j,k):k1ifgrid[i][j](else-1ifk0orkmn-i-j-2:returnFalseifim-1andjn-1:returnTrueifvis[i][j][k]:returnFalsevis[i][j][k]Trueifi1manddfs(i1,j,k):returnTrueifj1nanddfs(i,j1,k):returnTruereturnFalsereturndfs(0,0,0)9/30 1111. 有效括号的嵌套深度要把有效括号串拆成两组让两组里更深的那一组尽量浅。嵌套深度就是当前还没配对的左括号有多少层。一层分给 A、下一层分给 B交替分两组深度大约各一半。遇到左括号按当前层数的奇偶分到一组再进入下一层遇到右括号先回到上一层按那一层的奇偶分到同一组保证一对括号分在一起。defmaxDepthAfterSplit(seq): :type seq: str :rtype: List[int] ans[0]*len(seq)x0fori,cinenumerate(seq):ifc(:ans[i]x1x1else:x-1ans[i]x1returnans10/1 20. 有效的括号用栈匹配括号遇到左括号压栈遇到右括号必须能和栈顶的左括号配成一对否则不合法。扫完后栈必须是空的说明每个左括号都有对应的右括号。defisValid(s): :type s: str :rtype: bool pair{):(,]:[,}:{}st[]forcins:ifcinpair:ifnotstorst[-1]!pair[c]:returnFalsest.pop()else:st.append(c)returnnotst10/2 22. 括号生成依次填入n个括号从一个开始 s记录当前i个括号所有可能性在每个合法的括号序列中任何位置可以插入一个完整的括号对defgenerateParenthesis(n): :type n: int :rtype: List[str] sset([])foriinrange(n):new_sset()forexpins:forjinrange(len(exp)):new_s.add(exp[:j]()exp[j:])new_s.add(exp())snew_sreturnlist(s)10/3 32. 最长有效括号栈里记下还没配对的括号下标先放一个 -1 当作「上一段无效位置」。遇到左括号把下标压栈。遇到右括号弹出栈顶来配对栈空了说明这个右括号多出来了它成为新的无效位置栈里还有东西当前下标减去栈顶就是这段有效括号的长度取最大值。deflongestValidParentheses(s): :type s: str :rtype: int st[-1]ans0fori,cinenumerate(s):ifc(:st.append(i)else:st.pop()ifnotst:st.append(i)else:ansmax(ans,i-st[-1])returnans10/4 678. 有效的括号字符串星号可以当左括号、右括号或空字符。用一个区间记下「当前还没配对的左括号可能有多少个」遇 ‘(’ 上下界都加 1遇 ‘)’ 都减 1遇 ‘*’ 下界减 1、上界加 1。下界小于 0 就当成 0相当于少把星号当成左括号。上界小于 0 说明右括号太多不可能合法。扫完后下界必须是 0才能配平。defcheckValidString(s): :type s: str :rtype: bool lohi0forcins:ifc(:lo1hi1elifc):lo-1hi-1else:lo-1hi1ifhi0:returnFalseiflo0:lo0returnlo0 
长河君 · 2026/10/9 2:44:23 · 阅读 1.2k LeetCode 每日一题 2026/9/28-2026/10/4
记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步目录9/28 1614. 括号的最大嵌套深度9/29 2267. 检查是否有合法括号字符串路径9/30 1111. 有效括号的嵌套深度10/1 20. 有效的括号10/2 22. 括号生成10/3 32. 最长有效括号10/4 678. 有效的括号字符串9/28 1614. 括号的最大嵌套深度遇到一个左括号嵌套深度1 一个右括号深度-1记录最大嵌套深度defmaxDepth(s): :type s: str :rtype: int ans0cur0forcins:ifc(:cur1ansmax(ans,cur)elifc):cur-1returnans9/29 2267. 检查是否有合法括号字符串路径只能往下或往右从左上走到右下沿途格子拼成的括号串必须合法。合法括号走的过程中右括号不能比左括号多走到终点时两者要一样多。路径长度固定是 mn-1长度是奇数、起点是右括号、或终点是左括号直接不可能。记「走到 (i,j) 时左括号比右括号多几个」多出来的变成负数就失败剩下格子就算全是右括号也填不完也失败。用记忆化避免重复搜索同一格子同一差值。defhasValidPath(grid): :type grid: List[List[str]] :rtype: bool m,nlen(grid),len(grid[0])if(mn)%20orgrid[0][0])orgrid[m-1][n-1](:returnFalsevis[[[False]*(mn)for_inrange(n)]for_inrange(m)]defdfs(i,j,k):k1ifgrid[i][j](else-1ifk0orkmn-i-j-2:returnFalseifim-1andjn-1:returnTrueifvis[i][j][k]:returnFalsevis[i][j][k]Trueifi1manddfs(i1,j,k):returnTrueifj1nanddfs(i,j1,k):returnTruereturnFalsereturndfs(0,0,0)9/30 1111. 有效括号的嵌套深度要把有效括号串拆成两组让两组里更深的那一组尽量浅。嵌套深度就是当前还没配对的左括号有多少层。一层分给 A、下一层分给 B交替分两组深度大约各一半。遇到左括号按当前层数的奇偶分到一组再进入下一层遇到右括号先回到上一层按那一层的奇偶分到同一组保证一对括号分在一起。defmaxDepthAfterSplit(seq): :type seq: str :rtype: List[int] ans[0]*len(seq)x0fori,cinenumerate(seq):ifc(:ans[i]x1x1else:x-1ans[i]x1returnans10/1 20. 有效的括号用栈匹配括号遇到左括号压栈遇到右括号必须能和栈顶的左括号配成一对否则不合法。扫完后栈必须是空的说明每个左括号都有对应的右括号。defisValid(s): :type s: str :rtype: bool pair{):(,]:[,}:{}st[]forcins:ifcinpair:ifnotstorst[-1]!pair[c]:returnFalsest.pop()else:st.append(c)returnnotst10/2 22. 括号生成依次填入n个括号从一个开始 s记录当前i个括号所有可能性在每个合法的括号序列中任何位置可以插入一个完整的括号对defgenerateParenthesis(n): :type n: int :rtype: List[str] sset([])foriinrange(n):new_sset()forexpins:forjinrange(len(exp)):new_s.add(exp[:j]()exp[j:])new_s.add(exp())snew_sreturnlist(s)10/3 32. 最长有效括号栈里记下还没配对的括号下标先放一个 -1 当作「上一段无效位置」。遇到左括号把下标压栈。遇到右括号弹出栈顶来配对栈空了说明这个右括号多出来了它成为新的无效位置栈里还有东西当前下标减去栈顶就是这段有效括号的长度取最大值。deflongestValidParentheses(s): :type s: str :rtype: int st[-1]ans0fori,cinenumerate(s):ifc(:st.append(i)else:st.pop()ifnotst:st.append(i)else:ansmax(ans,i-st[-1])returnans10/4 678. 有效的括号字符串星号可以当左括号、右括号或空字符。用一个区间记下「当前还没配对的左括号可能有多少个」遇 ‘(’ 上下界都加 1遇 ‘)’ 都减 1遇 ‘*’ 下界减 1、上界加 1。下界小于 0 就当成 0相当于少把星号当成左括号。上界小于 0 说明右括号太多不可能合法。扫完后下界必须是 0才能配平。defcheckValidString(s): :type s: str :rtype: bool lohi0forcins:ifc(:lo1hi1elifc):lo-1hi-1else:lo-1hi1ifhi0:returnFalseiflo0:lo0returnlo0