sitJac's Blog
0%

字节跳动2022春招研发笔试第六场4.10-算法方向

Posted on In
  • 涨潮淹没岛屿考察深度优先搜索（DFS）在二维网格上的应用，主要目标是找到二维网格中的岛屿（由1组成的连通区域），并将与边界相连的岛屿“淹没”（将1变为0）
  • 网球装箱、网球装箱主要考察排序（Sorting）和线性扫描（Linear Scan）相关知识点以及对一维、二维数组的基本读取和操作。
  • 集齐卡牌用了贪心算法（Greedy Algorithm）和哈希表（Hash Table）的数据结构知识点来解决问题，每次都选择覆盖剩余最多元素的商品，直到所有元素都被覆盖。

涨潮淹没岛屿

有一个矩阵，矩阵中每个数字代表一块海洋/土地块（数字1代表土地，数字0代表海洋），每块土地仅与上下左右四块其他的土地块/海洋接壤。矩阵边缘以外视为土地。

涨潮时，与海洋接壤两个或者两格以上的土地块将被淹没为海洋。请返回涨潮后的矩阵。

输入描述：

1.第一行包含一个数字T，代表总共有T个案例。
2.以下重复T次：
a. 第一行包含空格分隔的两个数字M和N，代表矩阵高M、宽N。
b. 后续M行，每一行都包含一个长度为N的，由0/1组成的数组。

输出描述：

返回涨潮后的矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/*
Input:
2
3 4
1011
0000
0010
1 2
01

Output:
0001
0000
0000
01
*/

#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    void dfs(vector<vector<int>>& grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != 1)
            return;
        grid[i][j] = 2;
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }

    vector<vector<int>> floodIslands(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i * j == 0 || i == m - 1 || j == n - 1 || grid[i][j] == 0)
                    dfs(grid, i, j);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = grid[i][j] == 2 ? 1 : 0;
            }
        }
        return grid;
    }
};

int main() {
    int T;
    cin >> T;
    while (T--) {
        int M, N;
        cin >> M >> N;
        vector<vector<int>> grid(M, vector<int>(N));
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                cin >> grid[i][j];
            }
        }
        Solution solution;
        grid = solution.floodIslands(grid);
        for (const auto& row : grid) {
            for (int val : row) {
                cout << val;
            }
            cout << endl;
        }
    }
    return 0;
}

机器人能否走到最后

小明设计了一个简单的机器人，它每移动一步至少需要消耗一个能量值。例如当小明给它输入5个能量值的时候，它可能会走0步（也就是不动），也可能走1步，但是不会走超过5步。
小明希望机器人往前走N步，每个位置有不同的能量值，每次消耗了能量值之后可以往前走几步，到达新的位置之后，可以继续消耗当前位置的能量值，继续往前。如果当前位置的能量值为0，那么机器人就无法行动了。
小明现在的疑惑是，机器人是否有机会移动到最后一个指令，你可以帮他计算一下吗？

输入描述：

第一行N代表总共有多少个位置，第二行是空格分割的每个位置能量值，总共有N个。

输出描述：

判断机器人是否能够到达最后一个位置，如果可以到达的话，输出TRUE否则输出FALSE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
Input: 
5
2 3 1 1 4
Output:
TRUE
Explain:
2→3→4 √

Input:
5
3 2 1 0 4
Output:
FALSE
Explain:
3→0 ×
*/

#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    Solution solution;
    cout << (solution.canJump(nums) ? "TRUE" : "FALSE") << endl;
    return 0;
}

网球装箱

字节网球部门有一套特殊的装箱姿势：首先取出N个网球桶和K个网球，给每个网球依次印上编号（1,2,3,…,k）。接着按照编号从小到大的顺序依次取出每个网球，对于每个网球，随机找一个网球桶，从任意一个开口塞进去。
波波现在要对一批产品进行质量检测，请帮他判断这箱网球是否严格遵循了上述装箱流程。

输入描述：

第一行为一个整数T表示test case数量
对于每组输入数据，第一行为一个整数N，表示网球桶数
接下来N行，每行第一个数字为K1，表示第1个桶包含多少网球；后面跟K1个数字，表示该桶中每个网球的编号（按顺序）。
输入保证每组test case中不会有两个网球编号相同，且网球编号一定会覆盖1-k
1≤T≤10
1≤N<10
0≤Ki≤1e5
1≤∑Ki≤1e7

输出描述:

对于每组测试数据，输出一行。如果判断装箱方式符合规定，输出数字1，否则输出数字0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*
Input:
2
1
1 1
2
5 5 4 3 2 1
4 9 6 7 8
Output:
1
1

Input:
1
3
0
5 1 2 5 4 3
4 6 9 8 7
Output:
0
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    bool check(const vector<int>& balls) {
        for (int i = 1; i < balls.size(); ++i) {
            if (balls[i] < balls[i - 1]) {
                return false;
            }
        }
        return true;
    }

    int minBalls(int T, vector<vector<int>>& data) {
        while (T--) {
            vector<int> balls;
            for (int i = 0; i < data.size(); ++i) {
                for (int j = 0; j < data[i].size(); ++j) {
                    balls.push_back(data[i][j]);
                }
            }
            sort(balls.begin(), balls.end());
            return check(balls) ? 1 : 0;
        }
        return 0;
    }
};

int main() {
    int T;
    cin >> T;
    vector<vector<int>> data;
    while (T--) {
        int N;
        cin >> N;
        vector<int> balls;
        for (int i = 0; i < N; ++i) {
            int K;
            cin >> K;
            for (int j = 0; j < K; ++j) {
                int ball;
                cin >> ball;
                balls.push_back(ball);
            }
        }
        data.push_back(balls);
    }
    Solution solution;
    cout << solution.minBalls(T, data) << endl;
    return 0;
}

集齐卡牌

某商品在促销时推出了集换活动，集齐全套卡片即可获得神秘大奖，集换活动的规侧如下：
1.每次购买都可以获得三张集换卡
2.一套集换卡中包含10种不同的卡片（用0-9标识）假设你知道每件商品中包含的集换卡，请判断输出集齐整套卡片最少需要购买几件商品

输入描述：

输入分为一行，每行包含M个字符串，每个字符串代表一件商品，每个字符串由3个数字组成，不同的数字代表不同的集换卡。

输出描述：

如果不能集齐，输出-1，否则输出集齐一套集换卡所需购买商品数量的最小值.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*
Input:
000 111 222 345 678 891
Output:
5
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int minGoods(string s, vector<string>& goods) {
        size_t pos = 0;
        while ((pos = s.find(' ')) != string::npos) {
            goods.push_back(s.substr(0, pos));
            s.erase(0, pos + 1);
        }
        goods.push_back(s);

        vector<vector<int>> counts(goods.size(), vector<int>(10, 0));
        for (int i = 0; i < goods.size(); ++i) {
            for (char c : goods[i]) {
                counts[i][c - '0'] = 1;
            }
        }

        vector<int> total(10, 0);
        for (const auto& count : counts) {
            for (int i = 0; i < 10; ++i) {
                total[i] += count[i];
            }
        }

        if (*min_element(total.begin(), total.end()) == 0) {
            return -1;
        }

        int res = 0;
        unordered_set<int> remaining({0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
        while (!remaining.empty()) {
            int max_count = 0;
            int max_index = -1;
            for (int i = 0; i < counts.size(); ++i) {
                int count = 0;
                for (int j : remaining) {
                    count += counts[i][j];
                }
                if (count > max_count) {
                    max_count = count;
                    max_index = i;
                }
            }
            for (int i = 0; i < 10; ++i) {
                if (counts[max_index][i] == 1) {
                    remaining.erase(i);
                }
            }
            ++res;
        }

        return res;
    }
};

int main() {
    string s;
    getline(cin, s);
    vector<string> goods;
    Solution solution;
    cout << solution.minGoods(s, goods) << endl;
    return 0;
}