本周的周赛题目看上去似乎比较简单，差不多 1 小时做完被挤出了 top 200，所以相对来说可能大家也做得比较顺手。
（有个值得一提的点是这周的比赛似乎考察了 4 个树的题目？）
| 图 1：第 179 场周赛排名（临时） |
|---|
|
Q1：生成每种字符都是奇数个的字符串
这道题的题目比较唬烂，看上去很难，其实就是两种情况，如果给定的数是奇数，那么返回 N 个 A 就好了，如果给定的是偶数，那么就返回 N-1 个 A 和 1 个 B 就好了：
[[email protected]]# cat Q1.go
import "strings"
func generateTheString(n int) (rst string) {
for i := 0; n != 0 && i < 26; i++ {
if n%2 == 1 {
rst += strings.Repeat(string('a'+i), n)
n = 0
} else {
rst += strings.Repeat(string('a'+i), n-1)
n = 1
}
}
return
}
Q2：灯泡开关 III
这道题其实也不难，但是说实话，我还是卡了一下的，最后还是想明白了，其实你只要保证当前亮着的最大序号的灯和当前的时刻一致就好了，这就表示所有亮着的灯都是蓝色了。
其实回头想一想，这道题目还是在题目的描述很绕，仔细想一想就比较简单了：
[[email protected]]# cat Q2.go
func numTimesAllBlue(light []int) (rst int) {
var (
i int
maxOpen = 0
length = len(light)
)
for i = 0; i < length; i++ {
if light[i] > maxOpen {
maxOpen = light[i]
}
if maxOpen == i+1 {
rst++
}
}
return rst
}
Q3：通知所有员工所需的时间
这道题其实就是一个 BFS，然后针对每个叶子节点判断到当前叶子节点需要的时间，然后进行一个最大值的计算就可以了。
这里我的处理是一开始将 manager 构造出一棵树，因为 manager 不是一棵树，所以我构造了 employee：
[[email protected]]# cat Q3.go
type obj struct {
No int
Time int
}
func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
var (
i, count int
curr obj
length = len(manager)
l = list.New()
employee = make([][]int, length)
)
for i = 0; i < length; i++ {
if i == headID {
continue
}
employee[manager[i]] = append(employee[manager[i]], i)
}
l.PushBack(obj{
No: headID,
Time: informTime[headID],
})
for l.Len() > 0 {
curr = l.Remove(l.Front()).(obj)
for i = 0; i < len(employee[curr.No]); i++ {
l.PushBack(obj{
No: employee[curr.No][i],
Time: curr.Time + informTime[employee[curr.No][i]],
})
}
if len(employee[curr.No]) == 0 {
if curr.Time > count {
count = curr.Time
}
}
}
return count
}
Q4：T 秒后青蛙的位置
这其实也是一道 BFS 的题目，但是，有几个点需要注意：
- 这棵树是无向树，所以你考虑输入怎么构造成一棵树
- 一个是概率，其实就是根结点的概率除以子节点的数量就是子节点的概率
- 一个是时间
- 如果时刻 t 小于从根结点到子节点的长度，那么很明显是不可能到子节点的，概率为 0
- 如果到达目的节点之后，但是时间 t 还有多，那么这个时候需要考虑是否还有节点可以走
- 如果有，那么最终肯定不可能回来的，概率为 0
- 如果没有，那么就直接是这个节点的概率了
理解完这些之后其实就简单了：
[[email protected]]# cat Q4.go
type obj struct {
target int
length int
posible float64
}
func frogPosition(length int, edges [][]int, t int, target int) float64 {
var (
i int
curr obj
graph = make([][]int, length+1)
visited = map[int]bool{}
l = list.New()
)
for i = 0; i < len(edges); i++ {
graph[edges[i][0]] = append(graph[edges[i][0]], edges[i][1])
graph[edges[i][1]] = append(graph[edges[i][1]], edges[i][0])
}
l.PushBack(obj{
target: 1,
length: 0,
posible: 1.0,
})
for l.Len() != 0 {
curr = l.Remove(l.Front()).(obj)
if visited[curr.target] {
continue
}
visited[curr.target] = true
if curr.target == target {
if curr.length > t {
return 0
}
if curr.length == t {
return curr.posible
}
for i = 0; i < len(graph[curr.target]); i++ {
if !visited[graph[curr.target][i]] {
return 0
}
}
return curr.posible
}
for i = 0; i < len(graph[curr.target]); i++ {
childNum := len(graph[curr.target])
if curr.target != 1 {
childNum--
}
l.PushBack(obj{
target: graph[curr.target][i],
length: curr.length + 1,
posible: curr.posible / float64(childNum),
})
}
}
return 0
}