字节2020笔试题总结

第一题：

这种字符串模式匹配的题经常采用有限状态机的方法，差一点的方法是双指针，一般会更加麻烦，要熟悉状态机的使用。
我的代码：

#include<string>
#include<vector>
#include<iostream>
using namespace std;
int main() {
    int n = 0;
    cin>>n;
    while (n--) {
        string s;
        cin>>s;
        char cur = s[0];
        string res = "";
        res += cur;
        int state = 0;
        for (int i = 1; i < s.size(); i++) {
            if (state == 0) {
                res += s[i];
                if (s[i] == cur) state = 1;
                else {
                    cur = s[i];
                    continue;
                }
            }
            else if (state == 1) {
                if (s[i] == cur) continue;
                else {
                    state = 2;
                    res += s[i];
                    cur = s[i];
                }
            }
            else if (state == 2) {
                if (cur == s[i]) continue;
                else {
                    state = 0;
                    cur = s[i];
                    res += s[i];
                }
            }
        }
        cout<<res<<endl;
    }

    return 0;
}

第二题：

这道题可以利用双指针来做，第一个指针指向A特工的位置，第二个指针去找A特工在该位置下另外两名特工的最远位置，利用组合数求解总次数后取模即可。

#include<string>
#include<vector>
#include<iostream>
using namespace std;
int main() {
    long long n = 0, dis = 0;
    cin>>n;
    cin>>dis;
    long long left = 0;
    long long right = 0;
    vector<int> buildings(n);
    long long res = 0;
    for (long i = 0; i < n; i++) cin >> buildings[i];
    while (left < n - 2) {
        if (right < n && buildings[right] - buildings[left] <= dis) right ++;
        else {
            res += (right - left - 1)*(right - left - 2)/2;
            left ++;
        }
    }
    cout<<res%99997867;
    return 0;
    }

第三题：

这种游戏一般由于数据规模较小，可以利用回溯来暴力穷举可能，关键点在于每次都先加入第14张牌，然后再判断是否可行。

#include<string>
#include<vector>
#include<iostream>
using namespace std;
void dfs(vector<int>& result, unordered_map<int, int>& fly, unordered_map<int, int>& rest, int pos) {
    if (pos == 12) {

        return;
    }
    for (int i = 1; i <= 9; i++) {
        if (fly[i] >= 2) {
            fly[i] -= 2;
            dfs(result, fly, pos + 2);
            fly[i] += 2;
        }
        if (i <= 7 && fly[i] && fly[i+1] && fly[i+2]) {
            fly[i] --;
            fly[i+1] --;
            fly[i+2] --;
            dfs(result, fly, pos + 3);
            fly[i] ++;
            fly[i+1] ++;
            fly[i+2] ++;
        }
    }
}
int main() {
    unordered_map<int, int> fly;
    for (int i = 1; i <= 13; i ++) {
        int tmp = 0;
        cin>>tmp;
        fly[tmp] ++;
    }
    unordered_map<int, int> rest;
    for (int i = 1; i <= 9; i++) {
        rest[i] = 4 - fly[i];
    }
    vector<int> result;
    dfs(1)
    return 0;
    }

第四题：

这道题可以采用的数据结构包括哈希表和map。
利用哈希表无法处理pair，因此题解采用了map，代码如下：

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
    int n, m;
    cin >> n;

    int len;
    pair<int, int> xy;

    while (n--)
    {
        cin >> m;

        int maxCnt = 0;
        map<pair<int, int>, int> preFeaTimes;
        map<pair<int, int>, int> feaTimes;
        while (m--)
        {
            cin >> len;
            for (int i = 0; i < len; i++)
            {
                cin >> xy.first >> xy.second;

                if (preFeaTimes.count(xy))
                    feaTimes[xy] = preFeaTimes[xy] + 1;
                else
                    feaTimes[xy] = 1;

                if (feaTimes[xy] > maxCnt)
                    maxCnt = feaTimes[xy];
            }
            preFeaTimes.clear();
            preFeaTimes.swap(feaTimes);
        }
        cout << maxCnt << endl;
    }

    return 0;
}

我的方法如下：

#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;
int check(vector<int>& seq) {//0 1 2 6 7 
    int tmp = -1;
    for (int i = 0; i < seq.size(); ) {
        int cur = i;
        while (cur < seq.size() - 1 && seq[cur + 1] - seq[cur] == 1) cur ++;
        tmp = max(tmp, cur - i + 1);
        if (i == cur) i ++;
        else i = cur;
    }
    return tmp;
}
int main() {
    int loop = 0;
    cin >> loop;
    while (loop --) {
        int frame = 0;
        cin >> frame;
        unordered_map<int, unordered_map<int, vector<int> > > map;
        for (int i = 0; i < frame; i++) {
            int sz = 0;
            cin >> sz;
            while (sz --) {
                int a, b;
                cin >> a;
                cin >> b;
                map[a][b].push_back(i);
            }
        }
        int resVal = -1;
        for (auto m:map) {
            for (auto n:m.second) {
                int cur = check(n.second);
                resVal = max(resVal, cur);
            }
        }
    cout<< resVal<<endl;
    }
    return 0;
}

第五题：

旅行商问题，利用动态规划可以求解
状态设置得比较有意思，利用二进制得知识求解

#include<vector>
#include<iostream>
using namespace std;
int helper(vector<vector<int>>& dis, vector<vector<int>>& dp, int city, int mode, int n) {
    if (dp[city][mode] != 20001) return dp[city][mode];
    if (mode == ((1<<n) - 1)) return dis[city][0];
    for (int i = 1, index = 0; i < (1<<n); i<<=1, index ++) {//一定要<<=而不是<<
        if ((mode | i) != mode) {
            dp[city][mode] = min(dp[city][mode], dis[city][index] + helper(dis, dp, index, (mode|i), n));
        }
    }
    return dp[city][mode];
}
int main() {
    int n = 0;
    cin >> n;
    vector<vector<int>> dis(n, vector<int> (n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cin>>dis[i][j];
    }
    int k = (1 << n) + 1;
    vector<vector<int>> dp(n, vector<int>(k, 20001));
    cout<<helper(dis, dp, 0, 1, n);
    return 0;
}

第六题：

传统的动态规划，找零钱问题

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int n = 0;
    cin>>n;
    int dp[1024 - n + 1];
    dp[0] = 0;
    for (int i = 1; i <= 1024 - n; i++) {
        dp[i] = 2048;
        dp[i] = min(dp[i], dp[i - 1] + 1);
        if (i >= 4) dp[i] = min(dp[i], dp[i - 4] + 1);
        if (i >= 16) dp[i] = min(dp[i], dp[i - 16] + 1);
        if (i >= 64) dp[i] = min(dp[i], dp[i - 64] + 1);
    }
    cout<<dp[1024 - n];
    return 0;
}

第七题：

类似力扣地下城问题，要求反向dp

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int n = 0;
    cin>>n;
    vector<int> H(n);
    for(int i = 0; i < n; i++) cin>>H[i];
    vector<int> dp(n + 1, 0);
    for (int i = n - 1; i >= 0; i --) dp[i] = (dp[i + 1] + H[i])/2;
    cout<<dp[0] + 1;
    return 0;
}