Fork me on GitHub

ARTS(7)

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

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-------------