美团2024年春招第一场笔试解析
嗨~我是可拟雀,一个全栈开发工程师,毕业于某985大学,目前供职于bat某大厂核心部门后端。每天分享最新面经答案,希望在大环境不好的当下能帮到你,让你多积累面试经验。免费分享个人学习2个月速通大厂路线(请看认证标)
其他群友有补充Java等语言版本请私信我加上去
先对输入字符串进行处理,然后再使用二维前缀和去统计子区域中1的个数,然后再逐步遍历k大小的子区域进行判断即可。
#include<bits/stdc++.h> using namespace std; const int N = 1000; int n; char str[N][N]; int m[N][N], s[N][N]; int ans[N]; int GetPreSub(int x1, int y1, int x2, int y2) { return s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1]; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> str[i]; for (int i = 0; i < n; i ++) { for (int j = 0; j < n; j ++) { if (str[i][j] == '1') { m[i + 1][j + 1] = 1; } else { m[i + 1][j + 1] = 0; } } } for (int i = 1; i <= n; i ++) { for (int j = 1; j <= n; j ++) { s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + m[i][j]; } } for (int i = 0; i < n; i ++) { for (int j = 0; j < n; j ++) { for (int k = 0; k < n; k ++) { if(i + k >= n || j + k >= n) { break; } int sub = GetPreSub(i, j, i + k, j + k); if (sub * 2 == (k + 1) * (k + 1)) { ans[k] ++; } } } } for (int i = 0; i < n; i ++) cout << ans[i] << endl; return 0; }
T2
最大最小理所应当的是当未知数分别取l和r时成立。
#include <bits/stdc++.h> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> a(n); long long tot = 0; int numa = 0; for (int i = 0; i < n; i++) { cin >> a[i]; tot += a[i]; if (a[i] == 0) numa++; } while (q--) { int l, r; cin >> l >> r; cout << numa * (long long)l + tot << " " << numa * (long long)r + tot << "\n"; } return 0; }
T3
先扫描一遍原本有n个M和T,然后总数减一下,剩下m个,再看可以添加k个,返回n+min(m,k)
#include <bits/stdc++.h> using namespace std; int main() { int n, k; cin >> n >> k; string s; cin >> s; int ans = 0; int tot = 0; for(int i = 0; i < n; i++) { char c = s[i]; if(c != 'M' && c != 'T') { tot++; } } if(k >= tot) { cout << n << "\n"; } else { cout << n - tot + k << "\n"; } return 0; }
T4
我们可以使用并查集(Union-Find)数据结构。并查集是处理不相交集合合并及查询问题的一种有效数据结构,非常适合用于解决动态连通性问题。在这个场景中,每个人可以看作一个节点,朋友关系可以看作是节点间的边。当两个人淡忘了他们的朋友关系时,我们就移除这条边;查询两个人是否能通过朋友介绍互相认识,实际上就是查询这两个节点是否在同一个连通分量中。
#include <iostream> #include <vector> #include <unordered_map> using namespace std; // 并查集类 class UnionFind { private: unordered_map<int, int> parent; // 存储每个节点的父节点 unordered_map<int, int> rank; // 存储每个根节点的秩(用于优化) public: // 查找节点x的根节点 int find(int x) { if (parent.find(x) == parent.end()) parent[x] = x, rank[x] = 0; // 如果节点未出现过,初始化 if (x != parent[x]) parent[x] = find(parent[x]); // 路径压缩 return parent[x]; } // 将节点x和节点y所在的集合合并 void unite(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { // 按秩合并,保持树的平衡 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else { parent[rootY] = rootX; if (rank[rootX] == rank[rootY]) rank[rootX]++; } } } // 检查节点x和节点y是否连通 bool connected(int x, int y) { return find(x) == find(y); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; UnionFind uf; // 处理初始的朋友关系 for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; uf.unite(u, v); } // 处理事件 for (int i = 0; i < q; ++i) { int op, u, v; cin >> op >> u >> v; if (op == 1) { // 如果是淡忘关系事件,由于题目要求仅在查询中使用,并查集操作不涉及“删除”操作,因此忽略 } else if (op == 2) { // 如果是查询事件,输出查询结果 cout << (uf.connected(u, v) ? "Yes" : "No") << '\n'; } } return 0; }
T5
首先,想要得到末尾是0就必须有一对2和5,简单的数学知识。使用前缀和+双指针,可以优化到O(n)复杂度。
#include <iostream> #include <vector> using namespace std; // 寻找有多少个2 long long getTwoNum(long long x) { long long ct = 0; while (x % 2 == 0) { ct++; x /= 2; } return ct; } // 寻找有多少个5 long long getFiveNum(long long x) { long long ct = 0; while (x % 5 == 0) { ct++; x /= 5; } return ct; } int main() { long long n, k; while (cin >> n >> k) { vector<long long> arrsTwoNum(n, 0), arrsFiveNum(n, 0); long long totTwoNum = 0, totFiveNum = 0; for (long long i = 0; i < n; ++i) { long long x; cin >> x; arrsTwoNum[i] = getTwoNum(x); arrsFiveNum[i] = getFiveNum(x); totTwoNum += arrsTwoNum[i]; totFiveNum += arrsFiveNum[i]; } if (totTwoNum < k || totFiveNum < k) { cout << 0 << endl; return 0; } long long rangeMaxTwoNum = totTwoNum - k; // 最大可用删除的2的数量 long long rangeMaxFiveNum = totFiveNum - k; // 最大可用删除的5的数量 long long ans = 0; // 前缀和,统计到i为止2和5的数量 for (long long i = 1; i < n; ++i) { arrsTwoNum[i] += arrsTwoNum[i - 1]; arrsFiveNum[i] += arrsFiveNum[i - 1]; } long long j = 0; // 快指针 while (j < n && arrsTwoNum[j] <= rangeMaxTwoNum && arrsFiveNum[j] <= rangeMaxFiveNum) { j++; } ans += j; // 每次快指针使得段内2和5超标,更新一次ans for (long long i = 0; i < n; i++) { while (j < n && arrsTwoNum[j] - arrsTwoNum[i] <= rangeMaxTwoNum && arrsFiveNum[j] - arrsFiveNum[i] <= rangeMaxFiveNum) { j++; } ans += (j - i - 1); } cout << ans << endl; } return 0; }
大厂校招实习最新面经解析 文章被收录于专栏
专注于最新各大厂最新面筋解析