TAL好未来秋招编程题

[编程题] n个数里最小的k个

时间限制：1秒
空间限制：32768K
找出n个数里最小的k个
输入描述:
每个测试输入包含空格分割的n+1个整数，最后一个整数为k值,n不超过100。
输出描述:
输出n个整数里最小的k个数。升序输出。
输入例子1:
3 9 6 8 -10 7 -11 19 30 12 23 5
输出例子1:
-11 -10 3 6 7

解析：

（1）方法一：借鉴快排中partition的思想。以第k个数为基准，将小于基准的数放在基准左边，把大于基准的数放在右边。这样前k个数就是最小的k个数，再对这k个数进行排序。因此，总的时间复杂度为O（n+klogk）。
（2）方法二：大顶堆。建立一个容量为K的大顶堆，遍历数组，如果大顶推还有空间，直接将数字加入大顶堆。如果没有空间了，判断堆顶最大值是否大于该数字，如果大于，则将其替换并调堆，如果小于则直接抛弃该数字。然后对k个数进行堆排序。总的时间复杂度为O(nlogk + klogk)。可以使用multiset。

C++代码实现：
方法一：

#include 
#include 
#include
using namespace std;

int n=0,k=0;
int num[100];

int partition(int start,int end)
{
    int key = num[start];
    while(start<end){
        while(start<end && num[end]>=key)
            end--;
        num[start] = num[end];
        while(start<end && num[start]<=key)
            start++;
        num[end] = num[start];
    }
    num[start] = key;
    return start;
}

void minKElement()
{
    int left = 0,right=n;
    int index = partition(left,right);
    while(index!=k-1){
        if(index > k-1){
            right = index - 1;
        }
        else
            left = index + 1;
        index = partition(left,right);
    }
    sort(num,num+k);
    for(int i=0; i        cout<" ";
}


int main()
{
    while(scanf("%d",&num[n])!=EOF && getchar()!='\n'){
        n++;
    }
    k = num[n--];
    minKElement();
    return 0;
}

方法二：

#include 
#include 
#include
using namespace std;

int n=0,k=0;
int num[100];
vector<int> heap;

void heapAdjust(int start,int end)
{
    if(start==end)
        return;
    int rc = heap[start];
    for(int j=2*start; j<=end; j*=2){
        if(j1])
            j++;
        if(rc > heap[j])
            break;
        heap[start] = heap[j];
        start = j;
    }
    heap[start] = rc;
}

void minKElement()
{
    int j = 0, i = 0;
    for(; i<=n && j        heap.push_back(num[i]);
    }
    heapAdjust(0,k-1);  //调整成大顶堆
    for(; i<=n; i++){
       if(num[i]0]){
            heap[0] = num[i];
            heapAdjust(0,k-1);
        }
    }
    for(i=k-1; i>0; i--){
        j = heap[i];
        heap[i] = heap[0];
        heap[0] = j;
        heapAdjust(0,i-1);
    }
    for(i=0; i        cout<" ";
}

int main()
{
    while(scanf("%d",&num[n])!=EOF && getchar()!='\n'){
        n++;
    }
    k = num[n--];
    minKElement();
    return 0;
}

[编程题] n个数里出现次数大于等于n/2的数

时间限制：1秒
空间限制：32768K
输入n个整数，输出出现次数大于等于数组长度一半的数。
输入描述:
每个测试输入包含 n个空格分割的n个整数，n不超过100，其中有一个整数出现次数大于等于n/2。
输出描述:
输出出现次数大于等于n/2的数。
输入例子1:
3 9 3 2 5 6 7 3 2 3 3 3
输出例子1:
3

解析：

（1）方法一：用一个unordered_map记录某个数及其出现次数，然后遍历map找到次数超过n/2的数。时间复杂度为O(n)。
（2）方法二：排序。中间的数字必定是出现次数超过一半的数字。时间复杂度是O(nlogn)。
（3）方法三：借鉴快速排序思想，取第一个元素作为基准，把小于基准的数字放在它前面，把大于基准的数字放在它后面。如果基准的位置在n/2，则基准即为出现次数大于一半的数字。如果基准的位置小于n/2，则该数字在基准的右边；如果基准位置大于n/2，则该数字在基准左边。时间复杂度为O(n)。
（4）方法四：在遍历数组时，保存两个变量：一个是数组的一个数字，一个是次数。当我们遍历下一个数字时，如果该数字和我们保存的数字相同，则次数加1；如果不同，则次数减1。如果次数为0，我们需要保存下一个数字，并把次数设为1。要找的数字就是最后一次把次数设成1时对应的数字。

c++代码实现：
方法一

#include 
#include 
#include 
using namespace std;

int num[100];
int n = 0;

int halfOfNum()
{
    unordered_map<int,int> dict;
    for(int i=0; i<=n; i++){
        dict[num[i]]++;
    }
    auto it = dict.begin();
    int half = (n-1)/2+1;
    while(it!=dict.end()){
        if(it->second >= half)
            return it->first;
        it++;
    }
    return 0;
}

int main()
{
    while(scanf("%d",&num[n])!=EOF && getchar()!='\n'){
        n++;
    }
    cout<    return 0;
}

方法三：

#include 
#include 
using namespace std;

int num[100];
int n = 0;

int partition(int start,int end)
{
    int key = num[start];
    while(start<end){
        while(start<end && num[end]>=key)
            end--;
        num[start] = num[end];
        while(start<end && num[start]<=key)
            start++;
        num[end] = num[start];
    }
    num[start] = key;
    return start;
}

int halfOfNum()
{
    int left=0,right=n;
    int middle = (n-1)/2+1;
    int index = partition(left,right);
    while(index!=middle){
        if(index>middle){
            right = index-1;
        }
        else{
            left = index+1;
        }
        index = partition(left,right);
    }
    return num[index];
}

int main()
{
    while(scanf("%d",&num[n])!=EOF && getchar()!='\n'){
        n++;
    }
    cout<    return 0;
}

方法四：

#include 
#include 
using namespace std;

int num[100];
int n = 0;

int halfOfNum()
{
    int result = num[0];
    int times = 1;
    for(int i=1; i<=n; i++){
        if(times==0){
            result = num[i];
            times=1;
        }
        else if(result==num[i])
            times++;
        else
            times--;
    }
    return result;
}

int main()
{
    while(scanf("%d",&num[n])!=EOF && getchar()!='\n'){
        n++;
    }
    cout<    return 0;
}

[编程题] 字符串中找出连续最长的数字串
时间限制：1秒
空间限制：32768K
读入一个字符串str，输出字符串str中的连续最长的数字串
输入描述:
测试输入包含1个测试用例，一个字符串str，长度不超过255。
输出描述:
在一行内输出str中里连续最长的数字串。
输入例子1:
abcd12345ed125ss123456789
输出例子1:
123456789

C++代码实现：

#include 
#include 
#include
using namespace std;

string longgestNumStr(const string& str)
{
    int len = str.size();
    string result,tmp;
    int lOnggest= 0;
    for(int i=0; i        if(str[i]>='0' && str[i]<='9'){
            tmp += str[i];
        }
        else{
            if(tmp.size()>longgest){
                lOnggest= tmp.size();
                result = tmp;
            }
            tmp.clear();
        }
    }
    if(tmp.size()>longgest){
            lOnggest= tmp.size();
            result = tmp;
    }
    return result;
}


int main()
{
    string str;
    cin>>str;
    cout<    return 0;
}

[编程题] 求和

时间限制：1秒
空间限制：32768K
输入两个整数 n 和 m，从数列1，2，3…….n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来
输入描述:
每个测试输入包含2个整数,n和m
输出描述:
按每个组合的字典序排列输出,每行输出一种组合
输入例子1:
5 5
输出例子1:
1 4
2 3
5

解析：

深度搜索。

C++代码

#include 
#include 
#include 
using namespace std;

bool dfs(vector<vector<int>>&result,vector<int>&answer,int rest,int last)
{
    if(rest==0)
        return true;
    int sum = last*(last+1)/2;
    if(rest>sum)
        return false;
    for(int i=last-1; i>=1; i--){
        if(rest>=i){
            answer.push_back(i);
            if(dfs(result,answer,rest-i,i)){
                result.push_back(answer);
            }
            answer.pop_back();
        }
    }
    return false;
}

void sumCombine(int n,int m)
{
    int sum = n*(n+1)/2;
    if(m>sum)
        return;
    vector<vector<int>> result;
    int i = m<=n? m : n;
    for(; i>=1; i--){
        vector<int> answer;
        if(m>=i){
            answer.push_back(i);
            if(dfs(result,answer,m-i,i))
                result.push_back(answer);
        }
    }
    sort(result.begin(),result.end(),[](const vector<int>&a,const vector<int>&b){
        int lenA = a.size(),lenB = b.size();
        int i=lenA-1,j=lenB-1;
        for(; i>=0 &&j>=0; i--,j--){
            if(a[i]!=b[j])
                return a[i]        }
        return false;
    });
    int len = result.size();
    for(int i=0; i        for(int j=result[i].size()-1; j>=0; j--){
            if(j!=0)
                cout<" ";
            else
                cout<        }
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    sumCombine(n,m);
    return 0;
}

[编程题] 删除公共字符

时间限制：1秒
空间限制：32768K
输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”They are students.”和”aeiou”，则删除之后的第一个字符串变成”Thy r stdnts.”
输入描述:
每个测试输入包含2个字符串
输出描述:
输出删除后的字符串
输入例子1:
They are students.
aeiou
输出例子1:
Thy r stdnts.

解析:

用字典unordered_set记录第二个字符串中出现的字符，遍历字符串1的每个字符a，如果在字典中找不到该字符，则将该字符加到result字符串末尾。

C++代码实现：

#include 
#include 
using namespace std;

string deleteChar(string&a, string&b)
{
    int lenA = a.size();
    int lenB = b.size();
    int i=0;
    string result;
    unordered_set<char> dict;
    for(;i        dict.insert(b[i]);
    for(i=0; i        if(dict.find(a[i])==dict.end()){
            result += a[i];
        }
    }
    return result;
}


int main()
{
    string a,b;
    getline(cin,a);
    getline(cin,b);
    cout<    return 0;
}

[编程题] 倒置字符串

时间限制：1秒
空间限制：32768K
将一句话的单词进行倒置，标点不倒置。比如 I like beijing. 经过函数后变为：beijing. like I
输入描述:
每个测试输入包含1个测试用例： I like beijing. 输入用例长度不超过100
输出描述:
依次输出倒置之后的字符串,以空格分割
输入例子1:
I like beijing.
输出例子1:
beijing. like I

C++代码实现：

#include 
#include 
using namespace std;

string reverseString(string &str)
{
    string result;
    int len = str.size();
    string temp;
    vector<string> words;
    for(int i=0; i        if(str[i]!=' '){
            temp += str[i];
        }
        else{
           words.push_back(temp);
           temp.clear();
        }
    }
    if(str[len-1]!=' ')
        words.push_back(temp);
    for(int i=words.size()-1; i>=0; i--){
        result += words[i];
        if(i!=0)
            result += " ";
    }
    return result;
}


int main()
{
    string str;
    getline(cin,str);
    cout<    return 0;
}