w*****h
发帖数: 423 | 1 就是一个矩阵，求最大island的所有坐标
上个星期一个中国人电面的。我用stack来进行DFS，没有用递归。
https://coderpad.io/7DTXXJXJ
调试所有例子都通过了。
当时我用一维数字来代替矩阵坐标，他还似乎觉得不可能的样子，要我转换回来。
最后所有例子都通过，他还似乎觉得更多的例子要出错的样子。
希望有人能指出问题来，让我死个明白。
PS. 那里面的例子一开始只有前三行，后三行是后来做test的时候加上去的。 |
w*****h
发帖数: 423 | 2 有人不愿意进去看的话，我贴这
private static List findMaxIsLand(int[][] m)
{
List poslist = new ArrayList();
if(m.length == 0 || m[0].length == 0)return poslist;
int x = m.length, y = m[0].length;
boolean[][] visited = new boolean[x][y];
for(int i = 0; i < x; i++)
{
for(int j = 0; j < y; j++)
{
if(m[i][j] == 0 || visited[i][j])continue;
Stack stk = new Stack();
List pos = new ArrayList();
int p = i * y + j;
stk.push(p);
pos.add(p);
visited[i][j] = true;
while(!stk.empty())
{
int p1 = stk.pop();
ArrayList nbs = getNeighbors(p1, m);
for(int k = 0; k < nbs.size(); k++)
{
int nb = nbs.get(k);
if(m[nb/y][nb%y] == 0 || visited[nb/y][nb%y])
continue;
stk.push(nb);
pos.add(nb);
visited[nb/y][nb%y] = true;
}
}
if(pos.size() > poslist.size())poslist = pos;
}
}
return poslist;
}
private static ArrayList getNeighbors(int pos, int[][] m)
{
int i = pos / m[0].length, j = pos % m[0].length;
ArrayList nbs = new ArrayList();
if(i + 1 < m.length)nbs.add((i + 1) * m[0].length + j);
if(i - 1 >= 0)nbs.add((i - 1) * m[0].length + j);
if(j + 1 < m[0].length)nbs.add(i * m[0].length + j + 1);
if(j - 1 >= 0)nbs.add(i * m[0].length + j - 1);
return nbs;
}
|
l******s
发帖数: 3045 | 3 面试人脑子里想的是他自己用习惯的int[1][2]，你给的是int[2]，他脑子没转过弯来
。 |
f***k
发帖数: 147 | 4 不太明白最大island的定义。
是island所有数字之和最大就是最大island吗？
还是只算面积，任何数字都算一个单位。
那题目给的例子的答案应该不是3414吧？
【在 w*****h 的大作中提到】
: 就是一个矩阵，求最大island的所有坐标
: 上个星期一个中国人电面的。我用stack来进行DFS，没有用递归。
: https://coderpad.io/7DTXXJXJ
: 调试所有例子都通过了。
: 当时我用一维数字来代替矩阵坐标，他还似乎觉得不可能的样子，要我转换回来。
: 最后所有例子都通过，他还似乎觉得更多的例子要出错的样子。
: 希望有人能指出问题来，让我死个明白。
: PS. 那里面的例子一开始只有前三行，后三行是后来做test的时候加上去的。
|
w*****h
发帖数: 423 | 5 跟数字无关，一个岛就是所有联通的位置。
声明一下，那个例子矩阵开始只有前三行，后面是要加test case给加了另外三行上去
的。
【在 f***k 的大作中提到】
: 不太明白最大island的定义。
: 是island所有数字之和最大就是最大island吗？
: 还是只算面积，任何数字都算一个单位。
: 那题目给的例子的答案应该不是3414吧？
|
