【秋招笔试】9.01字节跳动秋招(已改编)-三语言题解
🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历
✨ 本系列打算持续跟新
春秋招笔试题👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷春秋招笔试合集
🍒 本专栏已收集
90+套笔试题，笔试真题会在第一时间跟新🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。
🧩 备战秋招还没订阅的朋友们可以冲一下啦，当试题收集至
100套后，价格会进行一波调整~🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞
🪔 字节跳动的秋招笔试，来啦！！！
🍥 本次的代码难度都不大，主要是思维题
1️⃣ 比较简单，可以前后缀预处理或者直接上数据结构
2️⃣ 数学思维题，对原本的等式做下变形即可
3️⃣ 思维题+数论相关
4️⃣ 动态规划，需要用二分或者树状数组优化
🎀 01.LYA的彩色画布
问题描述
LYA是一位热爱艺术的年轻画家。她最近得到了一块特殊的画布，这块画布被分成了 个小格子。每个格子都有一个独特的色彩值。LYA想要创作一幅独特的作品，她决定选择一个分界点
，将分界点左边（包括分界点）的格子涂成红色，右边的格子涂成蓝色。
LYA希望她的作品能够呈现出和谐的美感。她定义了一个"和谐度"的概念：红色区域的色彩极差（最大值减最小值）与蓝色区域的色彩极差的差的绝对值。LYA想要找到一个分界点，使得这个"和谐度"最小。你能帮助LYA找到这个最小的"和谐度"吗？
输入格式
第一行输入一个整数 ，表示画布的格子数。
第二行输入 个整数
，表示每个格子的色彩值。
输出格式
输出一个整数，表示最小的"和谐度"。
样例输入
5
1 2 4 3 5
样例输出
1
样例解释
当选择 时，红色区域为
，极差为
；蓝色区域为
，极差为
。"和谐度"为
，这是所有可能分界点中的最小值。
数据范围
题解
维护一个前缀最大和最小，以及后缀的最大和最小值即可。
这里为了方便直接用数据结构写了，时间复杂度会多带一个log
参考代码
- Python
from sortedcontainers import SortedList
def main():
# 读取输入
n = int(input())
a = list(map(int, input().split()))
# 初始化左右两个SortedList
left = SortedList()
right = SortedList(a)
res = float('inf')
# 遍历数组
for i in range(n - 1):
# 将当前元素从右侧移到左侧
curr = right.pop(right.index(a[i]))
left.add(curr)
# 如果右侧为空，跳出循环
if not right:
break
# 计算左右两侧的极差
left_range = left[-1] - left[0]
right_range = right[-1] - right[0]
# 更新结果
res = min(res, abs(left_range - right_range))
# 输出结果
print(res)
if __name__ == "__main__":
main()
- Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 使用TreeMap来模拟多重集
TreeMap<Integer, Integer> left = new TreeMap<>();
TreeMap<Integer, Integer> right = new TreeMap<>();
// 初始化右侧多重集
for (int num : a) {
right.put(num, right.getOrDefault(num, 0) + 1);
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < n - 1; i++) {
// 将当前元素从右侧移到左侧
left.put(a[i], left.getOrDefault(a[i], 0) + 1);
right.put(a[i], right.get(a[i]) - 1);
if (right.get(a[i]) == 0) right.remove(a[i]);
// 计算左右两侧的极差
int leftRange = left.lastKey() - left.firstKey();
int rightRange = right.lastKey() - right.firstKey();
// 更新结果
res = Math.min(res, Math.abs(leftRange - rightRange));
}
System.out.println(res);
}
}
- Cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
// 使用multiset来存储左右两侧的元素
multiset<int> left, right;
// 读取输入并初始化右侧multiset
for (int& x : a) {
cin >> x;
right.insert(x);
}
int res = INT_MAX;
// 遍历数组
for (int i = 0; i < n - 1; ++i) {
// 将当前元素从右侧移到左侧
left.insert(a[i]);
right.erase(right.find(a[i]));
// 计算左右两侧的极差
int left_range = *left.rbegin() - *left.begin();
int right_range = *right.rbegin() - *right.begin();
// 更新结果
res = min(res, abs(left_range - right_range));
}
// 输出结果
cout << res << "\n";
return 0;
}
🚙 02.K小姐的珠宝配对
问题描述
K小姐是一位珠宝设计师，她最近收到了一批特殊的宝石。这批宝石共有 颗，每颗宝石都有一个独特的魔力值。K小姐想要将这些宝石制作成一系列成对的耳环。
她发现，当两颗宝石的魔力值之和等于它们在序列中的位置之和时，这对宝石就能产生奇妙的共鸣效果。K小姐想知道在这批宝石中，有多少对宝石可以形成这种奇妙的共鸣。
具体来说，如果第 颗宝石和第
颗宝石满足
且
（其中
表示第
颗宝石的魔力值），那么这对宝石就可以形成一对完美的耳环。
请你帮K小姐计算一下，这批宝石中有多少对可以形成完美的耳环。
输入格式
输入包含两行。
第一行是一个正整数 （
），表示宝石的数量。
第二行包含 个正整数
（
），表示每颗宝石的魔力值。保证输入的魔力值序列是一个
到
的排列。
输出格式
输出一行，包含一个整数，表示可以形成完美耳环的宝石对数。
样例输入
5
2 1 3 5 4
样例输出
4
样例解释
在这个例子中，以下四对宝石可以形成完美的耳环：
- 第 1 颗和第 2 颗：
- 第 2 颗和第 4 颗：
- 第 1 颗和第 5 颗：
- 第 4 颗和第 5 颗：
数据范围
题解
这道题的核心在于如何高效地找出满足条件的宝石对。
一个直观的想法是遍历所有可能的对，但这样的时间复杂度是 ，对于给定的数据范围来说太高了。
可以通过数学变换来简化问题。
对于任意一对满足条件的宝石 和
，有：
将 移到等式右边：
这意味着，如果我们计算每个宝石的 值，那么满足条件的一对宝石的这个值之和应该为 0。
因此，可以使用哈希表来存储每个 值出现的次数。
遍历一遍数组，对于每个宝石，检查 是否在哈希表中，如果在，就将其出现次数加到结果中。然后将当前的
加入哈希表。
参考代码
- Python
def main():
# 读取宝石数量
n = int(input())
# 读取每颗宝石的魔力值
p = list(map(int, input().split()))
# 初始化结果和哈希表
res = 0
diff_count = {}
# 遍历每颗宝石
for i in range(n):
# 计算 p[i] - (i+1)
diff = p[i] - (i + 1)
# 检查是否存在匹配的宝石
if -diff in diff_count:
res += diff_count[-diff]
# 更新哈希表
diff_count[diff] = diff_count.get(diff, 0) + 1
# 输出结果
print(res)
if __name__ == "__main__":
main()
- Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 读取宝石数量
int n = Integer.parseInt(br.readLine());
// 读取每颗宝石的魔力值
int[] p = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 初始化结果和哈希表
long res = 0;
Map<Integer, Integer> diffCount = new HashMap<>();
// 遍历每颗宝石
for (int i = 0; i < n; i++) {
// 计算 p[i] - (i+1)
int diff = p[i] - (i + 1);
// 检查是否存在匹配的宝石
res += diffCount.getOrDefault(-diff, 0);
// 更新哈希表
diffCount.put(diff, diffCount.getOrDefault(diff, 0) + 1);
}
// 输出结果
System.out.println(res);
}
}
- Cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
// 使用unordered_map来存储差值的出现次数
unordered_map<int, int> diff_count;
long long res = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
// 计算差值
int diff = x - i;
// 检查是否存在匹配的宝石
res += diff_count[-diff];
// 更新差值的出现次数
diff_count[diff]++;
}
// 输出结果
cout << res << "\n";
return 0;
}
🍰 03.LYA的魔法调和
问题描述
LYA是一位魔法调和师，她有一组魔法元素，每个元素都有一个能量值。LYA希望将所有元素的能量值调和至1，这样它们就能完美融合。她可以使用一种特殊的调和魔法：每次选择两个不同的元素，然后同时将它们的能量值除以这两个数的任意一个公因数。
LYA想知道，她是否能通过若干次调和魔法，将所有元素的能量值都变为1。你能帮助她判断这是否可能吗？
输入格式
输入的第一行是一个整数 （
），表示测试用例的数量。
对于每个测试用例：
- 第一行包含一个整数
（
），表示魔法元素的数量。
- 第二行包含
（
），表示每个魔法元素的初始能量值。
保证所有测试用例中 的总和不超过
。
输出格式
对于每个测试用例，如果LYA能够将所有元素的能量值调和为1，输出"YES"，否则输出"NO"。
样例输入
2
3
18 18 36
3
3 2 1
样例输出
YES
NO
样例解释
对于第一组测试数据：
- 将第一个和第三个元素同时除以6，得到{3, 18, 6}
- 将第二个和第三个元素同时除以6，得到{3, 3, 1}
- 将第一个和第二个元素同时除以3，得到{1, 1, 1}
对于第二组测试数据，无法通过调和魔法使所有元素变为1。
数据范围
- 所有测试用例中
题解
对于每个数，我们需要
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
这里收集了超全的刷题笔记，欢迎大家的订阅，会持续跟新的
投递字节跳动等公司10个岗位