现在的位置: 首页 > 综合 > 正文

leetcdoe Next Permutation & longest Valid Parentheses

2019年04月02日 ⁄ 综合 ⁄ 共 998字 ⁄ 字号 评论关闭

Next Permutation  求解对应排列的下一个排列(按递增方式),通过找到最后一组满足num[i]>num[i+1]的对,然后将num[i]与后面的比自己大的最小值交换后,排序i+1及其以后的数(按递增)。如果完全是降序,就全部翻转

class Solution {

public:
    void nextPermutation(vector<int> &num) {
        int len=num.size();
        if(len<=1)return;
        int count=1;
        
        int i;
        for( i=len-1;i>0;i--){
           
            if(num[i]<=num[i-1])count++;
                else break;
        }
        int m=num[i];
        int mi=i;
        for(int k=len-1;k>i-1;k--)
         if(num[k]<m&&num[k]>num[i-1]){m=num[k];mi=k;}
        if(count<len){
            int tmp=num[mi];
            num[mi]=num[i-1];
            num[i-1]=tmp;
        }
        if(count>1)
        sort(num.begin()+i,num.end());
            
       

    }

};

longestValidParentheses: 求最长的合法匹配的括号长度,典型的动态规划,通过,从后往前,每次遇到i='('就查看对应j=i+1+dp[i+1]处是否是')',如果是,就把该段长度增加二,并后查看后面已配的段是否可以和现在相加,组成更长的合法段

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

抱歉!评论已关闭.