ByteDance 2019 春招題目

2021 年 1 月 30 日
筆記
面試機考

牛客網字節跳動筆試真題：//www.nowcoder.com/test/16516564/summary

分了 2 次做，磕磕碰碰才寫完，弱雞悲鳴。

1. 聰明的編輯

題目：Link .

兩遍掃描

兩遍掃描：第一次處理情況 1 ，第二次處理情況 2 。

// 萬萬沒想到之聰明的編輯
// //www.nowcoder.com/test/question/42852fd7045c442192fa89404ab42e92?pid=16516564&tid=40818118
#include <string>
#include <iostream>
using namespace std;
string stupid_check(string &s)
{
    for (int i = 0; i + 1 < (int)s.length(); i++)
    {
        if (s[i] == s[i + 1])
        {
            if (i + 2 < (int)s.length() && s[i + 1] == s[i + 2])
                s.erase(s.begin() + i + 2), i--;
        }
    }
    for (int i = 0; i + 3 < (int)s.length(); i++)
    {
        if (s[i] == s[i + 1] && s[i + 2] == s[i + 3])
            s.erase(s.begin() + i + 3);
    }
    return s;
}
int main()
{
    int n;
    cin >> n;
    cin.ignore();
    while (n--)
    {
        string s;
        cin >> s;
        cin.ignore();
        cout << stupid_check(s) << endl;
    }
}

自動機

由題意可得以下有限自動機：

每個狀態的轉移條件為：當前字元與上一個字元是否相等。

// 萬萬沒想到之聰明的編輯
// //www.nowcoder.com/test/question/42852fd7045c442192fa89404ab42e92?pid=16516564&tid=40818118
#include <string>
#include <iostream>
using namespace std;
string stupid_check(const string &s)
{
    int len = s.length();
    string result = "";
    char cur = s[0], last = s[0];
    int state = 0;
    result.append(1, cur);
    for (int i = 1; i < len; i++)
    {
        cur = s[i];
        switch (state)
        {
        case 0:
        {
            if (cur == last) state = 1;
            else state = 0;
            result.append(1, cur);
            break;
        }
        case 1:
        {
            if (cur == last) state = 1;
            else state = 2, result.append(1, cur);
            break;
        }
        case 2:
        {
            if (cur == last) state = 2;
            else state = 0, result.append(1, cur);
            break;
        }
        }
        last = cur;
    }
    return result;
}
int main()
{
    int n;
    cin >> n;
    cin.ignore();
    while (n--)
    {
        string s;
        cin >> s;
        cin.ignore();
        cout << stupid_check(s) << endl;
    }
}

2. 抓捕孔連順

題目：Link.

滑動窗口的思想，\(O(n^2)\) 的解法超時。

#include <iostream>
#include <vector>
using namespace std;
const uint64_t mod = 99997867;
int main()
{
    ios::sync_with_stdio(0);
    int n, d;
    cin >> n >> d;
    cin.ignore();
    vector<int> pos(n, 0);
    for (int i = 0; i < n; i++)
        cin >> pos[i];
    cin.ignore();

    uint64_t ans = 0;
    int i = 0;
    while (i + 2 < n)
    {
        int j = i + 2;
        while (j < n && ((pos[j] - pos[i]) <= d))
            j++;
        uint64_t t = j - i - 1;
        ans = (ans + t * (t - 1) / 2) % mod;
        i++;
    }
    cout << ans << endl;
}

優化一下，變成 \(O(n)\) . 注意有的地方需要用 uint64_t，用 int 會溢出導致結果錯誤。

#include <iostream>
#include <vector>
using namespace std;
const uint64_t mod = 99997867;
int main()
{
    ios::sync_with_stdio(0);
    int n, d;
    cin >> n >> d;
    cin.ignore();
    vector<int> pos(n, 0);
    uint64_t ans = 0;
    for (int i = 0, j = 0; i < n; i++)
    {
        cin >> pos[i];
        while (i >= 2 && pos[i] - pos[j] > d) j++;
        uint64_t t = i - j;
        if (t >= 2)
            ans = (ans + t * (t - 1) / 2) % mod;
        
    }
    cout << ans << endl;
}

3. 雀魂

題目：Link.

考慮暴力枚舉方法（模擬法）：

利用哈希表 table 計算 13 個數字的頻率
枚舉 1 - 9 加入 table，檢查 14 張牌是否能和牌

檢查和牌的函數 check(table)：

在 table 選取次數大於等於 2 的作為雀頭
檢查剩下的 12 張牌是否能組成 4 對順子/刻子

檢查順子/刻子的函數 sub_check(table, n)，n 表示剩下多少張牌可以檢查。枚舉 1 - 9：

如果該牌數目大於等於 3 ，說明可以組成刻子，繼續檢查 sub_check(table, n-3) .
如果 table[i], table[i+1], table[i+2] 的數量都大於 1 ，說明可以組成順子，繼續檢查 sub_check(table, n-3) .

程式碼：

// 雀魂啟動！
// //www.nowcoder.com/question/next?pid=16516564&qid=362291&tid=40818118
#include <iostream>
#include <array>
#include <vector>
using namespace std;

// 剩下的 n 張是否能組成順子或者刻子
bool sub_check(array<int, 10> &table, int n)
{
    if (n == 0) return true;
    for (int i = 1; i <= 9; i++)
    {
        if (table[i] >= 3)
        {
            table[i] -= 3;
            if (sub_check(table, n - 3)) return true;
            table[i] += 3;
        }
        if (i + 2 <= 9 && table[i] >= 1 && table[i + 1] >= 1 && table[i + 2] >= 1)
        {
            table[i]--, table[i + 1]--, table[i + 2]--;
            if (sub_check(table, n - 3)) return true;
            table[i]++, table[i + 1]++, table[i + 2]++;
        }
    }
    return false;
}
// 任意選取次數 >= 2 的牌作為雀頭
bool check(array<int, 10> table)
{
    for (int i = 1; i <= 9; i++)
    {
        if (table[i] >= 2)
        {
            table[i] -= 2;
            if (sub_check(table, 12)) return true;
            table[i] += 2;
        }
    }
    return false;
}
int main()
{
    vector<int> result;
    array<int, 10> table = {0};
    int val;
    for (int i = 0; i < 13; i++)
    {
        cin >> val;
        table[val]++;
    }
    for (int x = 1; x <= 9; x++)
    {
        if (table[x] >= 4) continue;
        table[x]++;
        if (check(table)) result.push_back(x);
        table[x]--;
    }
    if (result.size() == 0) result.push_back(0);
    for (int x : result) cout << x << ' ';
    cout << endl;
}

4. 特徵提取

題目：Link.

用 map 記錄連續出現的次數。

具體實現細節：set 記錄本次出現的 (x, y) 。每次來一幀，如果 map 中的 feature 不在 set 中出現，說明該 feature 不是連續出現的，置為 0 。

程式碼：

// 特徵提取
// //www.nowcoder.com/question/next?pid=16516564&qid=362292&tid=40818118
#include <iostream>
#include <map>
#include <set>
using namespace std;
struct feature
{
    int x, y;
    feature(int _x, int _y) : x(_x), y(_y) {}
    bool operator<(const feature &f) const { return x < f.x || (x == f.x && y < f.y); }
};
int main()
{
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    cin.ignore();
    map<feature, int> a;
    set<feature> s;
    a.clear(), s.clear();
    int ans = 1;
    while (n--)
    {
        int frames;
        cin >> frames;
        cin.ignore();
        while (frames--)
        {
            int k, x, y;
            cin >> k;
            for (int i = 0; i < k; i++)
            {
                cin >> x >> y;
                a[feature(x, y)]++;
                s.insert(feature(x, y));
            }
            for (auto &[key, val] : a)
            {
                ans = max(ans, val);
                if (s.count(key) == 0)
                    a[key] = 0;
            }
            s.clear();
        }
    }
    cout << ans << endl;
}

5. 畢業旅行問題

題目：Link.

居然是 TSP 問題（離散數學中稱之為哈密頓迴路），我記得上課學的時候只會寫貪心 😅 。

看了題解，可以用狀態壓縮的 DP 求解。此處的最後一道題也是狀壓 DP 。

狀態定義 \(dp[s,v]\) ，\(s\) 表示沒去過的城市集合，\(v\) 表示當前所在城市。因此，\(dp[0,0]\) 表示所有城市去過，並在所在地為 0 城市，即結束狀態；\(dp[2^n-1, 0]\) 表示所有城市都沒去過，當前在 0 號城市，即開始狀態。

定義 is_visited(s, u) 為集合 s 是否包含了城市 u, 即當前狀態是否已經訪問過 u .

定義 set_zero(s, k) 把 s 的從左往右數的第 k 比特置為 1 ，表示城市 k 已訪問。

時間複雜度 \(O(n^2\cdot2^n)\)，空間複雜度 \(O(n \cdot 2^n)\) .

程式碼：

#include <iostream>
#include <vector>
using namespace std;
const int N = 21;
int graph[N][N] = {{0}};
int tsp(int n)
{
    vector<vector<int>> dp((1 << n), vector<int>(n, 0x3f3f3f3f));
    auto is_visited = [](int s, int u) { return ((s >> u) & 1) == 0; };
    auto set_zero = [](int s, int k) { return (s & (~(1 << k))); };
    dp[(1 << n) - 1][0] = 0;
    // double 'for' loop to fill the dp
    for (int s = (1 << n) - 1; s >= 0; s--)
    {
        for (int v = 0; v < n; v++)
        {
            // for current 's', try all the cities
            for (int u = 0; u < n; u++)
            {
                if (!is_visited(s, u))  // if 'u' has not been visited
                {
                    int state = set_zero(s, u);
                    dp[state][u] = min(dp[state][u], dp[s][v] + graph[v][u]);
                }
            }
        }
    }
    return dp[0][0];
}
int main()
{
    int n;
    cin >> n;
    cin.ignore();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cin >> graph[i][j];
        cin.ignore();
    }
    cout << tsp(n) << endl;
}

6. 找零

題目：Link.

老水題了。不過要注意的是：這裡沒有 2 和 8 面值的硬幣（原來寫了個 for 循環，浪費了一次提交 😅 ）。

// 硬幣找零
// //www.nowcoder.com/question/next?pid=16516564&qid=362294&tid=40818118
#include <iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    cin.ignore();
    n = 1024 - n;
    int ans = n / 64;
    n %= 64;
    ans += n / 16;
    n %= 16;
    ans += n / 4;
    n %= 4;
    ans += n;
    cout << ans << endl;
}

Tags: 面試機考