ARTS-第47周

发表于

ARTS （第47周）

压力并不能转化为动力。 压力和动力的来源都是目标。从目标看到了希望,就产生了动力,从目标看到了阻碍,就产生了压力。

Algorithm 算法

从上往下打印二叉树

1
2
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?tpId=13&tqId=11175&tPage=2&rp=2&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
import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
   // BFS广度优先算法
	public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		if(root==null)
			return res;
		// 用ArrayList 模拟栈功能
		ArrayList<TreeNode> stack = new ArrayList<TreeNode>();
		stack.add(root);
		while (stack.size() > 0) {
			TreeNode node = stack.remove(0);
			if (node.left != null)
				stack.add(node.left);
			if (node.right != null)
				stack.add(node.right);
			res.add(node.val);
		}
		return res;
	}
}

二叉搜索树的后序遍历序列

1
2
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同
https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&tPage=2&rp=2&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
public boolean VerifySquenceOfBST1(int[] sequence) {
		if (sequence == null || sequence.length == 0) {
			return false;
		}
		return VerifySquenceOfBSTHelp(sequence, 0, sequence.length - 1);
	}

	// 后面看了题解 r变量可以不设置，
	// 可以在找右子树末尾的循环中，改成如果a[i] > root==false 就直接return false;
	// 因为这种时候，就是错误的情况即右子树有小于根节点数据的情况
	public boolean VerifySquenceOfBSTHelp(int[] a, int s, int e) {
		if (s >= e)
			return true;
		int root = a[e];// 根节点是最后一个
		// 找出左子树的末尾
		int l = s - 1;
		for (int i = s; i < e && a[i] < root; i++) {
			l++;
		}
		int r = l;
		// 找出右子树的末尾
		for (int i = r + 1; i < e && a[i] > root; i++) {
			r++;
		}
		// 1 3 2 5
		// 如果r没有到达e-1 就是非法的结果
		if (r != e - 1) {
			return false;
		}
		// 左右节点是否正确
		boolean leftRes = true;
		boolean rightRes = true;
		// 有左子树
		if (l != s - 1) {
			leftRes = VerifySquenceOfBSTHelp(a, s, l);
		}
		// 有右子树
		if (r != l) {
			leftRes = VerifySquenceOfBSTHelp(a, l + 1, e - 1);
		}
		return leftRes && rightRes;
	}

优化版

看到的题解，得到了启发做出来的结果。每次都砍掉末尾的根节点。然后把左子树当作是右子树的最小节点的左子树。

因为：原本的遍历结果，和把当前左子树当作是右子树的最小节点的左子树进行遍历的结果，其实是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean VerifySquenceOfBST(int[] sequence) {
		if (sequence == null || sequence.length == 0) {
			return false;
		}
		int root = sequence.length - 1;// root的索引
		int i = 0;// 遍历的索引
		while (root > 0) {
			while (sequence[i] < sequence[root]) {
				i++;
			}
			while (sequence[i] > sequence[root]) {
				i++;
			}

			if (i < root) {
				return false;
			}
			i = 0;
			root--;
			// 在这里root--，即把根节点去掉，把左子树当作是右子树的最小节点的左子树。
			// 原本的遍历结果，和把当前左子树当作是右子树的最小节点的左子树进行遍历的结果，其实是一样的。
		}
		return true;
	}

这是看到的别人的写法

最初看到创建了多个Stack 以为是创建多个Stack来模拟递归的方法栈的写法，然后发现不是
这个方法是利用后续遍历的规律做的，
例如 最后一个节点是根，如果最后一个节点比根大，就是根节点的右子树，反之就是左子树
一个很强大的写法 Orz

来自 https://www.nowcoder.com/profile/709610362 凉风起天末

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
// 这是看到的别人的写法
	// 最初看到创建了多个Stack 以为是创建多个Stack来模拟递归的方法栈的写法，然后发现不是
	// 这个方法是利用后续遍历的规律做的，
	// 例如 最后一个节点是根，如果最后一个节点比根大，就是根节点的右子树，反之就是左子树
	// 一个很强大的写法 Orz
	// https://www.nowcoder.com/profile/709610362
	// 凉风起天末
	boolean VerifySquenceOfBST_(int[] sequence) {
		if (sequence.length < 1)
			return false;
		else if (sequence.length < 3)
			return true;
		else {
			int idx = sequence.length - 1;
			Stack<Integer> bound_min = new Stack<Integer>();
			Stack<Integer> bound_max = new Stack<Integer>();
			Stack<Integer> roots = new Stack<Integer>();
			roots.push(sequence[idx--]);
			bound_min.push(Integer.MIN_VALUE);
			bound_max.push(Integer.MAX_VALUE);

			for (; idx > -1; idx--) {
				if (sequence[idx] > sequence[idx + 1]) {
					// 倒序遍历趋势为递增，说明是进入了某个右子树
					if (sequence[idx] > bound_max.peek())
						// 当前元素超越了最大上限约束，这是不合法的
						return false;
					else {
						// 合法，进入右子树，更新三个栈
						bound_min.push(roots.peek());
						bound_max.push(bound_max.peek());
						roots.push(sequence[idx]);
					}
				} else {
					// 倒序遍历趋势为递减，说明是进入了某个左子树
					if (sequence[idx] < bound_min.peek()) {
						// 当前元素打破了最小下限约束，说明是右子树遍历完了，跳转到兄弟左子树
						// 当前元素为兄弟左子树的根，之前右子树节点全部出栈
						while (sequence[idx] < bound_min.peek()) {
							bound_min.pop();
							bound_max.pop();
							roots.pop();
						}
					} else {
					} // 没有突破下限，说明是右子树不存在，直接进入左子树，不做特殊处理
						// 进入左子树，更新三个栈
					bound_min.push(bound_min.peek());
					bound_max.push(roots.peek());
					roots.push(sequence[idx]);
				}
			}
			return true;
		}
	}

二叉树中和为某一值的路径

1
2
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

这里的题目要求在返回值的list中，数组长度大的数组靠前。

我就想用BFS，BFS按层遍历，结果会是数组越短的越靠前，最后做个reverse即可。

不给这个方法，创建了太多集合。耗内存较大

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
// 输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意:在返回值的list中，数组长度大的数组靠前)
	public ArrayList<ArrayList<Integer>> FindPath1(TreeNode root, int target) {
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		if (root == null)
			return res;// 这里原本是return null的 结果报错了
		// 用ArrayList 模拟栈功能
		ArrayList<TreeNode> stack = new ArrayList<TreeNode>();
		// 用ArrayList 模拟栈功能
		ArrayList<Integer> vals = new ArrayList<Integer>();
		// 用ArrayList 模拟栈功能
		ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
		stack.add(root);
		vals.add(root.val);
		ArrayList<Integer> p = new ArrayList<Integer>();
		p.add(root.val);
		paths.add(p);
		while (stack.size() > 0) {
			TreeNode node = stack.remove(0);
			Integer val = vals.remove(0);
			ArrayList<Integer> path = paths.remove(0);
			if (node.left != null) {
				stack.add(node.left);
				vals.add(val + node.left.val);
				ArrayList<Integer> pl = (ArrayList<Integer>) path.clone();
				pl.add(node.left.val);
				paths.add(pl);
			}
			if (node.right != null) {
				stack.add(node.right);
				vals.add(val + node.right.val);
				ArrayList<Integer> pr = (ArrayList<Integer>) path.clone();
				pr.add(node.right.val);
				paths.add(pr);
			} else if (node.left == null) {
				// 叶子节点
				// res.add(node.val);
				if (Integer.valueOf(val) == target) {
					res.add(path);
				}
			}

		}

		res = reverse(res);
		return res;

	}

	// 反转
	private ArrayList<ArrayList<Integer>> reverse(ArrayList<ArrayList<Integer>> res) {
		ArrayList<ArrayList<Integer>> copy = new ArrayList<ArrayList<Integer>>();
		for (int i = res.size() - 1; i >= 0; i--) {
			copy.add(res.get(i));
		}
		return copy;
	}

解法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
public class Solution {
    //全局变量
	private ArrayList<ArrayList<Integer>> findPathAll = new ArrayList<ArrayList<Integer>>();
	private ArrayList<Integer> findPathList = new ArrayList<Integer>();
	private int findPathVal=0;

	public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
		if (root == null)
			return findPathAll;
		//配合后面的删除，可以仅在当前、子级生效，不影响父级和兄弟节点
		findPathList.add(root.val);
		findPathVal+=root.val;
		
		if(root.left==null && root.right==null&&findPathVal==target ){
			findPathAll.add((ArrayList<Integer>) findPathList.clone());
		}
		
		FindPath(root.left, target);
		FindPath(root.right, target);
		//每次迭代完后删除这些，避免创建过多的变量
		findPathList.remove(findPathList.size()-1);
		findPathVal-=root.val;
		return findPathAll;
	}
}

复杂链表的复制

1
2
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&tPage=2&rp=2&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
// 复杂链表的复制
	public RandomListNode Clone(RandomListNode pHead) {
		if(pHead == null) {
            return null;
        }
		CloneCopyNodes(pHead);
		CloneLinkRandomNodes(pHead);
		return CloneGetResult(pHead);
	}

	// 复制链表
	public void CloneCopyNodes(RandomListNode pHead) {
		RandomListNode cur = pHead;
		while (cur != null) {
			RandomListNode copy = new RandomListNode(cur.label);
			copy.next = cur.next;
			cur.next = copy;
			cur = copy.next;
		}
	}

	// 复制链表的随机指针
	public void CloneLinkRandomNodes(RandomListNode pHead) {
		RandomListNode cur = pHead;
		while (cur != null) {
			RandomListNode copy = cur.next;
			if(cur.random!=null)
				copy.random = cur.random.next;
			// 必定是偶数个指针 所以这么写
			cur = cur.next.next;
		}
	}

	// 分离链表 获取结果
	public RandomListNode CloneGetResult(RandomListNode pHead) {
		RandomListNode result = pHead.next;
		RandomListNode cur = pHead;
		while (cur != null) {
			RandomListNode copy = cur.next;
			RandomListNode next = cur.next.next;
			if(next!=null)
				copy.next = next.next;
			// 重新链接回去
			cur.next = next;
			cur = cur.next;
		}
		return result;
	}

二叉搜索树与双向链表

1
2
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&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
17
18
19
20
21
22
23
24

// 二叉树 改成双向链表
	public TreeNode Convert_(TreeNode pRootOfTree) {
		// 中序遍历
		if (pRootOfTree == null) {
			return null;
		}
		TreeNode left = Convert_(pRootOfTree.left);
		// 找出左子树链表最后一个节点
		TreeNode p = left;
		while (p != null && p.right != null) {
			p = p.right;
		}
		if (left != null) {
			p.right = pRootOfTree;
			pRootOfTree.left = p;
		}
		TreeNode right = Convert_(pRootOfTree.right);
		if (right != null) {
			pRootOfTree.right = right;
			right.left = pRootOfTree;
		}
		return left != null ? left : pRootOfTree;
	}

解法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
// 用栈结构进行中序遍历 每次保存前一个变量
	public TreeNode Convert(TreeNode root) {
		if (root == null)
			return null;
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur=root;
		TreeNode result=null;
		
		while(cur !=null){
			//每个节点都先处理左子节点
			result= cur;//最后的时候这是最小的节点 即链表头
			stack.push(cur);
			cur=cur.left;
		}
		TreeNode prev=null;
		while(!stack.isEmpty() || cur !=null){
			while(cur !=null){
				//每个节点都先处理左子节点
				stack.push(cur);
				cur=cur.left;
			}
			cur = stack.pop();
			TreeNode temp = cur.right;//先记录
			//遍历操作
			cur.left=prev;
			if(prev != null)
				prev.right=cur;
			prev = cur;
			//处理右子节点
			cur = temp;
			
		}
		return result;
	}

Review 英文文章

http://kafka.apache.org/intro

kafka的介绍

Tip 技巧

https://blog.csdn.net/qq_41781322/article/details/82867116 centos7 修改mac地址

https://blog.csdn.net/ntuxiaolei/article/details/81130866 CentOS7 修改hostname，ip地址以及hosts（永久生效）

Share 分享

https://www.douban.com/note/689615574/ 压力和动力