目录

1 785号问题，判断二分图

1.1 题目

1.2 代码示例

2 岛屿最大面积问题

2.1 问题

2.2 技巧分析

2.3 代码实现

---

1 785号问题，判断二分图

1.1 题目

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

示例 1: 输入: [[1,3], [0,2], [1,3], [0,2]] 输出: true 解释:  无向图如下: 0----1 |    | |    | 3----2 我们可以将节点分成两组: {0, 2} 和 {1, 3}。示例 2: 输入: [[1,2,3], [0,2], [0,1,3], [0,2]] 输出: false 解释:  无向图如下: 0----1 | \  | |  \ | 3----2 我们不能将节点分割成两个独立的子集。

注意：

graph 的长度范围为 [1, 100]。graph[i] 中的元素的范围为 [0, graph.length - 1]。graph[i] 不会包含 i 或者有重复的值。图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

1.2 代码示例

基于深度优先遍历的实现

public class Solution { bool[] visited; int[][] graph; int[] colors; public bool IsBipartite(int[][] graph) { this.graph = graph; int V = graph.GetLength(0); visited = new bool[V]; colors = new int[V]; for(int i = 0; i < V; i++) { visited[i] = false; colors[i] = 0; } for(int v = 0; v < V; v++) { if(!visited[v]) { if(!dfs(v, 0)) { return false; } } } return true; } public bool dfs(int v, int color) { colors[v] = color; visited[v] = true; foreach(int w in graph[v]) { if(!visited[w]) { if(!dfs(w, 1-color)) { return false; } }else if(colors[v] == colors[w]) { return false; } } return true; } }

2 岛屿最大面积问题

2.1 问题

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],  [0,0,0,0,0,0,0,1,1,1,0,0,0],  [0,1,1,0,1,0,0,0,0,0,0,0,0],  [0,1,0,0,1,1,0,0,1,0,1,0,0],  [0,1,0,0,1,1,0,0,1,1,1,0,0],  [0,0,0,0,0,0,0,0,0,0,1,0,0],  [0,0,0,0,0,0,0,1,1,1,0,0,0],  [0,0,0,0,0,0,0,1,1,0,0,0,0]] 对于上面这个给定矩阵应返回 6。

注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

 

示例 2:

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50

2.2 技巧分析

分析：二维到一维、一维到二维的快速转换

四联通：

2.3 代码实现

public class Solution { private int R, C; private int[,] grid; private HashSet<int>[] g; private bool[] visited; int[,] dirs = new int[4, 2]; public int MaxAreaOfIsland(int[,] grid) { dirs[0, 0] = -1; dirs[0, 1] = 0; dirs[1, 0] = 0; dirs[1, 1] = 1; dirs[2, 0] = 1; dirs[2, 1] = 0; dirs[3, 0] = 0; dirs[3, 1] = -1; if (grid == null) { return 0; } R = grid.GetLength(0); if (R == 0) { return 0; } C = grid.GetLength(1); if (C == 0) { return 0; } this.grid = grid; g = ConstructGraph(); int res = 0; visited = new bool[g.Length]; for (int v = 0; v < g.Length; v++) { int x = v / C; int y = v % C; //如果没有被访问，且为陆地的话，找到了新的岛屿 if (!visited[v] && grid[x, y] == 1) { res = Math.Max(res, dfs(v)); } } return res; } //返回联通分量中节点的个数 public int dfs(int v) { visited[v] = true; int res = 1; foreach (int w in g[v]) { if (!visited[w]) { res += dfs(w); } } return res; } private HashSet<int>[] ConstructGraph() { HashSet<int>[] GG = new HashSet<int>[R * C]; for (int i = 0; i < GG.Length; i++) { GG[i] = new HashSet<int>(); } for (int v = 0; v < GG.Length; v++) { int x = v / C; int y = v % C; if (grid[x, y] == 1) { for (int d = 0; d < 4; d++) { int nextx = x + dirs[d, 0]; int nexty = y + dirs[d, 1]; if (inArea(nextx, nexty) && grid[nextx, nexty] == 1) { int next = nextx * C + nexty; GG[v].Add(next); GG[next].Add(v); } } } } return GG; } private bool inArea(int x, int y) { return x >= 0 && x < R && y >= 0 && y < C; } }