華為2023年筆試題

華為2023筆試題

1.刪除字符串中的指定字符

1.1問題描述

輸入兩個字符串M和N，從字符串M中刪除字符串N中全部的字符。例如，輸入”abcda”和”ac”，則刪除之后的”第一個字符串變成”bd”。

1.2問題求解

這個比擬簡潔，給出如下參考代碼：

#include

usingnamespacestd;

voiddeleteCharacter(stringstr0,stringstr1){

for(inti=0;i

if(str1.find(str0[i])!=string::npos){

str0.erase(i,1);

continue;

}

++i;

}

}

2.成績排名

2.1問題描述

題目總共包含如下兩種格式的字符串命令：

LODGRADE命令，其格式：

LODGRADE:NAME=XiaoMing,MATH=80,LANG=90;

(1)此命令用于導(dǎo)入學(xué)生成績

(2)NAME字段表示學(xué)生姓名

(3)MATH字段表示學(xué)生數(shù)學(xué)成績

(4)LANG字段表示語文成績

(5)MATH字段和LANG字段挨次不肯定MATH在前，LANG在后

(6)一樣的分?jǐn)?shù)，名次一樣，后面的名次空缺;例如100,99,99,99,98,98，名次:1,2,2,2,5,5

(7)此命令會連續(xù)執(zhí)行，直到遇到第一個LSTGRADE

LSTGRADE命令，其格式：

LSTGRADE:NAME=XiaoMing;

(1)此命令用于查詢學(xué)生成績

(2)NAME字段表示學(xué)生姓名

(3)查詢結(jié)果格式：姓名數(shù)學(xué)語文總分?jǐn)?shù)學(xué)排名語文排名總排名

(4)每組用例，此命令僅執(zhí)行一次

輸入:連續(xù)多組LODGRADE后跟一個LSTGRADE查詢命令

輸出:輸出查詢格式為：

姓名數(shù)學(xué)語文總分?jǐn)?shù)學(xué)排名語文排名總排名

樣例輸入:LODGRADE:NAME=XiaoMing,MATH=80,LANG=90;

LODGRADE:NAME=XiaoHong,LANG=60,MATH=100;

LODGRADE:NAME=XiaoMei,MATH=70,LANG=90;

LSTGRADE:NAME=XiaoHong;

樣例輸出:XiaoHong10060160132

2.2問題求解

此問題也不難，沒有涉及到簡單的算法，就是比擬繁瑣，主要考察數(shù)據(jù)的表示，字符串的提取與排序，下面給出參考代碼：

#include

#include

#include

#include

usingnamespacestd;

structStudent{

stringname;

intmath;

intlang;

Student(){

this-name=;

this-math=0;

this-lang=0;

}

Student(stringname,intmath,intlang){

this-name=name;

this-math=math;

this-lang=lang;

}

booloperator==(constStudentele){

returnthis-name==;

}

};

//自定義比擬函數(shù),數(shù)學(xué)排名

boolcompareMath(constStudentleft,constStudentright){

returnleft.mathright.math;//降序排列

}

//自定義比擬函數(shù),語文排名

boolcompareLang(constStudentleft,constStudentright){

returnleft.langright.lang;//降序排列

}

//自定義比擬函數(shù),總分排名

boolcompareTotal(constStudentleft,constStudentright){

returnleft.math+left.langright.math+right.lang;//降序排列

}

intmain(){

vectorstudentVec;

stringinput;

Studentstudent;

vectorsplitedRes;

while(getline(cin,input)){

ints=input.find(NAME=);

inte=input.find(,,s);

if(input.find(LODGRADE)!=string::npos){//輸入成績

=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;

stringname=input.substr(s+5,e-s-5);

Studentstudent;

//數(shù)學(xué)排名

std::sort(studentVec.begin(),studentVec.end(),compareMath);

vector::iteratorit=find(studentVec.begin(),studentVec.end(),Student(name,0,0));

student=*it;

while(it!=studentVec.begin()(it-1)-math==it-math)--it;

intmathRank=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;

intlangRank=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;

inttotalRank=it-studentVec.begin()+1;

cout

cout

3.2動態(tài)規(guī)劃法求解

遞歸法易于理解，但是存在對子問題的重復(fù)計算，時間效率低下，可以將子問題的結(jié)果存儲起來，把遞歸實現(xiàn)，轉(zhuǎn)換為迭代實現(xiàn)，這樣就變成了動態(tài)規(guī)劃。遞歸法是自頂向下，而動態(tài)規(guī)劃是自底向上遞歸法是需要某個結(jié)果時就調(diào)用自己來計算，動態(tài)規(guī)劃把每次遞推的結(jié)果保存在數(shù)組中。由于這里有i，ir，j，jr一個4個變量，所以其實需要一個4維數(shù)組，這里用了一個宏代替，將4維數(shù)組通過下標(biāo)轉(zhuǎn)變變?yōu)橐痪S數(shù)組。詳細(xì)實現(xiàn)參考如下代碼：

intfunc2(conststringa,conststringb){

constintla=(int)a.length();

constintlb=(int)b.length();

vectorret(la*la*lb*lb);

#defineVRET(a,b,c,d)(ret[(a)*la*lb*lb+(b)*lb*lb+(c)*lb+(d)])

for(intix=la-1;ix=0;ix--)

for(intirx=ix;irxla;irx++)

for(intjx=lb-1;jx=0;jx--)

for(intjrx=jx;jrxlb;jrx++){

inti=ix;

intir=irx;

intj=jx;

intjr=jrx;

while(i=irj=jra[i]==b[j]){

i++;

j++;

}

while(i=irj=jra[ir]==b[jr]){

ir--;

jr--;

}

if(iir){//A為空串

VRET(ix,irx,jx,jrx)=(jr+1-j)+2;

continue;

}elseif(jjr){//B為空串

VRET(ix,irx,jx,jrx)=2;

continue;

}

inttmp=2+(jr+1-j)+2;//最壞狀況，將A全部刪除再增加到B

for(intk=i+1;k=ir;k++)

tmp=min(tmp,2+VRET(k,ir,j,jr));

for(intk=ir-1;k=i;k--)

tmp=min(tmp,2+VRET(i,k,j,jr));

for(intk=j+1;k=jr;k++)

tmp=min(tmp,