ByteDance 2019 春招题目
2024-09-06 04:46:40
牛客网字节跳动笔试真题：https://www.nowcoder.com/test/16516564/summary
分了 2 次做，磕磕碰碰才写完，弱鸡悲鸣。
1. 聪明的编辑
题目：Link .
两遍扫描
两遍扫描：第一次处理情况 1 ，第二次处理情况 2 。
// 万万没想到之聪明的编辑
// https://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;
}
}
自动机
由题意可得以下有限自动机：
每个状态的转移条件为：当前字符与上一个字符是否相等。
// 万万没想到之聪明的编辑
// https://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).
代码：
// 雀魂启动！
// https://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 。
代码：
// 特征提取
// https://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 循环，浪费了一次提交 ）。
// 硬币找零
// https://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;
}
最新文章
- Windows 网络通讯开发
- xml_TO_object
- Angular过滤器
- linux 内核邮件列表
- 使用jQuery，实现完美的表单异步提交
- 关于offer选择
- ios 面试题 0
- 超强JavaScript编辑器WebStorm代码提示迟缓问题及其它想到的
- Discuz! 7.x 反射型xss
- Linux学习笔记：nginx基础
- 剑指Offer 8. 跳台阶 （递归）
- 【BZOJ】4011: [HNOI2015]落忆枫音
- 面向对象——单例模式，五种方式
- Android GetMethodID 函数的说明
- 【Unity/Kinect】Kinect入门——项目搭建
- Spring 父子容器
- 基于C#的微信公众平台开发系列1
- 项目中整合第三方插件与SpringMVC数据格式化关于ip地址
- MySQL之函数
- IntelliJ IDEA开发工具println报错的解决方法