华为 5月20日 笔试

华为,520,但我不配拥有offer

昨晚做了华为笔试,一道题都没做出来,我不配拥有offer。

下面的代码都是我下来之后写的,注释也很详细,希望能给大家带来一些帮助。

这些代码都是能够运行的,并且我想到的情况都能通过,但是由于无法提交验证,不排除仍有错漏的情形。如果你发现本文中有漏洞,不妨在评论区指出来吧。

第一题 [编程|100分] 链表分组

题目描述
Node有2个属性{id:Int, name:string},
输入一个Node链表collection,及分组标识splitter:string,将Node.name==splitter作为分组条件,对传入的Node链表进行分组。
输入描述:
第一行是分组条件,是一个字符串
第二行开始,每行是一个Node实例{id:Int, name:string},Ex:1,name1
输出描述:
第一行输出分组总数
第二行开始,每行输出分组后的Node,每行一个分组,Node实例间使用|做为分隔符,输出顺序与输入顺序保持一致
示例1输入输出示例仅供调试,后台判题数据一般不包含示例
输入

*
1,name1
2,name2
3,*
4,name4
5,name5

输出

2
1,name1|2,name2
4,name4|5,name5

备注:
输入不满足要求,输出为0

第一题 解答

这道题本身不算难,但是循环输入可能难倒了一批人,比如我。

平常碰到的循环输入大多是一行一个用例,不需要结束,这种情况的处理我以前写过。
编程题 多用例 循环输入 C++/Java/Python/Golang

但这道题的输入很特殊,这道题只有一个用例,空行结束。
那篇文章里的C++代码就不行了,这里写个C++的循环输入给大家参考一下。

#include <iostream>

using namespace std;

int main()
{
    //循环输入,空行结束
    char s[1024];
    while(gets(s))
    {
        if(s[0]=='\0')break;
        //转string方便处理
        string ss=s;
        cout<<ss<<endl;
    }
    cout<<"end"<<endl;
    return 0;
}

好了,下面进入正题。
我最开始写的是常规解法,但是这道题使用正则表达式会简便很多。因为输出和输入其实是完全一样的结构,所以我们不需要真的去将字符串解析为实例,只需要判断这个字符串是否匹配就够了。
我两种解法都写了,常规解法磨叽且可读性较低,建议直接阅读正则表达式解法。
另外多说一句,华为特别爱考字符串处理,如果你想考好华为笔试,建议你着重复习/预习一下正则表达式。

常规解法

package main

import "fmt"

type node struct {
    id int
    name string
    next *node
}

func main() {
    var id int
    var pt,name string
    fmt.Scan(&pt)
    head:=&node{}
    pre:=head
    cnt:=0
    flag:=false
    nodeCnt:=0
    for {
        n, err := fmt.Scanln(&id, &name)
        //空行或输入不合法
        if n < 2 {
            break
        }
        if err != nil {
            fmt.Println(0)
            return
        }
        //这里的name包含“,”
        if len(name)==1 && name[0]!=','{
            fmt.Println(0)
            break
        }
        name=name[1:]
        node := node{id: id, name: name}
        pre.next = &node
        pre = &node
        nodeCnt++
        if name != pt {
            if !flag{
                cnt++
            }
            flag = true
        } else {
            flag = false
        }
    }
    fmt.Println(cnt)
    cur:=head.next
    newLine:=true
    for i:=0;i<nodeCnt;i++{
        if cur.name==pt&&!newLine{
            fmt.Println()
            newLine=true
        }else{
            if !newLine{
                fmt.Print("|")
            }
            fmt.Print(cur.id,",",cur.name)
            newLine=false
        }
        cur=cur.next
    }
}

正则表达式

package main

import (
    "fmt"
    "regexp"
)

func main() {
    pt:=""
    fmt.Scan(&pt)
    input:=""
    cnt:=0
    lastNodeMatch:=true
    groups:=[][]string{}
    group:=[]string{}
    for{
        n,_:=fmt.Scanln(&input)
        //输入结束
        if n==0{
            groups= append(groups, group)
            break
        }
        //判断输入格式
        valid,_:=regexp.MatchString("[1-9]?\\d+,.+",input)
        if valid{
            //判断是否匹配模式
            maxch,_:=regexp.MatchString("[1-9]?\\d*,"+regexp.QuoteMeta(pt),input)
            if !maxch{
                //上一个匹配而这一个不匹配则创建新组
                if lastNodeMatch{
                    groups= append(groups, group)
                    group=make([]string,0)
                    cnt++
                }
                group= append(group, input)
                lastNodeMatch=false
            }else{
                lastNodeMatch=true
            }
        }else{
            fmt.Println(0)
            return
        }
    }
    fmt.Println(cnt)
    groups=groups[1:]
    for _,gp:=range groups{
        for i,rc:=range gp{
            if i!=0{
                fmt.Print("|")
            }
            fmt.Print(rc)
        }
        fmt.Println()
    }
}

第二题 [编程|200分] 有向图寻找环路

题目描述
给定一个有向图,假定最多10个节点,节点编号依次为A~J,如果A节点到B节点之间有通路则描述为A->B,多条边的描述之间以分号隔开,给定一个有向图,求该有向图中的所有环路,环路以节点编号的最小的节点开始输出,假定一个有向图最多一个环路,如果没有环路则输出空字符串“-”。输入为连接链表。
输入描述:
输入为连接链表字符串,如 :A->B;B->D;C->B;C->E;D->C

输出描述:
环路节点组成的字符串,如:输出字符串BDC,标识B->D->C->B组成环路
示例1输入输出示例仅供调试,后台判题数据一般不包含示例
输入

A->B;B->D;C->B;C->E;D->C

输出

BDC

第二题 解答

package main

import (
    "fmt"
    "regexp"
    "strings"
)

//字符转数字,如A->0
func a2i(r uint8) int {
    return int(r)-'A'
}

func i2a(i int) string {
    return string(i+'A')
}

var find=false

func dfs(i int,adjacentTable [][]int,used []bool,path []int)  {
    //找到环路
    if used[i]{
        for _,v:=range path{
            if v==i{
                //找到环起点
                find=true
            }

            if find{
                fmt.Print(i2a(v))
            }
        }
        return
    }else{
        used[i]=true
        //golang里的slice很特别
        //形参slice append不影响实参,因此不需要还原
        path = append(path, i)
        for _,v:=range adjacentTable[i]{
            dfs(v,adjacentTable,used,path)
        }
        used[i]=false
    }
}

func main() {
    input:="A->B;B->D;C->B;C->E;D->C"
    fmt.Scan(&input)

    //检查输入合法性
    valid,_:=regexp.MatchString("[A-J]->[A-J](;[A-J]->[A-J])*",input)
    if !valid{
        fmt.Println("-")
        return
    }

    adjacentTable:=make([][]int,10)
    paths:=strings.Split(input,";")

    for _,p:=range paths{
        adjacentTable[a2i(p[0])]= append(adjacentTable[a2i(p[0])],a2i(p[3]))
    }

    used:=make([]bool,10)
    path:=[]int{}
    dfs(0,adjacentTable,used,path)
    if !find{
        fmt.Println("-")
    }
}

第三题 [编程|300分] 街区监控

题目描述
一个街区,为提高街区安全性,需在街区的路灯上安装若干摄像头,用一个二叉树表示街区的路灯,每个节点表示一个路灯,在路灯上安装摄像头。每个摄影头都可以监视其父对象、自身及其直接子对象。为保证每个路灯都被监控,请计算街区所需的最小摄像头数量。
输入描述:
输入一串字符,代表由前序排列的二叉树表示的路灯,字符由‘0’和‘#’组成,每个‘0’表示一个要监控路灯,‘#’表示子节点为空。
输出描述:
所需最小摄像头数量。
示例1输入输出示例仅供调试,后台判题数据一般不包含示例
输入

00##0#0

输出

2

说明
输入的路灯可以构建如下二叉树,1表示需要安装摄像头的路灯,输入的路灯数最少为2。

 0
 / \
1  1
      \
        0

第三题 解答

这道题拿到手,我首先想到按层序从1开始编号的二叉树的性质。
序号为n的节点父节点为n/2,左子为2n,右子为2n+1.
利用这个性质可以不解析二叉树,直接操作字符串,我真是个天才。
在这里插入图片描述
当我一顿操作,代码都写好了才发现人家给的字符串并不是层序遍历。
加上第一题也没做出来,我心态直接崩坏。
在这里插入图片描述
现在只能重新中规中矩地重新来过,先反序列化,然后递归。
我目前只想到了递归,如果你有更酷的方法,不妨在评论区告诉我吧。

“天才”解法

package main

import "fmt"

var min=int(^uint(0) >> 1)

//点亮点前节点,及其父子节点
func light(i int,s []rune)  {
    if (i+1)/2-1>=0{
        s[(i+1)/2-1]='1'
    }
    s[i]='1'
    if 2*i+1<= len(s){
        s[2*i+1]='1'
    }
    if 2*i+2<= len(s){
        s[2*i+2]='1'
    }
}

//判断是否已点亮整棵树
func allLighted(s []rune) bool {
    for _,v:=range s{
        if v=='0'{
            return false
        }
    }
    return true
}

//尝试点亮整棵树,n为当前点亮的灯的数量,本质是dfs
func cover(s []rune,n int){
    if allLighted(s){
        if n<min{
            min=n
        }
    }
    for i,v:=range s{
        if v=='0'{
            v='1'
            ss:=make([]rune, len(s))
            copy(ss,s)
            light(i,ss)
            cover(ss,n+1)
            v='0'
        }
    }
}

func main() {
    str:=""
    fmt.Scan(&str)
    runes:=[]rune(str)
    //fmt.Println(runes)
    cover(runes,0)
    fmt.Println(min)
}

常规解法

package main

import "fmt"

type node struct {
    leftChild *node
    rightChild *node
}

//重构二叉树
func dlr(i int,s string)(int,*node) {
    if i>= len(s) || s[i]=='#'{
        return 1,nil
    }
    root:=&node{}
    nl,lt:=dlr(i+1,s)
    nr,rt:=dlr(i+1+nl,s)
    root.leftChild=lt
    root.rightChild=rt
    return nl+nr+1,root
}

//点亮当前树,返回所需灯的最少数量
func light(fatherIsLighted bool,node *node) int {
    if node==nil{
        return 0
    }

    //点亮当前节点
    cnt:=light(true,node.leftChild)+
        light(true,node.rightChild)+1

    //若父节点已点亮,当前节点可以不点亮
    if fatherIsLighted{
        tmp:=light(false,node.leftChild)+
            light(false,node.rightChild)
        if tmp<cnt{
            cnt=tmp
        }
    }
    return cnt
}

func main() {
    var str string
    fmt.Scan(&str)
    //str="00##0#0"
    _,root:=dlr(0,str)
    fmt.Println(light(true,root))
}

好了,今天的活整到这里就结束了,最后祝大家都能拿到想要的offer。

心情有点糟糕,我出门走走。

#华为春招笔试##华为##笔试题目#
全部评论
你这面试题感觉比我的难多了
1 回复 分享
发布于 2020-05-23 18:23
老哥每题过了多少啊
点赞 回复 分享
发布于 2020-05-21 17:40
同总分没100,能有面试通知吗楼主
点赞 回复 分享
发布于 2020-05-23 14:06
第一题是这个意思吗 处理输入终止是输入空格还是什么。。
点赞 回复 分享
发布于 2020-07-29 01:58
楼主,哪个城市的,都开始了吗
点赞 回复 分享
发布于 2020-07-31 13:03
搞这种输入输出的太烦了,宁愿出一道难的算法慢慢想也不想要一道简单的题考输入输出+各种处理+边界
点赞 回复 分享
发布于 2020-07-31 13:25
想问下第二题, CBD不也可以吗为啥DBC呢,有什么具体的返回限制吗
点赞 回复 分享
发布于 2021-07-01 20:57

相关推荐

不愿透露姓名的神秘牛友
10-21 18:17
已编辑
点赞 评论 收藏
分享
10-24 00:43
门头沟学院
点赞 评论 收藏
分享
投递华为软件技术有限公司等公司10个岗位
点赞 评论 收藏
分享
评论
20
73
分享
牛客网
牛客企业服务