1.删除字符串中的指定字符
1.1问题描述
输入两个字符串M和N，从字符串M中删除字符串N中所有的字符。例如，输入”abcda”和”ac”，则删除之后的第一个字符串变成”bd”。
1.2问题求解
这个比较简单，给出如下参考代码：
#include <string>using namespace std;void deleteCharacter(string& str0,string& str1){ for(int i=0;i<str0.length();){ if(str1.find(str0[i])!=string::npos){ str0.erase(i,1); continue; } ++i; }}
2.成绩排名
2.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
LST GRADE命令，其格式： LST GRADE:NAME=XiaoMing; （1） 此命令用于查询学生成绩 （2） NAME字段表示学生姓名 （3） 查询结果格式：姓名 数学 语文 总分 数学排名 语文排名 总排名 （4） 每组用例，此命令仅执行一次
输入: 连续多组LOD GRADE后跟一个LST GRADE查询命令 输出: 输出查询格式为： 姓名 数学 语文 总分 数学排名 语文排名 总排名 样例输入: 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
2.2问题求解
此问题也不难，没有涉及到复杂的算法，就是比较繁琐，主要考察数据的表示，字符串的提取与排序，下面给出参考代码：
#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;struct Student{ string name; int math; int lang; Student(){ this->name=""; this->math=0; this->lang=0; } Student(string name,int math,int lang){ this->name=name; this->math=math; this->lang=lang; } bool operator==(const Student& ele){ return this->name==ele.name; }};//自定义比较函数,数学排名bool compareMath(const Student& left,const Student& right){ return left.math>right.math; //降序排列}//自定义比较函数,语文排名bool compareLang(const Student& left,const Student& right){ return left.lang>right.lang; //降序排列}//自定义比较函数,总分排名bool compareTotal(const Student& left,const Student& right){ return left.math+left.lang>right.math+right.lang; //降序排列}int main(){ vector<Student> studentVec; string input; Student student; vector<string> splitedRes; while(getline(cin,input)){ int s=input.find("NAME="); int e=input.find(',',s); if(input.find("LOD GRADE")!=string::npos){ //输入成绩 student.name=input.substr(s+5,e-s-5); s=input.find("MATH="); e=input.find(',',s); if(e==string::npos) e=input.length()-1; student.math=stoi(input.substr(s+5,e-s-5)); s=input.find("LANG="); e=input.find(',',s); if(e==string::npos) e=input.length()-1; student.lang=stoi(input.substr(s+5,e-s-5)); studentVec.push_back(student); }else { //查询成绩 e=input.length()-1; string name=input.substr(s+5,e-s-5); Student student; //数学排名 std::sort(studentVec.begin(),studentVec.end(),compareMath); vector<Student>::iterator it=find(studentVec.begin(),studentVec.end(),Student(name,0,0)); student=*it; while(it!=studentVec.begin()&&(it-1)->math==it->math) --it; int mathRank=it-studentVec.begin()+1; //语文排名 std::sort(studentVec.begin(),studentVec.end(),compareLang); it=find(studentVec.begin(),studentVec.end(),Student(name,0,0)); while(it!=studentVec.begin()&&(it-1)->lang==it->lang) --it; int langRank=it-studentVec.begin()+1; //总分排名 std::sort(studentVec.begin(),studentVec.end(),compareTotal); it=find(studentVec.begin(),studentVec.end(),Student(name,0,0)); while(it!=studentVec.begin()&&(it-1)->math+(it-1)->lang==it->math+it->lang) --it; int totalRank=it-studentVec.begin()+1; cout<<student.name<<" "<<student.math<<" "<<student.lang<<" "<<student.math+student.lang<<" "<<mathRank<<" "<<langRank<<" "<<totalRank<<endl; studentVec.clear(); } } getchar();}
3.字符串变换最小费用
3.1问题描述
给出两个字串A，B。将A字串转化为B字串，转化一共有两种方式:删除连续的n个字符，一次操作费用为2。增加连续的n个字符(增加的字符是什么由你决定)，一次操作费用为n+2。求把A变为B最小费用。
输入: 第一行输入一个正整数T(1 <= T <= 10)，表示有T组测试数据。 对于每组测试数据，有两行字符串A, B（字符串长度不超过2000，字符仅包含小写字母）。
输出: 对于每组测试数据，输出一行一个整数，表示最小费用。
样例输入: 2 dsafsadfadf fdfd aaaaaaaa bbbbbbbb 样例输出: 7 12
答案提示: “dsafsadfadf” 变成 “fdfd” 最少的代价的一种方法是： （1）“dsafsadfadf” -> “f” 删除连续的10个，代价2 ； （2）“f” -> “fdfd” 增加连续的3个（”dfd”），代价为3 ＋ 2 ＝ 5 ���共的最小代价为2 ＋ 5 ＝ 7，其他方法的代价都不小于7 。 “aaaaaaaa” 变成 “bbbbbbbb” 最小代价的一种方法是： （1）“aaaaaaaa” 全部删除，代价2； （2）增加8个连续的’b’，代价10 。 总共的最小代价为2 ＋ 10 ＝ 12 。 注意，有些最优的方案可能要做多次的删除和增加操作，不限于两次。
3.2递归法求解[1]
问题分析： 从给定的问题描述，我们可以得到如下几条信息： （1）A串变为B串，只有两种变换的方式，一是删除，二是增加。增加和删除的位置可以在A串中的任意位置； （2）每一次删除和增加都需要额外的代价，因此，对同一段字符，应该使用贪心思想，尽可能的连续删除和连续增加； （3）A串和B串的相同的首尾子串是不需要考虑的。
除去相同的首尾子串，得到的子串A’和B’，将A’变为B’时，因为此时的A’的首尾字符与B’的首尾字符是不相同的，所以，对A’此时的操作有两种： （1）对A’从左起和右起使用贪心的思想删除连续的字符； （2）对A’从左起和右起用贪心的思想分别增加B’的左起连续的字符和B’的右起连续的字符。 这里为什么不考虑从A的中间部分开始插入和删除，是因为这样做的话，A’的首尾位字符与B’的首尾字符还是不相同，还是需要进行删除或者增加的操作，很明显这样不是最优的，所以抛弃这种做法。
具体实现请，参考如下代码：
/********************************************@brief:将字符串a变为字符串b的最小费用*@param:a:字符串a;b:字符串b;i:a的起始下标;ir:a的结束下标;j:b的起始下标;jr:b的结束下标*******************************************/int func1 (const char a[] ,const char b[] ,int i ,int ir ,int j ,int jr) { //ab有相同前缀，则去除掉也不影响 while (i <= ir && j <= jr && a[i] == b[j]) { i++ ; j++ ; } //ab有相同后缀，则去除掉也不影响 while (i <= ir && j <= jr && a[ir] == b[jr]) { ir-- ; jr-- ; } if (i > ir) { //如果a是空串，则只需增加操作，代价是b的长度+2 return (jr + 1 - j) + 2 ; } else if (j > jr) { //如果b是空串，则只需删除操作，代价是2 return 2 ; } //如果ab无公共前后缀，则代价是求a的所有前后子串转为b的最小值 //最坏的情况是将a全部删除再增加到b int tmp = 2 + (jr + 1 - j) + 2 ; //a的非空后子串 for (int k = i + 1 ; k <= ir ; k++) tmp = min (tmp ,2 + func1 (a ,b ,k ,ir ,j ,jr)) ; //a的非空前子串 for (int k = ir - 1 ; k >= i ; k--) tmp = min (tmp ,2 + func1 (a ,b ,i ,k ,j ,jr)) ; //在a的左边增加连续的b的非空前子串 for (int k = j + 1 ; k <= jr ; k++) tmp = min (tmp ,(k - j) + 2 + func1 (a ,b ,i ,ir ,k ,jr)) ; //在a的右边增加连续的b的非空后子串 for (int k = jr - 1 ; k >= j ; k--) tmp = min (tmp ,(jr - k) + 2 + func1 (a ,b ,i ,ir ,j ,k)) ; return tmp ;}
运行结果：
cout<<func1("1aaa1","aaa",0,4,0,2)<<endl; //输出4cout<<func1("aaa","1aaa1",0,2,0,4)<<endl; //输出6
3.2动态规划法求解
递归法易于理解，但是存在对子问题的重复计算，时间效率低下，可以将子问题的结果存储起来，把递归实现，转换为迭代实现，这样就变成了动态规划。递归法是自顶向下，而动态规划是自底向上递归法是需要某个结果时就调用自己来计算，动态规划把每次递推的结果保存在数组中。因为这里有i，ir，j，jr一个4个变量，所以其实需要一个4维数组，这里用了一个宏代替，将4维数组通过下标转变变为一维数组。具体实现参考如下代码：
int func2 (const string &a ,const string &b) { const int la = (int) a.length () ; const int lb = (int) b.length () ; vector<int> ret (la * la * lb * lb) ; #define VRET(a ,b ,c ,d) (ret[(a) * la * lb * lb + (b) * lb * lb + (c) * lb + (d)]) for (int ix = la - 1 ; ix >= 0 ; ix--) for (int irx =ix ; irx < la ; irx++) for (int jx = lb - 1 ; jx >= 0 ; jx--) for (int jrx =jx ; jrx < lb ; jrx++) { int i = ix ; int ir = irx ; int j = jx ; int jr = jrx ; while (i <= ir && j <= jr && a[i] == b[j]) { i++ ; j++ ; } while (i <= ir && j <= jr && a[ir] == b[jr]) { ir-- ; jr-- ; } if (i > ir) { //A为空串 VRET (ix ,irx ,jx ,jrx) = (jr + 1 - j) + 2 ; continue ; } else if (j > jr) { //B为空串 VRET (ix ,irx ,jx ,jrx) = 2 ; continue ; } int tmp = 2 + (jr + 1 - j) + 2 ; //最坏情况，将A全部删除再增加到B for (int k = i + 1 ; k <= ir ; k++) tmp = min (tmp ,2 + VRET (k ,ir ,j ,jr)) ; for (int k = ir - 1 ; k >= i ; k--) tmp = min (tmp ,2 + VRET (i ,k ,j ,jr)) ; for (int k = j + 1 ; k <= jr ; k++) tmp = min (tmp ,(k - j) + 2 + VRET (i ,ir ,k ,jr)); for (int k = jr - 1 ; k >= j ; k--) tmp = min (tmp ,(jr-k) + 2 + VRET (i ,ir ,j ,k)); VRET (ix ,irx ,jx ,jrx) = tmp ; continue ; } return VRET (0 ,la - 1 ,0 ,lb - 1) ; #undef VRET}
运行结果：
cout<<func2("dsafsadfadf","fdfd")<<endl; //7cout<<func2("aaaaaaaa","bbbbbbbb")<<endl; //12
本文永久更新链接地址：http://www.xuebuyuan.com/Linux/2017-03/141268.htm
以上就上有关华为2017校招C++岗笔试题的全部内容，学步园全面介绍编程技术、操作系统、数据库、web前端技术等内容。