腾讯2017暑期实习生笔试题解题答案汇总
构造回文
题目
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数
输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。
输入例子:
abcda
google
输出例子:
2
2
解题思路
本题可以转换为求该字符串与其反序字符串的最长公共子序列问题，即利用LCS算法求解。例如：abcda的反序字符串为adcba，最长公共子序列为aba，其公共子序列必为回文序列，然后可求出最少删除多少个字节使其成为回文字符串。本题采用动态规划来求解问题，下面看看模拟的推导过程。状态转移方程为：（令A为输入字符串，B为其反序字符串，num[][]记录当前最长公共子序列的长度）
| | 0 | a | b | c | d | a |
|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 | 1 | 2 |
| d | 0 | 1 | 1 | 1 | 2 | 2 |
| c | 0 | 1 | 1 | 2 | 2 | 2 |
| b | 0 | 1 | 2 | 2 | 2 | 2 |
| a | 0 | 1 | 2 | 2 | 2 | 3 |
下面来看解题代码：
#include <stdio.h>#include <iostream>#include <string.h>#include <vector>#include <string>using namespace std;int main（）{string s;while（cin>>s）{int len = s.length（）;int maxlen = 0;vector<vector<int> > Vec;for（int i = 0 ; i < len+1 ; i++）{vector<int> temp（len+1,0）;Vec.push_back（temp）;}for（int i = 1; i< len+1 ; i++）{for（int j = 1 ; j < len+1;j++）{if（s[i-1]==s[len-j]）{Vec[i][j] = Vec[i-1][j-1]+1;}else {Vec[i][j] = max（Vec[i-1][j],Vec[i][j-1]）;}}}cout<<len-Vec[len][len]<<endl;}}字符移位
小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。
你能帮帮小Q吗？
输入描述:输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:对于每组数据，输出移位后的字符串。
输入例子:AkleBiCeilD
输出例子:
kleieilABCD
解题思路
如果碰到大写，就插入到字符串的最后面，这个没什么好说的，看代码吧。
#include <stdio.h>#include <iostream>#include <string.h>#include <vector>#include <string>using namespace std;int main（）{char a[1000];while（cin>>a）{int len = strlen（a）;int end = len-1;for（int i = 0 ;i <= end ;）{if（a[i]>="A"&&a[i]<="Z"）{char temp = a[i];int idx = i;for（int j = i+1;j<len;j++）{a[idx++] = a[j];}a[len-1] = temp;end--;}else i++;}cout<<a<<endl;}}有趣的数字
小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，差最小的有多少对呢？差最大呢？
输入描述:输入包含多组测试数据。
对于每组测试数据：
N - 本组测试数据有n个数
a1,a2…an - 需要计算的数据
保证:
1<=N<=100000,0<=ai<=INT_MAX.
输出描述:对于每组数据，输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。
输入例子:
6
45 12 45 32 5 6
输出例子:
1 2
解题思路
先对数组进行排序，然后求最大差值组和最小差值组。最大差值肯定发生在首尾两个数字之间，不过注意到存在相同数字，所以最大差值组数等于最小数的个数*最大数的个数最小差值出现在相邻两个数之间，这里需要考虑差值最小为0的情况。如果差值为0，计算相等的数的个数n，则共有n*（n-1）/2组不为0的话，直接累加即可。
#include <stdio.h>#include <iostream>#include <string.h>#include <vector>#include <string>#include <limits.h>#include <algorithm>using namespace std;int main（）{int n;while（cin>>n）{vector<int> vec（n,0）;for（int i = 0 ; i < n; i++）{cin>>vec[i];}sort（vec.begin（）,vec.end（））;int difmin = INT_MAX;int cntmin = 0;int cnt = 1;for（int i = 1 ;i<n;i++）{if（vec[i]==vec[i-1]） {//差值为0的情况if（difmin>0）{cntmin = 0;}difmin = 0;cnt++;//计算个数}else {if（cnt>1）{ // 如果存在差值为0的情况cntmin += cnt*（cnt-1）/2; cnt =1;}else {int dif = vec[i]-vec[i-1];if（dif<difmin）{difmin=dif;cntmin=1;}else if（difmin==dif） cntmin++;}}}if（cnt>1）{ // 当cnt大于1的时候，需要算进去cntmin += cnt*（cnt-1）/2;cnt =1;}int cnt1 = 1;int cnt2 = 1;for（int i = 1 ; i< n ;i++）{if（vec[i]==vec[0]） cnt1++;else break;}for（int i = n-2; i>=0 ; i--）{if（vec[i]==vec[n-1]） cnt2++;else break;}int cntmax = cnt1*cnt2;cout<<cntmin<<" "<<cntmax<<endl;}}本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-09/135167.htm
易网时代-编程资源站