博客

问题1、连续子数组的最大和

//给定数组{1,-2,3,10,-4,7,2,-5},则连续子数组的的最大和范围为{3,10,-4,7,2}
//解法一、直接写
int FindGreatestSumOfSubArray(int a[],int n){
    int sum=0;
    int temp=0;
    for(int i=0;i<n;i++){
        if(sum<=0){
            sum=a[i];
        }
        else{
            sum+=a[i];
        }
        if(temp<sum){
            temp=sum;
        }
    }
    return temp;
}
//解法二、动态规划
int FindGreatestSumOfSubArray(int a[], int n){

    int *f = new int[n+1];
    memset(f, 0, sizeof(f));
    int maxSum=0;
    for (int i = 0; i<n; i++){
        if (i == 0 || f[i - 1] <= 0){
            f[i] = a[i];
        } else{
            f[i] = f[i - 1] + a[i];
        }
        if (maxSum<f[i])
            maxSum = f[i];
    }
   return maxSum;
}

问题2、钢条切割问题。给定钢条长度，为了获取最优收益，求解最优切割方案

//长度：1  2  3  4  5  6  7  8  9  10  
//价格：1  5  8  9  10 17 17 20 24 30
int CutRod(int a[], int n){
    if (n==0)   return 0;
    int q=-1000;
    for (int i = 0; i<n; i++){
        q = max(q,a[i]+CutRod(a,n-i-1));
    } 
    return q;
}
//可以用带备忘录的方式计算，避免重复递归求解相同子问题
//带备忘的自顶向下
memset(memory_p,-1,11*sizeof(int));
emory_p[0]=0;
int cut_rod_memory(int prices[], int len){
    if(len==0)      return 0;
    if(memory_p[len]>=0)    return memory_p[len];//查询是否已经求出对应的部分最优解
    int sum=INT_MIN;
    for(int i=1;i<=len;i++)
    {
            sum=max(sum,prices[i-1]+cut_rod(prices,len-i));
    }
    memory_p[len]=sum;     //保存每一次的结果，大力提升速度（空间换时间）
    return sum;
}

问题3、求解两个字符串的最长公共子串

string LongestSubstring(string str1,string str2){
    int len1=str1.size();
    int len2=str2.size();
    //f[i][j]表示到str1[i]=str[j]之前的相同数目
    int **f=new int*[len1+1];
    for(int i=0;i<len2;i++)
            f[i]=new int[len2+1];
    memset(&(f[0][0]),0,siszeof(int)*(len1+1)*(len2+1));
    int index=1;
    int sum=0;
    for(int i=0;i<len1;i++){
        for(int j=0;j<len2;j++)
        {
            if(str1[i]==str2[j])
                f[i+1][j+1]=f[i][j]+1;
            else 
                f[i+1][j+1]=0;          
            if(sum<f[i+1][j+1]){
                    index=i+1;
                    sum=f[i+1][j+1];
            }
        }
    }
    int last=index-1;
    return str1.substr(last-sum-1,sum);
}

问题4、求两个字符串的最长公共子序列

void PrintLCS(char **b,string s,int len1,int len2){
    if(len1==0||len2==0)    return ;
    if(b[len1][len2]=='Y'){
        PrintLCS(b,s,len1-1,len2-1);
        cout<<s[len1-1];
    }else if(b[len1][len2]=='|')
    {
        PrintLCS(b,s,len1-1,len2);
    }else
    {
        PrintLCS(b,s,len1,len2-1);
    }
}
void LCS(string s1,string s2){
    int n1=s1.size();
    int n2=s2.size();
    int **c=new int*[n1+1];//保存LCS长度
    char **p=new char*[n1+1];   //保存路径
    for(int i=0;i<n1+1;i++){
            c[i]=new int[n2+1];
    }
    for(int i=0;i<n1+1;i++){
            p[i]=new char[n2+1];
    }
    memset(&(c[0][0]),0,sizeof(int)*(n1+1)*(n2+1));//清零操作

    for(int i=1;i<n1+1;i++){

        for(int j=1;j<n2+1;j++){
            if(s1[i-1]==s2[j-1]){
                c[i][j]=c[i-1][j-1]+1;
                p[i][j]='Y';
            }
            //此时的LCS即为前期已经确定下来的LCS，比较取得最大的
            else if(c[i-1][j]>=c[i][j-1])
            {
                c[i][j]=c[i-1][j];
                p[i][j]='|';
            }else
            {
                c[i][j]=c[i][j-1];
                p[i][j]='-';
            }
        }
    }
    PrintLCS(p,s1,n1,n2);
}

问题3、最长回文字符串

string LongestPalindromestring(string str){

        int len=str.size();
        bool f[100][100];
        memset(&(f[0][0]),false,sizeof(f));
        int start=0;
        int maxLen=1;
        for(int i=0;i<len;i++){//i表示终点
            f[i][i]=true;
            for(int j=0;j<i;j++){
                if(j+1==i&&str[i]==str[j]){
                        f[j][i]=true;
                }else if(j+1<i&&str[i]==str[j]){
                        f[j][i]=f[j+1][i-1];
                }else{
                    f[j][i]=false;
                }

                if(f[j][i]&&maxLen<i-j+1){
                    maxLen=i-j+1;
                    start=j;
                }
            }
        }
        return str.substr(start,maxLen);
}

特别注意：memset和fill_n一般不能对申请的堆空间进行清零。