腾讯2017暑期实习生编程题

Posted on by Dennis

前言

最近在刷Leetcode 没搭理牛客网（逃，纪念第一次全AC，在细节上面比较棘手，这方面的基本功我还有待加强，争取做到”心里想什么，代码就能编什么，无Bug“

第一题

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？

输出需要删除的字符个数。
输入描述:

输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:

对于每组数据，输出一个整数，代表最少需要删除的字符个数。
示例1

输入

abcda
google

输出

2
2

这道题和Leetcode 583比较像，这道题就是把Leetcode上面的替换成字符串和其逆序字符串之间的最小公共子序列长度问题，我们可以使用同样地方法进行处理，不过需要对结果进行一个额外处理。

  1. #include <bits/stdc++.h>  
  2. using namespace std;  
  3.    
  4. int main() {  
  5.     string s1;  
  6.     while(cin>>s1) {  
  7.         string s2(s1.rbegin(), s1.rend());  
  8.         int n = s1.length();  
  9.         vector<vector<int>> dp(n+1, vector<int>(n+1, 0));  
  10.         for(int i = 1; i <= n; ++i) {  
  11.             for(int j = 1; j <= n; ++j) {  
  12.                 if(s1[i-1] != s2[j-1]) {  
  13.                     dp[i][j] = max(dp[i-1][j], dp[i][j-1]);  
  14.                 } else {  
  15.                     dp[i][j] = dp[i-1][j-1] + 1;  
  16.                 }  
  17.             }  
  18.         }  
  19.         int ans = n - dp[n][n];  
  20.         cout<<ans<<endl;  
  21.     }  
  22.     return 0;  
  23. }  

第二题

小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。

你能帮帮小Q吗？

输入描述:

输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出移位后的字符串。
示例1

输入

AkleBiCeilD

输出

kleieilABCD

这道题的关键在于理清好逻辑，我之前尝试过使用Two pointers进行交换，但是这样却改边了相对位置，后来在草稿纸上推了一下过程，梳理好逻辑。

  1. #include <bits/stdc++.h>  
  2. using namespace std;  
  3. int main() {  
  4.     string s;  
  5.     while(cin>>s) {  
  6.         int last = 0;  
  7.         for(int i = 0; i < s.length(); ++i) {  
  8.             if((s[i] >= 'A' && s[i] <= 'Z')) continue;     //大写字母跳过，交换小写字母  
  9.             for(int j = i; j > last; --j) swap(s[j], s[j-1]); //持续两两交换，直到移动到上一次交换的位置为止  
  10.             ++last;  
  11.         }  
  12.         cout<<s<<endl;  
  13.     }  
  14.     return 0;  
  15. }  

第三题

小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，相差最小的有多少对呢？相差最大呢？

输入描述:
 输入包含多组测试数据。

 对于每组测试数据：

 N - 本组测试数据有n个数

 a1,a2...an - 需要计算的数据

 保证:

 1<=N<=100000,0<=ai<=INT_MAX.



输出描述:

对于每组数据，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。
示例1

输入

6
45 12 45 32 5 6

输出

1 2

想过暴力求解，时间复杂度是O(N^2)，后来发现LTE。那就只能排序再解决问题啦，不过这里面有一个坑，举个例子就是当两个数之间的差值为0时：5 5 5 5，此时的方案数目为C_4^2。这里面需要谨慎处理。

  1. #include <bits/stdc++.h>  
  2. using namespace std;  
  3. int main() {  
  4.     int n;  
  5.     while(cin>>n) {  
  6.         vector<int> nums;  
  7.         while(n--) {  
  8.             int tmp; cin>>tmp;  
  9.             nums.push_back(tmp);  
  10.         }  
  11.         n = nums.size();  
  12.         sort(nums.begin(), nums.end());  
  13.         int minv = INT_MAX, maxv = INT_MIN, mincnt = 1, maxcnt = 1, diff0 = 1;  
  14.         //计算最小  
  15.         int i = 0;  
  16.         while(i < n - 1) {  
  17.             int diff = nums[i+1] - nums[i];  
  18.             if(diff == 0) {  
  19.                 minv = 0;  
  20.                 break;  
  21.             }  
  22.             if(diff < minv) {  
  23.                 minv = diff;  
  24.                 mincnt = 1;  
  25.             } else if(diff == minv) {  
  26.                 ++mincnt;  
  27.             }  
  28.             ++i;  
  29.         }  
  30.         if(minv == 0) {  
  31.             mincnt = 0;  
  32.             while(i < n - 1) {  
  33.                 int cur = i, cnt = 1;  
  34.                 while(cur < n - 1) {  
  35.                     if(nums[cur] == nums[cur+1]) {  
  36.                         ++cnt;  
  37.                         ++cur;  
  38.                     }  
  39.                     else break;  
  40.                 }  
  41.                 mincnt += (cnt * (cnt - 1) / 2);  
  42.                 i = cur + 1;  
  43.             }  
  44.         }  
  45.         //计算最大  
  46.         int l = 1, r = 1;  
  47.         for(int i = 0; i < n - 1; ++i) {  
  48.             if(nums[i] == nums[i+1]) ++l;  
  49.             else break;  
  50.         }  
  51.         for(int i = n - 1; i > 0; --i) {  
  52.             if(nums[i] == nums[i-1]) ++r;  
  53.             else break;  
  54.         }  
  55.         maxcnt = l * r;  
  56.         cout<<mincnt<<" "<<maxcnt<<endl;  
  57.     }  
  58. }  

发表回复

您的电子邮箱地址不会被公开。