ARTS 第53周

发表于

ARTS （第53周）

知识总是带有很大的关联性，可以关联分析总结。

Algorithm 算法

二叉树的深度

1
2
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
https://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b?tpId=13&tqId=11191&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1 递归

递归计算子节点的值后，加一返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 递归
	public int TreeDepth_(TreeNode root) {
		// 空返回0
		if (root == null)
			return 0;
		// 左
		int r1 = TreeDepth(root.left);
		// 右
		int r2 = TreeDepth(root.right);
		if (r1 < r2) {
			r1 = r2;
		}
		// 子树深度+1
		return r1 + 1;
	}

解法2 bfs

每遍历一层 返回值就加一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// bfs
	public int TreeDepth(TreeNode root) {
		if (root == null)
			return 0;
		int h = 0;
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		// 按层遍历 
		while (queue.size() > 0) {
			//每次的size都为当前层的大小
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.pop();
				if (node.left != null)
					queue.add(node.left);
				if (node.right != null)
					queue.add(node.right);
			}
			//每便利完一层累加
			h++;
		}
		return h;
	}

数字在排序数组中出现的次数

1
2
统计一个数字在排序数组中出现的次数
https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&tqId=11190&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法 二分法

我这里的思路是找到第一个K 然后向后计算长度

也可以用其它方式，例如用二分法找到任意一个K，然后向前向后计算长度。

或者用二分法找到第一个k，然后用二分法找最后一个k，计算二者之间的距离。

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
public int GetNumberOfK(int[] array, int k) {
		if(array==null || array.length==0)
			return 0;
		int high = array.length - 1;
		int low = 0;
		//二分查找第一个K
		while (low < high) {
			int mid = low + (high - low) / 2;
			if (k == array[mid]) {
				// 如果找到了,就把当前当作high继续找 即找出第一个k
				high = mid;
			} else if (k > array[mid]) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		int len = 0;
		//有找到的话
		if (array[high] == k) {
			//计算长度
			for (int i = high; i < array.length; i++) {
				if (array[i] == k) {
					len++;
				} else {
					break;
				}
			}
		}
		return len;
	}

两个链表的第一个公共结点。

1
2
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法1 暴力搜索

第一个想到的解法自然就是 暴力搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 暴力
	public ListNode FindFirstCommonNode_(ListNode pHead1, ListNode pHead2) {
		ListNode c1 = pHead1;
		// 暴力双重循环
		while (c1 != null) {
			ListNode c2 = pHead2;
			while (c2 != null) {
				if (c1 == c2) {
					return c1;
				}
				c2 = c2.next;
			}
			c1 = c1.next;
		}
		return null;
	}

解法2 保证同步

如果两个链表有共同节点，那么链表的后半段一定是一样的。

计算2个链表长度差值，让长的链表先走差值的步数。

然后共同前进，这样就可以找到第一个共同的节点。

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
public ListNode FindFirstCommonNode__(ListNode pHead1, ListNode pHead2) {
		if (pHead1 == null || pHead2 == null) {
			return null;
		}
		int l1 = 0;
		int l2 = 0;
		ListNode c1 = pHead1;
		ListNode c2 = pHead2;
		// 分别求出2个的长度
		while (c1 != null) {
			l1++;
			c1 = c1.next;
		}
		while (c2 != null) {
			l2++;
			c2 = c2.next;
		}
		int diff = l1 - l2;
		// 用c1保存更长的链表
		if (diff < 0) {
			diff = -diff;
			c1 = pHead2;
			c2 = pHead1;
		} else {
			c1 = pHead1;
			c2 = pHead2;
		}
		// 长链表先走相差步数
		for (int i = 0; i < diff; i++) {
			c1 = c1.next;
		}
		// 一起前进
		while (c1 != null && c2 != null) {
			if (c1 == c2) {
				return c1;
			}
			c1 = c1.next;
			c2 = c2.next;
		}
		return null;
	}

解法3 不停循环

两个链表，一直走总会有遇到的时候。

这种解法有2个弊端，

（1）如果链表有环就会死循环。

（2）如果两个链表长度一致，又没有共同节点，也会死循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
		if (pHead1 == null || pHead2 == null) {
			return null;
		}
		ListNode c1 = pHead1;
		ListNode c2 = pHead2;
		// 只要不存在环 一直走总会有遇到的时候
		while (c1 != c2) {
			c1 = c1.next;
			c2 = c2.next;
			//
			if (c1 != c2) {
				if (c1 == null) {
					c1 = pHead1;
				}
				if (c2 == null) {
					c2 = pHead2;
				}
			}
		}
		return c1;
	}

Review 英文文章

https://spring.io/guides/gs/validating-form-input/

使用@valid注解验证web表单

Tip 技巧

你知道哪些JVM性能调优
得观察程序运行，和判断程序。
设定堆内存大小
-Xmx：堆内存最大限制。
设定新生代大小。 新生代不宜太小，否则会有大量对象涌入老年代
-XX:NewSize：新生代大小
-XX:NewRatio 新生代和老生代占比
-XX:SurvivorRatio：伊甸园空间和幸存者空间的占比
设定垃圾回收器 年轻代用 -XX:+UseParNewGC 年老代用-XX:+UseConcMarkSweepGC

MYSQL优化主要分为以下四大方面：
设计：存储引擎，字段类型，范式与逆范式
功能：索引，缓存，分区分表。
架构：主从复制，读写分离，负载均衡。
合理SQL

高并发怎么编程
1、系统拆分。如搭配反向代理，负载均衡来实现微服务，RPC等
2、热点数据缓存
3、根据场景使用MQ等中间件，又或者是其它ES等中间件，削峰并提高速度。
4、数据库分库分表，提高响应速度，大表查询慢。
5、数据库进行读写分离、主从复制 等配置。

Share 分享

https://blog.csdn.net/beiyetengqing/article/details/49580559 多线程之指令重排序

https://www.zhihu.com/question/37601861 java中的notify和notifyAll有什么区别？

https://www.jianshu.com/p/f3fae8658f13 单例模式