ARST打卡第163周[163/521]

Algorithm

lc508出现次数最多的子树元素和

维护一个子树和的map次数,然后取最多次数的一个slice

dfs记忆搜索

结果写了60分钟,各种翻车…白板写新学的go,写得太菜了…,还是有错,快凌晨了,明天debug一下

难道是我map使用方式有问题???

map提出去又出现下面的问题…

输入:
[1]
输出:
[2]
预期结果:
[1]

第二天用本地go环境去跑,发现跑出来的结果和LeetCode跑出来的结果不一样,本地可以正确得到结果

查了一下,发现是LeetCode的golang不能用全局变量…所以改成引用传值,就过了…

教训: 下次还是要装一个本地golang环境,白板没法调试,不方便…反而会浪费更多宝贵的时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// 输入:
// [1]
// 输出:
// []
// 预期结果:
// [1]

// var maxCnt = 0

/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findFrequentTreeSum(root *TreeNode) (ans []int) {
treeSum := make(map[int]int)
// missing len argument to make([]int)
// ans := make([]int)

// [0,0,0,0,0,0,0,0,0,0]
// ans := make([]int, 10)
// ans := make([]int, 0)
maxCnt := 0
// cannot use dummyNode (type leetcode.TreeNode) as type *leetcode.TreeNode in argument to dfsGetSum
// dummyNode := TreeNode{
// dummyNode := &TreeNode{
// // unexpected =, expecting comma or }
// // Left = root
// Left: root,
// }
// dfsGetSum(treeSum, dummyNode, maxCnt)
dfsGetSum(treeSum, root, &maxCnt)
for k, v := range treeSum {
if v == maxCnt {
ans = append(ans, k)
}
}
return
}

// maxCnt是传值!!!不会往上传!!!这里是错的
func dfsGetSum(treeSum map[int]int, root *TreeNode, maxCnt *int) int {
// func dfsGetSum(treeSum map[int]int, root *TreeNode) int {
// panic: runtime error: invalid memory address or nil pointer dereference
// if nil == root.Left && nil == root.Right {
// treeSum[root.Val] += 1
// if treeSum[root.Val] > maxCnt {
// maxCnt = treeSum[root.Val]
// }
// return treeSum[root.Val] : 返回错了...
// }
if root == nil {
return 0
}

nodeSum := root.Val + dfsGetSum(treeSum, root.Left, maxCnt) +
dfsGetSum(treeSum, root.Right, maxCnt)
treeSum[nodeSum] += 1
if treeSum[nodeSum] > *maxCnt {
*maxCnt = treeSum[nodeSum]
}
// return treeSum[nodeSum] : 返回错了...
return nodeSum
}

题解写得比我优美,用了闭包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func findFrequentTreeSum(root *TreeNode) (ans []int) {
cnt := map[int]int{}
maxCnt := 0
var dfs func(*TreeNode) int
dfs = func(node *TreeNode) int {
if node == nil {
return 0
}
sum := node.Val + dfs(node.Left) + dfs(node.Right)
cnt[sum]++
if cnt[sum] > maxCnt {
maxCnt = cnt[sum]
}
return sum
}
dfs(root)

for s, c := range cnt {
if c == maxCnt {
ans = append(ans, s)
}
}
return
}
// 链接:https://leetcode.cn/problems/most-frequent-subtree-sum/solution/chu-xian-ci-shu-zui-duo-de-zi-shu-yuan-s-kdjc/

Review

golangci-lint Linters

golangci-lint有很详细的说明和配置方法,挺好的

Tips

Could not find nil pointer

关于golangci-lint无法找到内嵌结构体的nil引用,静态检查比较难发现,需要结合单元测试来配合才比较好

Share

golangci-lint在vscode的使用,以及配置的一些探索