b**********5
发帖数: 7881 | 1 Generate a random starting board for Bejeweled:
Constraints:
1) No 3-in-a-rows of a particular color (horizontally or vertically)
2) At least one valid starting move (i.e., can swap two cells to get a 3-in-
a-row).
int[][] generateRandomBoard(int NColors, int N, int M) |
b**********5
发帖数: 7881 | |
e**y
发帖数: 784 | 3 sigh
没玩过这个游戏，做起题来岂不是很吃亏
in-
【在 b**********5 的大作中提到】
: Generate a random starting board for Bejeweled:
: Constraints:
: 1) No 3-in-a-rows of a particular color (horizontally or vertically)
: 2) At least one valid starting move (i.e., can swap two cells to get a 3-in-
: a-row).
: int[][] generateRandomBoard(int NColors, int N, int M)
|
g**i
发帖数: 20 | 4 曾经gg也问的我这道题 记得是个android组的人问的
不过我的要求是在随机产生数这块的
LZ加油 |
b**********5
发帖数: 7881 | 5 哎， 我这是店面， 先上来聊背景， 然后问了一堆multithread的问题， 然后留了大
概20分钟叫我做这题。 然后我先按照sudoku的答案， 给他解答了不是random的， 满
足第一个要求的。 然后写完后， 我口头上聊了聊， 第二个要求， 怎么modify我的
code。 然后再简单说了说， 要random， 怎么modify我的code。。。
也不知道这样的店面，能不能有第二轮。。。
【在 g**i 的大作中提到】
: 曾经gg也问的我这道题 记得是个android组的人问的
: 不过我的要求是在随机产生数这块的
: LZ加油
|
l*****n
发帖数: 246 | 6 没什么思路，想这样做，不知道会不会被人鄙视：
public int[][] generateRandomBoard(int NColors, int N, int M) {
int[][] board = new int[N][M];
boolean isEnd = false;
while(!isEnd){
generateRandomBoard(board, NColors);
isEnd = checkBoard(board);
}
return board;
}
private void generateRandomBoard(int[][] board, int NColors) {
Random rm = new Random();
int N = board.length;
int M = board[0].length;
for(int i=0; i
for(int j=0; j
int temp = Math.abs(rm.nextInt()%NColors);
while((i>=2 && temp==board[i-1][j] && temp==board[i-2][j])||(j>=
2 && temp==board[i][j-1] && temp==board[i][j-2])){
temp=Math.abs(rm.nextInt()%NColors);
}
board[i][j] = temp;
}
}
}
private boolean checkBoard(int[][] board){
int N = board.length;
int M = board[0].length;
for(int i=0; i
for(int j=0; j
//check 合适的pattern，如果满足返回true；
}
}
return false;
}
合适的pattern比如说：
011
123
或者
01
01
13
就是check board[i][j]附近有没有在特定的两个位子跟他相等的。
只要NColor不是个特别小的数字，比如说2什么的，就能够基本上得到合适的board.如
果是2的话，第二个函数的while循环可能就停不下来了。。。。orz。。。
【在 b**********5 的大作中提到】
: 哎， 我这是店面， 先上来聊背景， 然后问了一堆multithread的问题， 然后留了大
: 概20分钟叫我做这题。 然后我先按照sudoku的答案， 给他解答了不是random的， 满
: 足第一个要求的。 然后写完后， 我口头上聊了聊， 第二个要求， 怎么modify我的
: code。 然后再简单说了说， 要random， 怎么modify我的code。。。
: 也不知道这样的店面，能不能有第二轮。。。
|
l*****n
发帖数: 246 | 7 二十分钟内要把code全部写完，考虑到所有的case然后bug free，好难。。。。 |
b***e
发帖数: 1419 | 8 这题要是我店面也做不出来。但是这题挺有意思的。我看分两步走：
第一步先把条件2满足了，也就是在一个随机的三连位置生成一个可调整的染色。
第二步从第一步结果的位置开始，从中间往两边，按对角线的方式扫描填色。按对角线
的原因是对角线上的染色互相无干涉。
in-
【在 b**********5 的大作中提到】
: Generate a random starting board for Bejeweled:
: Constraints:
: 1) No 3-in-a-rows of a particular color (horizontally or vertically)
: 2) At least one valid starting move (i.e., can swap two cells to get a 3-in-
: a-row).
: int[][] generateRandomBoard(int NColors, int N, int M)
|
w***w
发帖数: 84 | 9 先满足1 一个个字符的生成 需要算 marginal probability 就是count符合条件的串的
数目 条件2就用 check and rejection 就好 因为符合条件的可能性不小 |
b**********5
发帖数: 7881 | 10 我是先按照sudoku那么做， 然后要满足第二条件时， 就是在一开始随机的三联位置生
成一个可调整的。
哎， 谁说G家女马工去面， 就容易。。 我一个女马工， 面过G家几次， 店面都是这
么难， 记得上次是一个二维DP， 去onsite， 题目见都没见过， 听都没听说过。。。
【在 b***e 的大作中提到】
: 这题要是我店面也做不出来。但是这题挺有意思的。我看分两步走：
: 第一步先把条件2满足了，也就是在一个随机的三连位置生成一个可调整的染色。
: 第二步从第一步结果的位置开始，从中间往两边，按对角线的方式扫描填色。按对角线
: 的原因是对角线上的染色互相无干涉。
:
: in-
|
|
|
b**********5
发帖数: 7881 | 11 顺便问问， 店面后第二天没回音， 是不是就没戏了 |
B*******1
发帖数: 2454 | 12 什么变态。问这种问题
★ 发自iPhone App: ChineseWeb 1.0.2
【在 b**********5 的大作中提到】
: 我是先按照sudoku那么做， 然后要满足第二条件时， 就是在一开始随机的三联位置生
: 成一个可调整的。
: 哎， 谁说G家女马工去面， 就容易。。 我一个女马工， 面过G家几次， 店面都是这
: 么难， 记得上次是一个二维DP， 去onsite， 题目见都没见过， 听都没听说过。。。
|
h****e
发帖数: 2125 | 13 拍张你正在BBS发文的照片，P掉脸露乳沟，我们才知道你是不是女马工。
【在 b**********5 的大作中提到】
: 我是先按照sudoku那么做， 然后要满足第二条件时， 就是在一开始随机的三联位置生
: 成一个可调整的。
: 哎， 谁说G家女马工去面， 就容易。。 我一个女马工， 面过G家几次， 店面都是这
: 么难， 记得上次是一个二维DP， 去onsite， 题目见都没见过， 听都没听说过。。。
|
p*u
发帖数: 2454 | 14 lol 女马工 my ass...
【在 h****e 的大作中提到】
: 拍张你正在BBS发文的照片，P掉脸露乳沟，我们才知道你是不是女马工。
|
e********u
发帖数: 587 | 15 我觉得我会先在所有颜色中, random选四种颜色,凑成一个方块. 一个小方块每种颜色
最多出现一次, 然后搭积木一样搭出来,这样能保证不会出现三个同颜色连在一起. 解
决了第一个问题.
第二个问题我觉得有很多种解法,是我要尽快想出的话,我会随机选一个两个连色的, 然
后修改离它们一个位置但是在同一条线上的颜色. |
b******i
发帖数: 914 | 16 不知道这个随机是怎么定义？
完全随机？就是所有满足1)和2)的棋盘等概率的出现？
如果不要求这个，其实还是蛮简单的
in-
【在 b**********5 的大作中提到】
: Generate a random starting board for Bejeweled:
: Constraints:
: 1) No 3-in-a-rows of a particular color (horizontally or vertically)
: 2) At least one valid starting move (i.e., can swap two cells to get a 3-in-
: a-row).
: int[][] generateRandomBoard(int NColors, int N, int M)
|
b**********5
发帖数: 7881 | 17 如果不random， 你怎么解？ 我是就sudoku解， 然后在一开时的时候， 放一个（0，0
）（1，0）（1，1）同样颜色的
【在 b******i 的大作中提到】
: 不知道这个随机是怎么定义？
: 完全随机？就是所有满足1)和2)的棋盘等概率的出现？
: 如果不要求这个，其实还是蛮简单的
:
: in-
|
l*****8
发帖数: 1083 | 18 这道题要做到完全random挺难的
要么对每个生成的board检查一遍，看是否有valid move
要么随机生成valid move的坐标，类型，方向，颜色。。。再放到board中
，0
【在 b**********5 的大作中提到】
: 如果不random， 你怎么解？ 我是就sudoku解， 然后在一开时的时候， 放一个（0，0
: ）（1，0）（1，1）同样颜色的
|
b**********5
发帖数: 7881 | 19 G家是悲剧了好多次了。 每次都遇到这种难题。 有哪个真能人说说到底怎么做？
我就是用soduku II的方法做， DFS加isValid。 然后要满足第二个条件的话， 就一
开始在（0，0），（1，0), (1,1) set to the same color， 然后再DFS
能人说说这对不对啊？ 面试官也没说不对。 就让我写。。。 然后我问feedback，
recruiter说不能share feedback。。。。
random有怎么做呢？ |
h***k
发帖数: 161 | 20 G onsite碰到这道题。思路是首先满足第二个条件，就是先random一个valid move，然
后开始一边fill board一边查相邻是否valid，是用sudoku那题的backtracking。表示
完整写完code时间不够，只写了个主要的结构，查valid的helper method跟面试官讨论
了下如何实现就没有写出来。 |
|
|
b**********5
发帖数: 7881 | 21 ok. 那我不就是差不多这么做的么？ 我就是先弄一下valid move， 把（0，0），（1
，0）， （1，1） set成同样地， 然后我soduku， 然后我写了整个的soduku II， 就
是不知怎么random。。。 我写完后， 跟它说， 你要random， 就可以一开始set 那
个color的时候， random pick一下。。。。
我都写了， 为什么还要据我? 而且， 我写的时候， 他也没有提出什么不对的。。。
【在 h***k 的大作中提到】
: G onsite碰到这道题。思路是首先满足第二个条件，就是先random一个valid move，然
: 后开始一边fill board一边查相邻是否valid，是用sudoku那题的backtracking。表示
: 完整写完code时间不够，只写了个主要的结构，查valid的helper method跟面试官讨论
: 了下如何实现就没有写出来。
|
w***w
发帖数: 84 | 22 答案不是在这里了吗？概率问题无非就是数数 你先数所有满足条件1的排列数 不会就
从两种颜色 n=1,2,3 ... 数起 数到5 6啥的总可以看出点规律来吧
没折 暖男总喜欢套公式
【在 w***w 的大作中提到】
: 先满足1 一个个字符的生成 需要算 marginal probability 就是count符合条件的串的
: 数目 条件2就用 check and rejection 就好 因为符合条件的可能性不小
|
b**********5
发帖数: 7881 | 23 大姐， 我是做不出来了， 你给个code， 让我看看呗。 虽然我这店面， 已经被拒了
【在 w***w 的大作中提到】
: 答案不是在这里了吗？概率问题无非就是数数 你先数所有满足条件1的排列数 不会就
: 从两种颜色 n=1,2,3 ... 数起 数到5 6啥的总可以看出点规律来吧
: 没折 暖男总喜欢套公式
|
w***w
发帖数: 84 | |
b**********5
发帖数: 7881 | 25 我数不清啊。 你再说说清楚， 或者给个pseudo code看看。。。
【在 w***w 的大作中提到】
: 看了有啥用呢？还是先数数吧
|
r*******g
发帖数: 1335 | 26 我对这题很迷糊，怎么感觉不用backtracing
当你需要新插入一个颜色的时候，只需要比较已经有的两个方向就行了，一个是当前方
格左边，一个是当前方格上边，只要保证新插入的颜色和这两个邻接格子颜色不同，就
可以保证没有3个格子是一样颜色，而且也满足了随机性。
估计所谓的随机性是要求每个格子插入每个颜色的概率是相等吧，但是我一下子推导不
出来概率是相等的。 |
n*******s
发帖数: 17267 | 27 碰上这种题， 还跟他费什么话啊， 直接让他滚。
【在 b**********5 的大作中提到】
: 我数不清啊。 你再说说清楚， 或者给个pseudo code看看。。。
|
E******g
发帖数: 204 | 28 这个方法好！
【在 b***e 的大作中提到】
: 这题要是我店面也做不出来。但是这题挺有意思的。我看分两步走：
: 第一步先把条件2满足了，也就是在一个随机的三连位置生成一个可调整的染色。
: 第二步从第一步结果的位置开始，从中间往两边，按对角线的方式扫描填色。按对角线
: 的原因是对角线上的染色互相无干涉。
:
: in-
|
f***k
发帖数: 147 | 29 思路是对的，先生成一行或一列同颜色的；
然后随机填满剩下所有cell，color的int随机取，用类似sudoku的方法validate每一次
取。
最后把同颜色列任取一个cell和旁边置换。 |
l******s
发帖数: 3045 | 30 I'm thinking filling out rest of cells around the random valid move a better
idea. |
|
|
m*****n
发帖数: 204 | 31 如果我没理解错的话，你的代码生成的是一个固定的盘，而不是随机的。你说的换起始
颜色不改变盘的性质。
按六楼的思路写个满足第一条的解法，嘴上再把第二条扯一扯就行了。八楼是一个思路
。一个一个硬试也是个思路，谈谈复杂度啥的应该能混过去。
（1
【在 b**********5 的大作中提到】
: ok. 那我不就是差不多这么做的么？ 我就是先弄一下valid move， 把（0，0），（1
: ，0）， （1，1） set成同样地， 然后我soduku， 然后我写了整个的soduku II， 就
: 是不知怎么random。。。 我写完后， 跟它说， 你要random， 就可以一开始set 那
: 个color的时候， random pick一下。。。。
: 我都写了， 为什么还要据我? 而且， 我写的时候， 他也没有提出什么不对的。。。
|
