腾讯2017暑期实习生编程题（3题）

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

　　思路：区间DP即可。我一开始想的是统计i~j内可以回文的字符个数，然后ans=len-dp[1][len]; 后来发现没法实现，即使是一个字符也是回文的这种情况也考虑到了也没办法做，因为我的思路是在dp[i][j]和dp[i+1][j-1]上进行，这样没有包括边界，这样做肯定是错的。比方说aab，在考虑外边的a和b时，如果这么转移应该是得到答案是2的，却得到了1（中间的a本身）。那么答案给出的方法是直接考虑dp[i][j]表示的是i~j内需要删除的个数，且考虑了边界。其代码如下：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1000 + 5;

int dp[N][N];
char s[N];

int main()
{
    while(scanf("%s",s+1)==1)
    {
        int len = strlen(s+1);
        memset(dp,0,sizeof(dp));
        for(int i=2;i<=len;i++)
        {
            dp[i-1][i] = s[i-1]==s[i]?0:1;
            for(int j=i-2;j>=1;j--)
            {
                if(s[j]==s[i]) dp[j][i] = dp[j+1][i-1];
                else dp[j][i] = min(dp[j][i-1],dp[j+1][i]) + 1;
            }
        }
        printf("%d
",dp[1][len]);
    }
    return 0;
}

那么，借鉴一下dp考虑边界的思路，再用我自己的方法，就也能通过了~我的代码如下：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1000 + 5;

int dp[N][N];
char s[N];

int main()
{
    while(scanf("%s",s+1)==1)
    {
        int len = strlen(s+1);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=len;i++)
        {
            dp[i][i] = 1;
            dp[i][i+1] = s[i]==s[i+1]?2:1;
        }
        for(int i=3;i<=len;i++)
        {
            for(int j=1;j+i-1<=len;j++)
            {
                if(s[j]==s[j+i-1]) dp[j][j+i-1] = dp[j+1][j+i-2] + 2;
                else
                {
                    dp[j][j+i-1] = max(dp[j][j+i-2],dp[j+1][j+i-1]);
                }
            }
        }
        printf("%d
",len-dp[1][len]);
    }
    return 0;
}

所以说这样就得到了一个区间dp需要注意的一点，有时候是要考虑边界的！

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

　　思路：最初的想法就是直接写一个cmp：return (a>='a' && a<='z' && b>='A' && b<='Z'); 之后对字符串sort一下。思路看上去很棒，但是无法通过，有些长的会出现问题，原因的话我想是因为快排的实现原理吧：随机选一个位置的字符x，按照跟x的比较关系把序列分成小于x的和大于等于x的，然后把x放在这两段之间，然后分别递归做这两段。那么，就没办法保持小写字母和大写字母它们内部原先的顺序了，比方说我选出一个B，可以保证的是小写的全在它左边，但是大写字母和它没有比较关系，那么就乱了。

　　但是，这个思路是值得借鉴的，只要手写个冒泡就能通过了。代码如下：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;

char s[1000+5];

bool needChange(char a,char b)
{
    return (a>='A' && a<='Z' && b>='a' && b<='z');
}

int main()
{
    while(scanf("%s",s+1)==1)
    {
        int len = strlen(s+1);
        for(int i=1;i<=len-1;i++)
        {
            for(int j=1;j<=len-i;j++)
            {
                if(needChange(s[j],s[j+1])) swap(s[j],s[j+1]);
            }
        }
        puts(s+1);
    }
}

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

　　一开始想着先排序，然后各种lower_bound,upper_bound等等。。然后发现写起来非常烦，那么这里给出一种用map的方法，非常巧妙！代码如下：

#include <stdio.h>
#include <algorithm>
#include <map>
#include <string.h>
#include <iostream>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        map<int,int> M;
        bool flag = false;  //flag表示有相同元素
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            if(M.find(x) == M.end()) M.insert(make_pair(x,1));
            else M[x]++,flag = true;
        }

        int ans1=0,ans2;
        int num = M.size();  //相差最大值的答案和元素的种类数有关
        if(num>1) ans2 = (*M.begin()).second * (*M.rbegin()).second;
            else ans2 = (*M.begin()).second * ((*M.begin()).second - 1)/2;
        if(flag)
        {
            for(map<int,int>::iterator it = M.begin();it!=M.end();it++)
            {
                if((*it).second>1) ans1 += (*it).second * ((*it).second - 1)/2;
            }
        }
        else
        {
            int diff = (*M.rbegin()).second - (*M.begin()).second;
            for(map<int,int>::iterator it = M.begin(),it2 = ++M.begin();it2!=M.end();it++,it2++)
            {
                int t = (*it2).first - (*it).first;
                if(t < diff) ans1 = (*it2).second * (*it).second,diff = t;
                else if(t == diff) ans1 += (*it2).second * (*it).second;
            }
        }

        cout<<ans1<<" "<<ans2<<endl;
    }
}

现在，真心感受到了STL工具的强大！