华为 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。
心情有点糟糕,我出门走走。
#华为春招笔试##华为##笔试题目#