笔试强训错题总结(二)(下)

简介: 笔试强训错题总结(二)
  1. 以下代码的运行结果为()
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;
}


相关文章
|
算法 C++
48天C++笔试强训 001(下)
48天C++笔试强训 001(下)
45 1
|
6月前
【笔试强训】day12
【笔试强训】day12
|
6月前
【笔试强训】day8
【笔试强训】day8
|
6月前
【笔试强训】day9
【笔试强训】day9
|
6月前
|
人工智能
【笔试强训】day10
【笔试强训】day10
|
存储 C语言 C++
48天C++笔试强训 001(上)
48天C++笔试强训 001
56 0
|
安全 编译器 C++
笔试强训错题总结(二)(上)
笔试强训错题总结(二)
|
存储 编译器 C++
笔试强训错题总结(一)(上)
笔试强训错题总结(一)
121 0
|
算法 编译器 C语言
笔试强训错题总结(一)(下)
笔试强训错题总结(一)
|
算法 C++
【笔试强训】Day_01
目录 一、选择题 1、 2、 3、 4、 5、 6、 7、 8、 9、 10、 二、编程题 1、组队竞赛 2、删除公共字符
92 0
【笔试强训】Day_01