贝壳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;
}