二零一四年华为校招机试题和多种代码实现（多个数的最大公约数，相同子串，单词计数）

转载请注明出处：http://blog.****.net/zhoubin1992/article/details/46460055

大家都知道，每年华为校招面试前要机试，每个地方的题目都不同，一般为3道题，题目难度逐渐加大。话说做出一题就行了。而且我发现华为特别喜欢考字符串处理的题目。
下面给出我做的一套14年西安地区的题目及解答。每题给出了多种解答方法，详细解释都在注释里，适合考前练练手。

2014年华为机试—多个数的最大公约数

题目一：多个数的最大公约数
输入一组正整数（数量小于20），输出其最大公约数。
输入：121 33 44 11 1111
输出：11
思路：先求出两个数的最大公约数，再求出这个最大公约数和第三个数的最大公约数。。。。。

/*********************************
-----------------------------------
2014年华为机试—多个数的最大公约数
题目一：求最大公约数
输入一组正整数（数量小于20），输出其最大公约数。
输入：121 33 44 11 1111
输出：11
-----------------------------------
PS:求最小公倍数：
最小公倍数=两整数的乘积÷最大公约数
-----------------------------------
Author:牧之丶  Date：2015年6月1日
Email:bzhou84@163.com
**********************************/
#include <stdio.h>

int largestCommonDivisor(int a,int b)           //辗转相除法——递归
{
    return a%b?largestCommonDivisor(b,a%b):b;
}
int largestCommonDivisor1(int a,int b)          //辗转相除法——while循环
{
    int c;
    while(b!=0)
    {
        c=a%b;      //余数c
        a=b;
        b=c;
    }
    return a;
}
int largestCommonDivisor2(int a,int b)  //相减法
{
    while ( a!=b) 
    {   if (a>b)  a=a-b;

        else  b=b-a;

    }
    return a;   //return b;
}
int main()
{
    int N,a[20],i;
    while (scanf("%d",&N)!=EOF)     //输入N,并实现多组数据的输入
    { 
        for (i=0;i<N;i++)
        {
            scanf("%d",&a[i]);
        }
        int z=a[0];             //初始化最大公约数
        for (i=1;i<N;i++)       //从a[1]开始遍历
        {
            z=largestCommonDivisor2(z,a[i]);        //初始最大公约数和后一个数比较得出最大公约数,然后这个最大公约数和第三个数比较
        }
        printf("%d\n",z);
    }
    return 0;
}

2014年华为机试—相同子串

题目二：输入一组数字（最多15个），去掉连续次数大于等于三的数字，如果去掉后仍有连续次数大于等于三的，
继续进行同样的处理，直到结果中没有出现连续次数大于等于三的数字为止。
如果最终全部消除完了 输出“none”
输入：1 1 1 1 2 2 2 1 3 3 3 3 1 1 1
输出：none

/*********************************
-----------------------------------
2014年华为机试—相同子串
题目二：输入一组数字（最多15个），去掉连续次数大于等于三的数字，如果去掉后仍有连续次数大于等于三的，
继续进行同样的处理，直到结果中没有出现连续次数大于等于三的数字为止。
如果最终全部消除完了 输出“none”
输入：1 1 1 1 2 2 2 1 3 3 3 3 1 1 1
输出：none
-----------------------------------

-----------------------------------
Author:牧之丶  Date：2015年5月25日
Email:bzhou84@163.com
**********************************/
#include <iostream>
#include <vector>
using namespace std;


void deleteNum2(vector<int> a){         //方法一
    int cnt = 1, flag=0;
    while(!flag){
        vector<int>::iterator iter;
        for (iter=a.begin();iter!=a.end();iter++)
        {
            //vector<int>::iterator iter2 = iter+1;
            if((iter+1)!=a.end()){
                if (*iter==*(iter+1))
                {
                    cnt++;
                } 
                else
                {
                    if (cnt>=3)
                    {
                        a.erase(iter+1-cnt,iter+1);
                        flag = 0;
                        cnt = 1;
                        break;
                    } 
                    cnt = 1;
                }
            }else{
                if (cnt>=3)
                {
                    a.erase(iter+1-cnt,iter+1);
                    flag = 1;
                    break;
                } 
            }
            flag = 1;
        }
    }
    if (a.empty())
    {
        cout<<"none"<<endl; 
    }
    else
    {
        for (vector<int>::iterator it=a.begin();it!=a.end();it++)
        {
            cout<<*it<<" ";
        }
    }
}


void deleteNum(vector<int> a)           //方法二
{
    for (vector<int>::iterator iter=a.begin();iter!=a.end();)
    {
        int i=1;
        int flag=0;
        vector<int>::iterator iter2;
        for (iter2=iter+1;iter2!=a.end();iter2++)
        {
            if (*iter==*iter2)
            {
                i++;
            } 
            else
            {
                if (i>=3)
                {
                    a.erase(iter,iter+i);
                    flag=1;
                    i=1;
                    break;
                } 
                else
                {
                    flag=0;
                    break;
                }
            }
        }
        if (i>=3)
        {
            a.erase(iter,iter+i);
            break;
        } 
        if (flag)
        {
            iter=a.begin();
        }
        else
        {
            iter++;
        }

    }
    if (a.size()==0)
    {
        cout<<"none"<<endl; 
    }
    else
    {
        for (vector<int>::iterator it=a.begin();it!=a.end();it++)
        {
            cout<<*it<<" ";
        }
    }
}

int main()
{
    vector<int> a;
    int n;
    while(cin>>n&&n!=10)
    {
        a.push_back(n);
    }
    deleteNum(a);
    system("pause");
    return 0;
}

2014年华为机试—单词计数

题目三：输入一段文章，输出最高频与次高频的单词(全部小写，逗号分隔)。
文章中仅出现空格，逗号和句号这三种分隔符。不考虑频率一致的情况。忽略大小写。
输入：I am a student.I come from XiDian,I love XiDian.
输出：i,xidian
思路：输入文章后，先把逗号和句号去除，分割字符串。再进行忽略大小写，再用map统计出现频率，最后找出最高频与次高频的单词。

/*********************************
-----------------------------------
2014年华为机试—单词计数
题目三：输入一段文章，输出最高频与次高频的单词(全部小写，逗号分隔)。
文章中仅出现空格，逗号和句号这三种分隔符。不考虑频率一致的情况。忽略大小写。
输入：I am a student.I come from XiDian,I love XiDian.
输出：i,xidian
-----------------------------------
思路：输入文章后，先把逗号和句号去除，分割字符串。再进行忽略大小写，最后用map统计出现频率。
-----------------------------------
Author:牧之丶  Date：2015年5月25日
Email:bzhou84@163.com
**********************************/
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

void maxSecond(vector<string> v)
{
    //1.逗号和句号去除，分割字符串
    //这里需要注意的是erase()删除操作后，迭代器的指向问题！！
    for (vector<string>::iterator it=v.begin();it!=v.end();)    //遍历所有字符串
    {
        int flag=0;                         //标志位（进行删除操作至1，默认0）
        int length=(*it).length();          
        for(int i=0;i<length;i++)       //遍历字符串的字符
        {
            if ((*it)[i]==','||(*it)[i]=='.')
            {
                //截取字符串
                string t=(*it).substr(0,i);     //substr(0,i)获得字符串中从第0位开始的长度为i的字符串      
                string z=(*it).substr(i+1);     //一个参数，默认截取到字符串最后
                v.erase(it);                    //截取字符串分别保存后，先删除it,再插入字符串
                if (t!="")
                {
                    v.push_back(t);
                }
                if (z!="")
                {
                    v.push_back(z);
                }
                flag=1;             //至1
                break;
            }
        }
        if (flag)                   //删除操作后,迭代器的指向v.begin() 
        {
            it=v.begin();
        } 
        else                        
        {
            it++;
        }
    }
    //2.遍历所有字符串进行忽略大小写
    for (vector<string>::iterator it=v.begin();it!=v.end();it++)    
    {
        transform(it->begin(), it->end(), it->begin(), ::tolower);
    }
    //3.map统计出现频率
    map<string,int> m;      
    for (vector<string>::iterator it=v.begin();it!=v.end();it++)    
    {
        m[(*it)]++;
    }
    //4.找出最高频与次高频的单词
    multimap<int,string> mi;        //multimap 允许插入重复键值的元素,频率为key,字符串为value
    for (map<string,int>::iterator it=m.begin();it!=m.end();it++)
    {
        mi.insert(pair<int,string>(it->second,it->first));          //频率为key,字符串为value  利用map的自动排序功能(从小到大)
    }
    multimap<int,string>::iterator iter=mi.end();       //输出最高频与次高频的单词
    cout << (--iter)->second <<",";
    cout<< (--iter)->second<<endl;

}
int main()
{
    string s;
    vector<string> v;
    while(cin>>s)
    {
        v.push_back(s);
    }
    maxSecond(v);
    system("pause");
    return 0;
}