Fork me on GitHub

ARTS(7)

Posted on | Edited on | In | Views:

ARTS 第七周

每周完成一个ARTS（也就是 Algorithm、Review、Tip、Share 简称ARTS）：

  1. 每周至少做一个 leetcode 的算法题
  2. 阅读并点评至少一篇英文技术文章
  3. 学习至少一个技术技巧
  4. 分享一篇有观点和思考的技术文章。

Algorithm

力扣 79. 单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]

给定 word = “ABCCED”, 返回 true.
给定 word = “SEE”, 返回 true.
给定 word = “ABCB”, 返回 false.

思路：DFS 的解法，发现匹配即返回true

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

import org.junit.Test;

public class 单词搜索 {

	public int[][] visited;
	public int[] X = {0, 0, 1, -1};
	public int[] Y = {1, -1, 0, 0};
	public int n, m;

	@Test
	public void getResult() {
		char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
		String word = "ABCB";
		boolean result = exist(board, word);
		System.out.println(result); // expect false
	}

	@Test
	public void getResult1() {
		char[][] board = {{'C', 'A', 'A'}, {'A', 'A', 'A'}, {'B', 'C', 'D'}};
		String word = "AAB";
		boolean result = exist(board, word);
		System.out.println(result); //expect true
	}

	@Test
	public void getResult2() {
		char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'E', 'S'}, {'A', 'D', 'E', 'E'}};
		String word = "ABCESEEEFS";
		boolean result = exist(board, word);
		System.out.println(result); //expect true
	}

	public boolean exist(char[][] board, String word) {
		char head = word.charAt(0);
		n = board.length;
		m = board[0].length;
		boolean result;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				visited = new int[n][m];
				if (board[i][j] == head) {
					String temp = "";
					temp += head;
					visited[i][j] = 1;
					int depth = 0;
					result = DFS(board, i, j, word, temp, depth);
					if (result == true) {
						return true;
					}
				}
			}
		}
		return false;

	}

	private boolean DFS(char[][] board, int x, int y, String word, String temp, int depth) {
		if (word.equals(temp)) {
			return true;
		}
		if (temp.length() > word.length()) {
			return false; // 剪枝
		}

		for (int i = 0; i < 4; ++i) {
			int newX = x + X[i];
			int newY = y + Y[i];
			if (visited(newX, newY) == true && board[newX][newY] == word.charAt(depth + 1)) {
				visited[newX][newY] = 1;
				temp += board[newX][newY];
				boolean flag = DFS(board, newX, newY, word, temp, depth + 1);
				temp = temp.substring(0, temp.length() - 1); // 关键步骤，temp 删尾
				visited[newX][newY] = 0; // 关键步骤，visited 状态清空
				if (flag == true) {
					return true;
				}
			}
		}
		return false;
	}

  // 判断边界以及是否已被访问
	private boolean visited(int i, int j) {
		if (i < 0 || i >= n || j < 0 || j >= m) {
			return false;
		}
		if (visited[i][j] == 1) {
			return false;
		}
		return true;
	}
}

Review

本周阅读英文：Top 5 Big Data and Apache Spark Courses for Java Developers to Learn Online in 2019

文中指出 Spark 比之 Hadoop 效率要更高，并且推荐了五门课程：

  1. 推荐：Apache Spark with Java - Learn Spark from a Big Data Guru
  2. Apache Spark with Scala - Learn Spark from a Big Data Guru
  3. 推荐：Apache Spark Fundamentals
  4. Big Data: The Big Picture By Pluralsight
  5. 推荐：Apache Spark 2.0 + Java : DO Big Data Analytics & ML

不定时更新学习内容

Tip

一点心得：还是要有月计划，不然容易被琐事打乱节奏。

Share

本周分享机器学习平台 PAI 入门，参考本站文章，点击：Ali 机器学习平台 PAI

-------------The End-------------