呓语 | 杨英明的个人博客

专注于c++、Python,欢迎交流

By

【2018秋招笔试】2018.9.12 华为笔试

前言

华为笔试比较实在,三道编程题,一道200分,2个小时。

题目不难,两道模拟题,一道大数乘法,20分钟全部AC。

第一题

思路:

貌似只考虑大写字母就可以,所以开一个 26 个元素大小的哈希表,统计每个字母出现的次数,然后倒着遍历一遍字符串,寻找第一个次数为1的字母,如果找到,输出该字母,如果没找到输出NULL。

代码:

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

int main()
{
    char s[100010] = {0};
    int h[26] = {0};
    int i;
    scanf("%s",s);
    for(i=0;s[i];i++){
        h[s[i]-'A']++;
    }
    for(i=strlen(s)-1;i>=0;i--){
        if(h[s[i]-'A']==1){
            break;
        }
    }
    if(i==-1)
        printf("NULL");
    else
        printf("%c",s[i]);
    return 0;
}

第二题

思路:

循环读入每个单词,将每个单词倒序输出,直到读入到文件尾部(EOF)。

代码:

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

int main()
{
    char s[100010];
    int cnt = 1;
    while(scanf("%s",s)!=EOF){
        int i;
        if(cnt!=1)
            printf(" ");
        cnt++;
        for(i=strlen(s)-1;i>=0;i--){
            printf("%c",s[i]);
        }
    }
    return 0;
}

第三题

思路:

典型的大数乘法,用字符串存储数字,模拟乘法运算,算出最终的结果。

直接套模板,AC。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 4e5 + 5;
const double pi = acos(-1.0);
struct complex
{
    double r, i;
    complex() {r = i = 0;}
    complex(double a,double b){r = a; i = b;}
    complex operator + (const complex &o) const{
        return complex(r + o.r, i + o.i);
    }
    complex operator - (const complex &o) const{
        return complex(r - o.r, i - o.i);
    }
    complex operator * (const complex &o) const{
        return complex(r * o.r - i * o.i, r * o.i + i * o.r);
    }
}x1[maxn], x2[maxn], A[maxn];

int n, rev[maxn];
double a[maxn], b[maxn];
int c[maxn];
void init(int &l, int len1, int len2)
{
    int L, k, r, t;
    k = 1; L = 0;
    while(k < 2 * len1 || k < 2 * len2) k <<= 1, ++ L;
    l = k;
    for(int i = 0; i < l; i++){
        t = i; r = 0; k = L;
        while(k--){
            r <<= 1;
            r |= t & 1;
            t >>= 1;
        }
        rev[i] = r;
    }
}
void fft(complex *x, int l, int op)
{
    complex u, t;
    for(int i = 0; i < l; i++) A[rev[i]] = x[i];
    for(int i = 0; i < l; i++) x[i] = A[i];
    for(int k = 2; k <= l; k <<= 1){
        complex wn(cos(2 * pi/ k * op), sin(2 * pi / k * op));
        for(int i = 0; i < l; i += k){
            complex w(1, 0);
            for(int j = 0; j < k / 2; j++){
                u = x[i + j]; t = w * x[i + j + k/2];
                x[i + j] = u + t; x[i + j + k/2] = u - t;
                w = w * wn;
            }
        }
    }
    //IDFT
    for(int i = 0; i < l && op == -1; i++)  x[i].r /= l;
}
char s1[maxn], s2[maxn];
int main()
{
    while(~scanf("%s%s", s1, s2)){
        int len1 = strlen(s1), len2 = strlen(s2);
        int l; init(l, len1, len2);
        for(int i = 0; i < l; i++){
            x1[i] = complex(0, 0);
            x2[i] = complex(0, 0);
        }
        for(int i = 0; i < len1; i++) x1[i].r = s1[len1 - 1 - i] - '0';
        for(int i = 0; i < len2; i++) x2[i].r = s2[len2 - 1 - i] - '0';
        fft(x1, l, 1); fft(x2, l, 1);
        for(int i = 0; i < l; i++)  x1[i] = x1[i] * x2[i];
        fft(x1, l, -1);
        memset(c, 0, sizeof(c));
        for(int i = 0; i < l; i++){
            c[i] = x1[i].r + 0.5;
            //cout<<x1[i].r<<' '<<c[i]<<endl;
        }
        for(int i = 0; i < l; i++){
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        int i = l;
        while(i && c[i] == 0) i--;
        for(int j = i; j >= 0; j-- ){
            printf("%d", c[j]);
        }
        puts("");
    }
    return 0;
}

原创声明

转载请注明:呓语 » 【2018秋招笔试】2018.9.12 华为笔试