面试笔试题

Given a 2d grid map of '1’s (land) and’0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:
11110
11010
11000
00000
Answer: 1

Example 2:
11000
11000
00100
00011
Answer: 3

给定的一个二维网格的地图(’1’(陆地)和0(水)),计数岛的数量。岛屿是四面环水,是由相邻的陆地水平或垂直连接而形成的。你可以假设该网格的所有四个边都被水包围。

采用深度优先遍历,把访问过的改为‘0’,继续遍历

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
public class 岛屿的数量 {
public int (char[][] grid) {
if (grid == null || grid.length == 0
|| grid[0].length == 0)
return 0;
int rows = grid.length;
int cols = grid[0].length;
int count = 0;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)

if (grid[i][j] == '1') {
count++;
dfsSearch(grid, i, j, rows, cols);
}
return count++;
}

// 每遇到'1'后, 开始向四个方向 递归搜索. 搜到后变为'0',
// 因为相邻的属于一个island. 然后开始继续找下一个'1'.
private void dfsSearch(char[][] grid,
int i, int j, int rows, int cols) {
if (i < 0 || i >= rows || j < 0 || j >= cols)
return;
if (grid[i][j] != '1')
return;
// 也可以才用一个visited数组,标记遍历过的岛屿
grid[i][j] = '0';
dfsSearch(grid, i + 1, j, rows, cols);
dfsSearch(grid, i - 1, j, rows, cols);
dfsSearch(grid, i, j + 1, rows, cols);
dfsSearch(grid, i, j - 1, rows, cols);

}
}

最大公约数

参考自:java 算法基础之一寻找最大公约数

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

public class GreatestCommonDivisor {

public static void main(String[] args) {
int a=60;
int b=45;
System.out.println(getGCD(a, b));

}

public static int getGCD(int a, int b) {
if (a < b) {
return getGCD(b, a);
}
if (0 == b) {
return a;
}
if (isTwo(a)) {
if (isTwo(b)) {
return getGCD(a / 2, b / 2) * 2;
}
return getGCD(a / 2, b);
} else {
if (isTwo(b)) {
return getGCD(a, b / 2);
}
return getGCD(b, a - b);
}

}

private static boolean isTwo(int a) {
if (0 == a % 2) {
return true;
} else {
return false;
}
}

}

海伦公式

假设在平面内,有一个三角形,边长分别为$a$ 、$b$ 、$c$ ,三角形的面积$S$ 可由以下公式求得:
$$S=sqrt{p(p-a)(p-b)(p-c)}$$

而公式里的p为半周长:
$$p=(a+b+c)/2$$