字节1022秋招笔试真题解析
- 2026-11-07 14:50:16
关注我们，每周更新两到三次大厂最新笔试题解析
前言
四道题都属于中等难度，第一题要注意是个有向图，不能一昧的从s到t，也可以借由中间节点节省时间，第二题要注意实际上就是能不能构造出一个递增数组(增量不超过2,第一个数是1或2)，使得数组的和等于x，这样我们可以先将数组初始化为(1,2,3,4,.......,n)，然后再看要加在哪些部分。第三题实际上就是一个模拟题，注意修改了当前位置所影响到的都有哪些位置即可。第四题对区间排序，然后进行利用前缀和计算区间价值，进行简单dp即可。
第一题
小红和朋友被困在了迷宫里，迷宫有n 个传送阵，每个传送阵都有一个编号i(编号从1到n)，编号为i的传送阵会将小红传送到编号为ai的传送阵。小红最初在编号为s的传送阵，朋友最初在编号为t的传送阵，小红和朋友都可以通过传送阵传送，每次传送都会花费一分钟(两人可以同时传送)。现在小红想知道，小红和朋友最少需要多少分钟才能在同一个传送阵里见面，如果不能见面，输出 -1。
输入描述
第一行输入三个整数n，s，t，表示传送阵的数量，小红最初所在的传送阵编号，朋友最初所在的传送阵编号。
第二行输入n个整数ai，表示编号为i的传送阵会将小红传送到编号为ai的传送阵。
1<=n<=10^5
1<=s,t<=n
1<=ai<=n
保证 a 数组中的元素互不相同。
输出描述
输出一个整数，表示小红和朋友最少需要多少分钟才能在同一个传送阵里见面，如果不能见面，输出-1。
示例1
输入
5 1 2
5 1 2 3 4
输出
1
思路与代码
该程序的核心思想是通过使用广度优先搜索（BFS）算法，计算从给定起点 s 和终点 t 到图中所有其他节点的最短距离。首先，将输入的节点信息存储在向量中，并初始化两个向量 S 和 T，用于分别记录从 s 和 t 到各个节点的距离，初始值为无穷大（INT_MAX）。然后，通过两次BFS遍历计算出从 s 和 t 到每个节点的最短距离，并将结果存储在 S 和 T 向量中。接下来，程序找到从 s 和 t 到每个节点的最短距离之间的最大值，找到最小值，这将是从 s 和 t 到达某个节点的最短路径。最后，程序输出这个最小值作为答案，如果无法从 s 和 t 到达任何节点，则输出 -1。这个核心思想允许解决一种特定问题，即从起点 s 和终点 t 出发，寻找最短路径，并输出其长度。
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n,s,t;
cin >> n >> s >> t;
s--,t--;
vector<int> next(n);
for(int i = 0;i < n;i++) {
int a;
cin >> a;
a--;
next[i] = a;
}
vector<int> S(n,INT_MAX);
S[s] = 0;
vector<int> T(n,INT_MAX);
T[t] = 0;
queue<int> q;
q.push(s);
int d = 0;
while(!q.empty()) {
int cur = q.front();
q.pop();
S[cur] = d;
if(S[next[cur]] == INT_MAX) {
q.push(next[cur]);
}
d++;
}
q.push(t);
d = 0;
while(!q.empty()) {
int cur = q.front();
q.pop();
T[cur] = d;
if(T[next[cur]] == INT_MAX) {
q.push(next[cur]);
}
d++;
}
int ans = INT_MAX;
for(int i = 0;i < n;i++) {
if(S[i] != INT_MAX && T[i] != INT_MAX) {
ans = min(ans,max(S[i],T[i]));
}
}
if(ans == INT_MAX) {
cout << -1 << endl;
}else {
cout << ans << endl;
}
}
int main() {
solve();
}
第二题
给定两个正整数n，x，小红希望你构造一个长度为n的数组，满足 ∑（n,i=1）sum(i) = x。
sum(i)即数组的前i项之和。换言之，小红希望你构造一个长度为n的数组满足，n个前缀和之和等于t。
要求数组的元素仅由1和2组成。
输入描述
两个正整数n，x
1<=n<=10^5
1<=x<=10^18
输出描述
如果无解，请输出-1。
否则输出n个正整数，每个正整数为1或者2。有多解时输出任意即可
示例1
输入
3 8
输出
1 2 1
思路与代码
核心思想是解决一个将整数 x 分解成 n 个正整数的问题，同时要求这些正整数之间的差值尽可能小。为了达到这个目标，程序首先检查 x 是否在可行的范围内，如果不在范围内，就无法找到合适的解，会输出 -1 表示无解。
然后，程序通过计算前缀和和差值的方式来构建这个分解。它初始化一个前缀和向量和一个差值向量，并通过逐步调整这些向量的元素，以满足 x 的分解条件。具体而言，程序逐步减去从 1 到 n 的整数，并将这些减去的值分配给差值向量，以确保每个正整数之间的差值尽可能小。如果 x 仍然大于零，程序会调整差值向量，以便平衡剩余的 x。
最后，程序计算出每个正整数并输出它们，以满足分解条件。通过这种方式，程序通过调整正整数之间的差值，找到了一种满足条件的分解方式，从而解决了问题。这个核心思想允许在给定限制条件下找到一种合适的分解方式，使得分解后的正整数尽可能接近，并且它们的和等于给定的整数 x。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve() {
int n;
ll x;
cin >> n >> x;
if(x > 1LL * (2 + 2 + (n - 1) * 2) * n / 2) {
cout << -1 << endl;
return;
}
if(x < 1LL * (1 + 1 + (n - 1)) * n / 2) {
cout << -1 << endl;
return;
}
vector<int> preSum(n + 1,0);
vector<int> diff(n + 1);
for(int i = 1;i <= n;i++) {
preSum[i] = i;
x -= i;
diff[i] = preSum[i] - preSum[i-1];
}
int cur = 0;
while(x != 0) {
while(n - cur > x) {
cur++;
}
x -= (n - cur);
diff[cur + 1]++;
cur++;
}
for(int i = 1;i <= n;i++) {
preSum[i] = preSum[i-1] + diff[i];
}
for(int i = 1;i <= n;i++) {
cout << preSum[i] - preSum[i-1] << " ";
}
cout << endl;
}
int main() {
solve();
}
第三题
小红拿到了一个矩阵，矩阵上每个格子都有一个字母。
请你维护以下两种操作:
1.输入 1 x y c，将第x行第y列的字母修改为c
2.输入2 str，查询str单词在矩阵中出现的次数。
注:我们定义，单词在矩阵中出现当且仅当向下、向右、向右下 (和水平线夹角 135度)三种方向即可，且必须是一条直线上的字符 (不能转弯)。具体可以参考样例说明。
输入描述
第一行输入两个正整数n,m，用空格隔开，代表矩阵的行数和列数。
接下来的n行，每行输入一个长度为m的字符串，代表小红拿到的矩阵
接下来的一行输入一个正整数q，代表操作次数。
接下来的q行，每行输入一行操作: 1xyc或者2str，含义如题意所示
1 <=n,m <= 300
1<=q <= 10^5
str的长度不超过4。
输出描述
对于每次2号操作，输出一个整数代表答案
示例1
输入
3 4
abcd
cbae
cccC
3
2 abc
1 3 3b
2 ab
输出
2
3
思路与代码
核心思想是维护一个字符子串出现次数的映射表，以支持字符矩阵的操作和查询操作。它通过遍历和更新矩阵，同时更新字符子串的出现次数，来实现不同操作的功能。这种方法能够高效地处理矩阵操作和查询操作，保持了查询性能的优化。
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n,m;
cin >> n >> m;
vector<string> g(n);
for(int i = 0;i < n;i++) {
cin >> g[i];
}
int q;
cin >> q;
unordered_map<string,int> mp;
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
string s;
for(int k = j;k < min(j + 4,m);k++) {
s += g[i][k];
mp[s]++;
}
s.clear();
for(int k = i;k < min(i + 4,n);k++) {
s += g[k][j];
mp[s]++;
}
s.clear();
for(int k = 0;k < 4;k++) {
if(i + k < n && j + k < m) {
s += g[i + k][j + k];
mp[s]++;
}
}
}
}
for(int i = 0;i < q;i++) {
int t;
cin >> t;
if(t == 1) {
int x,y;
char c;
cin >> x >> y >> c;
x--,y--;
if(g[x][y] == c) continue;
string t,d,l,r,lt,rd,ori;
ori = g[x][y];
t = d = l = r = lt = rd = ori;
mp[ori]--;
for(int k = 1;k < 4;k++) {
if(x - k >= 0) {
t += g[x - k][y];
string rev = t;
reverse(rev.begin(),rev.end());
mp[rev]--;
}
if(y - k >= 0) {
l += g[x][y - k];
string rev = l;
reverse(rev.begin(),rev.end());
mp[rev]--;
}
if(x - k >= 0 && y - k >= 0) {
lt += g[x - k][y - k];
string rev = lt;
reverse(lt.begin(),lt.end());
mp[rev]--;
}
if(x + k < n) {
d += g[x + k][y];
mp[d]--;
}
if(y + k < m) {
r += g[x][y + k];
mp[r]--;
}
if(x + k < n && y + k < m) {
rd += g[x + k][y + k];
mp[rd]--;
}
}
g[x][y] = c;
ori = g[x][y];
mp[ori]++;
t = d = l = r = lt = rd = ori;
for(int k = 1;k < 4;k++) {
if(x - k >= 0) {
t += g[x - k][y];
string rev = t;
reverse(rev.begin(),rev.end());
mp[rev]++;
}
if(y - k >= 0) {
l += g[x][y - k];
string rev = l;
reverse(rev.begin(),rev.end());
mp[rev]++;
}
if(x - k >= 0 && y - k >= 0) {
lt += g[x - k][y - k];
string rev = lt;
reverse(lt.begin(),lt.end());
mp[rev]++;
}
if(x + k < n) {
d += g[x + k][y];
mp[d]++;
}
if(y + k < m) {
r += g[x][y + k];
mp[r]++;
}
if(x + k < n && y + k < m) {
rd += g[x + k][y + k];
mp[rd]++;
}
}
}else {
string str;
cin >> str;
cout << mp[str] << endl;
}
}
}
int main() {
solve();
}
第四题
现有一个长度为n的数组a和m个区间。
你可以选择任意个区间，选择的区间不能相交。如果选择一个区间[l,r]。那么可以获得∑(i=1,r)ai的分数。
请你计算出你可以获得的最大分数。
请注意，如果区间右端点在数组的范围之外，则该区间不可选取。
假设两个区间分别是[l1,r1]和[l2,r2]，如果它们满足l1<=l2<=r1或l2<=r1<=r2，则认为这两个区间相交。
输入描述
第一行两个整数n，m，表示数组的长府和区间的个数。
第二行n个整数ai，表示数组的元素。
接下来m行每行两个整数li,ri，表示每一个区间
1 <= n, m, ai <= 10^5
1<=l<=r<=10^5
输出描述
输入
5 3
1 2 3 4 9
1 4
2 3
4 5
输出
18
思路与代码
核心思想是使用动态规划来确定在给定区间选择下，达到的最大和。它通过对区间按右边界排序，并遍历数组 a，逐步更新 dp 数组来实现这一目标。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve() {
int n,m;
cin >> n >> m;
vector<int> a(n);
vector<ll> preSum(n + 1,0);
for(int i = 0;i < n;i++) {
cin >> a[i];
preSum[i + 1] = preSum[i] + a[i];
}
vector<pair<int,int>> intervals;
for(int i = 0;i < m;i++) {
int l,r;
cin >> l >> r;
if(r > n) continue;
intervals.push_back({l,r});
}
sort(intervals.begin(),intervals.end(),[&](pair<int,int> p1,pair<int,int> p2) -> bool {
return p1.second < p2.second;
});
vector<ll> dp(n + 1,0);
for(int i = 1,j = 0;i <= n;i++) {
dp[i] = dp[i-1];
while(j < intervals.size() && intervals[i].second <= i) {
int l = intervals[j].first,r = intervals[j].second;
dp[i] = max(dp[i],preSum[r] - preSum[l-1] + dp[l-1]);
j++;
}
}
cout << dp[n] << endl;
}
int main() {
solve();
}
最后插一下我们的进阶一对一辅导啦
我们是一个针对技术岗（前后端开发、测试、测开、大数据开发）校招一对一进阶提高的工作室。我们从2020年2月份开始，迄今整整三年的时间，带领300+学员斩获1500+大厂offer，参加活动的同学人均5个中大厂offer以上，以下是我们活动内容的介绍！ 万诺coding
我们主要是针对有一定基础的同学提供一对一笔试和面试辅导，针对每个同学不同的情况定制内容，包括但不限于“数据结构与算法”/“计算机基础知识”/“项目梳理”/“面试技巧”/“面试复盘”等内容。
摸底测试：如果有兴趣深入了解我们的活动，需要先参加我们的“摸底测试”（类似面试），方便我们了解你的具体情况（主要是code能力和计算机素养），定制出相应的辅导计划。同时这也是一个双向筛选的过程，如果基础过差的同学，抱歉我们可能无法辅导（基础过差的同学一对一辅导成本过高，对双方都不适合）；摸底测试通过的同学，我们会定制化一个针对性的提高计划。然后你再考虑是否参加我们的活动。
承诺保offer：通过摸底测试后，我们会针对每个同学的情况给定一个“保offer”计划。然后同学可以根据自己的实际情况考虑参不参加我们的活动。
有兴趣的同学可以扫码添加我们的微信（whynotlab）
