华为，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。

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