算法题之三道2016华为校招上机笔试题
为了准备应聘过程中的机试环节，找了些OJ机试题来做做。看了帖子http://www.cnblogs.com/whc-uestc/p/4733992.html后用自己的方法对三道华为机试题进行了编写。
题1
#include <iostream> #include <string> #include <vector> using namespace std; int getmax(vector<int> vec, int a, int b) { int max=0; for(int i=a-1;i<=b-1;i++) { if(max<vec[i]) { max=vec[i]; } } return max; } int main(){ //vector<Log> vec; //Log lg; //while(cin>>lg.path>>lg.row){ // writeLog(vec,lg); //} //for(int i=0; i<vec.size(); i++) // cout<<vec[i].path<<" "<<vec[i].row<<" "<<vec[i].count<<endl; //return 0; //string inputstr; //int a; //int b; //char c[3]; //while(cin>>inputstr>>a>>c) //{ // cout<<inputstr<<a<<c<<'/n'<<endl; //}//"cin>>string/int/char"以空格为分隔符跳入下一个">>"输入操作 //cout<<inputstr<<endl; //cout<<a<<endl; //cout<<c<<endl; //cout<<lg.row<<endl; int N,M,tem; cin>>N>>M; int n=N; int m=M; vector<int> score;//保存分数 while(n--)//输入分数并保存操作，不清除输入缓冲区，保证输入的一列被录入 { cin>>tem; score.push_back(tem); } char mode; int A,B; vector<int> answer(M);//想对vector直接赋值就得定义大小，如果不定义大小，直接赋值会出错，只能用push_back int i=0;//答案下标 while(m--) { cin.sync();//清空cin输入缓冲区，1.保证输入的是当前输入行的数据；2. 保证每次输入的是一行中的数据 cin>>mode>>A>>B; if(mode=='Q') answer[i++]=getmax(score,A,B); else score[A-1]=B;//将第A个ID改为B } for(int j=0;j<i;j++) cout<<answer[j]<<endl; } //样例输入： //5 6 //1 2 3 4 5 //Q 1 5 //U 3 6 //Q 3 4 //Q 4 5 //U 2 9 //Q 1 5
题2
#include <iostream> #include <string> #include <vector> using namespace std; struct Log { string name; int row; int times; }; string getname(string &addrandname) { string name; int N=addrandname.size(),num=1; while(addrandname[N-num]!='\\'&&num!=17)//跳出循环条件，遇到\或第17次循环 { num++; } name=addrandname.substr(N-num+1,num-1); return name; } void savelog(vector<Log> &vec_log, Log log) { int N=vec_log.size(),flag=0; for(int i=0;i<N;i++) { if(vec_log[i].name==log.name&&vec_log[i].row==log.row) { vec_log[i].times++; flag=1; } } if(flag==0) { vec_log.push_back(log); } } void prin(vector<Log> vec_log) { int N=vec_log.size(); for(int i=0;i<N;i++) { cout<<vec_log[i].name<<" "<<vec_log[i].row<<" "<<vec_log[i].times<<endl; } } int main() { string addrandname; int row; cin.sync();//清除输入缓冲区中的数据流 cin.clear();// 将流中的所有状态值都重设为有效值 vector<Log> vec_log; Log log; while(cin>>addrandname>>row) { log.name=getname(addrandname); log.row=row; log.times=1; savelog(vec_log,log); prin(vec_log); cin.sync(); cin.clear(); } //string name,aa="123456789123456789.c"; //name=getname(aa); //cout<<name<<endl; //addrandname="aaaa"; //addrandname="fie"; //cout<<addrandname<<endl; }
题3
#include<iostream> #include<string> #include<vector>//vector完全可以替代数组，以后数组用vector,字符串用string，char、int、double只用于单个变量 using namespace std; //单张1 对子3 三个5 顺子9 四个7 对王11 //首先判断是否存在一对王 //判断是否存在四个 //剩下的比较第一张牌大小 //难点：string类的使用，比较，赋值，长度等 //单张牌大小的比较 bool is2joker(string str)//判断是否为一对王 { string joker2="joker JOKER",joker21="JOKER joker"; if(str==joker2|str==joker21)//怎么比较两个string return true; return false; } bool isquar(string str)//判断是否为四个一样的牌 { if(str.size()==7) if(str[0]==str[6]) return true; return false; } int pai2num(string str_01) { int re; if(str_01=="jo") re=16; else if(str_01=="JO") re=17; else { switch(str_01[0]) { case '3':re=3;break; case '4':re=4;break; case '5':re=5;break; case '6':re=6;break; case '7':re=7;break; case '8':re=8;break; case '9':re=9;break; case '10':re=10;break; case 'j':re=11;break; case 'q':re=12;break; case 'k':re=13;break; case 'a':re=14;break; case 'J':re=11;break; case 'Q':re=12;break; case 'K':re=13;break; case 'A':re=14;break; case '2':re=15;break; default:re=0;break; } } return re; } bool isbig(string str1,string str2)//判断牌面值的大小 { return pai2num(str1.substr(0,2))>pai2num(str2.substr(0,2))?true:false; } void main() { string str;//这样的string类型只能由getline(cin,str)全局函数赋值 //char 类型的向量只能由cin.get(str,size)或cin.getline()赋值 string str1; string str2; getline(cin,str);//getline(cin,str,'/n')和cin.getline(char[],size)区别 int loc=0; int loc1=0; int loc2=0; int flag1=0;//是否遇到- cout<<str.size()<<endl; for(loc;loc<str.size();loc++) { //用什么方法在string后加入字符？如下 //str1+=str[loc];//为什么不能用str1.append(str[loc])或str1.push_back(),因为参数必须为string类型，而不能是char类型 //cout<<str1<<endl; //string类型的用法？ //赋值时用用“”括起来的内容，有+=，append(),insert()方法 //string类型不能用于switch（case 只能用于数值和单个字符‘’的内容比较），一般用if() else if()代替(if和elseif只执行一条，前面的优先级高) if(str[loc]=='-') { flag1=1; loc++; } if(flag1==0) str1+=str[loc]; else str2+=str[loc]; } cout<<"一手牌为："<<str1<<endl; cout<<"另一手牌为："<<str2<<endl; if(is2joker(str1)|is2joker(str2))//是否有一对王 { string bigone; bigone=is2joker(str1)?str1:str2; cout<<"最大的手牌为："<<bigone<<endl; } else if(isquar(str1)^isquar(str2))//是否其中一手为四张同样的牌 { string bigone; bigone=isquar(str1)?str1:str2; cout<<"最大的手牌为："<<bigone<<endl; } else if(str1.size()==str2.size())//直接比第一张牌的大小即可 { string bigone; bigone=isbig(str1,str2)?str1:str2; cout<<"最大的手牌为："<<bigone<<endl; } else cout<<"ERROR"<<endl; }
笔记：
1.OJ系统中的题目要求输入样例为一行或多行时，怎么考虑输入过程？
因为OJ系统的输入样例和输出样例是一一对应的，每输入一行样例就进行处理和输入n行样例再进行统一处理不会影响评判结果。在不明确输入样例具体为几行时，一般用while(getline(cin,str)){}或者while(cin>>str1>>str2){}语句对每一行数据分别进行处理和输出；当知道输入样例的行数时（一个样例分为了几行数据），一般用while(N--){cin>>str1>>str2}语句连续记录N行输入数据后再进行处理。
2.回顾了vector,string,getline(),cin.getline(),cin.get(),cin>>相关的知识
vector:创建vector时若不规定大小（默认为空），需用push_back()进行”赋值“；创建时若规定了大小，可用[]和=进行指定位置的赋值。vector<>::iterator it; it可看做一个广义指针，指向容器中的元素；而vector<>* p2v;是指向容器的指针，p2v->el。
string:完全可以代替字符数组char ch[]。一种特殊的字符容器（比单纯的字符容器更强大），可看作普通数据类型，能进行+（拼接）、=（赋值）、==（判断是否相等）等操作，一般用cin>>str和getline(cin,str)方式赋值。注：cin>>可对string和char数组进行赋值；getline()只用于对string赋值；cin.get()和cin.getline()只用于对char数组进行赋值。
getline()与cin.getline()不同之处在于，前者可以规定文件结束符（默认为‘\n’），且它们是不同的概念，前者属于istream，后者属于cin流。注意：getline()在vc6下需要多打一个回车才能确定赋值（第一个回车是结束符，第二回车是输入结束标志？），而在vs下只需一个回车符。
cin.get():虽然可用于获得字符串，但一般用于取一个字符（任何字符）。
cin>>:以‘ ’为分隔符，‘\n’为结束符。一次>>到分隔符为至，剩余字符保存在缓冲区中，可用于下一个>>操作。为了避免误操作，一般用cin.clear()和cin.sync()恢复cin状态和清空缓冲区。