- 以下代码的运行结果为()
class Base { public: Base() { echo(); } virtual void echo() { printf("Base"); } }; class Derived :public Base { public: Derived() { echo(); } virtual void echo() { printf("Derived"); } }; int main() { Base* base = new Derived(); base->echo(); return 0; }
A. DerivedDerivedDerived
B. DerivedBaseDerived
C. BaseDerivedBase
D. BaseDerivedDerived
因为Derived类继承了Base类,所以在调用构造函数时会首先调用Base类的构造函数,此后在调用Derived的构造函数,随后因为echo构成多态,按对象调用,所以调用的也是Dervied的echo函数
所以本题选:D
编程题
1.跳石板
小易来到了一条石板路前,每块石板上从1挨着编号为:1、2、3…
这条石板路要根据特殊的规则才能前进:对于小易当前所在的编号为K的 石板,小易单次只能往前跳K的一个约数(不含1和K)步,即跳到K+X(X为K的一个非1和本身的约数)的位置。 小易当前处在编号为N的石板,他想跳到编号恰好为M的石板去,小易想知道最少需要跳跃几次可以到达。
例如:
N = 4,M = 24:
4->6->8->12->18->24
于是小易最少需要跳跃5次,就可以从4号石板跳到24号石板
解法
该题要采用动态规划的思想,可以设定两个数组,一个数组存放k的约数来表明在当前位置有几种走法,另一个数组存放从起始位置走到当前位置所需要的最小步数,因为要是最小步数,所以存放步数的数组每次有新的值来临就要和当前值进行比较,如果小于当前值才更新。如果无法抵达就返回-1,判断是否无法抵达可以在初始化的时候做文章,比如将所有位置都初始化为整数的最大值,然后再将起始位置初始化为0,从起始位置往后走,能抵达的每一个位置都会被初始化,最后如果目标位置是整数的最大值就表示无法抵达。
#include<iostream> #include<vector> #include<cmath> #include<limits.h> using namespace std; void jump_way(int way,vector<int>&a) { //求约数,1和本身不算 for(int i=2;i<=sqrt(way);i++) { if(way%i==0) { a.push_back(i); if(way/i!=i) a.push_back(way/i); //因为这里开平方了,所以i只能取到约数的一遍,但是只要i是way的约数,那么way/i肯定也是way的约数 } } } int Jump(int n,int m) { //主要过程在这个函数中进行 vector<int>step(m+1,INT_MAX);//数组用于存放起始位置到当前位置的最小步数 step[n]=0; for(int i=n;i<=m;i++) { if(step[i]==INT_MAX)//第一次是起始位置,所以可以往后执行,并且会将所有可达位置改变为其他值,最后要是某个位置还是INT_MAX,说明该点不可达 continue; vector<int> a;//这个数组用来存放约数个数 jump_way(i,a); //a数组中存放的是i位置的约数 for(int j=0;j<a.size();j++) { //如果位置合法,需要挑选一个最小值 if(a[j]+i<=m&&step[a[j]+i]!=INT_MAX) { step[a[j]+i]=min(step[a[j]+i],step[i]+1);//这个位置已经被初始化过了,那么就要比较一下此次步数和之前的步数哪个小 } else if(a[j]+i<=m) { step[a[j]+i]=step[i]+1; } } } return step[m]==INT_MAX ? -1:step[m]; } int main() { int n,m,minstep; while(cin>>n>>m)//n表示当前位置,m是目标位置 { //通过jump函数来得到最小步数 minstep = Jump(n,m); cout<<minstep<<endl; } return 0; }
2.扑克牌大小
扑克牌游戏大家应该都比较熟悉了,一副牌由54张组成,含3~A,2各4张,小王1张,大王1张。牌面从小到大用如下字符和字符串表(其中,小写joker表示小王,大写JOKER表示大王)😃
3 4 5 6 7 8 9 10 J Q K A 2 joker JOKER
输入两手牌,两手牌之间用“-”连接,每手牌的每张牌以空格分隔,“-”两边没有空格,如:4 4 4 4-joker JOKER 请比较两手牌大小,输出较大的牌,如果不存在比较关系则输出ERROR
基本规则:
(1)输入每手牌可能是个子,对子,顺子(连续5张),三个,炸弹(四个)和对王中的一种,不存在其他情况,由输入保证两手牌都是合法的,顺子已经从小到大排列;
(2)除了炸弹和对王可以和所有牌比较之外,其他类型的牌只能跟相同类型的存在比较关系(如,对子跟对子比较,三个跟三个比较),不考虑拆牌情况(如:将对子拆分成个子)
(3)大小规则跟大家平时了解的常见规则相同,个子,对子,三个比较牌面大小;顺子比较最小牌大小;炸弹大于前面所有的牌,炸弹之间比较牌面大小;对王是最大的牌;
(4)输入的两手牌不会出现相等的情况。
答案提示:
(1)除了炸弹和对王之外,其他必须同类型比较。
(2)输入已经保证合法性,不用检查输入是否是合法的牌
(3)输入的顺子已经经过从小到大排序,因此不用再排序了.
输入描述:
输入两手牌,两手牌之间用“-”连接,每手牌的每张牌以空格分隔,“-”两边没有空格,如4 4 4 4-joker JOKER。
输出描述:
输出两手牌中较大的那手,不含连接符,扑克牌顺序不变,仍以空格隔开;如果不存在比较关系则输出ERROR。
解题思路
这个题目描述真是长到吓人,但其实真正重要的是以下几点:
1.两手牌输入到同一个字符串中,以-
分割,这就暗示了我们要在程序中以-
位分割符来得到两手牌
2.只有炸弹和王炸可以跟其他类型的牌比较,其他的都只能跟同类型的牌比较,并且只需要比第一张牌的大小即可(因为是有序的)
3.已经保证了输入的合法性,也就是说如果长度相同肯定是同类型的,长度不同且不是王炸,那肯定是“ERROR”
所以首先要切割字符串得到两手牌,再看两个子串的长度是否相等,如果相等就比较点数,如果不相等就看是否有炸弹,如果既不相等,又没有炸弹,那么就输出"ERROR",此外王炸是最大的牌,可以在程序的开始判断是否有王炸,如果有,就直接输出王炸。此外还有两点需要注意:1.扑克牌大小的比较规则和数字有些不同,所以可以再设置一个字符串,在这个字符串中位置越靠后,点数越大;2.关于牌的张数不能使用size
函数,这里可以使用算法库中的count
函数
#include <iostream> #include<string> #include<algorithm> using namespace std; string bigstr(const string&car) { if(car.find("joker JOKER")!=string::npos) return "joker JOKER";//王炸最大 //首先要切割字符串得到两手牌 string car1,car2; int pos=car.find('-',0); car1=car.substr(0,pos); car2=car.substr(pos+1); //判断两手牌的长度是否一致 int cnt1=count(car1.begin(),car1.end(),' ')+1;//count查找的是空格的个数,空格的个数+1就是字符个数 int cnt2=count(car2.begin(),car2.end(),' ')+1; if(cnt1==cnt2) { //两手牌个数相等,比较第一张牌的大小,但是这里有一个问题,就是说比较规则并不是单纯按大小,所以这里又可以设置一个字符串,位置越靠后点数越大 string car1_first=car1.substr(0,car.find(' ')); string car2_first=car2.substr(0,car2.find(' ')); string comp="345678910JQKA2jokerJOKER"; if(comp.find(car1_first)>comp.find(car2_first)) return car1; return car2; } //类型不一致看是不是炸弹 if(cnt1==4) return car1; if(cnt2==4) return car2; return "ERROR"; } int main() { string str,res; while(getline(cin,str)) { res=bigstr(str); cout<<res<<endl; } return 0; }
3.杨辉三角的变形
以上三角形的数阵,第一行只有一个数1,以下每行的每个数,是恰好是它上面的数、左上角数和右上角的数,3个数之和(如果不存在某个数,认为该数就是0)。
求第n行第一个偶数出现的位置。如果没有偶数,则输出-1。例如输入3,则输出2,输入4则输出3,输入2则输出-1。
解题思路
这题有两种解法:
1.可以构建一个二维数组,然后根据输入的n生成一个n行的杨辉三角,每行的列数就是行数的两倍(从0开始),构造完杨辉三角以后直接根据输入的行数进到里面查找,但是这样会显示超出内存限制
#include<iostream> #include<vector> using namespace std; int findnum(int n) { //创建二维数组,生成杨辉三角 vector<vector<int>> vv(n,vector<int>(2*n-1,0)); //初始化 vv[0][0]=1; for(int i=1;i<n;i++) { vv[i][0]=vv[i][2*i]=1;//第一列和最后一列都是1 //除了第二列和倒数第二列都是两个数相加以外,其他位置的数都是三个数相加 for(int j=1;j<2*i;j++) { if(j==1) vv[i][j]=vv[i-1][j]+vv[i-1][j-1]; else if(j==2*i-1) vv[i][j]==vv[i-1][j-2]+vv[i-1][j-1]; else vv[i][j]=vv[i-1][j]+vv[i-1][j-1]+vv[i-1][j-2]; } } //初始化完毕,随后开始查找 for(int j=0;j<2*n-1;j++) { if(vv[n-1][j]%2==0) return j+1; } return -1; } int main() { int n; cin>>n; int ret=findnum(n); cout<<ret<<endl; }
解法二
2.这里有个规律:仔细观察可以发现,第一行和第二行是没有偶数的;如果行数是奇数,那么它的第二列就是就是偶数,如果行数是4的倍数,那么偶数就在第三个位置,除此之外偶数都在第四个位置;(这里的行数是从1开始的)
#include<iostream> #include<vector> using namespace std; int findnum(int n) { if(n<=2) return -1; if(n%2==1) return 2; if(n%4==0) return 3; return 4; } int main() { int n; cin>>n; int ret=findnum(n); cout<<ret<<endl; }
4.字符串通配符
问题描述:在计算机中,通配符一种特殊语法,广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求:
实现如下2个通配符:
*:匹配0个或以上的字符(注:能被 *和?匹配的字符仅由英文字母和数字0到9组成,下同)
?:匹配1个字符
注意:匹配时不区分大小写。
输入:
通配符表达式;
一组字符串。
输出:
返回不区分大小写的匹配结果,匹配成功输出true,匹配失败输出false
输入描述:
先输入一个带有通配符的字符串,再输入一个需要匹配的字符串
输出描述:
返回不区分大小写的匹配结果,匹配成功输出true,匹配失败输出false
解题思路
起初我想以暴力匹配的方式尝试解决这道题,但是无论如何也无法通过题解,最后发现题目说*
可以匹配一个或者以上的字符,这句话的意思或许是在说,有时候*
不用匹配字符,有时候却需要匹配一个或者多个字符;
于是这题可以选用递归的思想来解决,大致分为三种情况:
1.两者走到末尾,肯定是匹配的
2.两者只有一者走到末尾,这种情况就是不匹配
3.以上两种情况都是递归的结束条件,如果不是以上两种情况,如果当前是*
那么可以递归匹配0个,匹配1个或者匹配多个;如果是?
那么就只匹配一个;这里面还有一些注意事项,就是因为*
可以匹配一个或者多个字符,所以一个*
和多个*
其实是一样的,如果有多个*
我们要把它归成一个*
来处理,否则会出现时间复杂度过大,此外因为不区分大小写,所以可以使用tolower
函数来帮助匹配
#include <iostream> #include<string> using namespace std; bool ismatch(const char*match,const char*str) { if(*match=='\0'&&*str=='\0') return true; if(*match=='\0'||*str=='\0') return false; if(*match=='?') { if(!isdigit(*str)&&!isalpha(*str)) return false; return ismatch(match+1,str+1); } else if(*match=='*') { while(*match=='*') { match++; } match--;//前面的循环中将*全部跳过了,但是我们的本意是当成一个*来处理,所以这里要回退一位 if(!isdigit(*str)&&!isalpha(*str)) return false; return ismatch(match+1,str)||ismatch(match+1,str+1)||ismatch(match,str+1); } else if(tolower(*match)==tolower(*str)) return ismatch(match+1,str+1); return false; } int main() { string match,str; while(cin>>match>>str) { bool ret=ismatch(match.c_str(),str.c_str()); if(ret) cout<<"true"<<endl; else cout<<"false"<<endl; } return 0; }