【字节跳动】算法岗笔试 100 20 100 70
本来看到题目觉得还好，结果第二题卡死了，还是太菜
第一题豆油瓶，很朴素统计之后>=3的存成邻接表，dfs就可以了
第二题花园，通项写错了，看大佬门说是卡特兰数，我也想求解释
第三题2048，分四种情况照着实现就好，四种情况比较类似改改索引就行
第四题天上糖果，只写了暴力解，辗转相除+邻接表+dfs，过70%，后面都卡在第二题了也没优化
楼下放代码
#字节跳动##笔试题目##算法工程师#
2019-08-26 10:17 已编辑 拼多多_推荐_算法工程师
关注
全部评论
Blue5437 楼主
楼主 拼多多_推荐_算法工程师
顺便求大佬给我讲下第二题卡特兰数怎么找出来的
RussellV587
东南大学 Java
第三题过了90...
Blue5437 楼主
楼主 拼多多_推荐_算法工程师
第四题： int gcd(int a, int b) { if (a < b) swap(a, b); if (a % b == 0) return b; else return gcd(b, a % b); } int main() { int n; cin >> n; vector<int> candy(n); for (int i = 0; i < n; i++) cin >> candy[i]; vector<vector<int>> neigh(n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (gcd(candy[i], candy[j]) > 1) { neigh[i].push_back(j); neigh[j].push_back(i); } } } vector<bool> flag(n, false); int res = 0; for (int i = 0; i < n; i++) { if (flag[i] == false) { int sum = 0; queue<int> q; q.push(i); flag[i] = true; while (!q.empty()) { int cur = q.front(); sum++; q.pop(); for (int j = 0; j < neigh[cur].size(); j++) { if (flag[neigh[cur][j]] == false) { q.push(neigh[cur][j]); flag[neigh[cur][j]] = true; } } } res = max(res, sum); } } cout << res << endl; system("pause"); return 0; }
Blue5437 楼主
楼主 拼多多_推荐_算法工程师
第三题： int main() { int n; cin >> n; vector<vector<int>> a(4, vector<int>(4)); for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) cin >> a[i][j]; if (n == 1) { for (int j = 0; j < 4; j++) { int ll = 0; for (int i = 0; i < 4; i++) { if (a[i][j] == 0) continue; if (i + 1 < 4 && a[i][j] == a[i + 1][j]) { a[i][j] *= 2; a[i + 1][j] = 0; } swap(a[i][j], a[ll][j]); ll++; } } } else if (n == 2) { for (int j = 0; j < 4; j++) { int ll = 3; for (int i = 3; i >= 0; i--) { if (a[i][j] == 0) continue; if (i - 1 >= 0 && a[i][j] == a[i - 1][j]) { a[i][j] *= 2; a[i - 1][j] = 0; } swap(a[i][j], a[ll][j]); ll--; } } } else if (n == 3) { for (int i = 0; i < 4; i++) { int ll = 0; for (int j = 0; j < 4; j++) { if (a[i][j] == 0) continue; if (j + 1 < 4 && a[i][j] == a[i][j + 1]) { a[i][j] *= 2; a[i][j + 1] = 0; } swap(a[i][j], a[i][ll]); ll++; } } } else if (n == 4) { for (int i = 0; i < 4; i++) { int ll = 3; for (int j = 3; j >= 0; j--) { if (a[i][j] == 0) continue; if (j - 1 >= 0 && a[i][j] == a[i][j - 1]) { a[i][j] *= 2; a[i][j - 1] = 0; } swap(a[i][j], a[i][ll]); ll--; } } } for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) cout << a[i][j] << ' '; cout << endl; } system("pause"); return 0; }
Blue5437 楼主
楼主 拼多多_推荐_算法工程师
第一题： int main() { int n; cin >> n; vector<vector<int>> a(n, vector<int>(n)); vector<vector<int>> neigh(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; if (a[i][j] >= 3) neigh[i].push_back(j); } } vector<bool> flag(n, false); int res = 0; for (int i = 0; i < n; i++) { if (flag[i] == false) { res++; flag[i] = true; queue<int> q; q.push(i); while (!q.empty()) { int cur = q.front(); q.pop(); for (int j = 0; j < neigh[cur].size(); j++) { if (flag[neigh[cur][j]] == false) { flag[neigh[cur][j]] = true; q.push(neigh[cur][j]); } } } } } cout << res << endl; system("pause"); return 0; }
相关推荐
，养生