腾讯2017暑期实习生编程题

腾讯2017暑期实习生编程题

题目来源：https://www.nowcoder.com/questionTerminal/28c1dc06bc9b4afd957b01acdf046e69

1.构造回文

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

输入描述:

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

输出描述:

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

输入例子:

abcda
google

输出例子:

2

2

思路：

求原字符串和其反串的最大公共子串的长度，然后用原字符串的长度减去这个最大公共子串的长度就得到了最小编辑长度。

特别注意：最大公共子串并不一定要连续的，只要保证出现次序一致即可看作公共子串

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

const int MAX = 1001;
int MaxLen[MAX][MAX]; //最长公共子序列，动态规划求法

int maxLen(string s1, string s2)
{
    int length1 = s1.size();
    int length2 = s2.size();
    for (int i = 0; i <= length1; ++i)
        MaxLen[i][0] = 0;
    for (int i = 0; i <= length2; ++i)
        MaxLen[0][i] = 0;

    for (int i = 1; i <= length1; ++i)
    {
        for (int j = 1; j <= length2; ++j)
        {
            if (s1[i - 1] == s2[j - 1])
            {
                MaxLen[i][j] = MaxLen[i - 1][j - 1] + 1;
            }
            else
            {
                MaxLen[i][j] = max(MaxLen[i - 1][j], MaxLen[i][j - 1]);
            }
        }
    }

    return MaxLen[length1][length2];
}

int main()
{
    string s;
    while (cin >> s)
    {
        int length = s.size();
        if (length == 1)
        {
            cout << 1 << endl;
            continue;
        }
        //利用回文串的特点
        string s2 = s;
        reverse(s2.begin(), s2.end());
        int max_length = maxLen(s, s2);
        cout << length - max_length << endl;
    }
    return 0;
}

2.字符移位

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

输入描述:

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

输出描述:

对于每组数据，输出移位后的字符串。

输入例子:

AkleBiCeilD

输出例子:

kleieilABCD

#include<iostream>  
#include<string>
using namespace std;
int main()
{
    string str1;
    while (cin >> str1)
    {
        int i = str1.length();//指向末尾的指针  
        int j = i - 1;//指向前一个  
        while (j >= 0)
        {
            if (isupper(str1[j]))//如果是大写字母 
            {
                 char temp = str1[j];
                 int t = j;
                 i--;
                 while (t < i)//将j-i间的小写字母前移  
                 {
                      str1[t] = str1[t + 1];
                      t++;
                 }
                 str1[i] = temp;
              }
              j--;
        }
        cout << str1 << endl;
    }
    return 0;
}

另外，也可以直接输出两次，第一次输出小写字母；第二次输出大写字母。

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    while (cin >> s)
    {
        if (s.length() >= 1 && s.length() <= 1000)
        {
            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;
}

3.有趣的数字

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

输入描述:

输入包含多组测试数据。 对于每组测试数据： N - 本组测试数据有n个数 a1,a2...an - 需要计算的数据 保证: 1<=N<=100000,0<=ai<=INT_MAX.

输出描述:

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

输入例子:

6
45 12 45 32 5 6

输出例子:

1 2

思路：

1.先排序

   特殊情况：如果排完序之后发现数组中所有数都相同，直接输出结果

   结果为：差最大个数 = 差最小个数 = （n * (n-1))/2;(两两组合)

2.排序之后

　　2.1差值最大的好求，看有序数组有几个最小值和几个最大值，相乘即可。

　　2.2差值最小的，由于是有序数组，必定是相邻的差值较小，故由排序后的有序数组求出差值最小值。如果差值最小值为0，则算出数组中相等的元素的对数；

　　如果差值最小值不为0，则只需计算有多少个最小值即可。

 

#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());
        if (nums[0] == nums[n-1])
        {
            maxNum = minNum = (n*(n - 1) / 4);
            cout << minNum << " " << maxNum << endl;
            continue;
        }

        //最大
        int m1 = 0, m2 = n - 1, a = 1, b = 1;
        while (nums[m1 + 1] == nums[m1]) 
        {
            a++;
            m1++;
        }
        while (nums[m2] == nums[m2 - 1]) 
        {
            b++;
            m2--;
        }
        maxNum = a*b;

        //最小
        int minTemp = nums[n - 1];
        for (int i = 1; i<n; i++) 
        {
            if (nums[i] - nums[i - 1]<minTemp) 
            {
                minTemp = nums[i] - nums[i - 1];
            }
        }
        if (minTemp >0) 
        {
            for (int i = 1; i<n; i++) 
            {
                if (nums[i] - nums[i - 1] == minTemp) 
                {
                    minNum++;
                }
            }
        }
        else
        {
            for (int i = 1; i<n; i++) 
            {
                int j = i - 1;
                while (nums[j] == nums[i] && j >= 0) 
                {
                    minNum++;
                    j--;
                }
            }
        }
        cout << minNum << " " << maxNum << endl;
    }
    return 0;
}