Re: [閒聊] 每日leetcode

看板Marginalman作者sustainer123 (溫水佳樹的兄長大人)時間11月前 (2025/01/12 16:52)推噓0(0推 0噓 3→)

※ 引述《dont (dont)》之銘言： : 2116. Check if a Parentheses String Can Be Valid : ## 思路 : 記錄還沒配對的括號個數 open : 把locked==0的也當作 `(` : 如果遇到配對不了的括號就回傳FALSE : 兩個方向各掃一遍 : ## Code : ```cpp : class Solution { : public: : bool canBeValid(string s, string locked) { : int n = s.size(); : if (n & 1) return false; : int open = 0; : for (int i=0; i<n; ++i) { : if (locked[i] == '0' || s[i] == '(') { : ++open; : } else if (open == 0) { : return false; : } else { : --open; : } : } : open = 0; : for (int i=n-1; i>=0; --i) { : if (locked[i] == '0' || s[i] == ')') { : ++open; : } else if (open == 0) { : return false; : } else { : --open; : } : } : return true; : } : }; : ``` 思路: 1.len(s) % 2 == 1一定不平衡 2.先前向遍歷，確認是否有足夠的(匹配) 3.最後反向遍歷，確認是否有足夠的)匹配( Python Code: class Solution: def canBeValid(self, s: str, locked: str) -> bool: left = 0 right = 0 n = len(s) if n % 2 == 1: return False for i in range(n): if s[i] == "(" or locked[i] == "0": left += 1 else: left -= 1 if left < 0: return False for i in range(n-1,-1,-1): if s[i] == ")" or locked[i] == "0": right += 1 else: right -= 1 if right < 0: return False return True AB卡我好久看Constraints才發現問題不難 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1736671973.A.F69.html

→

Rushia

01/12 16:54, 11月前 , 1^F

01/12 16:54, 1^F

→

sustainer123

01/12 16:55, 11月前 , 2^F

01/12 16:55, 2^F

→

Meaverzt

01/12 16:55, 11月前 , 3^F

01/12 16:55, 3^F