携程0921秋招笔试真题解析
- 2026-11-06 21:40:56
关注我们，每周更新两到三次大厂最新笔试题解析
前言
难度比较大。总体题目有些灵活，特别是第四题，需要找到一些规律以后再进行动态规划。
第一题
游游拿到了一个排列a。她希望你构造一个长度相等的排列b，满足ai≠bi且b的字典序尽可能小。你能帮帮她吗?
所谓排列，即长度为n的数组，其中 1到n每个正整数都恰好出现了 1次。
输入描述
第一行输入一个正整数n，代表排列a的长度。
第二行输入几个正整数ai，代表游游拿到的排列。
2<=n<=10^5
输出描述
n个正整数bi，代表构造的排列。
示例1
输入
3
1 2 3
输出
2 3 1
思路与代码
该程序的核心思想是：对于给定的序列a，创建一个新的序列b，该序列的元素从1到n，但避免使b[i]等于a[i]。当不可能满足这个条件时，就选择下一个可能的数字。
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
TreeSet<Integer> set = new TreeSet<>();
for(int i = 0;i < n;i++) {
a[i] = sc.nextInt();
set.add(i+1);
}
int[] b = new int[n];
for(int i = 0;i < n;i++) {
int ai = a[i];
int bi = set.first();
if(bi == ai || (set.size() == 2 && set.higher(bi) == a[i+1])) {
bi = set.higher(bi);
}
b[i] = bi;
set.remove(bi);
}
for(int bi : b) {
System.out.print(bi + " ");
}
System.out.println();
}
}
第二题
小红拿到了一个字符串s。她可以进行任意次以下操作
选择字符串中的一个字母ch1和任意一个字母ch2 (ch2可以不在字符串中出现)，将字符串S中的所有ch1变成ch2。
小红想知道，自己能否通过一些操作将字符串s变成t?
输入描述
第一行输入一个正整数q，代表查询次数
对于每次查询输入2行:
第一行输入一个字符串s.
第二行输入一个字符串t
1<=q<=10
保证s和t的长度相同，且均由小写字母组成。长度不超过10000
输出描述
输出q行，每行输出一个字符串代表答案。如果可以把s变成t，则输出Yes。否则输出no.
示例1
输入
3
ab
ba
abc
aaa
aaaa
abcd
输出
Yes
Yes
No
思路与代码
检查两个字符串s和t，看是否可以通过替换s中的字符来得到t，其中每个字符在s中只能被替换为一个特定的字符。
#include<bits/stdc++.h>
using namespace std;
void solve() {
string s,t;
cin >> s >> t;
unordered_map<char,unordered_set<char>> mp;
bool ok = true;
for(int i = 0;i < s.size();i++) {
mp[s[i]].emplace(t[i]);
if(mp[s[i]].size() > 1) {
ok = false;
}
}
cout << (ok ? "Yes" : "No") << endl;
}
int main() {
int t;
cin >> t;
while(t--){
solve();
}
}
第三题
游游拿到了一个n行m列的字母矩阵，矩阵中所有字符都是小写字母。
游游想知道，有多少个子矩阵满足，每个字母最多出现一次?
输入描述
第一行输入两个正整数n和m，代表矩阵的大小。
接下来的n行，每行输入一个长度为m的、仅包含小写字母的字符串
1<=n,m <= 500
输出描述
每种字母只出现一次的子矩阵数量。
示例1
输入
2 3
a a d
a b c
输出
1
思路与代码计算给定字符网格中所有的矩形子网格，其中每个字符在子网格中仅出现一次。
使用四重循环枚举矩形子网格的左上角坐标 (i, j)和宽度w与高度h。对于每个矩形子网格，使用一个 cnt数组来统计该子网格中每个字符的出现次数。如果某个字符在子网格中出现多次，则该子网格不满足条件。在这种情况下，使用 goto out;跳到标签out处，结束这次子网格的检查。如果该子网格满足条件（即每个字符仅出现一次），则答案 ans增加 1。
#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 ans = 0;
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
for(int w = 1;w <= min(m-j,26);w++) {
for(int h = 1;h <= min(n-i,26) && h * w <= 26;h++) {
int cnt[26];
bool ok = true;
memset(cnt,0,sizeof cnt);
for(int k = i;k < i + h;k++) {
for(int l = j;l < j + w;l++) {
cnt[g[k][l]-'a']++;
if(cnt[g[k][l]-'a'] > 1) {
ok = false;
goto out;
}
}
}
out:
if(ok) {
ans++;
}
}
}
}
}
cout << ans << endl;
}
int main() {
solve();
}
第四题
游游拿到了一个正整数，她准备恰好修改其中k位，使得该正整数变成75的倍数。你能帮游游求出有多少种修改方案吗?修改后，仍是正整数，且不允许存在前导零，答案请对10^9+ 7取模。
输入描述
第一行输入一个正整数n.
第二行输入一个正整数k
1<=n <=10^1000
1<=k<=1000
输出描述
修改的方案数，对10^9+7取模
示例1
输入
355
2
输出
9
说明
共有150、225、300、450、525、675、750、825、975这9种方案.
思路与代码代码主要基于以下事实：
一个数字是75的倍数，当且仅当它是3的倍数并且以00、25、50或75结尾。 为了满足这个条件，我们使用DP来考虑所有可能的修改和余数组合。 最后，我们特别考虑数字的最后两位，因为它们决定了数字是否以00、25、50或75结尾。 DP数组的初始化: 使用一个三维DP数组 dp，其中dp[i][j][k]表示考虑到第i位，有j次修改，且余数为k时的方案数量。dp[0][0][0] = 1表示开始时，没有考虑任何数字，没有做任何修改，且余数为0的方案数量为1。DP的状态转移: 使用四层循环，分别遍历数字的位置、修改次数、余数和当前考虑的数字的余数。 在这些循环中，通过状态转移更新 dp数组。计算结果: 初始化结果 ans = 0。suffix是一个存储75的倍数的后两位数字的字符串数组。对于每个 suffix，计算需要多少次修改以使数字的最后两位匹配，并更新ans。然后，取模更新答案 ans %= MOD。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve() {
string num;
cin >> num;
int k;
cin >> k;
int n = num.size();
ll dp[n + 1][k + 1][3];
ll MOD = 1e9 +7;
memset(dp,0,sizeof dp);
dp[0][0][0] = 1;
for(int i = 1;i <= n;i++) {
for(int j = 0;j <= k;j++) {
for(int k = 0;k < 3;k++) {
int mod = (num[i-1]-'0') % 3;
for(int l = 0;l < 3;l++) {
if((mod + (l * 10) % 3) % 3 == k) {
dp[i][j][k] += dp[i-1][j][l];
dp[i][j][k] %= MOD;
}
}
if(j > 0) {
int start = (i == 1 ? 1 : 0);
for(int cur = start;cur <= 9;cur++) {
if(cur == num[i-1]-'0') continue;
mod = cur % 3;
for(int l = 0;l < 3;l++) {
if((mod + (l * 10) % 3) % 3 == k) {
dp[i][j][k] += dp[i-1][j-1][l];
dp[i][j][k] %= MOD;
}
}
}
}
}
}
}
ll ans = 0;
vector<string> suffix = {"75","50","25","00"};
for(string suf : suffix) {
int change = 0;
if(num[n-2] != suf[0]) change++;
if(num[n-1] != suf[1]) change++;
if(change > k) continue;
if(suf == "75" || suf == "00") {
ans += dp[n-2][k-change][0];
}else if(suf == "50") {
ans += dp[n-2][k-change][1];
}else {
ans += dp[n-2][k-change][2];
}
ans %= MOD;
}
cout << ans << endl;
}
int main() {
solve();
}
最后插一下我们的进阶一对一辅导啦
我们是一个针对技术岗（前后端开发、测试、测开、大数据开发）校招一对一进阶提高的工作室。我们从2020年2月份开始，迄今整整三年的时间，带领300+学员斩获1500+大厂offer，参加活动的同学人均5个中大厂offer以上，以下是我们活动内容的介绍！ 万诺coding
我们主要是针对有一定基础的同学提供一对一笔试和面试辅导，针对每个同学不同的情况定制内容，包括但不限于“数据结构与算法”/“计算机基础知识”/“项目梳理”/“面试技巧”/“面试复盘”等内容。
摸底测试：如果有兴趣深入了解我们的活动，需要先参加我们的“摸底测试”（类似面试），方便我们了解你的具体情况（主要是code能力和计算机素养），定制出相应的辅导计划。同时这也是一个双向筛选的过程，如果基础过差的同学，抱歉我们可能无法辅导（基础过差的同学一对一辅导成本过高，对双方都不适合）；摸底测试通过的同学，我们会定制化一个针对性的提高计划。然后你再考虑是否参加我们的活动。
承诺保offer：通过摸底测试后，我们会针对每个同学的情况给定一个“保offer”计划。然后同学可以根据自己的实际情况考虑参不参加我们的活动。
有兴趣的同学可以扫码添加我们的微信（whynotlab）
