ARTS-第31周

发表于

ARTS （第31周）

做事要有针对性。

针对性的学习，针对性的工作。

还应当要拓展深入。

Algorithm 算法

二叉树的最大深度

LeetCode 104

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

3
  / \
 9  20
   /  \
  15   7

返回它的最大深度 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1

广度优先算法 bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int maxDepth(TreeNode root) {

		return bfs(root, 0);

	}

public int bfs(TreeNode root, int d) {
		if (root == null) {
			return d;
		}

		int deep = d + 1;
		if (root.left != null) {
			deep = bfs(root.left, d + 1);
		}
		if (root.right != null) {
			int r = bfs(root.right, d + 1);
			if (r > deep) {
				deep = r;
			}
		}
		return deep;
	}

解法2

深度优先算法 dfs 双队列的

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

public int dfs_(TreeNode root) {
	if (root == null) {
		return 0;
	}
	//双队列DFS
	Queue<TreeNode> q1 = new LinkedList<TreeNode>();
	Queue<TreeNode> q2 = new LinkedList<TreeNode>();
	int deep = 1;
	if (root.left != null)
		q1.add(root.left);
	if (root.right != null)
		q1.add(root.right);
	while (!q1.isEmpty()) {
		deep++;
		TreeNode e = q1.poll();
		while (e != null) {
			if (e.left != null)
				q2.add(e.left);
			if (e.right != null)
				q2.add(e.right);
			e = q1.poll();
		}

		// swap
		Queue<TreeNode> t = q1;
		q1 = q2;
		q2 = t;
	}
	return deep;

}

解法3

深度优先算法 dfs 单队列的

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
public int dfs(TreeNode root) {
		if (root == null) {
			return 0;
		}
		//单队列DFS
		Queue<TreeNode> q1 = new LinkedList<TreeNode>();
		int deep = 1;
		if (root.left != null)
			q1.add(root.left);
		if (root.right != null)
			q1.add(root.right);
		while (!q1.isEmpty()) {
			deep++;
			int size = q1.size();
			for (int i = 0; i < size; i++) {
				TreeNode e = q1.poll();
				if (e.left != null)
					q1.add(e.left);
				if (e.right != null)
					q1.add(e.right);
			}
			
		}
		return deep;

	}

Review 英文文章

https://spring.io/guides/gs/maven/

如何用maven构建spring项目

Tip 技巧

线程安全的机制

1
2
3
4
5
6
7
8
synchronized关键字
显式锁（lock类）
volatile变量
原子变量
写时复制（cow）
原子级的cas算法（需要硬件支持）
ThreadLocal
等等

多线程协作机制

1
2
3
4
5
wait/notify
显式锁的条件（condition类）
线程中断（interrupt）
各类工具和框架（线程池、CountDownLatch、Semaphore、Barrier等）
各种支持线程安全的容器（以JUC为代表）

Share 分享

https://blog.csdn.net/S1amDuncan/article/details/95788892

线程数的设置–CPU密集型和IO密集型

https://github.com/getlantern/lantern

蓝灯发布站

https://github.com/nusr/hacker-laws-zh

对开发人员有用的定律、理论、原则和模式。