3.21 贝壳C++研发工程师笔试题答案

3.21 贝壳C++研发工程师笔试题答案

第一题：s字符串，划分为几个连续的字符数组，字符为偶数个的时候，val+1，字符为奇数个的时候，val-1，最后输出最大的val。

emmm，听大佬说第一题用动态规划的方法，具体还没想清楚，欢迎大佬们在评论里解答，谢谢！

第二题：判断[l,r]中间的自余数的个数。

思路：采用打表的方法，提前存储1~1e6的自余数。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[27455];//27455是1~1e6的自余数的个数
int main ()
{
    int t;
    int l,r;
    cin>>t;
    int j = 0;
    for(int i=1; i<=1000000; i++) //打表
    {
        int tmp = i;
        int zhi;
        long long sum = 0;
        while(tmp > 0)
        {
            zhi = tmp % 10;
            sum += zhi;
            tmp /= 10;
        }
        if(i % sum == 1)
        {
            a[j++] = i;
        }
    }
    for(int i=1;i<20;i++)
        cout<<a[i]<<" ";

    while(t--) // 1000
    {
        cin>>l>>r;
        int left = 0,right = 0;
        int ans = 0;
        for(int i=0; i<27455; i++)
        {
            if(a[i] <= l)
            {
                left = i;
            }
            if(a[i]<= r)
            {
                right = i;
            }
        }
        ans = right - left + 1;
        //for(int i=0;i<j;i++)
        //cout<<a[i]<<" ";
        //cout<<j<<endl;
        cout<<ans<<endl;
    }
    return 0;
}
/*
3
11 11
13 13
1 20
*/

第三题：字符匹配，在一个n*n的字符矩阵从上往下或者从左往后找到与字符串s匹配的字符串的个数。
思路：暴力的方法，先寻找从左往右匹配的字符个数，再寻找从上往下匹配的个数。
代码：

#include <bits/stdc++.h>
using namespace std;

char a[110][110];
int main ()
{
    int n;
    cin >>n;
    string s;
    cin>>s;
    int str = s.size();
    //getchar();
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>a[i][j];
        }
    }
    long long ans = 0;

    string tmp;
    for(int i=0; i<=n-1; i++)
    {
        for(int j=0; j<=n-str; j++)
        {
            //if(a[i][j] == s[k])
            for(int k=0; k<str; k++)
            {
                tmp += a[i][j+k];//从左往右
            }
            if(tmp == s)
            {

                ans++;
            }
            tmp = "";
        }
    }

    tmp = "";
    for(int j=0; j<=n-1; j++)
    {
        for(int i=0; i<=n-str; i++)
        {
            for(int k=0; k<str; k++)
            {
                tmp += a[i+k][j];//从上往下
            }
            if(tmp == s)
            {
                ans++;
            }
            tmp = "";
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
3
abc
xax
abc
xcx

*/

#笔试题目##贝壳找房#