一道G家onsite题# JobHunting - 待字闺中
t*y
1 楼
常见的俄罗斯方块，每一个图案都是由4个block组成，现在给定一个N表示N个block，
把所有有效的俄罗斯方块组合都输出出来，（有效的是指block是横着或者竖着连接的
，不是直接斜着连接）。数据结构什么的都自己定义。
把所有有效的俄罗斯方块组合都输出出来，（有效的是指block是横着或者竖着连接的
，不是直接斜着连接）。数据结构什么的都自己定义。
z*g
2 楼
不知道是我没看懂题目还是楼主题目太简单。貌似这个题目是个简单的数学问题啊？ N
/4 =M 可以算出一共有M个方块。每个方块一共有6个变化。所有的方块组合不就是6的M
次方个变化吗。
/4 =M 可以算出一共有M个方块。每个方块一共有6个变化。所有的方块组合不就是6的M
次方个变化吗。
t*y
3 楼
N=4的俄罗斯方块，一共有7种不同的pieces.任何一种pieces要是能从其他的piece旋转
的来就不能算不同的pieces。
的来就不能算不同的pieces。
r*7
4 楼
这不是典型的backtracking么
【在 t********y 的大作中提到】
: N=4的俄罗斯方块，一共有7种不同的pieces.任何一种pieces要是能从其他的piece旋转
: 的来就不能算不同的pieces。
【在 t********y 的大作中提到】
: N=4的俄罗斯方块，一共有7种不同的pieces.任何一种pieces要是能从其他的piece旋转
: 的来就不能算不同的pieces。
w*e
5 楼
是你没看懂题目，楼主的题肯定要求正好拼成n*n
N
的M
【在 z*******g 的大作中提到】
: 不知道是我没看懂题目还是楼主题目太简单。貌似这个题目是个简单的数学问题啊？ N
: /4 =M 可以算出一共有M个方块。每个方块一共有6个变化。所有的方块组合不就是6的M
: 次方个变化吗。
N
的M
【在 z*******g 的大作中提到】
: 不知道是我没看懂题目还是楼主题目太简单。貌似这个题目是个简单的数学问题啊？ N
: /4 =M 可以算出一共有M个方块。每个方块一共有6个变化。所有的方块组合不就是6的M
: 次方个变化吗。
h*c
6 楼
这个题出的有问题吧
n应该是个square number
n应该是个square number
t*y
7 楼
N没必要是square number， 比方说下面的funtion
vector findAll(int n).
vector里面的俄罗斯方块不能有重复。
vector findAll(int n).
vector里面的俄罗斯方块不能有重复。
M*u
8 楼
坐等大神解答
h*s
9 楼
既然不能重复 那n一定是4的倍数而且要小于等于28?
：N没必要是square number， 比方说下面的funtion
：vector<俄罗斯方块> findAll(int n).
：N没必要是square number， 比方说下面的funtion
：vector<俄罗斯方块> findAll(int n).
t*y
10 楼
n = 4 的请看图
我列出了n＝1，2，3，4 的pattern。
n = 1:
1)
*
n=2
2)
**
n = 3
1)
***
2)
*
**
3)
**
*
n=4
1)
****
2)
**
*
*
3)
*
*
**
4)
*
**
*
5)
*
**
*
6)
*
**
*
7)
**
**
【在 h***s 的大作中提到】
: 既然不能重复 那n一定是4的倍数而且要小于等于28?
:
: ：N没必要是square number， 比方说下面的funtion
: ：vector<俄罗斯方块> findAll(int n).
我列出了n＝1，2，3，4 的pattern。
n = 1:
1)
*
n=2
2)
**
n = 3
1)
***
2)
*
**
3)
**
*
n=4
1)
****
2)
**
*
*
3)
*
*
**
4)
*
**
*
5)
*
**
*
6)
*
**
*
7)
**
**
【在 h***s 的大作中提到】
: 既然不能重复 那n一定是4的倍数而且要小于等于28?
:
: ：N没必要是square number， 比方说下面的funtion
: ：vector<俄罗斯方块> findAll(int n).
h*s
11 楼
哦，明白题意了，列出用N个block可以组成的所有unique的形状，block和block只能横
竖连接，传统的俄罗斯方块是N是4的case。
竖连接，传统的俄罗斯方块是N是4的case。
t*y
12 楼
顶一下
w*a
13 楼
我想问一下如何处理重复。
比如N=2的时候，回溯做有四种情况
第2种
12
第2种
21
第3种
1
2
第4种
2
1
实际上12和21是同一种形状。
请问大牛这题如何干掉重复形状
比如N=2的时候，回溯做有四种情况
第2种
12
第2种
21
第3种
1
2
第4种
2
1
实际上12和21是同一种形状。
请问大牛这题如何干掉重复形状
t*y
14 楼
坐等大神解答
p*a
15 楼
看不懂
如果
1 2
3 4
和
1 2
3 4
算两种
为什么
1
2 4
3
1
4 2
3
不算？
【在 t********y 的大作中提到】
: n = 4 的请看图
: 我列出了n＝1，2，3，4 的pattern。
: n = 1:
: 1)
: *
: n=2
: 2)
: **
: n = 3
: 1)
如果
1 2
3 4
和
1 2
3 4
算两种
为什么
1
2 4
3
1
4 2
3
不算？
【在 t********y 的大作中提到】
: n = 4 的请看图
: 我列出了n＝1，2，3，4 的pattern。
: n = 1:
: 1)
: *
: n=2
: 2)
: **
: n = 3
: 1)
y*i
16 楼
睡前XJB写两句。。
你需要这么几个helper function:
void PushToCornor(Block) //把一个俄罗斯方块推向一个NXN grid的某个角落
void Rotate(Block, direction) //向direction rotate你的方块
attach_another_square_to_this_square() //这个没想清楚signature，意思就是拿到
一个square，给他attach一个legitimate neighboring square
然后递归解：
//以下都是秀逗扣的：
vector generateBlocks(target, current, vector & current_blocks
) {
if (current == target) {
return current_blocks;
}
for(auto block: blocks) {
for(auto square: block) {
square.attach_another_square_to_this_square();
for all 3 rotation directions {
Rotate(block, direction)
PushToCorner(block)
if (find(current_blocks.begin(), cucrent_blocks.end(), block
) == current_blocks.end()) {
current_blocks.push_back(block);
generateBlocks(target, current+1, current_blocks);
current_blocks.pop_back();
}
}
}
}
}
大概就是这么个意思吧。。。直接在这个框里写代码好麻烦。。。
你需要这么几个helper function:
void PushToCornor(Block) //把一个俄罗斯方块推向一个NXN grid的某个角落
void Rotate(Block, direction) //向direction rotate你的方块
attach_another_square_to_this_square() //这个没想清楚signature，意思就是拿到
一个square，给他attach一个legitimate neighboring square
然后递归解：
//以下都是秀逗扣的：
vector
) {
if (current == target) {
return current_blocks;
}
for(auto block: blocks) {
for(auto square: block) {
square.attach_another_square_to_this_square();
for all 3 rotation directions {
Rotate(block, direction)
PushToCorner(block)
if (find(current_blocks.begin(), cucrent_blocks.end(), block
) == current_blocks.end()) {
current_blocks.push_back(block);
generateBlocks(target, current+1, current_blocks);
current_blocks.pop_back();
}
}
}
}
}
大概就是这么个意思吧。。。直接在这个框里写代码好麻烦。。。
相关阅读
请教给位面过google的大神明年4月再申请H1B是不是生效期就是2013年10月1日了看来做IT还真是让人瞧不起?有谁知道pittsburgh的cogent infotech公司Bloomberg考Bloomfilter么？几个湾区工作机会，年底机会不多，大家抓紧。How important is "Senior Engineer" title vs "Engineer".最近没什么BL的面经？为什么L的onsite一天要见10个人呢？大家找research的工作一般在哪些网站？面试被问到，本科基础课学的东西，想不起来了怎么办？seniorvresearch engineer multiple openings @ south bay请教工资negotiation湾区105000base+15%bonus属于哪一档？JOB：hedge fund IT工作（CT）--支持H1B (转载)求助工作签证问题问一个recruiter的email问题。Amazon电面什么时候开始negociate salaryOPT vs. H1B