算法之牛客网上做的腾讯笔试题（1）

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

输入例子:
abcda
google
输出例子:
2
2

解题思路：先将字符串翻转，再求两个字符创的最大公共子序列，然后就可以知道应该删除那些字符。

区别：最大公共子序列和最大公共子串不同
子串要求在原字符中是连续的，子序列则只需保持相对顺序一致，不需要连续

答案： 大佬啊

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int MAX = 1001;
int MaxLen[MAX][MAX]; 

int MaxL(string s1,string s2){

 for(int i=0;i<=s1.size();i++){
            MaxLen[0][i]=0;
        }
        for(int j=1;j<=s2.size();j++){
            MaxLen[j][0]=0;
        }
        for(int i=1;i<=s1.size();i++){
            for(int j=1;j<=s2.size();j++){
                if(s1[i]==s2[j]){
                    MaxLen[i][j]=MaxLen[i-1][j-1]+1;
                }else{
                    MaxLen[i][j]=max(MaxLen[i-1][j],MaxLen[i][j-1]);
                }
            }
        }
        return MaxLen[s1.size()][s2.size()];
}
int main(){
    string s1;
    while(cin>>s1){
        string s2=s1;
        reverse(s2.begin(),s2.end());
        cout<<s1.size()-MaxL(s1,s2)<<endl;
    }
    return 0;
}

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

#include <iostream>
#include <string>
using namespace std;

int main()
{

    string s;
    while (cin >> s)
    {

        for (int i = 0; i < s.length(); i++)
            if (s[i] >= 'a' && s[i] <= 'z')
                cout << s[i];
        for (int i = 0; i < s.length(); i++)
            if (s[i] <= 'Z' && s[i] >= 'A')
                cout << s[i];
        cout << endl;
    }
    return 0;
}

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

输入描述:
请在这里输入引用内容
输入包含多组测试数据。

对于每组测试数据：

N - 本组测试数据有n个数
a1,a2...an -需要计算的数据
保证:
1<=N<=100000,0<=ai<=INT_MAX.

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

输入例子:
6
45 12 45 32 5 6

输出例子:
1 2

我的答案：（虽然但是，我错了，也不知道为什么）

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n = 0;
    cin >> n;
    vector<int> nums;
    int a ;
    for (int i = 0; i < n; i++) {
        cin >> a;
        nums.push_back(a);
    }
    sort(nums.begin(), nums.end());

    int count = 0;
    int min = nums[n - 1] - nums[0];
    for (int i = 0; i < n-1; i++) {
        if (nums[i + 1] - nums[i] < min) {
            count = 0;
            min = nums[i + 1] - nums[i];
            count++;
        }
        else if (nums[i + 1] - nums[i] == min) {
            count++;
        }
    }
    cout << count << " ";
    int max = nums[n - 1] - nums[0];
    int id = 0;
    int count1 = 0;
    for (int j = n - 1; j > 0; j--) {
        if (nums[j] - nums[id] == max) {
            count1++;
        }
        else {
            break;
        }
    }
    cout << count1 << endl;
    return 0;

}

注意：
2,4,6,8最小差值对数是3（因为差值都是2），但是2,2,2,2这种情况，最小差值对数就不是三，而是6

大佬的答案

#include<iostream>
#include<vector>
#include<algorithm>

 using namespace std;

int main(){
     int n;
     while(cin >> n)
     {
         vector<int> nums(n);
         for(int i = 0; i < n; i++)
             cin>> nums[i];

         int minNum = 0,  maxNum = 0;
         //排序
         sort(nums.begin(), nums.end());

         //最大
         int l = 0, r = n - 1;
         int i = 1, j = 1;//i为最小数的个数，j为最大数的个数
         while(nums[l] == nums[l + 1]) { i++; l++;}
         while(nums[r] == nums[r - 1]) { j++; r--;}
         maxNum = i * j;

         //最小
         int minTemp = nums[1] - nums[0];//最小差值
         int count = 1;
         for(int i = 2; i < n; i++)
         {
             if(nums[i] - nums[i - 1] < minTemp)
             {
                 minTemp = nums[i] - nums[i - 1];
                 count= 1;
             }else if(nums[i] - nums[i - 1] == minTemp) count++;
         }
         if(minTemp > 0) minNum = count;
         else 
         { 
             for(int i = 1; i < n; i++)
             {

                 int j = i - 1;
                 while(nums[i] == nums[j] && j >= 0)
                 {
                     j--; minNum++;
                 }
             }
         }
         cout << minNum <<' ' << maxNum << endl;
     }
     return 0;
 }