携程笔试 携程笔试题 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多种语言版本,持续更新中。