ARTS 第57周

发表于

ARTS （第57周）

吴军老师的五级工程师模型：

第五级：能独立解决问题，完成工程工作；
第四级：能指导和带领其他人一同完成更有影响力的工作；
第三级：能独立设计和实现产品，并且在市场上获得成功；
第二级：能设计和实现别人不能做出的产品，也就是说他的作用很难取代；
第一级：开创一个产业

Algorithm 算法

删除链表中重复的结点

1
2
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&tqId=11209&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法

思路就是循环的时候如果发现了有重复节点，就进行重复节点的删除

其他也可以使用各种集合保存重复节点。

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
public ListNode deleteDuplication(ListNode pHead) {
	if (pHead == null) {
		return null;
	}
	ListNode res = new ListNode(0);// 哨兵
	res.next = pHead;
	ListNode cur = pHead;
	ListNode prev = res;
	while (cur != null) {
		if (cur.next != null && cur.next.val == cur.val) {
			// 这种情况删除 cur和cur.next
			cur = cur.next;
			// 判断有没有更多要删除的
			while (cur.next != null && cur.next.val == cur.val) {
				cur = cur.next;
			}
			cur = cur.next;
			prev.next = cur;
		} else {
			prev = cur;
			cur = cur.next;
		}
	}
	return res.next;
}

二叉树的下一个结点

1
2
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法

因为中序遍历方式的特点。将各种情况进行罗列。然后写对应的判断。

详细思路可以看代码里的注释。

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
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
   public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
		if(pNode ==null) {
			return null;
		}
		//因为是中序遍历的下一个节点 
		//细分中序遍历的情况 
		//有右节点 
		if(pNode.right !=null) {
			TreeLinkNode node = pNode.right;
			//然后找右节点里的最后一个左节点
			//类似各种树结构算法的后继节点
			while(node.left!=null) {
				node=node.left;
			}
			return node;
		}
		//当前节点是父节点的左子树 （无右节点 ）
		if(pNode.next !=null && pNode.next.left == pNode) {
			return pNode.next;
		}
		//当前节点是父节点的右子树（无右节点 ）
		if(pNode.next !=null && pNode.next.right == pNode) {
			//这里 其实就代表着某个左子树已经循环完了 那么就要找到 这个已遍历完的左子树的父节点
			//即向父节点查找 直到找到当前节点是父节点的左子树 那么这个节点的父节点就是下一个节点
			//这里也可能是已经遍历完成了
			TreeLinkNode node = pNode.next;
			while(node.next!=null &&node.next.right==node) {
				node = node.next;
			}
			return node.next;
		}
		//整个树只有当前节点
		return null;
    }
}

对称的二叉树

1
2
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=13&tqId=11211&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法 镜像方式的遍历

每次遍历都获取两个节点，这两个节点是镜像对称位置的。

这里我实现是BFS 其它也可以用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
boolean isSymmetrical(TreeNode pRoot) {
	if (pRoot == null)
		return true;
	LinkedList<TreeNode> queue = new LinkedList<>();
	// 每次都是放入2个节点
	// 2个节点就是镜像相对的节点
	queue.offer(pRoot.left);
	queue.offer(pRoot.right);
	while (queue.size() > 0) {
		// P1 P2是镜像位置对应的节点
		TreeNode p1 = queue.poll();
		TreeNode p2 = queue.poll();
		//2个节点必须一致
		if (p1 == null && p2 == null)
			continue;
		if (p1 == null || p2 == null)
			return false;
		if (p1.val != p2.val)
			return false;
		//再以镜像的方式放入子节点 
		queue.offer(p1.left);
		queue.offer(p2.right);
		queue.offer(p1.right);
		queue.offer(p2.left);
	}
	return true;
}

Review 英文文章

https://spring.io/guides/gs/async-method/

官方文档里的spring 异方法

Tip 技巧

五级工程师模型

第五级：能独立解决问题，完成工程工作；
第四级：能指导和带领其他人一同完成更有影响力的工作；
第三级：能独立设计和实现产品，并且在市场上获得成功；
第二级：能设计和实现别人不能做出的产品，也就是说他的作用很难取代；
第一级：开创一个产业

摘自 吴军老师

极客时间《设计模式之美》23~24章

https://time.geekbang.org/column/intro/250

Share 分享

https://www.jianshu.com/p/2bceacd60b8a Zookeeper——一致性协议:Zab协议

https://blog.csdn.net/yanpenglei/article/details/80362561 ZooKeeper和CAP理论及一致性原则

https://blog.csdn.net/jsjwk/article/details/90714132 吴军博士眼中的五级软件工程师