HW2016_字符串_STL_DP

时间：2024-04-10 12:06:58

一、在字符串str1中删除那些在str2中出现的字符。

str2可能会有重复字符，直接遍历会导致效率低下，故先借助STL的set容器对str1查重；

然后，遍历str1和str2，对str1进行查重。

#include <iostream>

#include <string>

#include <set>

using namespace std;

void deleteChar(char* strRet, const string& str1,int len1, const string& str2,int len2)

{

    if(len1 < )                   //异常检测

    {

        return;

    }

    bool findIt = false;      //查找标记位

    set<char>mySet;

    int i = ,j = ,k = ;

    for(i = ; i < len2; ++i)  //str2去重复字符

    {

         mySet.insert(str2[i]);

    }

   for(j = ; j < len1; j++)

    {

       for(set<char>::iterator it = mySet.begin(); it != mySet.end(); ++it)

       {

           if(str1[j] == *it && findIt == false)

           {

               findIt = true;

               break;

           }

       }//end for

       if(!findIt)

       {

           strRet[k++] = str1[j];

       }

       findIt = false;    //标记位置位

    }//end for

   strRet[k] = '\0'; //c风格字符串结束标志

}

int main()

{

    string str1,str2;

    while(cin >> str1 >> str2)

    {

        int len1 = str1.size();

        int len2 = str2.size();

        char* strRet = new char[len1 + ];    //申请空间存放查重后的字符串

        deleteChar(strRet,str1,len1,str2,len2);

        cout << strRet << endl;

        delete strRet;              //防止内存泄漏

        return ;

    }

}

二、

编程题-成绩排名

题目总共包含如下两种格式的字符串命令：

1 LOD GRADE命令，其格式为：

LOD GRADE:NAME=XiaoMing,MATH=80,LANG=90;

（1）此命令用于导入学生成绩

（2）NAME字段表示学生姓名

（3）MATH字段表示学生数学成绩

（4）LANG字段表示学生语文成绩

（5）MATH字段和LANG字段顺序不一定是MATH在前，LANG在后

（6）相同的分数，名词相同，后面的名次孔雀：例如100,99,99,99,98,98，名次1,2,2,2,5,5

（7）此命令会连续执行，直到遇到第一个LST GRADE

2 LST GRADE命令，其格式为：

LST GRADE:NAME=XiaoHong;

（1）此命令用于查询学生成绩

（2）NAME字段表示学生姓名

（3）查询结果格式：姓名 数学 语文 总分 数学排名 语文排名 总排名

（4）每组用例，此命令仅执行一次

样例输入

LOD GRADE:NAME=XiaoMing,MATH=80,LANG=90;

LOD GRADE:NAME=XiaoHong,LANG=60,MATH=100;

LOD GRADE:NAME=XiaoMei,MATH=70,LANG=90;

LST GRADE:NAME=XiaoHong;

样例输出 XiaoHong 100 60 160 1 3 2

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <cstdlib>

using namespace std;

const string LOD = "LOD GRADE";

const string LST = "LST GRADE";

int myCout = ;

class student{

public:

    student(string str)

    {

        OPE = "";

        unsigned int posOPE = str.find_first_of(':');

        if( posOPE < str.size())

            OPE = str.substr(, posOPE);

        unsigned int posNAME1 = str.find_first_of('=');

        unsigned int posNAME2 = str.find_first_of(',');

        NAME = str.substr(posNAME1 + , posNAME2 - posNAME1 - );

        unsigned int posEnd = str.find_last_of(';');

        unsigned int posMATH = str.find_last_of('H');

        unsigned int posLANG = str.find_last_of('G');

        unsigned int posLastCommer = str.find_last_of(',');

        if(posEnd - posMATH > )

        {

            MATH = atoi(str.substr(posMATH + , posLastCommer - posMATH - ).c_str());

            LANG = atoi(str.substr(posLastCommer + , posEnd - posLastCommer -).c_str());

        }

        else

        {

            MATH = atoi(str.substr(posMATH + , posEnd - posMATH - ).c_str());

            LANG = atoi(str.substr(posLANG + , posLastCommer - posLANG - ).c_str());

        }

        totalScore = MATH + LANG;

        mathMarking = ;

        langMarking = ;

        totalMarking = ;

        count = ;

    }

    ~student(){}

    string OPE;

    string NAME;

    int MATH;

    int LANG;

    int totalScore;

    int mathMarking;

    int langMarking;

    int totalMarking;

    int count;

};

bool mathCompare(student*& stu1, student*& stu2)

{

    return (stu1->MATH > stu2->MATH) ||

           (stu1->MATH == stu2->MATH && stu1->count < stu2->count);         //desc  ; 成绩相等，按照出现的顺序排序

}

bool langCompare(student*& stu1, student*& stu2)

{

    return (stu1->LANG > stu2->LANG) ||

           (stu1->LANG == stu2->LANG && stu1->count < stu2->count);         //desc

}

bool totalCompare(student*& stu1, student*& stu2)

{

    return (stu1->totalScore > stu2->totalScore) ||

           (stu1->totalScore == stu2->totalScore && stu1->count < stu2->count);         //desc

}

int main()

{

    string str;

    vector<student* >students;

    while(getline(cin, str))   //去读一行，使用cin>>会有缓冲区的问题（空格,tab,回车）

    {

        //fill into vector

        student* stu = new student(str);

        if(LOD == stu->OPE)

        {

            students.push_back(stu);

            stu->count = myCout++;  //用于记录学生出现的顺序

        }

        if(LST == stu->OPE)

        {

           string stuName = "";     //提取学生姓名，用于匹配查找

           unsigned int posNAME01 = str.find_last_of('=');

           unsigned int posNAME02 = str.find_last_of(';');

           stuName = str.substr(posNAME01 + , posNAME02 - posNAME01 - );

            sort(students.begin(),students.end(),mathCompare);

            for(int i = ; i < students.size();++i)

            {

                if(students[i]->NAME == stuName)

                    students[i]->mathMarking = i+;    //根据数学成绩排序规则，给学生的数学排名赋值

            }

            sort(students.begin(),students.end(),langCompare);

            for(int i = ; i < students.size();++i)

            {

                if(students[i]->NAME == stuName)

                    students[i]->langMarking = i+;

            }

            sort(students.begin(),students.end(),totalCompare);

            for(int i = ; i < students.size();++i)

            {

                if(students[i]->NAME == stuName)

                    students[i]->totalMarking = i+;

            }

            for(int i = ; i < students.size();++i)

            {

                if(students[i]->NAME == stuName)    //输出查找学生的信息

                cout << students[i]->NAME << " " << students[i]->MATH << " "

                     << students[i]->LANG << " " << students[i]->totalScore << " "

                     << students[i]->mathMarking << " " << students[i]->langMarking

                     << " " <<students[i]->totalMarking;

            }

        }

    }//while

    return ;

}

三、

给出两个字符串A,B。将A字符串转化为B字符串，转化共两种方式：删除连续的n个字符，一次操作费用为2。增加连续的n个字符（增加的什么由你决定），一次操作的费用为n+2。求把A变为B最小费用。

输入：第一行输入一个正整数（1<=T<=10）,表示有T组测试数据。
对于每组测试数据：
两行字符串A,B(字符串长度不超过2000，字符仅包含小写字母。)

输出：对于每组测试数据，输出一行一个整数，表示最小费用。
样例输入
2
dsafsadfadf
fdfd
aaaaaaaa
bbbbbbbb

样例输出：
7
12

分析：参考知乎（时间复杂度O(N3)），后面自己有时间复杂度O(N2)的方法。

结尾应该只有三种情况即(不修改,删除结尾,添加结尾).
1. 不修改, 只有当str1[j - 1] == str2[i - 1]的情况才可能存在, 此时费用等于将A[0:i-1]变换为B[0:j-1]的最小费用(三种方式中最小的那个),否则为INF
2. 添加结尾, 考虑添加的长度为k,此时费用为将A[0:i]变换成B[0:j-k]再加上一个根据结尾不同变换的COST1
3. 删除结尾, 考虑删除的长度为k,此时费用为将A[0:i-k]变换为B[0:j]再加上一个根据结尾不同变换的COST2
（Delete: Min(F(0, m),...,F(n-1, m))+2;）
（ Insert: Min(F(n,0)+m,...,F(n, m-1)+1)+2;）
作者：AbmiP

链接：https://www.zhihu.com/question/50960106/answer/123577803

来源：知乎

著作权归作者所有，转载请联系作者获得授权。

#define _CRT_SECURE_NO_WARNINGS

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define INF 3000

using namespace std;

int de[][], ae[][], ne[][];

char s1[], s2[];

int main() {

    //freopen("io/in.txt", "r", stdin);freopen("io/out.txt", "w", stdout);

    int n, l1, l2;

    char c;

    scanf("%d%c", &n, &c);

    while (n--) {

        char* tmp = s1;

        char c;

        while ((scanf("%c", &c) != EOF) && c != '\n')*(tmp++) = c;

        *tmp = '\0';

        tmp = s2;

        while ((scanf("%c", &c) != EOF) && c != '\n')*(tmp++) = c;

        *tmp = '\0';

        l1 = strlen(s1);

        l2 = strlen(s2);

        for (int i = ; i <= l1; i++) {

            de[][i] = ; ae[][i] = ne[][i] = INF;

        }

        for (int i = ; i <= l2; i++) {

            ae[i][] = i + ; de[i][] = ne[i][] = INF;

        }

        ne[][] = ;

        for (int j = ; j <= l2; j++)

            for (int i = ; i <= l1; i++) {

                ne[j][i] = s1[i - ] == s2[j - ] ? min(min(ne[j-][i-], ae[j-][i-]), de[j-][i-]) : INF;

                ae[j][i] = de[j][i] = INF;

                for (int k = ; k <= j; k++)

                    ae[j][i] = min(ae[j][i], min(ae[j - k][i] + k, min(de[j - k][i] + k + , ne[j - k][i] + k + )));

                for (int k = ; k <= i; k++)

                    de[j][i] = min(de[j][i], min(de[j][i - k], min(ae[j][i - k] + , ne[j][i - k] + )));

            }

        printf("%d\n", min(min(ne[l2][l1], ae[l2][l1]), de[l2][l1]));

    }

    return ;

}

O(N2)：

addEnd[i][j]表示通过增加字符，使得str1[0 : j]变换为str2[0 : i];

delEnd[i][j]表示通过删除字符，使得str1[0 : j]变换为str2[0 : i];

noEnd[i][j]表示不做变换，使得str1[0 : j]变换为str2[0 : i]。

#include <iostream>

#include <cstring>

using namespace std;

#define max 2001

#define INF 10000

int addEnd[max][max];

int delEnd[max][max];

int noEnd[max][max];

int MIN(int x,int y)

{

    if(x>y)

        return y;

    else

        return x;

}

void initArray(int addEnd[][max], int delEnd[][max], int noEnd[][max], int len1, int len2)

{

    for(int i = ; i <= len1; i++)

    {

        delEnd[][i] = ;

        addEnd[][i] = noEnd[][i] = INF;

    }

    for(int i = ;i <= len2; i++)

    {

        addEnd[i][] = i + ;

        delEnd[i][] = noEnd[i][] = INF;

    }

    noEnd[][] = ;

}

void refreshArray(int addEnd[][max],int delEnd[][max],int noEnd[][max],const char* str1,int len1,const char* str2,int len2)

{

    for(int i = ;i <= len2; i++)

    {

        for(int j = ;j <= len1; j++)

        {

            noEnd[i][j]  = (str1[j-]==str2[i-]) ? MIN(addEnd[i-][j-],MIN(delEnd[i-][j-],noEnd[i-][j-])) : INF;

            delEnd[i][j] = addEnd[i][j] = INF;

            addEnd[i][j] = MIN(addEnd[i][j], MIN(addEnd[i-][j]+, MIN(delEnd[i-][j]++, noEnd[i-][j]++)));

            delEnd[i][j] = MIN(delEnd[i][j],MIN(addEnd[i][j-]+,MIN(delEnd[i][j-],noEnd[i][j-]+)));

        }

    }

}

int main()

{

    int num;

    while(cin >> num)

    {

        int ret[num];

        int retID = ;

        int retSize = num;

        while(num > )

        {

            char str1[max];

            char str2[max];

            cin >> str1 >> str2;

            int len1 = strlen(str1);

            int len2 = strlen(str2);

            //数组边界预定义

            initArray(addEnd, delEnd, noEnd, len1, len2);

            //刷新数组

            refreshArray(addEnd, delEnd, noEnd, str1, len1, str2, len2);

            //保存结果

            ret[retID++] = MIN(addEnd[len2][len1],MIN(delEnd[len2][len1],noEnd[len2][len1]));

//此处，切不可使用++retID（先自增为1，并将自增后的值赋给下标）；而retID++是自增，并将自增前的值赋给小标。  回忆一下STL中map删除中 it++的用法

            --num;

        }//end while

        //result display

        for(int i = ; i < retSize; i++)

        {

            cout << ret[i] << endl;

        }

    }//end while

    return ;

}

相关文章