Contents

ARST打卡第169周[169/521]

Algorithm

lc1161_最大层内元素和

bfs队列应用

 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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// 感觉这个题目和之前的一次面试题很像,就是bfs,但是面试时紧张记录了太多上下层的状态
func maxLevelSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	maxSum := math.MinInt64
	level := 1
	levelNodeCnt := 1
	queue := make([]*TreeNode, 0, 10)
	queue = append(queue, root)
	queueCnt := 1
	levelSum := 0
	ans := 1
	for queueCnt != 0 {
		head := queue[0]
		queue = queue[1:]
		queueCnt--
		levelNodeCnt--
		levelSum += head.Val
		if head.Left != nil {
			queue = append(queue, head.Left)
			queueCnt++
		}
		if head.Right != nil {
			queue = append(queue, head.Right)
			queueCnt++
		}
		if levelNodeCnt == 0 {
			if levelSum > maxSum {
				maxSum, ans = levelSum, level
			}
			level++
			// 这种没考虑null没有加入
			// levelNodeCnt = int(math.Pow(2, float64(level-1)))
			levelNodeCnt = len(queue)
			levelSum = 0
		}
	}

	return ans
}

// 答案比我的简洁多了
// bfs
func maxLevelSum_ans_Bfs(root *TreeNode) int {
	ans, maxSum := 1, root.Val
	q := []*TreeNode{root}
	for level := 1; len(q) > 0; level++ {
		tmp := q
		q = nil
		sum := 0
		for _, node := range tmp {
			sum += node.Val
			if node.Left != nil {
				q = append(q, node.Left)
			}
			if node.Right != nil {
				q = append(q, node.Right)
			}
		}
		if sum > maxSum {
			ans, maxSum = level, sum
		}
	}
	return ans
}

/*
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/solution/zui-da-ceng-nei-yuan-su-he-by-leetcode-s-2tm4/
*/
// dfs
func maxLevelSum_ans_Dfs(root *TreeNode) (ans int) {
	sum := []int{}
	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, level int) {
		if level == len(sum) {
			sum = append(sum, node.Val)
		} else {
			sum[level] += node.Val
		}
		if node.Left != nil {
			dfs(node.Left, level+1)
		}
		if node.Right != nil {
			dfs(node.Right, level+1)
		}
	}
	dfs(root, 0)
	for i, s := range sum {
		if s > sum[ans] {
			ans = i
		}
	}
	return ans + 1 // 层号从 1 开始
}

Review

【TED演讲】你的话可以预测你未来的心理健康

这个TED有点像NLP(Natural Language Processing)自然语言处理的推广片,哈哈,通过数据分析,相关性自动机,等等,来分析一个人的语言是否连贯,以及分析其中的词法相关性,从而得知其中的含义和情感,从而分析人的精神状态,心理健康

Tips

根据文件头数据判断文件类型

Share

再次分享Concurrence in go

初看感觉很一般,再看发现大佬用非常普通简单通俗易懂的引导方式,简练的代码,清晰的整理,讲好了go并发的知识点

比如go channel规范做的表格,推荐去读原文

channel使用权限规范

Operation Channel State Result
Read nil Block
Open and Not Empty Value
Open and Empty Block
Closed <default value>, false
Write Only Compilation Error
Write nil Block
Open and Full Block
Open and Not Full Write Value
Closed panic
Receive Only Compilation Error
Close nil panic
Open and Not Empty Close Channel; reads succeed until channel is drained, then reads produce default value
Open and Empty Close Channel; reads produce default value
Close panic
Receive Only Compilation Error