string
string s=”aannccnc”;
a.size()//求长度
int pos1=s.find("nc");//返回第一次出现an的位置3
int pos2=s.find("nc",5);//从s[5]开始查找nc,返回6
if(s.find("ac") != s.npos)//查找s中是否有ac字符串,有的话,进入if语句里,没有跳出
{
}
//删除用法
(1)erase(pos,n); 删除从pos开始的n个字符,比如erase(0,1)就是删除第一个字符
(2)erase(position);删除position处的一个字符(position是个string类型的迭代器)
(3)erase(first,last);删除从first到last之间的字符(first和last都是迭代器)
string str ("This is an example phrase.");
string::iterator it;
// 第(1)种用法
str.erase (10,8);
cout << str << endl; // "This is an phrase."
// 第(2)种用法
it=str.begin()+9;
str.erase (it);
cout << str << endl; // "This is a phrase."
// 第(3)种用法
str.erase (str.begin()+5, str.end()-7);
cout << str << endl; // "This phrase."
return 0;
华为的几道笔试题
1。
/*
编写函数,string deletestring(string str,string sub_str)从str中查找
匹配的字符串sub_str,采用最左匹配,且输出形式为str+"_"+匹配的次数。
*/
#pragma once
#include<iostream>
#include<string>
using namespace std;
void Deletestr(char *s, int start, int end)
{
char *p1 = &s[start];
char *p2 = &s[end+1];
while ((*p1++ = *p2++) != '\0');
}
int deletestring(char *str, char *subStr)
{
if (str == NULL || subStr == NULL)
return 0;
char *pstr = str;
char *psubStr = subStr;
int index = 0, count = 0;
while (*pstr != '\0')
{
if (*pstr == *psubStr)
{
pstr++;
psubStr++;
index++;
}
else
{
pstr = pstr - index + 1;
psubStr = subStr ;
index = 0;
}
if (*psubStr == '\0')
{
count++;
Deletestr(str, pstr - str - index, pstr - str - 1);
psubStr = subStr;
}
}
cout << str << "_" << subStr << "_" << count << endl;
}
2。 删除字符串中的指定字符
输入两个字符串M和N,从字符串M中删除字符串N中所有的字符。例如,输入”abcda”和”ac”,则删除之后的第一个字符串变成”bd”。
#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;
}
}
3。
成绩排名
题目总共包含如下两种格式的字符串命令:
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
#pragma once
#pragma once
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
class Student {
string name;
int math;
int lang;
public:
Student() {
name = "";
math = 0;
lang = 0;
}
Student(string na, int m, int l)
{
name = na;
math = m;
lang = l;
}
bool operator==(const Student temp)
{
return name == temp.name;
}
int mathvalue()const
{
return math;
}
int langvalue()const
{
return lang;
}
};
bool compareMath(const Student left, const Student right) {
return left.mathvalue()>right.mathvalue(); //降序排列
}
bool compareLang(const Student left, const Student right) {
return left.langvalue()>right.langvalue(); //降序排列
}
bool compareTotal(const Student left, const Student right) {
return left.mathvalue() + left.langvalue()>right.mathvalue() + right.langvalue(); //降序排列
}
void StudentManage()
{
string input;
/*while(cin.getline(input))*/
vector<string> Info;
/*Info.push_back("LOD GRADE:NAME=XiaoMing,MATH=80,LANG=90;");
Info.push_back("LOD GRADE:NAME=XiaoHong,LANG=60,MATH=100;");
Info.push_back("LOD GRADE:NAME=XiaoMei,MATH=70,LANG=85;");
Info.push_back("LST GRADE:NAME=XiaoHong;");*/
vector<Student> stuall;
int len = Info.size();
/*for (int i = 0; i < len; i++)
{*/
while (getline(cin, input))
{
/*input = Info[i];*/
int s = input.find("NAME=");//从位置0开始查找
int e = input.find(',', s);//从位置s开始查找
if (input.find("LOD GRADE") != input.npos)//添加命令
{
string name = input.substr(s + 5, e - s - 5);//取子串(位置和长度)
s = input.find("MATH=");
e = input.find(',', s);
int math = stoi(input.substr(s + 5, e - s - 5));
s = input.find("LANG=");
e = input.find(';', s);
if (e == input.npos) e = input.length() - 1;
int lang = stoi(input.substr(s + 5, e - s - 5));
Student stu(name, math, lang);
stuall.push_back(stu);
}
else
{
e = input.length() - 1;
string name = input.substr(s + 5, e - s - 5);
Student student(name, 0, 0);
sort(stuall.begin(), stuall.end(), compareMath);
int mathrank = 0;
int math = 0;
int lang = 0, Total = 0;
for (int i = 0; i < stuall.size(); i++)
{
if (stuall[i] == student)
{
mathrank = i + 1;
math = stuall[i].mathvalue();
break;
}
}
sort(stuall.begin(), stuall.end(), compareLang);
int langrank = 0;
for (int i = 0; i < stuall.size(); i++)
{
if (stuall[i] == student)
{
langrank = i + 1;
lang= stuall[i].langvalue();
break;
}
}
sort(stuall.begin(), stuall.end(), compareTotal);
int Totalrank = 0;
for (int i = 0; i < stuall.size(); i++)
{
if (stuall[i] == student)
{
Totalrank = i + 1;
break;
}
}
cout << name << " " << math << " " << lang << " " << math+lang<< " " << mathrank << " " << langrank << " " << Totalrank << endl;
}
}
}
4.字符串变换最小费用
给出两个字串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 。
注意,有些最优的方案可能要做多次的删除和增加操作,不限于两次。
递归法求解[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’的首尾字符还是不相同,还是需要进行删除或者增加的操作,很明显这样不是最优的,所以抛弃这种做法。
int func1(const char a[], const char b[], int astart, int aend, int bstart, int bend)
{
while (astart <= aend&&bstart <= bend&&a[astart] == b[astart])
{
astart++;
bstart++;
}
while (astart <= aend&&bstart <= bend&&a[aend] == b[bend])
{
aend--;
bend--;
}
if (astart > aend) return (bend - bstart + 1) + 2;
if (bstart > bend) return 2;
int tmp=2+ (bend - bstart + 1) + 2;
for (int k = astart + 1; k <= aend; k++)
tmp = min(tmp, 2 + func1(a,b,k,aend,bstart,bend));
for (int k = aend - 1; k >= astart; k--)
tmp = min(tmp, 2 + func1(a, b, astart, k, bstart, bend));
for (int k = bstart + 1; k <= bend; k++)
tmp = min(tmp, (k - bstart) + 2 + func1(a, b, astart, aend, k, bend));
for (int k = bend - 1; k >= bstart; k--)
tmp = min(tmp, (bend-k)+2 + func1(a, b, astart, aend, bstart, k));
return tmp;
}
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
}
参考博客:http://blog.csdn.net/k346k346/article/details/53013206