歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

騰訊2017暑期實習生筆試題解題答案匯總

騰訊2017暑期實習生筆試題解題答案匯總

構造回文

題目

給定一個字符串s,你可以從中刪除一些字符,使得剩下的串是一個回文串。如何刪除才能使得回文串最長呢?

輸出需要刪除的字符個數

輸入描述:

輸入數據有多組,每組包含一個字符串s,且保證:1<=s.length<=1000.

輸出描述:

對於每組數據,輸出一個整數,代表最少需要刪除的字符個數。

輸入例子:

abcda
google

輸出例子:

2
2

解題思路

本題可以轉換為求該字符串與其反序字符串的最長公共子序列問題,即利用LCS算法求解。

例如:abcda的反序字符串為adcba,最長公共子序列為aba,其公共子序列必為回文序列,然後可求出最少刪除多少個字節使其成為回文字符串。

本題采用動態規劃來求解問題,下面看看模擬的推導過程。

狀態轉移方程為:(令A為輸入字符串,B為其反序字符串,num[][]記錄當前最長公共子序列的長度)

   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;
    }
}

Copyright © Linux教程網 All Rights Reserved