华为机试题

1、约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列.

#include <list>
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int solve(int n,int k, int m){
    list<int> data;
    for(int i = 1 ; i <= n ; ++ i) data.push_back(i);
    int cnt = 1;
    list<int>::iterator iter = data.begin();
    while(cnt < k) {++iter;++cnt;}
    while(data.size() > 1){
        for(int i = 1 ; i < m; ++i){
            ++iter;
            if(iter == data.end()) iter = data.begin();
        }
        iter = data.erase(iter);
        if(iter== data.end()) iter = data.begin();
    }
    return data.front();
}

int main(){
    int n,k,m;
    cin >> n >> k >> m;
    cout<<solve(n,k,m)<<endl;
}

2、通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉，然后按字母表顺序输出。比如字符串“abfcacde”输出结果为“abcdef”。

#include <list>
#include <iostream>
#include <string>
#include <algorithm>
#include <set>

using namespace std;

int main(){
    string str;
    cin >> str;
    set<char> ch;
    for(int i = 0 ; i <  str.length(); ++ i) ch.insert(str[i]);
    cout<<string(ch.begin(),ch.end())<<endl;
}

3、输入若干（不超过1000个）非负整数数字，请先取出奇数的数字按从大到小排序，再取出偶数从小到大进行排序。

样例输入：12 34 5 7 92 3 8

样例输出：7 5 3 8 12 34 92

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

int main(){
    vector<int> data;
    int a;
    while(cin >> a) data.push_back(a);
    int left = 0, right = data.size()-1;
    while(left <= right){
        while(left <= right && data[left]%2) left++;
        if(left > right) break;
        while(left <= right && !(data[right]%2)) right--;
        if(left > right) break;
        swap(data[left++],data[right--]);
    }
    int mid = right+1;
    if(data[right+1]%2 == 0) mid-=1;
    sort(data.begin(),data.begin()+mid+1,greater<int>());
    sort(data.begin()+mid+1,data.end(), less<int>());
    for(int i = 0 ; i < data.size(); ++ i){
        if(i) cout<<" ";;
        cout<<data[i];
    }
    cout<<endl;
}

4、一个英文句子仅由单词和逗号、句号、空格组成。要求过滤掉句子中重复单词（保留重复单词中的第一个），按句子顺序输出不重复的单词（不包括标点符号）。单词区分大小写，Where和where不相同。

输入：仅包含逗号和句号的英文句子，长度小于200

输出：去掉标点符号和重复单词的句子。

样例输入： where there is a will, there is a way.

样例输出： where there is a will way

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cctype>

using namespace std;

string process(string& word){
    if(!isalpha(word[word.length()-1])){
        word.erase(word.end()-1);
    }
    return word;
}

int main(){
    vector<string> word;
    string w;
    while(cin >>w) word.push_back(process(w));
    vector<string> res;
    res.push_back(word[0]);
    for(int  i = 1; i < word.size(); ++ i){
        int j = 0;
        while( j <  res.size()){
            if(word[i]!=res[j]) ++j;
            else break;
        }
        if(j >= res.size()) res.push_back(word[i]);
    }
    for(int i = 0 ; i < res.size(); ++ i){
        if(i) cout<<" ";
        cout<<res[i];
    }
    cout<<endl;
}

5、将一个整型数组中的各个值进行比对，删除重复的数值，并向前对齐

输入：多行，每行一组数据，用“，”隔开，其最大长度小于4096个字符

输出：多行，每行对应删除重复后的结果

样例输入：

　　3,5,4,5,3

9,9,10,2,3,10,21,2,10

样例输出：

　　3,5,4

9,10,2,3,21