ARTS-第33周

发表于

ARTS （第33周）

Algorithm 算法

岛屿数量

leetcode 200

https://leetcode-cn.com/problems/number-of-islands/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

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

解法：

每当发现有点的时候，就用一个数组记录所有相连的点。

在这题里，还可以直接将grid数组里的值改变，比如改成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
//执行用时:2 ms,在所有java提交中击败了97.14%的用户
	//内存消耗:41.3 MB,在所有java提交中击败了82.60%的用户
	//也可以直接将grid数组里的值改变 这样可以省内存
	public int numIslands(char[][] grid) {
		if (grid == null || grid.length == 0) {
			return 0;
		}
		int size = 0;
		// 辅助数组
		boolean[][] mem = new boolean[grid.length][];
		for (int i = 0; i < grid.length; i++) {
			mem[i] = new boolean[grid[i].length];
		}
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				if (grid[i][j] == '1') {
					if (mem[i][j])// 记录过的点
						continue;
					mark(grid, mem, i, j);
					size++;
				}

			}
		}
		return size;
	}

	// 将本点和本点上下左右的点都编辑为true
	private void mark(char[][] grid, boolean[][] mem, int i, int j) {
		if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || (mem[i][j]) ||grid[i][j]!='1') {
			return;// 不存在的点或者当前点已记录
		}
		mem[i][j] = true;
		// 上下左右
		mark(grid, mem, i + 1, j);
		mark(grid, mem, i - 1, j);
		mark(grid, mem, i, j + 1);
		mark(grid, mem, i, j - 1);

	}

路径总和

leetcode 112

https://leetcode-cn.com/problems/path-sum/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

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

示例: 
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

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

树结构以及辅助方法

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
public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}

		@Override
		public String toString() {
			return " {val:" + val + ", left:" + left + ", right:" + right + "}";
		}

	}

	public static TreeNode arr2tree(Integer[] arr) {
		Integer[] a = new Integer[arr.length + 1];
		System.arraycopy(arr, 0, a, 1, arr.length);
		TreeNode root = new TreeNode(a[1]);
		arr2treeHelp(a, root, 1);
		return root;
	}

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

	}

解法1

递归穷举法将情况都罗列。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 执行用时:0 ms,在所有java提交中击败了100.00%的用户
	// 内存消耗:37.8 MB,在所有java提交中击败了45.70%的用户
	public boolean hasPathSum_(TreeNode root, int sum) {
		if (root == null)
			return false;
		sum -= root.val;
		if (root.left == null && root.left == null) {
			// 叶子节点
			return sum == 0;
		}
		// 左右
		return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
	}

和递归一样的思路，穷举，用队列保存，不使用递归，使用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
// 执行用时:2ms,在所有java提交中击败了21.41%的用户
	// 内存消耗:37.3MB,在所有java提交中击败了66.16%的用户
	public boolean hasPathSum(TreeNode root, int sum) {

		if (root == null)
			return false;
		// 和递归思路一致 使用队列保存递归时候的变量 更省内存
		LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();
		LinkedList<Integer> nums = new LinkedList<Integer>();
		nodes.add(root);
		nums.add(sum - root.val);
		while (!nodes.isEmpty()) {
			TreeNode node = nodes.poll();
			Integer v = nums.poll();
			if (node.left == null && node.right == null && v == 0) {
				return true;
			}
			if (node.left != null) {
				nodes.push(node.left);
				nums.push(v - node.left.val);
			}
			if (node.right != null) {

				nodes.push(node.right);
				nums.push(v - node.right.val);
			}
		}
		return false;

	}

Review 英文文章

https://spring.io/guides/gs/messaging-jms/

spring整合jms，发送邮件

Tip 技巧

java动态代理

1、在有接口的时候，使用jdk自带的InvocationHandler 类+Proxy类进行动态代理

2、在没有接口的时候，使用cglib的的Enhancer类和MethodInterceptor类进行动态代理

自定义classloader

继承classloader，然后重写findClass方法，

在findclass里有个defineClass方法，可以通过这个方法进行自定义。

方法定义如下：

protected final Class defineClass(String name, byte[] b, int off, int len)

这个方法里的第二个参数就是class文件的字节码，第一个是类名，因此我们可以在需要重新加载类的时候，自定义调用这个defineClass方法，实现自定义（如热部署）的效果。

Share 分享

https://www.cnblogs.com/sunhao96/p/7873842.html 事件驱动模型和异步IO多路复用

http://www.cnpaf.net/class/RFC/ RFC文档