携程笔试 携程笔试题 0905
笔试时间：2024年09月05日 秋招
历史笔试传送门：2023秋招笔试合集
第一题
题目
游游有两个整数n,k, 他希望构造出一个1~n的排列p, 需要p的最长上升子序列长度为k, 并且p是所有满足要求的排列中字典序最小的。最长上升子序列是一个序列中最长的严格单调递增的子序列。
输入描述
两个正整数n,k，用空格隔开。
输出描述
输出n个正整数，代表构造的排列。
样例输入
5 3
样例输出
1 2 5 4 3
参考题解
模拟。由于字典序要求最小，因此要贪心的考虑。容易想到首先构造出1, 2, 3, ..., k - 1，n, n - 1, ..., k是字典序最小的。
C++：[此代码未进行大量数据的测试，仅供参考]
#include<iostream>
#include<vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < k - 1; i++) {
a[i] = i + 1;
}
a[k - 1] = n;
for (int i = k, x = n - 1; i < n; i++, x--) {
a[i] = x;
}
for (int x : a) {
cout << x << " ";
}
cout << "\n";
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
import java.util.Vector;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
Vector<Integer> a = new Vector<>(n);
for (int i = 0; i < k - 1; i++) {
a.add(i + 1);
}
a.add(n);
for (int i = k, x = n - 1; i < n; i++, x--) {
a.add(x);
}
for (int x : a) {
System.out.print(x + " ");
}
System.out.println();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
n, k = map(int, input().split())
a = [0] * n
for i in range(k - 1):
a[i] = i + 1
a[k - 1] = n
x = n - 1
for i in range(k, n):
a[i] = x
x -= 1
print(" ".join(map(str, a)))
第二题
题目
一个长度为k的二进制字符串(下标从1开始)的权值定义如下：每次操作可以选择一个下标i(1 ≤ i ≤ k)，将[1, i]中的字符全部取反(0变成1，1变成0)，字符串的权值为将字符串变成全1所需要的最小操作次数。给定一个长度为n的01字符串，问：有多少个长度为奇数并且权值为奇数的子字符串？
输入描述
第一行输入一个正整数n，代表字符串的长度。第二行输入字符串S。
输出描述
输出包含一行一个整数，表示长度和权值都是奇数的非空子串数量。
样例输入
5
01010
样例输出
6
参考题解
动态规划。定义三维dp数组，第一个维度表示下标，第二个维度表示长度是奇数还是偶数，第三个维度表示权值是奇数还是偶数
例如：dp[i][0][0]就表示以下标i结尾的长度为偶数并且权值为偶数的子字符串的数量，dp[i][0][1]表示以下标i结尾的长度为偶数的权值为奇数的子字符串的数量，以此类推。
C++：[此代码未进行大量数据的测试，仅供参考]
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
vector<vector<vector<int>>> dp(n, vector<vector<int>>(2, vector<int>(2, 0)));
long long ans = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
dp[i][1][0]++;
if (i > 0) {
dp[i][0][0] += dp[i - 1][1][0];
dp[i][0][1] += dp[i - 1][1][1];
dp[i][1][0] += dp[i - 1][0][0];
dp[i][1][1] += dp[i - 1][0][1];
}
}else {
dp[i][1][1]++;
if (i > 0) {
if (s[i - 1] == s[i]) {
dp[i][0][0] += dp[i - 1][1][0];
dp[i][0][1] += dp[i - 1][1][1];
dp[i][1][0] += dp[i - 1][0][0];
dp[i][1][1] += dp[i - 1][0][1];
} else {
dp[i][0][0] += dp[i - 1][1][0];
dp[i][0][1] += dp[i - 1][1][1];
dp[i][1][0] += dp[i - 1][0][0];
dp[i][1][1] += dp[i - 1][0][1];
}
}
}
ans += dp[i][1][1];
}
cout << ans << "\n";
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.Scanner;
import java.util.Vector;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String s = scanner.next();
int[][][] dp = new int[n][2][2];
long ans = 0;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '1') {
dp[i][1][0]++;
if (i > 0) {
dp[i][0][0] += dp[i - 1][1][0];
dp[i][0][1] += dp[i - 1][1][1];
dp[i][1][0] += dp[i - 1][0][0];
dp[i][1][1] += dp[i - 1][0][1];
}
} else {
dp[i][1][1]++;
if (i > 0) {
if (s.charAt(i - 1) == s.charAt(i)) {
dp[i][0][0] += dp[i - 1][1][0];
dp[i][0][1] += dp[i - 1][1][1];
dp[i][1][0] += dp[i - 1][0][0];
dp[i][1][1] += dp[i - 1][0][1];
} else {
dp[i][0][0] += dp[i - 1][1][0];
dp[i][0][1] += dp[i - 1][1][1];
dp[i][1][0] += dp[i - 1][0][0];
dp[i][1][1] += dp[i - 1][0][1];
}
}
}
ans += dp[i][1][1];
}
System.out.println(ans);
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
n = int(input())
s = input()
dp = [[[0, 0] for _ in range(2)] for _ in range(n)]
ans = 0
for i in range(n):
if s[i] == '1':
dp[i][1][0] += 1
if i > 0:
dp[i][0][0] += dp[i - 1][1][0]
dp[i][0][1] += dp[i - 1][1][1]
dp[i][1][0] += dp[i - 1][0][0]
dp[i][1][1] += dp[i - 1][0][1]
else:
dp[i][1][1] += 1
if i > 0:
if s[i - 1] == s[i]:
dp[i][0][0] += dp[i - 1][1][0]
dp[i][0][1] += dp[i - 1][1][1]
dp[i][1][0] += dp[i - 1][0][0]
dp[i][1][1] += dp[i - 1][0][1]
else:
dp[i][0][0] += dp[i - 1][1][0]
dp[i][0][1] += dp[i - 1][1][1]
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解，包含python、C++、Java多种语言版本，持续更新中。
