- 以下代码的运行结果为()
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; }
