本篇內(nèi)容介紹了“C++最長有效括號(hào)問題怎么解決”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！
棗強(qiáng)網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián),棗強(qiáng)網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為棗強(qiáng)數(shù)千家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站制作要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的棗強(qiáng)做網(wǎng)站的公司定做！
Given a string containing just the characters "(" and ")", find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
這道求最長有效括號(hào)比之前那道 Valid Parentheses 難度要大一些，這里還是借助棧來求解，需要定義個(gè) start 變量來記錄合法括號(hào)串的起始位置，遍歷字符串，如果遇到左括號(hào)，則將當(dāng)前下標(biāo)壓入棧，如果遇到右括號(hào)，如果當(dāng)前棧為空，則將下一個(gè)坐標(biāo)位置記錄到 start，如果棧不為空，則將棧頂元素取出，此時(shí)若棧為空，則更新結(jié)果和 i - start + 1 中的較大值，否則更新結(jié)果和 i - st.top() 中的較大值，參見代碼如下：
解法一：
重慶分公司
重慶分公司
class Solution {
public:
int longestValidParentheses(string s) {
int res = 0, start = 0, n = s.size();
stack st;
for (int i = 0; i < n; ++i) {
if (s[i] == "(") st.push(i);
else if (s[i] == ")") {
if (st.empty()) start = i + 1;
else {
st.pop();
res = st.empty() ? max(res, i - start + 1) : max(res, i - st.top());
}
}
}
return res;
}
}; 還有一種利用動(dòng)態(tài)規(guī)劃 Dynamic Programming 的解法。這里使用一個(gè)一維 dp 數(shù)組，其中 dp[i] 表示以 s[i-1] 結(jié)尾的最長有效括號(hào)長度（注意這里沒有對(duì)應(yīng) s[i]，是為了避免取 dp[i-1] 時(shí)越界從而讓 dp 數(shù)組的長度加了1），s[i-1] 此時(shí)必須是有效括號(hào)的一部分，那么只要 dp[i] 為正數(shù)的話，說明 s[i-1] 一定是右括號(hào)，因?yàn)橛行Юㄌ?hào)必須是閉合的。當(dāng)括號(hào)有重合時(shí)，比如 "(())"，會(huì)出現(xiàn)多個(gè)右括號(hào)相連，此時(shí)更新最外邊的右括號(hào)的 dp[i] 時(shí)是需要前一個(gè)右括號(hào)的值 dp[i-1]，因?yàn)榧偃?dp[i-1] 為正數(shù)，說明此位置往前 dp[i-1] 個(gè)字符組成的子串都是合法的子串，需要再看前面一個(gè)位置，假如是左括號(hào)，說明在 dp[i-1] 的基礎(chǔ)上又增加了一個(gè)合法的括號(hào)，所以長度加上2。但此時(shí)還可能出現(xiàn)的情況是，前面的左括號(hào)前面還有合法括號(hào)，比如 "()(())"，此時(shí)更新最后面的右括號(hào)的時(shí)候，知道第二個(gè)右括號(hào)的 dp 值是2，那么最后一個(gè)右括號(hào)的 dp 值不僅是第二個(gè)括號(hào)的 dp 值再加2，還可以連到第一個(gè)右括號(hào)的 dp 值，整個(gè)最長的有效括號(hào)長度是6。所以在更新當(dāng)前右括號(hào)的 dp 值時(shí)，首先要計(jì)算出第一個(gè)右括號(hào)的位置，通過 i-3-dp[i-1] 來獲得，由于這里定義的 dp[i] 對(duì)應(yīng)的是字符 s[i-1]，所以需要再加1，變成 j = i-2-dp[i-1]，這樣若當(dāng)前字符 s[i-1] 是左括號(hào)，或者j小于0（說明沒有對(duì)應(yīng)的左括號(hào)），或者 s[j] 是右括號(hào)，此時(shí)將 dp[i] 重置為0，否則就用 dp[i-1] + 2 + dp[j] 來更新 dp[i]。這里由于進(jìn)行了 padding，可能對(duì)應(yīng)關(guān)系會(huì)比較暈，大家可以自行帶個(gè)例子一步一步執(zhí)行，應(yīng)該是不難理解的，參見代碼如下：
解法二：
class Solution {
public:
int longestValidParentheses(string s) {
int res = 0, n = s.size();
vector dp(n + 1);
for (int i = 1; i <= n; ++i) {
int j = i - 2 - dp[i - 1];
if (s[i - 1] == "(" || j < 0 || s[j] == ")") {
dp[i] = 0;
} else {
dp[i] = dp[i - 1] + 2 + dp[j];
res = max(res, dp[i]);
}
}
return res;
}
}; 此題還有一種不用額外空間的解法，使用了兩個(gè)變量 left 和 right，分別用來記錄到當(dāng)前位置時(shí)左括號(hào)和右括號(hào)的出現(xiàn)次數(shù)，當(dāng)遇到左括號(hào)時(shí)，left 自增1，右括號(hào)時(shí) right 自增1。對(duì)于最長有效的括號(hào)的子串，一定是左括號(hào)等于右括號(hào)的情況，此時(shí)就可以更新結(jié)果 res 了，一旦右括號(hào)數(shù)量超過左括號(hào)數(shù)量了，說明當(dāng)前位置不能組成合法括號(hào)子串，left 和 right 重置為0。但是對(duì)于這種情況 "(()" 時(shí)，在遍歷結(jié)束時(shí)左右子括號(hào)數(shù)都不相等，此時(shí)沒法更新結(jié)果 res，但其實(shí)正確答案是2，怎么處理這種情況呢？答案是再反向遍歷一遍，采取類似的機(jī)制，稍有不同的是此時(shí)若 left 大于 right 了，則重置0，這樣就可以 cover 所有的情況了，參見代碼如下：
解法三：
class Solution {
public:
int longestValidParentheses(string s) {
int res = 0, left = 0, right = 0, n = s.size();
for (int i = 0; i < n; ++i) {
(s[i] == "(") ? ++left : ++right;
if (left == right) res = max(res, 2 * right);
else if (right > left) left = right = 0;
}
left = right = 0;
for (int i = n - 1; i >= 0; --i) {
(s[i] == "(") ? ++left : ++right;
if (left == right) res = max(res, 2 * left);
else if (left > right) left = right = 0;
}
return res;
}
};“C++最長有效括號(hào)問題怎么解決”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！
