Programing Problems from ByteDance

One apple a day keeps doctor away, and one program a day keeps bug(hair) away.

变身程序员

Sourcce: 字节跳动19春招研发第二次在线笔试-C卷
Time Limit: C/C++ 5s, Other 10s
Space Limit: C/C++ 262144k, Other 524288k
64bit IO Format: %lld

Description Of Topic

公司的程序员不够用了，决定把产品经理都转之变为程序员以解决开发时长问题。在给定的矩形网格中，每个单元格可以有一下三个值之一：

值0代表空单元格；
值1代表产品经理；
值2代表程序员；

每分钟，任何与程序员（在4个正方向上）相邻的产品经理都会变成程序员。返回直到单元格中没有产品经理为止所经过的最小分钟数。如果不可能，返回-1。

Description Of Input

不固定多行（行数 <= 10），每行是按照空格分割的数字（不固定，每行数字个数 <= 10），其中每个数组项的取值仅为 0、1、2三种。空行则输入结束。

Description Of Output

如果能够将所有产品经理变成程序员，则输出最小的分钟数。如果不能，则返回-1。

Example Of I/O

e.g.1

1
2

0 2
1 0

-1

e.g.2

1
2
3

1 2 1
1 1 0
0 1 1

e.g.3

Solution Of Question

Language: C++ 14
Time Complexity:

Space Complexity:

//
// Created by DRY on 4/14/19.
//
#include <iostream>
#include <algorithm>

using namespace std;

#define MAX_LINE_NUM 10

int main() {
    string a[MAX_LINE_NUM + 2];
    string b[MAX_LINE_NUM + 2]; // As copy of `a`.
    string zeroStr = "000000000000";
    bool one2Two, existOne, allChanged = true;
    int times, lineNUm = 2, itemNUm = 0, oneNum = 0, minuteNum = 0;

    for (int i = 1; i < MAX_LINE_NUM + 1; i++) {
        // Input one line String.
        getline(cin, a[i]);
        if (a[i].length() == 0) {
            break;
        }
        a[i] = "0" + a[i];
        a[i] = a[i] + "0";
        a[i].erase(remove(a[i].begin(), a[i].end(), ' '),
                   a[i].end());
        b[i] = a[i];
        itemNUm = a[i].length();
        lineNUm++;
        oneNum += count(a[i].begin(), a[i].end(), '1');
    }
    a[0] = a[lineNUm - 1] = b[0] = b[lineNUm - 1] = zeroStr;
    times = oneNum + 1;

    while (times--) {
        one2Two = false;
        existOne = false;
        for (int i = 1; i <= lineNUm; i++) {
            for (int j = 1; j < itemNUm - 1; j++) {
                if (a[i][j] == '2') {
                    if (a[i - 1][j] == '1') {
                        b[i - 1][j] = '2';
                        one2Two = true;
                    }
                    if (a[i + 1][j] == '1') {
                        b[i + 1][j] = '2';
                        one2Two = true;
                    }
                    if (a[i][j - 1] == '1') {
                        b[i][j - 1] = '2';
                        one2Two = true;
                    }
                    if (a[i][j + 1] == '1') {
                        b[i][j + 1] = '2';
                        one2Two = true;
                    }
                } else if (a[i][j] == '1') {
                    existOne = true;
                }
            }
        }
        if (one2Two) {
            minuteNum++;
            for (int i = 1; i < lineNUm - 1; i++) {
                a[i] = b[i];
            }
        } else if (existOne) {
            allChanged = false;
            break;
        }
    }
    // Output result of program.
    if (allChanged) {
        cout << minuteNum << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}

特征提取

Sourcce: 字节跳动19春招研发第二次在线笔试-C卷
Time Limit: C/C++ 1s, Other 2s
Space Limit: C/C++ 32768k, Other 65536k
64bit IO Format: %lld

Description Of Topic

小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪视频里挖掘一些运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个2维的vector<x,y>，如果x_1=x_2 and y_1=y_2，那么二者是同一个特征。

因此，如果猫咪特征连续一致，可以认为猫咪在运动。也就是说，如果特征<a,b>在持续帧里出现，那么它将构成特征运动。比如，特征<a,b>在第2/3/4/7/8帧出现，那么该特征将形成两个特征运动2-3-4和7-8。

现在，给定每一帧的特征，特征的数量可能不一样。小明期望能找到最长的特征运动。

Description Of Input

第一行包含一个正整数N，代表测试用例的个数。
每个测试用例的第一行包含一个正整数M，代表视频的帧数。

接下来的M行，每行代表一帧。其中第一个数字是该帧的特征个数，接下来的数字是在特征的取值；比如e.g.1的第三行里，2代表该帧有两个猫咪特征，<1,1>和<2,2>。

所有用例的输入特征总和< 100000，N满足1 <= N <= 100000，M满足1 <= M <= 100000，一帧的特征个数满足 <= 100000。特征取值均为非负整数。

Description Of Output

对每一个测试用例，输出特征运动的长度作为一行，如果没有长度大于2的特征运动，返回1。

Example Of I/O

e.g.1

特征<1,1>在连续帧中连续出现三次，相比其他特征连续出现次数大，所以输出3。

Solution Of Question

Language: C++ 14
Time Complexity:
Space Complexity:

//
// Created by DRY on 4/16/19.
//
#include <iostream>

using namespace std;

struct feature {
    int x;
    int y;
    int t; // 表示 该特征是 其所处的连续运动中 的第几个特征
};

bool featEqual(feature, feature);

void mDelete(int);

feature **featArray;
int *lenArray;

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

    while (n--) {
        maxT = 0;
        cin >> m;
        featArray = new feature *[m];
        lenArray = new int[m];

        for (int i = 0; i < m; i++) {
            cin >> lenArray[i];
            featArray[i] = new feature[lenArray[i]];

            for (int j = 0; j < lenArray[i] * 2; j++) {
                if (j % 2 == 0) {
                    cin >> featArray[i][j / 2].x;
                } else {
                    cin >> featArray[i][(j - 1) / 2].y;
                    featArray[i][(j - 1) / 2].t = 1;

                    if (i != 0) {
                        for (int k = 0; k < lenArray[i - 1]; k++) {
                            if (featEqual(featArray[i - 1][k], featArray[i][(j - 1) / 2])) {
                                featArray[i][(j - 1) / 2].t += featArray[i - 1][k].t;
                            }
                        }
                    }
                    maxT = max(maxT, featArray[i][(j - 1) / 2].t);
                }
            }
        }
        maxT = maxT > 2 ? maxT : 1;
        cout << maxT << endl;
        mDelete(m);
    }


    return 0;
}

bool featEqual(feature a, feature b) {
    return (a.x == b.x) && (a.y == b.y);
}

void mDelete(int m) {
    while (m--) {
        delete[] featArray[m];
    }
    delete[] featArray;
}

机器人跳跃

Sourcce: 字节跳动19春招研发第二次在线笔试-C卷
Time Limit: C/C++ 1s, Other 2s
Space Limit: C/C++ 32768k, Other 65536k
64bit IO Format: %lld

Description Of Topic

机器人正在玩一个基于DOS的游戏，游戏中有N+1座建筑——从0到N编号，从左到右排列。编号为0的建筑物高度为0个单位，编号为i的建筑物的高度为H(i)个单位。

起初，机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量是E，下一步它将跳到第k+1个建筑。它将会得到或失去正比与H(k+1)与E之差的能量。如果H(k+1) > E那么机器人就失去H(k+1)-E的能量值，否则它将得到E-H(k+1)的能量值。

游戏的目标是到达第N个建筑，在这个过程中，能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏？

Description Of Input

第一行输入，表示一共有N组数据。
第二行是N个空格分隔的整数，H1，H2，H3，...，Hn代表建筑物的高度。

Description Of Output

输出一个单独的数表示完成游戏所需的最少单位的初始能量。

Example Of I/O

e.g.1

1 2	5 3 4 3 2 4

e.g.2

1
2

3
4 4 4

e.g.3

1
2

3
1 6 4

Solution Of Question

Language: C++ 14
Time Complexity:
Space Complexity:

//
// Created by DRY on 4/15/19.
//
#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int n, h;
    float minE = 0, molecule = 0, denominator = 1;
    cin >> n;
    
    while (n--) {
        cin >> h;
        molecule = molecule * 2 + h;
        denominator = denominator * 2;
        minE = max(minE, ceil(molecule / denominator));
    }
    cout << minE;
    return 0;
}

旅行商问题

Sourcce: 字节跳动19春招研发第二次在线笔试-C卷
Time Limit: C/C++ 1s, Other 2s
Space Limit: C/C++ 32768k, Other 65536k
64bit IO Format: %lld

Description Of Topic

小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后在回到北京，每个城市之间均乘坐高铁，且么个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费的花销。

Description Of Input

城市个数n（1 < n <= 20，包括北京）
城市间的车票价钱n行n列的矩阵m[n][n]

Description Of Output

最小车费花销s

Example Of I/O

e.g.1

该例子中，共4个城市，城市1和城市1的车费为 0，城市 1和城市2之间的车费为 2，城市1和城市3之间的车费为 6，城市1和城市4之间的车费为 5，依次类推。假设任意两个城市直接均有单程票可购买，且票价在1000元以内，无需考虑极端情况。

Solution Of Question

Language: C++ 14
Time Complexity:

Space Complexity:

//
// Created by DRY on 2019/4/15.
//
#include <iostream>
#include <climits>

using namespace std;
int **costArray;
int *city;
int minCost = INT32_MAX;

void mDelete(int);

void mTSP(int, int);

int main() {
    int n;
    cin >> n;
    city = new int[n + 1];
    costArray = new int *[n];

    for (int i = 0; i < n; i++) {
        city[i] = i;
        costArray[i] = new int[n];
        for (int j = 0; j < n; j++) {
            cin >> costArray[i][j];
        }
    }
    mTSP(n, 0);
    cout << minCost;
    mDelete(n);
    return 0;
}

void mDelete(int n) {
    while (n--) {
        delete[]costArray[n];
    }
    delete[]costArray;
    delete[]city;
}

void mTSP(int n, int s) {
    if (s == n) {
        int cost = 0;
        city[n] = city[0];

        for (int i = 0; i < n; i++) {
            // cout << city[i] << " ";
            cost += costArray[city[i]][city[i + 1]];
        }
        // cout << city[n] << "    " << cost << endl;
        minCost = min(minCost, cost);
    } else {
        for (int i = s; i < n; i++) {
            int t = city[i];
            city[i] = city[s];
            city[s] = t;
            mTSP(n, s + 1);
            city[s] = city[i];
            city[i] = t;
        }
    }
}

过河问题

Sourcce: 字节跳动19春招研发第二次在线笔试-C卷
Time Limit: C/C++ 1s, Other 2s
Space Limit: C/C++ 32768k, Other 65536k
64bit IO Format: %lld

Description Of Topic

有n个人要过河，但河边只有1只船。船每次最多坐3个人，每个人单独坐船过河的时间为a[i]，多人一起坐船时，过河时间为他们所有人中最长的过河时间。

为了安全起见，要求每次至少有2个人才能过河。问最短需要多少时间才能把所有人送过河。

Description Of Input

第一行是整数m，表示测试样例个数。

每个测试用例的第一行是一个正整数n，表示参加过河的人数（2 <= n <= 100000）。

第二行是n个正整数a[i]（0 < a[1] < 100000）,表示n个人单独过河的时间。

Description Of Output

对每个测试样例，输出最少的过河时间。

Example Of I/O

e.g.1

1
2

2
3

Solution Of Question

Language: C++ 14
Time Complexity:
Space Complexity:

//
// Created by DRY on 4/16/19.
//
#include <iostream>

using namespace std;

int main() {
    int m, n, minT, t;
    int *a;
    cin >> m;

    while (m--) {
        minT = 0;
        cin >> n;
        a = new int[n];

        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (i != 0) {
                for (int j = 0; j < i; j++) {
                    if (a[i] < a[j]) {
                        t = a[i];
                        for (int k = i; k >= j + 1; k--) {
                            a[k] = a[k - 1];
                        }
                        a[j] = t;
                        break;
                    }
                }
            }
        }

        for (int i = n - 1; i > 3; i = i - 2) {
            minT += min(a[1] + a[i - 1] + a[1] + a[i], a[2] + a[0] + a[i] + a[2]);
        }
        minT += a[2];

        if (n == 2 || n == 3) {
            minT = a[n - 1];
        } else if (n == 4) {
            minT = a[1] + a[2] + a[3];
        }

        cout << minT << endl;
        delete[] a;
    }
    return 0;
}

变身程序员

Description Of Topic

Description Of Input

Description Of Output

Example Of I/O

Solution Of Question

特征提取

Description Of Topic

Description Of Input

Description Of Output

Example Of I/O

Solution Of Question

机器人跳跃

Description Of Topic

Description Of Input

Description Of Output

Example Of I/O

Solution Of Question

旅行商问题

Description Of Topic

Description Of Input

Description Of Output

Example Of I/O

Solution Of Question

过河问题

Description Of Topic

Description Of Input

Description Of Output

Example Of I/O

Solution Of Question

Reference