第一题

题目描述

给定一个长度为n的字符串，问至少替换多少个字符变换成回文串？

分析

• 我们把字符串前一半和后一半拆成两个字符串，然后比较有多少个字符不相等即可
• 或者设置两个指针left和right分别指向字符串的开始和结尾，让他们同时向中间逼近，如果left和right位置的字符不等，那么就需要做替换操作

  解法

  #include <bits/stdc++.h>
  using namespace std;
  int main() {
    string s;
    cin >> s;
    int len = s.length();
    int ans = 0;
    for (int i = 0; i + i < len; ++i) {
        if (s[i] != s[len - i - 1]) ans++;
    }
    cout << ans << endl;
    return 0;
  }

第二题

题目描述

给你一个NxM的方格图，现在要求你对其中每个1x1的小方格进行染色，要求如下：

• 每种颜色的格子数都是相同的
• 相邻格子染色不同
• 所有格子必须染***r>现在最少要多少种颜色就可以完成任务。

输入描述

• 第一行一个整数T，表示测试数据组数
• 接下来T行每行两个空格分割的正整数N, M，代表方格的行数和列数
• 1 <= T <= 100>
• 1 <= N, M <= 1e8

  输出描述

• 共T行每行一个整数表示答案

分析

• 如果没有“每种颜色的格子数都是相同的”这个要求的话，用两种颜色就可以完成这个任务。
• 加上“每种颜色的格子数都是相同的”，那么最终用的颜色数应该是的一个因子，也就是说应该是的因子或者是的因子。那么我们只要知道或者的最小因子是多少就可以了。
• 注意处理或者的情况，这个时候求不是1的那个数字的最小因子即可；如果两个都等于1，那么1种颜色就可以。

第三题

题目描述

给出一个正整数序列A，求一个子区间使得这个区间内的数或起来尽可能的大。求所有满足条件的子区间里面，最短子区间长度。

分析

• 求最大或区间的最短长度，这种MaxMin的问题可以优先考虑用二分解决。这里可以枚举区间起点，二分区间长度。
• 那么剩下的问题就是，对于指定起点Ai和终点Aj，怎么快速算出这个子区间的或运算结果。这里可以利用前缀和的思想，对第i个数计算前i个数里面每一位的出现次数。求区间或运算结果的时候，只需要知道这个区间里面哪些位出现过即可。
• 对每一个数Ai计算出以它为起点的最大或区间最短长度，就可以得到题目的解。
• 另外，当指定起点时，从这个起点开始最长的序列一定是值最大的，所以这里可以提前做一些剪枝，大家可以自己尝试一下。
• 另外一种解法是使用滑动窗口，写起来比较简单

  解法

  更多代码&大厂笔试面试题，欢迎关注公众号“面鲸”，现在已经有网易&字节前几天的笔试题了。