携程的笔试整体给人一种都有思路但全A不了的感觉，我是觉得挺难的，携程这一波笔试的复盘还是很有价值的，不断学习…..
第一题
第一题比较简单，要么回溯要么调next_permutation库函数，反正也是复盘，我会提供手动回溯以及调库版本的代码，这道题倒是A得快；
1
2
3
题目：
- 输入n，代表1~n组成的序列，序列元素互不相同
- 求相邻两数和不为素数的序列个数
直接调用next_permutation库函数的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
// 判断一个树是否是素数
bool IsPrimeNum(int num) {
if (num <= 2) return true;
for (int i = 2; i * i <= num; ++i) {
if (num % i == 0) return false;
}
return true;
}
int main() {
int n;
cin >> n;
vector<int> seq;
for (int i = 1; i <= n; ++i) {
seq.push_back(i);
}
int res = 0;
do {
bool tag = true; // 标志位
for (int i = 0; i < n - 1; ++i) {
int sum = seq[i] + seq[i + 1];
if (IsPrimeNum(sum)) {
tag = false;
}
}
if (tag) ++res;
} while(next_permutation(seq.begin(), seq.end()));
cout << res << endl;
return 0;
}
手写回溯版本的代码：这种情况就是全排列的一个变种而已；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
int res = 0;
vector<int> every_seq;
bool IsPrimeNum(int num) {
if (num <= 2) return true;
for (int i = 2; i * i <= num; ++i) {
if (num % i == 0) return false;
}
return true;
}
void backtrace(vector<int>& v, int index) {
if (index == (int)v.size()) {
++res;
return;
}
for (int i = index; i < (int)v.size(); ++i) {
every_seq.push_back(v[i]);
swap(v[i], v[index]); // 换位置
if (every_seq.size() > 1 && IsPrimeNum(*every_seq.rbegin() + *(every_seq.rbegin() + 1))) {
every_seq.pop_back();
swap(v[i], v[index]); // 换回来
continue; // 剪枝
}
backtrace(v, index + 1);
every_seq.pop_back(); // 这两行同样的操作
swap(v[i], v[index]);
}
}
int main() {
int n;
cin >> n;
vector<int> seq;
for (int i = 1; i <= n; ++i) {
seq.push_back(i);
}
backtrace(seq, 0);
cout << res << endl;
return 0;
}
第二题
第二题多少有点可惜，其实题目不难，当时感觉没看懂题就跳过了，这次再做一遍：
1
2
3
4
5
题目：
- 给出一个n * m的字符矩阵，求三个顶点分别为'y', 'o', 'u'的直角三角形的个数；
输入范围：
- n, m <= 1000
经过分析，这道题目的思路基本可以按照如下步骤进行：
- 首先，遍历一轮矩阵，分别找到y o u三个字母的位置；
- 我们先做一个标记，用1代表y，用2代表o，用3代表u，用4代表其他；
- 遇到y，就将该位置标记为1，遇到o，就将该位置标记为2…类推；
- 接下来统计每一行，每一列中y o u各自出现的次数；
- 最终去遍历上述的标记矩阵，分别以y o u作为直角的顶点做判断；
- 这里又需要考虑两种情况，以顶点是y为例
- o出现在行，u出现在列；
- o出现在列，u出现在行；
- 解决；
贴上代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
int getTriangleNums(const vector<vector<char>>& mat) {
int row = mat.size();
int col = mat[0].size();
vector<vector<int>> tag_info(row, vector<int>(col));
vector<vector<int>> row_tag(row, vector<int>(5)); // 行状态，因为仅有四种状态，列维度设置为5是因为颜色的对应，不需要处理下标为0的情况
vector<vector<int>> col_tag(col, vector<int>(5)); // 列状态
// 下面这个循环标记相应字符出现的位置，同时统计了每行或者每列中y o u出现的次数
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j)
{
if (mat[i][j] == 'y') {
tag_info[i][j] = 1;
++row_tag[i][1];
++col_tag[j][1];
}
else if (mat[i][j] == 'o') {
tag_info[i][j] = 2;
++row_tag[i][2];
++col_tag[j][2];
}
else if (mat[i][j] == 'u') {
tag_info[i][j] = 3;
++row_tag[i][3];
++col_tag[j][3];
}
else {
tag_info[i][j] = 4;
++row_tag[i][4];
++col_tag[j][4];
}
}
}
long res = 0;
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (tag_info[i][j] == 1) {
res += row_tag[i][2] * col_tag[j][3];
res += row_tag[i][3] * col_tag[j][2];
}
if (tag_info[i][j] == 2) {
res += row_tag[i][1] * col_tag[j][3];
res += row_tag[i][3] * col_tag[j][1];
}
if (tag_info[i][j] == 3) {
res += row_tag[i][2] * col_tag[j][1];
res += row_tag[i][1] * col_tag[j][2];
}
}
}
return res;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<char>> input_char(n, vector<char>(m));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> input_char[i][j];
}
}
cout << getTriangleNums(input_char) << endl;
return 0;
}
第三题
先看题目：
1
2
3
题目：
- 给出n个整数，每一次操作可以选数组中两个数分别+1 -1，求使得n个数都位于[l, r]的最少操作次数；
- 不存在这种操作则输出-1；
其实这道题思路是想到了的，只是可惜没A全；
我考试时的思路：
- 先将整个数组排序，然后让最大的到右边界范围内，让最小的到左边界；
- 两者操作的次数取较大值，同时还要检测操作完成之后这两个数是否在边界范围内；
- 理论上说这个思路是没错的，只是可惜没有考虑用long去处理；
但是更简便的思路是这样做：用数组元素之和去束缚整个范围；
- 对数组求和，如果和小于左边界乘以元素数目的值或者和大于右边界乘以元素数目的值，则不可能在区间内；
- 这是很简单的思路…..因为+1，-1的操作并不会干扰数组的和；
- 如果能在上述区间内，显然，一定可以通过某种手段使得整个数组位于要求的左右边界之间；
- 我们只需要求出这个过程中的最小次数；
- 因此只需要对每个元素做处理，求使得每个元素在区间范围内的总次数即可；
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, l, r;
cin >> n >> l >> r;
vector<int> array(n);
for (int i = 0; i < n; i++)
{
cin >> array[i];
}
long sum = 0;
long cnt_1 = 0;
long cnt_2 = 0;
for (auto &&n : array)
{
sum += n;
if (n < l) cnt_1 += l - n;
else if (n > r) cnt_2 += n - r;
}
if (sum < l * n || sum > r * n) cout << -1 << endl;
else cout << max(cnt_1, cnt_2) << endl;
return 0;
}
第四题
第四题考试的时候直接暴力做的，O(n ^ 2)难以避免的超时了，这道题可能才是真的有点难想到；
先看题目：
1
2
3
题目：
- 给一个0和1组成的字符串，求子串中有多少"好串"。
- 对"好串"的定义是：所有的子串中，前缀0的数量全部严格大于1的数量。
思路：
- 我们设置一个计数cnt，计算整个字符串中’0’的个数；
- 该个数是这样的，遇到了1，cnt就减去1，遇到了0，cnt就加上1；
- 每次遍历只要cnt > 0，代表到这个位置前缀0的个数一定是大于1的；
- 且大于的个数代表了以该位置结尾的子串中新增的符合条件的”好串”个数，这个做法实在太妙了；
- 当cnt小于或者等于0了怎么办，说明0的数量已经不如1的数量了，这个时候显然不符合要求，也不会去新增符合条件的”好串”；
- 此刻我们将该数计为0即可，重新去做判断….
我只能说这个找规律的思路简直太妙了；
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
int main() {
int m;
cin >> m;
string s(m, ' ');
for (int i = 0; i < m; i++)
{
cin >> s[i];
}
long ans = 0;
int cnt = 0;
for (auto &&c : s)
{
cnt += c == '0' ? 1 : -1;
if (cnt > 0) ans += cnt;
else cnt = 0;
}
cout << ans << endl;
return 0;
}
以上就是本次携程笔试的复盘总结，只能说很多问题不要先入为主去判断难易；