华为19秋招算法笔试

我的想法也不够成熟,如有谬误,欢迎在评论指正,谢谢~!

第一题

数轴X上有两个点的序列A={A1,A2,...,Am}和B={B1,B2,...,Bn},A_i和B_i均为正整数,A、B已经从小到大排序,A、B一定不为空,给定一个距离R,列出同时满足如下条件的所有(Ai, Bj)数对:
1. A_i <= B_j
2. A_i 和B_j的距离小于等于R,但如果A_i找不到R范围内的B_j,则列出距离它最近的一个B_j当然这种情况要满足条件1,如果找不到,就抛弃A_i
输入描述:
按照人易读的格式输入一行数据,输入A和B已经排好序,A和B的大小不超过50, 正整数范围不超过65535
输出描述:
(A_i, B_j)数对序列,排列顺序满足序列中前面A_x <= A_y,前面的B_x <= B_y,因为输入的A和B已经排好序,所以实际输出结果不用特意排序,排序不是考察点。
输入:
A={1,3,5},B={2,4,6},R=1
输出:
(1,2)
(3,4)
(5,6)
(这里前辈给我发照片的时候输出挡上了 对这道还有些歧义理解,暂且按照这个输出理解吧)
解法一:暴力法二次遍历时间复杂度O(n^2),处理字符串还是交给py容易一些

ins = input()
splitIn = ins.split('}')
a = list(map(lambda x:int(x), splitIn[0][3:].split(',')))
b = list(map(lambda x:int(x), splitIn[1][4:].split(',')))
r = int(splitIn[2][3:])
j = 0
ans = []
for i in range(len(a)):
    min_j = -1
    min_value = 0x3f3f3f3f
    flag = 1
    for j in range(len(b)):
        if b[j] - a[i] >= 0 and b[j] - a[i] < min_value:
            min_value = b[j] - a[i]
            min_j = j
        if abs(a[i]-b[j]) <= r and a[i] <= b[j]:
            ans.append([a[i], b[j]])
            flag = 0
    if min_j != -1 and flag == 1:
        ans.append([a[i], b[min_j]])
for k,v in ans:
    print("({0},{1})".format(k,v))

解法二:Two-pointers(因为两个数组是有序的,看到这里立刻想到二分,two-pointers…),显然如果分数要拿满,two-pointers少不了。但是我们要怎么用呢,很简单我们用一个下标分别控制数组a和b,根据数组a和b的有序性进行指针调整。

ins = input()
splitIn = ins.split('}')

a = list(map(lambda x:int(x), splitIn[0][3:].split(',')))
b = list(map(lambda x:int(x), splitIn[1][4:].split(',')))
r = int(splitIn[2][3:])
j = 0
ans = []
for i in a:
    # 保证满足条件1
    while(j < len(b) and b[j] < i): j+=1
    # 怕找不到 记录指针
    index = j
    # 开始找满足条件2的b元素值
    while(j < len(b) and b[j] - i <= r):
        ans.append([i, b[j]])
        j += 1
    if index == j and j < len(b): #说明没有找到
        ans.append([i, b[index]]) # 添加最近的元素
for k,v in ans:
    print("({0},{1})".format(k,v))

第二题

对数字、字符串、字符串、以及数字与字符串组合进行倒序排列
1. 范围a-Z, 0-9
2. 符号'-'的定义:‘-’作为连接符使用时作为字符串的一部分,例如“20-years”作为一个整体的字符串呈现;连续出现两个‘-’及以上的字符间隔符,如‘out--standing’中的‘--’视为间隔符,是2个独立整体字符串‘out’和‘standing’
3. 除了1.2里面定义的字符意外的其他所有字符都是非法字符,作为字符串的间隔处理,倒序后间隔符作为空格处理
4. 要求倒排后的单词间隔符以一个空格表示;如果有多个间隔符是,倒排转换后也只允许出现一个空格间隔符
5. 每个数字串或者字符串或者数字、符号、字符串组合长度范围在0-20字节
6. 输入和输出的字符串、字符串、数字、符号、和字符串组合的个数不超过200个
7. 倒数方法前面的数字串、字符串、以及数字/符号/字符组合穿倒序后排放在最前面,排放在第二位的倒序排放在倒数第二位,以此类推

输入:
I am an 20-years out--standing @ * -stu- dent
输出:
dent stu standing out 20-years an am I

解决思路:这道题的考察点就是正则表达式的构造,python很适合处理字符串问题,但是在python正则表达式匹配有一个坑:不可以在前向界定的括号里写正则式。理解了这一点就能够体会到python的re引擎的匹配思路是什么,和其他语言的正则引擎(如Ruby)有点不太一样

import sys
import re
for line in sys.stdin:
    result = re.findall(r"\b\w+-{0,1}\w*\b", line)
    ans = ''
    for word in reversed(result):
        ans = ans + ' '+word
    print(ans[1:])

第三题

X航空公司经营着N条航线,最近因为天气原因, 取消了一批航班,需要对乘客的机票进行改签,需要根据航班号,对出售的机票信息进行修改。
输入描述:
输入第一行包括一个整数N(1<=N<=100),表示机票张数,接下来的N行每行包括航班号,座位号,姓名,使用空格分隔(然后你的例子给的是用逗号间隔…C++严重不友好)。第N+2包括了一个整数M(1<=M<=N),表示要调整的位置。接下来的M行包括原航班号,原座位号,新航班号,新座位号。新老航班号可能一样,新老座位号也可能一样。
输出描述:
输出修改后的机票信息。按照航班号和座位号进行排序,去除重复(同航班同座位多机票或者同用户同航班多张机票)的机票,每张机票输出一行,以换行结尾。

输入:
3
CZ7132,A1,ZHANGSAN
CZ7132,A2,ZHAOSI
CZ7156,A2,WANGWU
2
CZ7132,A1,CZ7156,A2
CZ7156,A2,CZ7156,A3
输出:
CZ7132,A2,ZHAOSI
CZ7156,A2,ZHANGSAN
CZ7156,A3,WANGWU

解决思路:这道题考察的是大模拟,对业务进行编程的能力。

#include <iostream>
#include <map>
#include <utility>
#include <sstream>
using namespace std;
struct comp {
    template<typename T>
    bool operator()(const T &l, const T &r) const {
        if (l.first == r.first) return l.second < r.second;
        return l.first < r.first;
    }
};
int main(int argc, const char * argv[]) {
    int n,m;
    cin>>n;
    map<pair<string, string>, string, comp> data;
    map<pair<string, string>, string, comp> newdata;
    while(n--) {
        string ca, seat, name, line;
        cin>>line;
        replace(line.begin(), line.end(), ',',' ');
        stringstream ss;
        ss.str(line);
        ss>>ca>>seat>>name;
        pair<string, string> tmp = make_pair(ca, seat);
        data[tmp] = name;
    }
    cin>>m;
    while(m--) {
        string oldca, oldseat, newca, newseat, line;
        cin>>line;
        replace(line.begin(), line.end(), ',',' ');
        stringstream ss;ss.str(line);
        ss>>oldca>>oldseat>>newca>>newseat;
        pair<string, string> tmp = make_pair(oldca, oldseat);
        string tmpname = data[tmp];
        data.erase(tmp);
        tmp = make_pair(newca, newseat);
        newdata[tmp] = tmpname;
    }
    map<pair<string, string>, string>::iterator pi;
    for(pi = data.begin(); pi != data.end(); ++pi) {
        newdata[pi->first] = pi->second;
    }
    for(pi = newdata.begin(); pi != newdata.end(); ++pi) {
        cout<<pi->first.first<<","<<pi->first.second<<","<<pi->second<<endl;
    }
    return 0;
}

和其他面试题相比,华为的秋招给我感觉还是相对简单的,没有考动态规划、也没有考树状数组、前缀树这些乱七八糟的数据结构,考的就是实打实的编程能力。最后吐槽一下牛客网,刷题体验远远不如LeetCode…,代码实现15分钟,剩下半个小时都卡在了输入输出上,以后要花些精力在牛客网上了。

这篇文章是否对您有帮助?

请您为我打分吧!

平均分数 / 5. 投票数量:

发表评论

电子邮件地址不会被公开。 必填项已用*标注