文章目录
  1. 1. 01生长问题

  前几天实验室几个人都参加了百度的校招,然后同时开始考试,大家很有默契的开始“共享信息”,嘻嘻。然后我没报名,但这不影响我们聊一聊考试题目,当然,还是机试题目。

  第一题和第三题都很简单,第一题是矩阵那个,第三题是二叉树的遍历问题,都没啥意思,略。下面说说第二题,很好玩。

01生长问题

  同样,这问题的名字也是我瞎几把起的。

  题目:

  给定m*n的01矩阵,1为房子的屋顶,0为空地屋顶可以横向或纵向扩展但不可以对角线扩展。如

1
2
0 1 1 1 0
1 1 0 0 0

  为一栋房屋,而

1
2
0 0 1 1 0
1 1 0 0 0

  有两栋房屋。求输入的01矩阵中有多少栋房屋。

  输入:

  m*n的01矩阵

  输出:

  矩阵中有的房屋数

  解析:

  这题有两种解决思路,一种比较容易理解但是实现起来较为复杂,另一种思路不是很好理解,但是编程实现很简单。前一种是我设计实现,而后一种是同实验室另一个也没参加考试的同学完成的。

  先说第一种解决思路,该思路的核心就是尽可能的扩展遍历到的1并做标记(另外设置一个标记矩阵)。具体的,遍历整个输入矩阵,遇到0跳过,遇到1进行生长步骤,所谓生长即有连续1的话便进行扩展范围。生长有四种方式,分别是横向的正方向生长、横向的负方向生长、纵向的正生长、纵向的负生长,新生长出的分支首先标记为已经遍历过(防止重复遍历),此外新生长出的分支还要继续进行生长,直到遇到0或者遇到矩阵边界。

  这种是典型的需要通过递归来实现的案例,不过进行递归的时候除了返回外还要注意剪枝,即如:11这样,从第一个1的正向生长得到第二个1,此时第二个1再进行生长的时候就只能进行↑、→、↓生长,而不能进行←向生长,否则会导致死循环,不停的在两个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
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
package baidu;

import java.util.Arrays;

public class HomeCount {
public static void main(String[] args) {
int[][] grid=
{{0,1,1},
{1,0,0},
{1,1,0}};
System.out.println(CountHomes(grid));
}
public static int CountHomes(int[][] grid) {
int row=grid.length;//行数
int col=grid[0].length;//列数
int[][] banchMark=new int[row][col];
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if (grid[i][j]==0) {
banchMark[i][j]=1;
}else{
banchMark[i][j]=0;
}
}
}

//System.out.println(Arrays.deepToString(banchMark));
int homes=0;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if (banchMark[i][j]!=1) {
homes++;
banchMark=growth(i, j, banchMark, grid);
// for (int[] ks : banchMark) {
// System.out.println(Arrays.toString(ks));
// }
// System.out.println();
}
}
}

return homes;
}

public static int[][] growth(int i,int j,int[][] banchMark,int[][] grid) {
int col=grid.length;
int row=grid[0].length;
boolean flag=true;
int Ypointi=i;
int Xpointj=j;
//横向正扩展
while(flag&&Xpointj<col-1){
// System.out.println(i+"-"+Xpointj);
//System.out.println("->");

banchMark[i][Xpointj]=1;
Xpointj++;
if (banchMark[i][Xpointj]==1) {
break;
}
if (grid[i][Xpointj]==0) {
flag=false;
}else{
banchMark=growth(i, Xpointj, banchMark, grid);
}
}
flag=true;
//横向负扩展
while(flag&&Xpointj>0){
// System.out.println(i+"-"+Xpointj);
//System.out.println("<-");

banchMark[i][Xpointj]=1;
Xpointj--;
if (banchMark[i][Xpointj]==1) {
break;
}
if (grid[i][Xpointj]==0) {
flag=false;
}else{
banchMark=growth(i, Xpointj, banchMark, grid);
}
}
flag=true;
//纵向正扩展
while(flag&&Ypointi<row-1){
// System.out.println(Ypointi+"-"+j);
//System.out.println("up");

banchMark[Ypointi][j]=1;

Ypointi++;
if (banchMark[Ypointi][j]==1) {
break;
}
if (grid[Ypointi][j]==0) {
flag=false;
}else{
banchMark=growth(Ypointi, j, banchMark, grid);
}
}
flag=true;
//纵向负扩展
while(flag&&Ypointi>0){
// System.out.println(Ypointi+"-"+j);
//System.out.println("down");

banchMark[Ypointi][j]=1;
Ypointi--;
if (banchMark[Ypointi][j]==1) {
break;
}
if (grid[Ypointi][j]==0) {
flag=false;
}else{
banchMark=growth(Ypointi, j, banchMark, grid);
}
}

return banchMark;
}

}

  第二种思路是一种骨骼惊奇很好玩的思路,比较超常规,是我同实验室另一个没考试帮别人做题目的童鞋写出来的,他用的是c++,我不会,于是照着他的思路写了个java版本的。具体如下:

  首先进行一次右下方向的扫描,如果遇到0则跳过,遇到非0则将该位的右边位和下边位乘以2,如:

  原矩阵是:

1
2
1 1
1 0

  则处理后的矩阵变为:

1
2
1 2
2 0

  进行这样一次遍历后再进行一次逆向遍历(按左上方向遍历,从最右下角点开始),此次遍历如果遇到某一个大于1的点的上方和左方的点均为1则去除其中某个点(把他变成非1的数,或直接乘以2),遍历完成后数一下1的个数即为房子数。

  我这么说你们肯定觉得很玄乎是吧,我当时听那小伙给我讲我也是这么觉得。不过仔细思考一下还是很正确的一个思路。首先第一次遍历的时候就等于第一种思路的横向正方向和纵向负方向的生长,这样留下的1除了所有的符合要求的房子数外,还有几种会出现多余的情况,而第二步的逆向遍历处理的就是这种情况。

  估计你们又得晕了,咱们再整理一下思路吧。首先,所有的房子构型均可由矩形以及如下四种特殊构型组合而来,这四种构型分别是:

1
2
3
A:
0 1
1 1

  和

1
2
3
B:
1 0
1 1

  以及

1
2
3
C:
1 1
0 1

  还有

1
2
3
D:
1 1
1 0

  首先矩形情况全部可以通过上述第一步的迭代正确的处理完成,而四种特殊构型中的B、C、D三种构型均可通过上述第一步的迭代被正确的处理。只有情况A,即

1
2
0 1
1 1

  会出现多计算一次的问题,如其经过第一次迭代后变为:

1
2
0 1
1 2

  此时统计的时候多了一个1,数量多了。而这种情况结果第二步的反向处理便可以顺利的纠正,按照反向处理后,变为:

1
2
0 1
2 2

  随便变哪个1,我挑选的处理方式是给行数较大的那个1乘以2。这样统计后原阴影(即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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package baidu;

public class HomeCountMethodTwo {
public static void main(String[] args) {
int[][] grid=
{{0,1,1},
{1,0,0},
{1,1,0}};
System.out.println(CountHomes(grid));
}
public static int CountHomes(int[][] grid) {
//正向遍历
//行
for(int i=0;i<grid.length;i++){
//列
for(int j=0;j<grid[0].length;j++){
if (grid[i][j]!=0) {
if (j+1<grid[0].length) {
grid[i][j+1]=2*grid[i][j+1];
}
if (i+1<grid.length) {
grid[i+1][j]=2*grid[i+1][j];
}
}
}
}
//逆向遍历
for(int i=grid.length-1;i>=1;i--){
for(int j=grid[0].length-1;j>=1;j--){
if ((grid[i][j]!=0)&&(grid[i][j-1]==1)&&(grid[i-1][j]==1)) {
grid[i][j-1]=grid[i][j-1]*2;
}
}
}
//统计数据
int count=0;
for (int[] col : grid) {
for (int i : col) {
if (i==1) {
count++;
}
}
}
return count;
}

}

  学弟的用c++实现代码:

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
#include<iostream>
using namespace std;
int main()
{
//int grid[5][5] = { { 0, 0, 0, 0, 0 }, { 0, 1, 1, 0, 0 }, { 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } };
//int grid[4][4] = { { 0, 0, 0, 1 }, { 0, 0, 1, 1 }, { 0, 0, 0, 0 }, { 1, 0, 1, 1 } };
int grid[3][6] = { { 1, 0, 1, 0, 0, 0 }, { 0, 1, 0, 1, 1, 0 }, {0,0,1,1,0,1} };
int n = sizeof(grid) / sizeof(grid[0]);
int m = sizeof(grid[0]) / sizeof(grid[0][0]);
int i, j;
int count = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
if (grid[i][j] >= 1) //非0数值
{
if (grid[i][j] == 1)
count++;
if (i+1<n) //防止行数越界
grid[i + 1][j] *= 2;
if (j+1<m) //防止列数越界
grid[i][j + 1] *= 2;
}
}
}
//上面循环完成一遍即可解决3/4的情况,下面逆序便利,去除第四种情况的引起重复计算

//下面的二重循环处理的矩形为从grid[1][1]-grid[n][m]
//除去了第一行和第一列,想想为什么?
for (i = n - 1; i >= 1; i--)
{
for (j = m - 1; j >= 1; j--)
{
if (grid[i][j] >= 1)
if (grid[i - 1][j] == 1 && grid[i][j - 1] == 1)
count--;
}
}
for (int nn = 0; nn < n; nn++)
{
for (int mm = 0; mm < m; mm++)
cout << grid[nn][mm] << " ";
cout << endl;
}

cout << count << endl;
system("pause");
return 0;
}
文章目录
  1. 1. 01生长问题