首页 > 贝壳8.11笔试题
头像
米茫
编辑于 2020-08-12 08:35
+ 关注

贝壳8.11笔试题

两小时4道题

1.给一个字符串和它的长度,求修改几个字符可以变成回文

解题:送分题,直接按照判断回文的方式从两边遍历字符串,遇到不同的字符结果就加1
代码:

//100%
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        int res = 0;
        string str;
        cin >> str;
        int left = 0, right = n-1;
        for(int i=0; i<n/2; ++i)
        {
            if(str.at(left+i)!=str.at(right-i)) ++res;
        }
        cout << res << endl;
    }
    return 0;
}

2.给一个n*m的表格染色,相邻的格子颜色必须不同,每个颜色染的格子数量必须相同,问最少需要多少种颜色

解题:1*1肯定是1种,偶数个格子肯定是2种,求最小的因子,但没时间写了,直接从3开始暴力试,一旦可以整除其中一个边长,就是答案
代码:

//100%
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, m;
        cin >> n >> m;
        if(n == m && n == 1) cout << 1 << endl;
        if(n%2==0 || m%2==0) cout << 2 << endl;
        else
        {

            for(int i=2; i<=max(n,m); ++i)
            {
                if(n%i==0 || m%i==0)
                {
                    cout << i << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

3.给一个数组,求一个子区间的长度,这个子区间满足元素的或最大且长度最小。

解题:或最大,分析一下就知道所有元素或在一起必然是最大值,好了我们得到了目标值,现在只需要找到或的值为这个目标值的最小子区间,想到滑动窗口?不太行,或的性质导致我们没办法以O(1)时间收缩左边界,不过依然可以降低时间复杂度,从暴力的O(n^3)降低到O(n^2),收缩左边界重新计算子区间
代码:

//100%
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        vector<int> nums(n);
        int maxval = 0, len = n;
        for(int i=0; i<n; ++i)
        {
            cin >> nums.at(i);
            maxval |= nums.at(i);
        }
        int left = 0, right = 0, val = 0;
        while(right < n)
        {
            //printf("%d %d %d %d %d\n", maxval, len, left, right, val);
            val |= nums.at(right);
            if(val < maxval)
            {
                ++right;
            }
            else
            {
                len = min(len, right-left+1);
                ++left;
                val = 0;
                if(left < n)
                {
                    for(int i=left; i<=right; ++i)
                    {
                        val |= nums.at(i);
                    }
                }
                else break;
            }
        }
        cout << len << endl;
    }
    return 0;
}

4.给一个无向图,和权重,求权重最大的最大联通子图

解题:不会,试了下贪心过了20%

全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐