c******t
发帖数: 391 | 1 今天面试码工职位,被问到了一道coding题，说有一个m x n的二维矩阵Item[][]，每一
个元素都是一个Item类的object， 其中Item类定义如下:
public class Item{
public int x; //
public int y;
}
x和y分别是矩阵里的另一个元素的横纵坐标。实现一个函数，给定一个起始点的横纵坐
标startX 和startY，返回从起始点出发的traversal是否能cover矩阵里的每一个点。
我的想法是用一个hashSet，每初始化一个Item，都放入这个set， 直到遇到重复元素
或null为止，然后计算hashSet的size是否等于matrix的size。我写的基本算法:
boolean getCoverage(Item[][] items, int startX, int startY){
Item item = items[startX][starty];
HashSet- set = new HashSet
- ();
set.add(item);
while(item!=null&&!set.contains(item)){
item = items[item.x][item.y];
}
return set.size()==sizeOf(items); //sizeOf is to get m*n of matrix
}
不知道解法是否合理，请指教， 多谢！ |
D**f
发帖数: 439 | 2 不必hash，只要一个boolean的matrix来记录访问过的点就行了，外加一个计数器。 |
R********y
发帖数: 88 | 3 只要记录起点就可以了，假设matrix有n*m的节点，跳n*m次，如果过程中经过起点或者
最后没回起点，false，否则true
这个跟单链表跳的题目一模一样啊。
【在 D**f 的大作中提到】
: 不必hash，只要一个boolean的matrix来记录访问过的点就行了，外加一个计数器。
|
y*****n
发帖数: 243 | 4 矩阵里的节点可以不是循环的啊，cover所有节点的话不一定要返回到自己吧，最后一
个点可以指向任何地方。
【在 R********y 的大作中提到】
: 只要记录起点就可以了，假设matrix有n*m的节点，跳n*m次，如果过程中经过起点或者
: 最后没回起点，false，否则true
: 这个跟单链表跳的题目一模一样啊。
|
R********y
发帖数: 88 | 5 原帖里说了“返回从起始点出发的traversal是否能cover矩阵里的每一个点。”
【在 y*****n 的大作中提到】
: 矩阵里的节点可以不是循环的啊，cover所有节点的话不一定要返回到自己吧，最后一
: 个点可以指向任何地方。
|
g****y
发帖数: 240 | 6 他的意思是，traversal可能已经cover了所有的点，但是最后一个点并不指向起始点。
[(0,1)(1,0)]
[(1,1)(1,1)]
起始点是（0，0）
【在 R********y 的大作中提到】
: 原帖里说了“返回从起始点出发的traversal是否能cover矩阵里的每一个点。”
|
R********y
发帖数: 88 | 7 这种情况下根本就不存在“返回从起始点出发的traversal”。
【在 g****y 的大作中提到】
: 他的意思是，traversal可能已经cover了所有的点，但是最后一个点并不指向起始点。
: [(0,1)(1,0)]
: [(1,1)(1,1)]
: 起始点是（0，0）
|
g****y
发帖数: 240 | 8 “返回从起始点出发的traversal”是什么意思。。。。
【在 R********y 的大作中提到】
: 这种情况下根本就不存在“返回从起始点出发的traversal”。
|
|
y****e
发帖数: 20 | 9 “返回”这里要断句，是指这个函数返回。。。
【在 g****y 的大作中提到】
: “返回从起始点出发的traversal”是什么意思。。。。
|
g****y
发帖数: 240 | 10 我也是这样理解的。。。。
【在 y****e 的大作中提到】
: “返回”这里要断句，是指这个函数返回。。。
|
|
|
p*g
发帖数: 141 | 11 如果每个元素只有唯一的一个下一个元素 那题目挺容易吧
如果Item里面是 int x[], int y[],
好像就比较麻烦了
嘿嘿
。
【在 c******t 的大作中提到】
: 今天面试码工职位,被问到了一道coding题，说有一个m x n的二维矩阵Item[][]，每一
: 个元素都是一个Item类的object， 其中Item类定义如下:
: public class Item{
: public int x; //
: public int y;
: }
: x和y分别是矩阵里的另一个元素的横纵坐标。实现一个函数，给定一个起始点的横纵坐
: 标startX 和startY，返回从起始点出发的traversal是否能cover矩阵里的每一个点。
: 我的想法是用一个hashSet，每初始化一个Item，都放入这个set， 直到遇到重复元素
: 或null为止，然后计算hashSet的size是否等于matrix的size。我写的基本算法:
|
c******t
发帖数: 391 | 12 我是LZ， 你是对的，如果只剩最后一个节点的话，其值可以随意指向。
【在 y*****n 的大作中提到】
: 矩阵里的节点可以不是循环的啊，cover所有节点的话不一定要返回到自己吧，最后一
: 个点可以指向任何地方。
|
c******t
发帖数: 391 | 13 正解，我的描述太含糊了，sorry……
【在 y****e 的大作中提到】
: “返回”这里要断句，是指这个函数返回。。。
|
c******t
发帖数: 391 | 14 请问单链表跳的题目是啥？
【在 R********y 的大作中提到】
: 只要记录起点就可以了，假设matrix有n*m的节点，跳n*m次，如果过程中经过起点或者
: 最后没回起点，false，否则true
: 这个跟单链表跳的题目一模一样啊。
|
s*********6
发帖数: 261 | |
