ARTS 第58周

发表于

ARTS （第58周）

不管做任何事情，如果我们总是等到所有的东西都想好了再开始，那这件事情可能永远都开始不了。有句老话讲：万事开头难，所以，先迈出第一步很重要。

Algorithm 算法

按之字形顺序打印二叉树

1
2
3
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=13&tqId=11212&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法 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
import java.util.ArrayList;
import java.util.LinkedList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
   public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		if (pRoot == null)
			return res;
		ArrayList<Integer> first = new ArrayList<Integer>();
		first.add(pRoot.val);
		res.add(first);
		LinkedList<TreeNode> queue1 = new LinkedList<TreeNode>();
		LinkedList<TreeNode> queue2 = new LinkedList<TreeNode>();
		int size = 0;// queue大小
		if (pRoot.left != null)
			queue1.add(pRoot.left);
		if (pRoot.right != null)
			queue1.add(pRoot.right);
		while (queue1.size() > 0 || queue2.size() > 0) {

			// 右向左
			size = queue1.size();
			ArrayList<Integer> level = new ArrayList<Integer>();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue1.removeLast();
				level.add(node.val);
				if (node.right != null)
					queue2.add(node.right);
				if (node.left != null)
					queue2.add(node.left);
			}
			if (level.size() > 0)
				res.add(level);
			// 左向右
			size = queue2.size();
			ArrayList<Integer> level2 = new ArrayList<Integer>();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue2.removeLast();
				level2.add(node.val);
				if (node.left != null)
					queue1.add(node.left);
				if (node.right != null)
					queue1.add(node.right);
			}
			if (level2.size() > 0)
				res.add(level2);
		}

		return res;

	}

}

把二叉树打印成多行

1
2
3
题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
https://www.nowcoder.com/practice/445c44d982d04483b04a54f298796288?tpId=13&tqId=11213&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

解法 BFS

这题的本质就是个bfs 直接使用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
import java.util.ArrayList;
import java.util.LinkedList;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		if (pRoot == null)
			return res;

		LinkedList<TreeNode> queue1 = new LinkedList<TreeNode>();
		int size = 0;// queue大小
		queue1.add(pRoot);
		while (queue1.size() > 0) {
			// 左向右
			size = queue1.size();
			ArrayList<Integer> level2 = new ArrayList<Integer>();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue1.removeFirst();
				level2.add(node.val);
				if (node.left != null)
					queue1.add(node.left);
				if (node.right != null)
					queue1.add(node.right);
			}
			if (level2.size() > 0)
				res.add(level2);
		}

		return res;

	}
    
}

序列化二叉树

1
2
3
4
5
6
7
8
9
10
题目描述
请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树

https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=13&tqId=11214&tPage=4&rp=4&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
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
String Serialize1(TreeNode root) {
		return tree2arr(root);
	}

	TreeNode Deserialize1(String str) {
		return arr2tree(str);
	}

	public static String tree2arr(TreeNode pRoot) {
		StringBuilder sb = new StringBuilder("#,");
		if (pRoot == null)
			return sb.toString();
		LinkedList<TreeNode> queue1 = new LinkedList<TreeNode>();
		int size = 0;// queue大小
		queue1.add(pRoot);
		while (queue1.size() > 0) {
			// 左向右
			size = queue1.size();
			boolean flag = false;
			StringBuilder currentLine = new StringBuilder();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue1.removeFirst();
				if (node == null) {
					currentLine.append("#,");
					queue1.add(null);
					queue1.add(null);
				} else {
					currentLine.append(node.val);
					currentLine.append(",");
					queue1.add(node.left);
					queue1.add(node.right);
					flag = true;
				}

			}
			if (!flag) {
				break;
			}
			sb.append(currentLine);
		}

		return sb.toString();

	}

	public static TreeNode arr2tree(String str) {
		String[] arr = str.split(",");
		if (arr.length <= 1) {
			return null;
		}
		TreeNode root = new TreeNode(Integer.valueOf(arr[1]));
		arr2treeHelp(arr, root, 1);
		return root;
	}

	public static void arr2treeHelp(String[] arr, TreeNode node, int idx) {
		int len = arr.length;
		if (len > 2 * idx && arr[2 * idx] != null && (!"#".equals(arr[2 * idx]))) {
			TreeNode left = new TreeNode(Integer.valueOf(arr[2 * idx]));
			node.left = left;
			arr2treeHelp(arr, left, 2 * idx);
		}
		if (len > 2 * idx + 1 && arr[2 * idx + 1] != null && (!"#".equals(arr[2 * idx + 1]))) {
			TreeNode r = new TreeNode(Integer.valueOf(arr[2 * idx + 1]));
			node.right = r;
			arr2treeHelp(arr, r, 2 * idx + 1);
		}

	}

解法2 前序遍历

Serialize就是一个前序遍历的结果保存

Deserialize 则是根据前序遍历的结果进行的解析。

核心思路为 当遇到#（空叶子节点）的时候就是遇到空叶子节点,就应该跳到下一个位置的遍历了。

如当前空节点为父节点的左节点，那么就应该遍历右节点了。

如果是右节点，则代表当前这个子树已经完成了。

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
import java.util.LinkedList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
  public String Serialize(TreeNode root) {
		if (root == null) {
			return "#";
		} else {
			return root.val + "," + Serialize(root.left) + "," + Serialize(root.right);
		}
	}

	TreeNode Deserialize(String str) {
		if (str == null || str.length() == 0)
			return null;
		deserializeHelpIndex =0;
		String[] arr = str.split(",");
		if(arr.length==1 && "#".equals(arr[0]))
			return null;
		return DeserializeHelp(arr);
	}
	int deserializeHelpIndex =0;
	private TreeNode DeserializeHelp(String[] arr) {
		if (deserializeHelpIndex < arr.length && arr[deserializeHelpIndex].equals("#")) {
			deserializeHelpIndex++;
			return null;
		}
		TreeNode node = new TreeNode(Integer.valueOf(arr[deserializeHelpIndex]));
		deserializeHelpIndex++; 
		node.left = DeserializeHelp(arr);//遍历直到左子树完成
		node.right = DeserializeHelp(arr);//遍历直到右子树完成
		return node;
	}
}

Review 英文文章

https://spring.io/guides/gs/handling-form-submission/

处理表单数据

Tip 技巧

极客时间《设计模式之美》25~26章

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

Repository 层只关注数据的读写。Service 层只关注业务逻辑，不关注数据的来源。Controller 层只关注与外界打交道，数据校验、封装、格式转换，并不关心业务逻辑。三层之间的关注点不同，分层之后，职责分明，更加符合单一职责原则，代码的内聚性更好。

针对 Controller、Service、Repository 三层，每层都会定义相应的数据对象，它们分别是 VO（View Object）、BO（Business Object）、Entity，例如 UserVo、UserBo、UserEntity。

系统拆分有垂直和水平两个方向。水平方向基于业务来做拆分，就是模块化；垂直方向基于流程来做拆分，就是分层。

迈出第一步很重要

对于非业务通用框架的开发，我们在做需求分析的时候，除了功能性需求分析之外，还需要考虑框架的非功能性需求。比如，框架的易用性、性能、扩展性、容错性、通用性等。对于复杂框架的设计，很多人往往觉得无从下手。今天我们分享了几个小技巧，其中包括：画产品线框图、聚焦简单应用场景、设计实现最小原型、画系统设计图等。这些方法的目的都是为了让问题简化、具体、明确，提供一个迭代设计开发的基础，逐步推进。实际上，不仅仅是软件设计开发，不管做任何事情，如果我们总是等到所有的东西都想好了再开始，那这件事情可能永远都开始不了。有句老话讲：万事开头难，所以，先迈出第一步很重要。

迭代思维

写代码的过程本就是一个修修改改、不停调整的过程，肯定不是一气呵成的。你看到的那些大牛开源项目的设计和实现，也都是在不停优化、修改过程中产生的。比如，我们熟悉的 Unix 系统，第一版很简单、粗糙，代码不到 1 万行。所以，迭代思维很重要，不要刚开始就追求完美。面向对象设计和实现要做的事情，就是把合适的代码放到合适的类中。至于到底选择哪种划分方法，判定的标准是让代码尽量地满足低耦合、高内聚、单一职责、对扩展开放对修改关闭等之前讲的各种设计原则和思想，尽量地做到代码可复用、易读、易扩展、易维护。

Share 分享

https://blog.csdn.net/u012009613/article/details/52752625 java的 spi机制