共计 1310 个字符,预计需要花费 4 分钟才能阅读完成。
???? 题目
有一个 M*N 的矩阵,每个元素的值取自 [1,2,3…MN] 的汇合,且互不雷同。设计一个程序,找出相邻数字的最长门路。
相邻数字的定义:在矩阵中上下左右地位相邻,且值相差为 1 的数字
例如,下图矩阵中相邻数字的最长链接门路为 1-2-3-4
9 | 8 | 7 |
---|---|---|
5 | 6 | 4 |
1 | 2 | 3 |
???? 解析
dfs。并应用 visited 数组判断拜访与否来缩小不必要的循环。每次递归完结后,把以后最长的 list 赋值给 maxList。
如果某次失去的 list 长度 > 总数的一半,则它就是最长的门路。直径退出外层循环。在返回前对 list 进行排序。
public class Solution {ArrayList<Integer> maxList = new ArrayList<Integer>();
ArrayList<Integer> list;
boolean[][] visited;
int xx, yy;
int m, n;
int[] dx = {1,-1,0,0};
int[] dy = {0,0,1,-1};
public List<Integer> calcMaxLen(int[][] grid) {
if (grid == null || grid.length == 0
|| grid[0].length == 0) {return new ArrayList<>();
}
m = grid.length;
n = grid[0].length;
visited = new boolean[m][n];
out: for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j]) {list = new ArrayList<>();
dfs(grid, i, j);
if (list.size() > m*n/2) {
maxList = list;
break out;
}
maxList = maxList.size() > list.size()? maxList: list;
}
}
}
Collections.sort(maxList, new Comparator<Integer>() {public int compare(Integer o1, Integer o2) {return o1-o2;}
});
return maxList;
}
private void dfs(int[][] grid, int i, int j) {visited[i][j] = true;
list.add(grid[i][j]);
for (int d = 0; d < 4; d++) {xx = i + dx[d];
yy = j + dy[d];
if (xx >=0 && xx < m && yy >=0 && yy < n
&& !visited[xx][yy] && Math.abs(grid[i][j] - grid[xx][yy]) == 1) {dfs(grid, xx, yy);
}
}
}
public static void main(String[] args) {int[][] grid = {{9,8,7},
{5,6,4},
{1,2,3}};
Solution s = new Solution();
List<Integer> queue = s.calcMaxLen(grid);
System.out.println(queue);
}
}
???? 类似题目
695. 岛屿的最大面积
正文完