搜狐2017秋招研發工程師筆試題目

第一題：保留最大的數字

題目

給定一個十進制的正整數number，選擇從裡面去掉一部分數字，希望保留下來的數字組成的正整數最大。

輸入描述:

輸入為兩行内容，第一行是正整數number，1 ≤ length(number) ≤ 1000。第二行是希望去掉的數字數量cnt 1 ≤ cnt < length(number)。

輸出描述:

輸出保留下來的結果。

示例1

輸入

325 1

輸出

35

分析

例如數字51643，需要删除3位數而使剩下的數字組合最大，此時需要從頭開始兩個數字比較大小，

如果目前數字比其下一位小，則删除目前數字，此時變為5643，繼續從頭開始周遊，5比6小，則删除5，變為643 繼續從頭周遊，當走到4的位置發現4比3大，而且4已經是倒數第二位數字，則删除最後一位數字，就得到了64 。

關鍵點：

1. 每次j都需要從頭周遊
2. 2.需要考慮最後兩個數字比較時，如果倒數第二位比最後一位小，需要删除最後一個數字。

代碼

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
    string number;
    int count;
    int j;
    cout<<"請輸入一個十進制的正整數:";
    while(cin>>number)
    {
        cout<<"請輸入要去掉的數字個數:";
        cin>>count;
        for(int i = ;i<count;i++)
        {
            int length = number.length();
            for(j = ;j<length-;j++)
            {
                if(number[j]<number[j+])
                {
                    number.erase(number.begin()+j);
                    break;
                }
            }
            if(j == length-)  //例如51643,當j到數字倒數第二位時，4比3大，此時要删除3，
                number.erase(number.end()-);
            j--; //每次都需要j--使j從數字的開始周遊。
        }
        cout<<number;
    }
    return ;
}
           

第二題：彩色寶石項鍊

題目

有一條彩色寶石項鍊，是由很多種不同的寶石組成的，包括紅寶石，藍寶石，鑽石，翡翠，珍珠等。 有一天國王把項鍊賞賜給了一個學者，并跟他說，你可以帶走這條項鍊， 但是王後很喜歡紅寶石，藍寶石，紫水晶，翡翠和鑽石這五種，我要你從項鍊中截取連續的一小段還給我， 這一段中必須包含所有的這五種寶石，剩下的部分你可以帶走。如果無法找到則一個也無法帶走。

請幫助學者找出如何切分項鍊才能夠拿到最多的寶石。

輸入描述:

我們用每種字元代表一種寶石，A表示紅寶石，B表示藍寶石，C代表紫水晶，D代表翡翠，E代表鑽石，F代表玉石，G代表玻璃等等，

我們用一個全部為大寫字母的字元序清單示項鍊的寶石序列，注意項鍊是首尾相接的。每行代表一種情況。

輸出描述:

輸出學者能夠拿到的最多的寶石數量。每行一個

示例1

輸入

ATTMBQECPD

輸出

3

代碼

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
    {
    string str;
    while (cin>>str) {
        int len=str.size();
        string str1="";
        for (int i=;i<len-;i++) {
            str1+=str[i];
        }
        str+=str1;
        int min=;
        int a,b,c,d,e,index=;
        for (int i=;i<*len-;i++) {
            a=,b=,c=,d=,e=;
            for (int j=i;j>=;j--) {
                if (str[j]=='A') a=;
                if (str[j]=='B') b=;
                if (str[j]=='C') c=;
                if (str[j]=='D') d=;
                if (str[j]=='E') e=;
                index++;
                if (a+b+c+d+e==) {
                    if (index<min) {
                        min=index;
                    }
                    index=;
                    break;
                }
            }
        }
        if (min==) cout<<<<endl;
        else cout<<len-min<<endl;
    }
    return ;
}
           

第三題：袋鼠過河

題目

一隻袋鼠要從河這邊跳到河對岸，河很寬，但是河中間打了很多樁子，每隔一米就有一個，每個樁子上都有一個彈簧，袋鼠跳到彈簧上就可以跳的更遠。每個彈簧力量不同，用一個數字代表它的力量，如果彈簧力量為5，就代表袋鼠下一跳最多能夠跳5米，如果為0，就會陷進去無法繼續跳躍。河流一共N米寬，袋鼠初始位置就在第一個彈簧上面，要跳到最後一個彈簧之後就算過河了，給定每個彈簧的力量，求袋鼠最少需要多少跳能夠到達對岸。如果無法到達輸出-1 。

輸入描述:

輸入分兩行，第一行是數組長度N (1 ≤ N ≤ 10000)，第二行是每一項的值，用空格分隔。

輸出描述:

輸出最少的跳數，無法到達輸出-1

1

1

輸入例子：

5

2 0 1 1 1

輸出例子：

4

代碼

#include <iostream>
#include <string>
using namespace std; 
int jump(int nums[], int n) {
    if (n == ) return ;
    int start = , end = , jumps = ;
    while (jumps<=n&&end<=n - ){
        ++jumps;
        int len = end;
        for (int i = start; i <= end; i++){
            if (nums[i] + i>len){
                len = nums[i] + i;
            }
        }
        start = end + ;
        end = len;
    }
    if (jumps > n)
        jumps = -;
    return jumps;
}
int main(){
    int n;
    cin >>n;
    int *array=new int[n];
    for (int i = ; i < n; i++){
        cin >> array[i];
    }
    cout << jump(array, n);
    return ;
}