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 | |