2022年4月14日——携程笔试

携程笔试主要分为选择题和编程题两部分。

选择题：

携程选择题一共 20 道，每题 1 分；

主要考察的点涵盖线性代数、概率论（考了两道几何概型）、机器学习基础知识、深度学习基础知识，整体的难度并不大，基本上都是比较基础的知识。

编程题：

携程编程题一共 4 道，每题 20 分；

1. 输出一个 'U' 字型：

   输入：1

   输出：

   输入：3

   输出：

   代码：

   #include<bits/stdc++.h>
   
   using namespace std;
   
   int main() {
       int n;
       cin >> n;
       for(int i = 0; i < 3 * n; ++i) {
           for(int j = 0; j < n; ++j)
               cout << '*';
           for(int j = 0; j < 2 * n; ++j)
               cout << '.';
           for(int j = 0; j < n; ++j)
               cout << '*';
           cout << endl;
       }
       for(int i = 1; i <= n; ++i) {
           for(int j = 0; j < i; ++j)
               cout << '.';
           for(int j = 0; j < n; ++j)
               cout << '*';
           for(int j = 0; j < 2 * (n - i); ++j)
               cout << '.';
           for(int j = 0; j < n; ++j)
               cout << '*';
           for(int j = 0; j < i; ++j)
               cout << '.';
           cout << endl;
       }
       return 0;
   }

   
   

2. 本质是一个统计频率的问题：

   代码：

   #include<bits/stdc++.h>
   
   using namespace std;
   
   int main() {
       int n;
       long long res = 0;
       char c;
       cin >> n;
       int nums[n];
       map<int, pair<int, int>> pMap;
       for(int i = 0; i < n; ++i) {
           cin >> nums[i];
           if(pMap.find(nums[i]) == pMap.end())
               pMap[nums[i]] = {0, 0};
       }
       for(int i = 0; i < n; ++i) {
           cin >> c;
           if(c == 'B')
               pMap[nums[i]].first++;
           else
               pMap[nums[i]].second++;
       }
       for(auto p : pMap) {
           res += p.second.first * p.second.second;
       }
       cout << res << endl;
       return 0;
   }

   
   

3. 贪心相关的问题

   给你一串字符串，里面只包含 '0' 和 '1'（两者数目相差不超过 1），现在通过两两交换让 '1' 和 ’0‘ 字符两两交叉排列，问最少的交换次数；

   代码：

   #include<bits/stdc++.h>
   
   using namespace std;
   
   int main() {
       string s;
       long long res = 0;
       cin >> s;
       vector<int> zero_index;
       vector<int> one_index;
       // 统计 '0' 和 '1' 出现的下标位置 
       for(int i = 0; i < s.size(); ++i)
           if(s[i] == '0')
               zero_index.push_back(i);
           else
               one_index.push_back(i);
       // 如果 '0' 更多，则 '0' 全部放在奇数位置 
       if(zero_index.size() > one_index.size()) 
           for(int i = 0; i < zero_index.size(); ++i)
               res += abs(i * 2 - zero_index[i]);
       // 如果 '1' 更多，则 '1' 全部放在奇数位置 
       else if(one_index.size() > zero_index.size())
           for(int i = 0; i < one_index.size(); ++i)
               res += abs(i * 2 - one_index[i]);
       // 如果 '1' 和 '0' 一样多，则选择两种情况最小的 
       else {
           long long a1 = 0, a2 = 0;
           for(int i = 0; i < zero_index.size(); ++i)
               a1 += abs(i * 2 - zero_index[i]);
           for(int i = 0; i < one_index.size(); ++i)
               a2 += abs(i * 2 - one_index[i]);
           res = min(a1, a2);
       }
       cout << res << endl;
       return 0;
   }

   
   

   
   

4. 能被 9 整除的子序列数目：

   给你一个数字组成的字符串，问你该字符串有多少个子串组成的数能被 9 整除，字符串可能很长；

   输入：“1188”

   输出：5，（因为可以组成 4 个 18, 1 个 1188都能被 9 整除）

   代码：

   // 典型的动态规划的问题
   #include<bits/stdc++.h>
   
   using namespace std;
   
   int main() {
       string s;
       int res = 0;
       int dp[9], tmp[9];
       memset(dp, 0, sizeof(dp));
       cin >> s;
       for(int i = 0; i < s.size(); ++i) {
           int t = s[i] - '0';
           memset(tmp, 0, sizeof(tmp));
           tmp[t % 9] = 1;
           for(int j = 0; j < 9; ++j)
               if(dp[j] != 0)
                   tmp[(j * 10 + t) % 9] += dp[j];
           res = (res + tmp[0]) % (1000000007);
           //cout << tmp[0] << endl;
           for(int j = 0; j < 9; ++j)
               dp[j] = (dp[j] + tmp[j]) % 1000000007;
       }
       cout << res << endl;
       return 0;
   }

总结：

携程的笔试整体难度不大，但是我觉的题目的质量还可以。