华为，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。
心情有点糟糕，我出门走走。
全部评论
(7) 回帖