你好,游客 登录 注册 搜索
背景:
阅读新闻

腾讯2017暑期实习生笔试题解题答案汇总

[日期:2016-09-13] 来源:Linux社区  作者:terence1212 [字体: ]

腾讯2017暑期实习生笔试题解题答案汇总

构造回文

题目

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

输出需要删除的字符个数

输入描述:

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

输出描述:

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

输入例子:

abcda
google

输出例子:

2
2

解题思路

本题可以转换为求该字符串与其反序字符串的最长公共子序列问题,即利用LCS算法求解。

例如:abcda的反序字符串为adcba,最长公共子序列为aba,其公共子序列必为回文序列,然后可求出最少删除多少个字节使其成为回文字符串。

本题采用动态规划来求解问题,下面看看模拟的推导过程。

状态转移方程为:(令A为输入字符串,B为其反序字符串,num[][]记录当前最长公共子序列的长度)

腾讯2017暑期实习生笔试题解题答案汇总

 
 0abcda
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

linux
相关资讯       腾讯2017暑期实习生笔试题 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款