🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系计划跟新各公司春秋招的笔试题
💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总,如果有需要的小伙伴可以关注CSDN同名公主号领取,会在飞书进行同步的跟新。
文章目录
- 📖 写在前面
- 夏天要来了 秋招还会远吗?
- 🎀 01.卢小姐的完美日程安排
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 数据范围
- 题解
- 参考代码
- 🌸 02.K小姐的探险之旅
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 数据范围
- 题解
- 参考代码
- ✈️ 03.K小姐的书架整理
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 数据范围
- 题解
- 参考代码
- 🎀 写在最后
- 🛖 这里介绍一下咱们的笔试打卡小屋
- 🥰 打卡奖励
- 🕰 每日学习安排
- 📖 打卡小屋涉及题型
- 基础算法
- 基础数据结构
- 搜索
- 动态规划 & 贪心 & 数论
📖 写在前面
夏天要来了 秋招还会远吗?
前不久春招也算是圆满结束咯,大家有拿到心仪的 offer吗?
接下来互联网的秋招也快来啦,小伙伴们有开始准备了吗?
本次给大家带来24届秋招 科大讯飞 的笔试题目三语言解析(Java/Python/Cpp)
文末有清隆学长的笔试陪伴打卡小屋活动介绍:
✨丰富的打卡奖励等你来领哦,大厂笔试题汇总,笔试面试经验贴,算法笔试模版…
💽 有兴趣的小伙伴们也可以了解一下,不要错过啦~
🎀 01.卢小姐的完美日程安排
问题描述
卢小姐是一位非常注重效率的人,她总是希望把一天的时间安排得满满当当。对于她来说,一个完美的日程安排需要满足以下条件:
- 将一天分为 n n n 个时间段,每个时间段用 1 1 1 到 n n n 的正整数表示,且不重复。
- 对于任意时间段 i i i,若安排在时间段 i i i 进行的活动编号为 a i a_i ai,则安排在时间段 a i a_i ai 进行的活动编号必须为 n − a i + 1 n - a_i + 1 n−ai+1。
现在卢小姐想要知道,在满足以上条件的情况下,字典序最大的日程安排是什么样的?
注:字典序指按照正整数大小比较两个序列的方法。对于两个长度相同的序列 A A A 和 B B B,若存在一个位置 i i i,使得对于任意 j < i j < i j<i,都有 A j = B j A_j = B_j Aj=Bj,而 A i > B i A_i > B_i Ai>Bi,则认为序列 A A A 的字典序大于序列 B B B。
输入格式
输入仅一行,包含一个正整数 n n n,表示一天被分为 n n n 个时间段。
输出格式
输出一行,包含 n n n 个正整数,用空格隔开,表示字典序最大的完美日程安排中每个时间段对应的活动编号。
样例输入
3
样例输出
3 2 1
数据范围
- 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105
题解
根据题目描述,对于任意时间段 i i i,若安排在时间段 i i i 进行的活动编号为 a i a_i ai,则安排在时间段 a i a_i ai 进行的活动编号必须为 n − a i + 1 n - a_i + 1 n−ai+1。因此,我们可以得到以下结论:
- 若 a i = n + 1 2 a_i = \frac{n+1}{2} ai=2n+1,则 a i = n − a i + 1 a_i = n - a_i + 1 ai=n−ai+1,即时间段 n + 1 2 \frac{n+1}{2} 2n+1 的活动编号必须为 n + 1 2 \frac{n+1}{2} 2n+1。
- 对于其他时间段,若 a i < n + 1 2 a_i < \frac{n+1}{2} ai<2n+1,则 a n − a i + 1 = a i a_{n-a_i+1} = a_i an−ai+1=ai;若 a i > n + 1 2 a_i > \frac{n+1}{2} ai>2n+1,则 a n − a i + 1 = n − a i + 1 a_{n-a_i+1} = n - a_i + 1 an−ai+1=n−ai+1。
因此,我们可以先确定中间时间段的活动编号,然后从大到小依次确定其他时间段的活动编号,即可得到字典序最大的完美日程安排。
具体步骤如下:
- 如果 n n n 为奇数,则将 n + 1 2 \frac{n+1}{2} 2n+1 安排在时间段 n + 1 2 \frac{n+1}{2} 2n+1。
- 从 n n n 开始,依次确定每个时间段的活动编号:
- 如果当前时间段 i i i 已经确定,则跳过;
- 否则,将当前时间段 i i i 的活动编号设为 i i i,并将时间段 n − i + 1 n - i + 1 n−i+1 的活动编号设为 n − i + 1 n - i + 1 n−i+1。
时间复杂度为 O ( n ) O(n) O(n),空间复杂度为 O ( n ) O(n) O(n)。
参考代码
- Python
n = int(input())
ans = [0] * (n + 1)for i in range(n, 0, -1):if ans[i] == 0:ans[i] = ians[n - i + 1] = n - i + 1print(*ans[1:][::-1])
- Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] ans = new int[n + 1];for (int i = n; i >= 1; i--) {if (ans[i] == 0) {ans[i] = i;ans[n - i + 1] = n - i + 1;}}for (int i = n; i >= 1; i --) {System.out.print(ans[i] + " ");}}
}
- Cpp
#include <iostream>
using namespace std;int main() {int n;cin >> n;int ans[n + 1];for (int i = 1; i <= n; i++) {ans[i] = 0;}for (int i = n; i >= 1; i--) {if (ans[i] == 0) {ans[i] = i;ans[n - i + 1] = n - i + 1;}}for (int i = n; i >= 1; i --) {cout << ans[i] << " ";}return 0;
}
🌸 02.K小姐的探险之旅
问题描述
K小姐正在玩一个探险游戏。游戏中有 n n n 个关卡,每个关卡都有一个字符表示的难度等级。K小姐有初始体力值 k k k,每通过一个关卡会消耗一定的体力。
游戏规则如下:
- K小姐必须按照关卡顺序挑战,即从第 1 1 1 个关卡开始,到第 n n n 个关卡结束。
- 第 i i i 个关卡的难度等级用字符 s i s_i si 表示,其中 s i s_i si 为小写字母。
- 如果 s i s_i si 和 s i − 1 s_{i-1} si−1 相同,则通过第 i i i 个关卡不消耗体力。
- 如果 s i s_i si 和 s i − 1 s_{i-1} si−1 不同,设 s i s_i si 和 s i − 1 s_{i-1} si−1 的 ASCII 码之差为 Δ \Delta Δ,则:
- 若 Δ > 0 \Delta > 0 Δ>0,则通过第 i i i 个关卡会消耗 Δ \Delta Δ 点体力;
- 若 Δ < 0 \Delta < 0 Δ<0,则通过第 i i i 个关卡会增加 ∣ Δ ∣ |\Delta| ∣Δ∣ 点体力。
- 当体力值不大于 0 0 0 时,游戏结束。
请你计算K小姐完成游戏后的剩余体力值,如果无法完成游戏,则输出 − 1 -1 −1。
输入格式
第一行包含两个正整数 n n n 和 k k k,表示关卡数和初始体力值。
第二行包含一个长度为 n n n 的字符串 s s s,表示每个关卡的难度等级。
输出格式
输出一个整数,表示K小姐完成游戏后的剩余体力值。如果无法完成游戏,则输出 − 1 -1 −1。
样例输入
5 10
abcde
样例输出
6
数据范围
- 1 ≤ n , k ≤ 1 0 5 1 \leq n, k \leq 10^5 1≤n,k≤105
- 字符串 s s s 仅包含小写字母
题解
本题可以通过模拟游戏过程来解决。我们可以依次处理每个关卡,根据当前关卡和前一个关卡的难度等级之差来计算体力值的变化。
具体步骤如下:
- 初始化剩余体力值为 k k k。
- 从第 2 2 2 个关卡开始,计算当前关卡和前一个关卡的难度等级之差 Δ \Delta Δ。
- 如果 Δ > 0 \Delta > 0 Δ>0,则剩余体力值减去 Δ \Delta Δ;如果 Δ < 0 \Delta < 0 Δ<0,则剩余体力值加上 ∣ Δ ∣ |\Delta| ∣Δ∣。
- 如果剩余体力值不大于 0 0 0,则游戏失败,输出 − 1 -1 −1 并结束程序。
- 处理完所有关卡后,输出最终的剩余体力值。
时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( 1 ) O(1) O(1)。其中 n n n 为关卡数。
参考代码
- Python
n, k = map(int, input().split())
s = input()for i in range(1, n):delta = ord(s[i]) - ord(s[i-1])k -= deltaif k <= 0:print(-1)exit()print(k)
- Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();String s = sc.next();for (int i = 1; i < n; i++) {int delta = s.charAt(i) - s.charAt(i-1);k -= delta;if (k <= 0) {System.out.println(-1);return;}}System.out.println(k);}
}
- Cpp
#include <iostream>
using namespace std;int main() {int n, k;cin >> n >> k;string s;cin >> s;for (int i = 1; i < n; i++) {int delta = s[i] - s[i-1];k -= delta;if (k <= 0) {cout << -1 << endl;return 0;}}cout << k << endl;return 0;
}
✈️ 03.K小姐的书架整理
问题描述
K小姐有两个书架,每个书架上都摆放着 n n n 本书。这些书是按照一定的顺序排列的,可以看作是两个长度为 n n n 的排列。
K小姐打算将这两个书架上的书合并起来,并且按照字典序从小到大的顺序重新摆放。不过,为了方便查找,她希望只保留其中不重复的书的排列。
现在,K小姐想知道,最终她的书架上会有多少种不同的书的排列方式呢?
注:排列是指由 1 1 1 到 n n n 组成的长度为 n n n 的序列,且每个数字仅出现一次。
输入格式
第一行包含一个正整数 n n n,表示每个书架上书的数量。
第二行包含 n n n 个正整数 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an,表示第一个书架上书的排列顺序。
第三行包含 n n n 个正整数 b 1 , b 2 , … , b n b_1, b_2, \dots, b_n b1,b2,…,bn,表示第二个书架上书的排列顺序。
输出格式
输出一个整数,表示最终K小姐书架上不同的书的排列方式的数量。
样例输入
3
1 2 3
3 2 1
样例输出
9
数据范围
1 ≤ n ≤ 2 × 1 0 5 1 \leq n \leq 2 \times 10^5 1≤n≤2×105
1 ≤ a i , b i ≤ n 1 \leq a_i, b_i \leq n 1≤ai,bi≤n
a i a_i ai 和 b i b_i bi 均为 1 1 1 到 n n n 的排列
题解
本题可以通过枚举子排列来解决。我们可以分别枚举两个书架上的书的子排列,然后统计它们的总数。
设 f ( x ) f(x) f(x) 表示长度为 x x x 的排列的子排列数量,那么有:
f ( x ) = x ( x + 1 ) 2 f(x) = \frac{x(x+1)}{2} f(x)=2x(x+1)
对于两个书架上的书,我们可以先分别计算它们的子排列总数,即 f ( n ) + f ( n ) f(n) + f(n) f(n)+f(n)。
然后,我们需要减去两个书架上相同的子排列数量。具体来说,对于第二个书架上的每一本书 b i b_i bi,我们找到它在第一个书架上的位置 j j j,然后检查从 b i b_i bi 开始,两个书架上连续的书是否相同。如果有连续的 k k k 本书相同,那么我们就要减去 f ( k ) f(k) f(k),因为这部分子排列被重复计算了。
综上,答案为:
f ( n ) + f ( n ) − ∑ i = 1 n f ( k i ) f(n) + f(n) - \sum_{i=1}^{n} f(k_i) f(n)+f(n)−i=1∑nf(ki)
其中 k i k_i ki 表示从第二个书架的第 i i i 本书开始,两个书架上连续相同的书的数量。
参考代码
- Python
def get_subseq_count(x):return x * (x + 1) // 2n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))pos_a = [0] * (n + 1)
for i in range(n):pos_a[a[i]] = ians = get_subseq_count(n) * 2i = 0
while i < n:j = pos_a[b[i]]cnt = 0while i < n and j < n and a[j] == b[i]:i += 1j += 1cnt += 1ans -= get_subseq_count(cnt)print(ans)
- 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();int[] b = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();int[] posA = new int[n + 1];for (int i = 0; i < n; i++) {posA[a[i]] = i;}long ans = getSubseqCount(n) * 2;for (int i = 0, j; i < n; ) {j = posA[b[i]];int cnt = 0;while (i < n && j < n && a[j] == b[i]) {i++;j++;cnt++;}ans -= getSubseqCount(cnt);}System.out.println(ans);}private static long getSubseqCount(int x) {return (long) x * (x + 1) / 2;}
}
- Cpp
#include <iostream>
#include <vector>
using namespace std;typedef long long LL;LL get_subseq_count(int x) {return (LL)x * (x + 1) / 2;
}int main() {int n;cin >> n;vector<int> a(n), b(n);for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {cin >> b[i];}vector<int> pos_a(n + 1);for (int i = 0; i < n; i++) {pos_a[a[i]] = i;}LL ans = get_subseq_count(n) * 2;for (int i = 0, j; i < n; ) {j = pos_a[b[i]];int cnt = 0;while (i < n && j < n && a[j] == b[i]) {i++;j++;cnt++;}ans -= get_subseq_count(cnt);}cout << ans << endl;return 0;
}
🎀 写在最后
🛖 这里介绍一下咱们的笔试打卡小屋
✨ 打卡小屋旨在陪伴大家,养成每日学习的好习惯。在这里,你可以:
- 🤝 与备战笔试的小伙伴相识,找到志同道合的学习小组
- 📝 通过写题解,巩固做题思路,养成良好的记录习惯
- 💡 系统掌握常考算法和数据结构,了解互联网笔试难度
- 🎁 坚持打卡,获得丰厚奖励,激励自己持之以恒
🥰 打卡奖励
打卡时长 | 奖励内容 |
---|---|
7天 | 任选一家最新互联网笔试真题 x 1 (价值29.9r) |
14天 | 任选一家最新互联网笔试真题 x 3 + 笔试面试经验贴 |
21天 | 任选一家最新互联网笔试真题 x 5 + 清隆三语言算法模版 |
28天 | 最新互联网大厂笔试真题汇总(价值199r) + 华为OD机试训练营 (价值89r) |
7天打卡即可值回票价,心动不如行动!=>笔试刷题陪伴小屋-打卡赢价值丰厚奖励 <=
🕰 每日学习安排
小屋将在每日上午发放打卡题目,包括:
- 一道算法模版题,帮助大家掌握常用算法套路
- 根据算法模版,精选一道对应的大厂笔试真题,巩固算法应用
让我们一起直击笔试重点,攻克常考题型!
📖 打卡小屋涉及题型
小屋从零基础出发,涵盖笔试常考知识点:
基础算法
- 自定义排序
- 二分
- 前缀和
- 差分
- 双指针
基础数据结构
- 栈 & 单调栈
- 队列 & 单调队列
- 并查集
- 优先队列(堆)
搜索
- DFS & BFS 基础应用
- 树的遍历
- 基础图论
动态规划 & 贪心 & 数论
- 快速幂
- 组合数
- 质数 & 因数
- 位运算
- 基础动态规划
- 常见贪心