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的使用，以及配置的一些探索