LeetCode—32.最長有効括弧(Longest Valid Parentheses)——分析とコード(C++)

LeetCode—32.最大有効かっこ[Longest Valid Parentheses]——分析とコード[C+]

一、テーマ

二、分析及びコード

1. スタックレコード左かっこ下付き

(1)考え方

(2)コード

(3)結果

2. 動的計画

(1)考え方

(2)コード

(3)結果

三、その他

一、テーマ
「(」と「)」のみを含む文字列を指定し、有効なカッコを含む最長のサブ列の長さを見つけます.
例1:

  : "(()"
  : 2
  :           "()"

例2:

  : ")()())"
  : 4
  :           "()()"

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/longest-valid-parentheses著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
二、分析及びコード
1.スタック記録左かっこ下
(1)考え方
左かっこの下付きを記録するスタックで処理し、遍歴時に3つの状況に分けることができる:1)次の記号は左かっこ:現在の下付きをスタックに入れる;2)次の記号は右かっこで、スタックの中の要素は1つより多い:スタックの下付き記号を出て、この時遍歴した下付き記号はスタックの上の要素を減らして有効な長さで、最大の長さを更新する;3)次の記号は右かっこで、スタック内の要素は1つに等しい:スタックの下付き文字を出し、現在の下付き文字をスタックに入れる.
(2)コード

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> left;//             
        left.push(-1);//              
        int size = 0, maxSize = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(')//     
                left.push(i);
            else {
                if (left.size() != 1) {//         
                    left.pop();
                    size = i - left.top();
                    maxSize = max(maxSize, size);
                }
                else {//         
                    left.pop();
                    left.push(i);
                }
            }
        }
        maxSize = max(maxSize, size);
        return maxSize;
    }
};

(3)結果
実行時間:8 ms、すべてのC++コミットで80.63%のユーザーを破った.メモリ消費量:9.7 MB.
2.動的計画
(1)考え方
かっこ数+1の整数配列で、各位置の左側文字列の有効な長さを記録します.状態遷移方程式は2つのケースに分けられる:1)右かっこ左が左かっこ:

if (s[i - 1] == '(' && s[i] == ')')
 	dp[i + 1] = dp[i - 1] + 2;

2)右かっこ左は右かっこのままです.

if (s[i - 1] == ')' && s[i] == ')' && i - dp[i] - 1 >= 0 && s[i - dp[i] - 1] == '(')
	dp[i + 1] = dp[i - dp[i] - 1] + dp[i] + 2;

(2)コード

class Solution {
public:
    int longestValidParentheses(string s) {
        int ssize = s.size();
        int dp[ssize + 1];//              
        for (int i = 0; i <= ssize; i++)
            dp[i] = 0;
        for (int i = 1; i < ssize; i++) {//        
            if (s[i - 1] == '(' && s[i] == ')')//         
                dp[i + 1] = dp[i - 1] + 2;
            if (s[i - 1] == ')' && s[i] == ')' && i - dp[i] - 1 >= 0 && s[i - dp[i] - 1] == '(')//2）          
                dp[i + 1] = dp[i - dp[i] - 1] + dp[i] + 2;
        }
        int maxSize = 0;
        for (int i = 1; i <= ssize; i++)
            maxSize = max(maxSize, dp[i]);
        return maxSize;
    }
};

(3)結果
実行時間:8 ms、すべてのC++コミットで80.63%のユーザーを破った.メモリ消費量:9.2 MBで、すべてのC++コミットで95.96%のユーザーを破った.
三、その他
しばらくありません.