字节跳动2021-后端开发笔试

题目一：用户喜好

题目描述：

这道题目是三道题目里面最简单的，题目要求寻找喜好为K的用户个数，对输入的各个用户的喜好进行遍历寻找喜好为K的即可。

C++代码：题目

#include
#include
using namespace std;


int main(){

    int m;
    cin >> m;
    vector nums(m);
    for(int i=0;i> nums[i];
    }
    int n;
    cin >> n;
    for(int i=0;i sourchnums(3);
        for(int j=0; j<3; j++){
            cin >> sourchnums[j];
        }
        int l = sourchnums[0];
        int r = sourchnums[1];
        int k = sourchnums[2];
        int res = 0;
        for(int s = l-1;s < r; s++){
            if(nums[s] == k){
                res++;
            }
        }
        cout << res << endl;
    }

    return 0;
}

题目二：字母交换

题目描述：

 这道题目是三道题目里面最难得一个，第一次做的时候并没有想到很好的解法，看了网上的一些题解才AC。解题思路：

题目要求是求在m次交换后，相邻字母数量的最大值，关于最大值问题，相信可以想到用动态规划的思路来解题，但是这道题目即使知道动态规划也很难想到动规的公式推导。从每个字母出发，遍历每个字母，然后从所有的字母中寻找相邻最多的字母。

定义dp数组；dp[i][j] 表示从位置 i 到位置 j 变换成全部相同相邻字母的最少交换次数。

动规公式推导：先给出公式：dp[i][j] = dp[i+1][j-1] + pos[j] - pos[i] -( j - i)

 pos数组保存每个字母在字符串的位置，想象pos数组[1,5,8,9,12,15,17]，如何才能保证变换的次数最少呢？其实这个是被证明了的，将两边的字符全部向中间靠拢交换次数是最少的。拿上面的数组举例：中间的字母位置为9,接下来进行交换。

左侧：左一位置为8，不用交换，则交换次数为0，左二位置为5，如果交换到位置9，则需要 9 - 5 -1 = 3（即5->6,6->7,7->8），对应公式中的 pos [ j ] - pos [ i ]，但是在之前的交换中8,9都已经相邻，则需要减去1，对应公式的 -( j - i）和 + dp [ i + 1 ] [ j - 1 ] 部分。以此类推，左侧总的交换次数为7。右侧同理。

看如何遍历：可以看出dp[i][j] 由 dp [ i + 1 ] [ j - 1 ]推导出来，则两层循环 i 从右向左遍历，j 由左向右遍历。

最后动规结束后判断 dp [ i ] [ j ] <= m ? 满足说明该字母符合m次交换条件，最后取每个满足条件字母的数量最大的数。

C++代码：

#include
#include
#include
#include
#include
using namespace std;

int main(){
    string str;
    int m;
    cin >> str >> m;
    int len = str.size();
    int ans = 1;
    for(char ch = 'a'; ch <= 'z'; ch++){
        vector pos;
        for(int i=0;i> dp(size,vector(size,0));
        for(int i = size-1;i>=0;i--){
            for(int j=i+1;j 
题目三：手串
 
题目描述：
 
 
 这道题目一开始理解有误，没有仔细阅读后面的样例解释，造成了错误，直接用unordered_set进行遍历寻找重复数值，最后AC了66%。
 
正确的思路应该是：给出 c 种不同颜色，可以按照样例描述那样进行求解，分别记录c种样例的位置，计算位置之间的差距，举个例子：颜色1的位置为[1,4,5]，m=2的情况，4,5相邻不符合，泛化一下就是当两个位置相减 <= m-1，则不符合。由于手串为环形，所以5,1也是相邻的不符合，泛化为：两位置相减 >= n-m+1,不符合。
 
C++代码：
 
#include 
#include 

using namespace std;

int n, m, c, num_i, kind, sum;

bool check(int n, int m, vector& posi){
    if(posi.size() == 1){
        return true;
    }
    for(int i = 0; i < posi.size(); i++){
        for(int j = i + 1; j < posi.size(); j++){
            int dis = abs(posi[i]-posi[j]);
            if( dis <= m-1 || n - dis <= m-1){
                return false;
            }
        }
    }
    return true;
    
}
int main()
{
    cin >> n >> m >> c;
    vector> pos(c + 1);

    for (int i = 1; i <= n; i++) {
        cin>>num_i;
        while(num_i--){
            cin>>kind;
            pos[kind].push_back(i);
        }
    }
    for(int i = 1; i <= c; i++ ){
        if(!check(n,m,pos[i])){
            sum++;
        }
    }
    cout< 
错误C++代码：
 
#include
#include
#include
using namespace std;

int main(){

    int n,m,c;
    cin >> n >> m >> c;
    vector> nums;
    vector one;
    int temp;
    for(int i=0; i> temp){
            one.push_back(temp);
            if( cin.get() == 'n'){
                break;
            }
        }
        nums.push_back(one);
        one.clear();
    }

    unordered_set unset;
    unordered_set sameelement;
    unordered_set allerror;
    int res = 0;
    for(int i=0;i