腾讯2017暑期实习生编程题

秒速五厘米 2022-03-10 02:36 322阅读 0赞

# 题目一： #

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

输出需要删除的字符个数。

输入描述:

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

输出描述:

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

## 解题思路： ##

先reverse求字符串的反串，然后求正反两字符串的最长公共子序列，要删除的字符个数就是总长度减去最长公共子序列的长度。

## 具体实现： ##

#include<bits/stdc++.h>
    using namespace std;
     
    int min_deleteNum(string s1){
        int len = s1.length();
        int temp[len+1][len+1];
        string s2(s1);
        reverse(s2.begin(), s2.end());
        memset(temp, 0, sizeof(temp));
        for(int i = 0; i < s1.length(); ++i){
            for(int j = 0; j < s2.length(); ++j){
                if(s1[i] == s2[j]){
                    temp[i+1][j+1] = temp[i][j] + 1;
                }else{
                    temp[i+1][j+1] = max(temp[i][j+1], temp[i+1][j]);
                }
            }
        }
        return len-temp[len][len];
    }
     
    int main(){
        string str;
        while(cin >> str){
            cout << min_deleteNum(str) << endl;
        }
        return 0;
    }

# 题目二： #

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

输入描述:

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

输出描述:

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

输入例子:

AkleBiCeilD

输出例子:

kleieilABCD

## 解题思路： ##

题目要求不能申请额外的空间，所以要在字符串上进行操作，从后向前处理。

用两个“指针”，一个指针i始终指向已处理过得字串之首（初始位于字符串末尾后面一个位置），另一个指针j前进，当遇到大写字母时停下进行如下操作：i指针前进1，用temp字符保存下这个大写字母，然后用循环将j-i之间的小写字母都前移一位，最后将s\[i\]置为保存的大写字母。

这里用了判断是否为大写字母的函数：isupper()

## 具体实现： ##

#include<iostream>
    #include<string>
    using namespace std;
     
    int main(){
    	string s;
    	while (cin >> s){
    		int i = s.length() ;
    		int j = i -1;
    		while (j >= 0){
    			if (isupper(s[j])){
    				char temp = s[j];
    				int t = j;
    				i--;
    				while (t < i){//将j-i间的小写字母前移
    					s[t] = s[t+1];
    					t++;
    				}
    				s[i] = temp;
    			}
    			j--;
    		}
    		cout << s << endl;
    	}
    	return 0;
    }

# 题目三： #

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

## 解题思路： ##

先将数组排序。

求相差最大的对数：特殊情况是所有数字相等，此时单独计算; 普通情况就算最大值有多少个相等的，最小值有多少个相等的，然后两个数相乘；

求相差最小的对数：首先求出最小相差多少。如果为0，则计算有多少个相等的数字对；如果不为0，则遍历数组求出相邻两个数有多少对的差等于最小差值。

## 具体实现： ##

#include <bits/stdc++.h>
    using namespace std;
    
    int main(){
        int n;
        while(cin >> n){
            vector<int> array(n);
            for(int i = 0; i < n; i++){ cin >> array[i]; }
            sort(array.begin(), array.end());
            int min_num = 0, max_num = 0;
            //max number
            if(array[0] == array[n-1]){ //如果所有的数字都相等
                max_num = n * (n-1) / 2;
            }else{
                int m1 = 0, m2 = n-1;
                int a = 1, b = 1;
                while(array[m1+1] == array[m1]){
                    a++;
                    m1++;
                }
                while(array[m2-1] == array[m2]){
                    b++;
                    m2--;
                }
                max_num = a * b;
            }
    
            //min number
            int tempMin = array[n-1]- array[0];
            for(int i = 0; i < n - 1; i++){
                if(array[i+1] - array[i] < tempMin){
                    tempMin = array[i+1] - array[i];
                }
            }
            if(tempMin != 0){ //如果没有相等的数
                for(int i = 0; i < n-1; i++){
                    if(array[i+1] - array[i] == tempMin){
                        min_num++;
                    }
                }
            }else{//有相等的数字
                int i = 0;
                while(i < n-1) {
                    int temp = 1;
                    int j = i + 1;
                    while (array[j] == array[i]) {
                        temp++;
                        j++;
                    }
                    min_num += temp * (temp - 1) / 2;
                    i = j + 1;
                }
            }
            
            cout << max_num << " " << min_num << endl;
        }
        return 0;
    }

—————————————————————————————————————————————

加油加油！ヾ(◍°∇°◍)ﾉﾞ编程能力都是练出来的！你也阔以的！