標(biāo)簽： C++ 算法 LeetCode 字符串
每日算法——leetcode系列
問(wèn)題 Longest Valid Parentheses
Difficulty: Hard
Given a string containing just the characters
'('and')', find the length of the longest valid (well-formed) parentheses substring.For
"(()", the longest valid parentheses substring is"()", which has length = 2.Another example is
")()())", where the longest valid parentheses substring is"()()", which has length = 4.
class Solution {
public:
int longestValidParentheses(string s) {
}
};
翻譯
最長(zhǎng)有效括號(hào)
難度系數(shù)：中等
給定一個(gè)僅僅包含'('或 ')'的字符串厢绝，找出其中最長(zhǎng)有效括號(hào)組成的子集的長(zhǎng)度豁跑。
字符串"(()"，它的最長(zhǎng)有效號(hào)符子集是"()"针肥，長(zhǎng)度為2。
另一個(gè)例子")()())"轰豆，它的最長(zhǎng)有效括號(hào)子集是"()()"赴叹，長(zhǎng)度是4。
思路
假定：起始匹配位置startIndex=-1;最大匹配長(zhǎng)度maxLen=0兵扬，當(dāng)前遍歷的索引為i:
遍歷字符串：
遍歷到的字符有兩種情況：
- 當(dāng)前字符為左括號(hào),壓棧, startIdnex = i;
- 當(dāng)前字符為右括號(hào)
- 如果棧為空,表示沒(méi)有匹配的左括號(hào),無(wú)任何操作
- 如果棧不空,出棧;
經(jīng)過(guò)上面的第二步操作后麻裳，棧有兩種情況：
- 棧空, 則i-startIndex為當(dāng)前找到的匹配長(zhǎng)度,檢查i-startIndex是否比maxLen
更大,如果更大就更新maxLen; - 棧不空,則當(dāng)前棧頂元素t是上次匹配的最后位置器钟。,檢查i-t
是否比ml更大,使得ml得以更新津坑。
注:因?yàn)槿霔５囊欢ㄊ亲罄ㄌ?hào),顯然沒(méi)有必要將它們本身入
棧,應(yīng)該入棧的是該字符在字符串中的索引。
代碼
class Solution {
public:
void nextPermutation(vector<int>& nums) {
size_t len = nums.size();
if (len == 1 || len == 0){
return;
}
int firstBreakNum = -1;
size_t firstBreakIndex = -1;
for (size_t i = len ;i > 1; --i){
if (nums[i-1] > nums[i-2]){
firstBreakNum = nums[i-2];
firstBreakIndex = i - 2;
break;
}
}
// 沒(méi)找到打破升序規(guī)律的傲霸，那就全部升序排列
if (firstBreakNum == -1){
reverse(nums.begin(), nums.end());
return;
}
for (size_t i = len; i > 1; --i){
if (nums[i-1] > firstBreakNum){
swap(nums[i-1], nums[firstBreakIndex]);
break;
}
}
auto iter = nums.begin();
for (size_t i = 0; i < firstBreakIndex + 1; ++i){
iter++;
}
reverse(iter, nums.end());
}
};
還可以繼續(xù)優(yōu)化
