2013华为机试与面试题

时间:2023-02-01 18:48:39
上机测试是3道题,2小时。估计一般的计算机专业的人不屑于写华为的机试题,好吧,我这篇文章只是向其他专业想做IT的同学分享题目,相互学习。
 
1. 字母大小写反转

这到题没什么可说的,只是我很久没写这样要IO输入输出的代码,当时看到华为的提示纸条上写着“只能使用stdin方式输入”,还愣了一会:一定是我打开方式不对,什么时候有了一个stdin的输入函数?难道我又学艺不精了……后面才反应过来,直接按英文字面意思理解为“只能使用标准输入方式”就好了。好了,言归正传,回到这道题,至少可以用以下两种方式:

  • C++ STL库string中 有  isupper , islower , toupper ,tolower 函数
  • 通过 +/- ('a'-'A'+0)
2. n个人围成一圈,从第1个人开始报数,每报到第m个人,则其出局,求最后出局的人的初始序号。
        

        第1种方法,我当时是用了个状态表来记录这人有没有出局,没出局则报数计数器加1并玩下走,碰到第m个报数号则更新状态为已出局,碰到队伍最末则重新移动到队首。

 
#include <iostream>
#define N 4
#define M 3
using namespace std;
int *man = NULL;
int JosephusSol_statusTab(int n,int m)
{
    int sn=0 , pos = 0 ,loop_pos=0;
    do
    {
        if( man[pos] == 0 ){//此人未出局
            loop_pos++;
            if(loop_pos == m){//找到一轮报数的出局者
                sn++;
                man[pos] = sn ; // 标记出局序号
                loop_pos = 0;
            }
        }
        pos ++ ;
        if(pos==n)
            pos = 0;
    }while(sn!=n);
    return pos;
}

int main()
{
    int sn=0 , pos = 0 ,loop_pos=0;
    man = new int [N];
    for(int i=0;i<N;i++)
        man[i] = 0;
    pos = JosephusSol_statusTab(N,M);
    cout << pos <<endl ;
    if(man != 0)
        delete [] man;
    return 0;
}

    
       第2种方法是双向链表,技术面面试的时候,面试官就考了我这一题,在纸上快速写代码的能力还是有所欠缺。

 

        第3种方法是递归,

    第0次报数(即初始排列状态)如下:

1
2
……
 
 
n
    第1次报数到m,剔除后的序列为
m+1
m+2
n
1
2
m-1
       重新编号的话为:   
1
2
n-m
n-m+1
n-m+2
n-1
       设f(n,m)为n个人的队伍,剔除报数人m,最后留下的人的序号;f(n-1,m)为n-1个人的队伍,剔除报数人m,最后留下的人的序号。则有:
              2013华为机试与面试题
   考虑到第1次报数后的序列号n的情况,可得到统一的公式为:

    2013华为机试与面试题
    这就是这个问题的一个递归公式,实现代码如下:

# include < iostream >
using namespace std;
int JosephusSol_mathRecursion( int n, int m)
{
      if (n == 1 )
          return 1 ;
      else
          return (JosephusSol_mathRecursion(n - 1 ,m) + m - 1 ) % n + 1 ;
}
int main()
{
    cout << JosephusSol_mathRecursion( 4 , 3 ) << endl ;
      return 0 ;
}
3.两段长度为1-5000变换的单词word1,word2,设计一个字母权重分配方案:该方案中不区分大小写字母;该方案A-Z的字母唯一对应一个1-26的数;该方案满足word1的字母权重和与word2的字母权重和的差值最大 。

这个问题是实质是比较单词,剔除相同的部分,看哪个剩余部分多,剩余多的单词部分再进行一个字母频率从大到小排列,频率最高的给最大的权重——26,频率低一些的依次给剩余的最大权重;剩余的单词部分再进行一个字母频率也是从大到小排列,只不过频率最高的给最小的权重——1,频率高一些的依次给剩余的最小权重。

至于实现,若是先直接比较单词,再字母频率统计,工作量有点大。可以考虑直接用 字母表A-Z为索引,将单词装换为字母表A-Z的编码(更形象点,即将杂乱的单词变成一个26进制数,当然这样没有包含单词的全部信息——字母在单词中的排序就不知道,所以可以装换成26个节点,每个节点还含有一个排序数组,如单词daddy,相对应的d节点下就含有一个size为3的数组,有sn['d'][3]={0,2,3}。当然本题只需要一个量就是size['d']=3。)

# include <iostream >
# include <string >
# include <vector >
 
using namespace std;
int main()
{
    string str1( "mother"),str2( "father");
     // string str1,str2;
     // cin  >> str1 >> str2;
    size_t i = 0 ,j = 0;
 
    vector < int > status1( 26, 0);
    vector < int > status2( 26, 0);
    vector < int > diff( 26, 0);
    vector < int > negative( 26, 0);   
    vector < int > positive( 26, 0);   
     int cntNeg = 0 , cntPos = 0;
     for( i = 0; i < str1.size(); i ++)
    {
         char c = str1[i];
         if( 'a' < =c && c < = 'z' ){
            status1[c - 'a' + 0] ++;
        }
         if( 'A' < =str1[i] && str1[i] < = 'Z' ){
            status1[c - 'A' + 0] ++;
        }
    }
     for( i = 0; i < str2.size(); i ++)
    {
         char c = str2[i];
         if( 'a' < =str2[i] && str2[i] < = 'z' ){
            status2[c - 'a' + 0] ++;
        }
         if( 'A' < =str2[i] && str2[i] < = 'Z' ){
            status2[c - 'A' + 0] ++;
        }
    }
 
     for( i = 0; i < 26; i ++){
        diff[i] = status2[i] - status1[i];
         if(diff[i] < 0)
        {
            negative[i] = -diff[i];
            cntNeg += negative[i];
        }
         else
        {
            positive[i] = diff[i];
            cntPos += positive[i];
        }
    }
     for( i = 0; i < 26; i ++)
        cout << ' ' << status1[i] << ' ' << status2[i] << ' ' << diff[i] << endl;
 
     int tmp = 0;
     int a[ 26],b[ 26];
    cout << ' ' << cntNeg << ' ' << cntPos;
     for( i = 0 ; i < 26;i ++ )
    {
        a[i] = 26 -i;
        b[i] = i + 1;
    }
 
     for( i = 0 ; i < 26;i ++ )
         for(j = i + 1 ;j < 26;j ++)
        {
             if( negative[i] < negative[j] ){
                tmp = negative[i];
                negative[i] = negative[j];
                negative[j] = tmp;
            }
        }
     for( i = 0 ; i < 26;i ++ )
         for(j = i + 1 ;j < 26;j ++)
        {
             if( positive[i] < positive[j] ){
                tmp = positive[i];
                positive[i] = positive[j];
                positive[j] = tmp;
            }
        }
 
     int out = 0 , large = 0, small = 0 ;
     for( i = 0 ; i < 26;i ++ )
    {
         if( cntNeg > = cntPos  ) {
            large += a[i] *negative[i];   
            small += b[i] *positive[i];
        }           
         else{
            large += a[i] *positive[i];
            small += b[i] *negative[i];
        }
    }
 
    out = large - small;
    cout << out ;
 
     return 0;
}