Re: [閒聊] 每日leetcode

[SecondRun (南爹摳打)]

1249. Minimum Remove to Make Valid Parentheses

給定input string

移除任意左括號或右括號使得所有左右括號可以配對

回傳任一個移除最少括號的合法字串

想法:
兩圈for
第一圈先把不合法的')'拿掉
第二圈再把不合法的'('拿掉

C# code:
public class Solution
{
    public string MinRemoveToMakeValid(string s)
    {
        var stack = new Stack<char>();
        int left = 0, right = 0;
        foreach (var c in s)
        {
            if (c == '(') left++;
            if (c == ')') right++;
            if (right > left)
            {
                right--;
                continue;
            }
            stack.Push(c);
        }

        var list = new List<char>();
        while (stack.Count > 0)
        {
            var c = stack.Pop();
            if (c == '(' && left > right)
            {
                left--;
                continue;
            }
            list.Add(c);
        }
        list.Reverse();
        return new string(list.ToArray());
    }
}


是說一開始後半部不是用list

用了str = c + str;

結果TLE

原來這東西這摸慢喔

--
(づ′・ω・）づ

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.160.52 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1712378954.A.5CE.html
※ 編輯: SecondRun (49.158.160.52 臺灣), 04/06/2024 12:52:11
※ 編輯: SecondRun (49.158.160.52 臺灣), 04/06/2024 12:55:35
推 wu10200512: string=vector<char>
→ wu10200512: 超出size就會申請新空間複製過去 超級慢
→ SecondRun: 那我猜加在後面最後用reverse應該可以過