问一道面经题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道面经题

问一道面经题# JobHunting - 待字闺中

l*t2015-08-26 07:08

1 楼

(3) 一个 2 ＊4 的数组不重复包含1-8这些整数，有3种操作
a) 上下两个row交换.
b) 所有元素向右shift一个位置
c) 中间4个元素，顺时针旋转90度
现在随便给一个这样的数组，最小复员到1234，5678的步骤。
在一亩三分地上看到的，求指点...

b*b2015-08-26 07:08

2 楼

i will try the brute force way first:
1. create a hashmap, whose key is the sequence of the matrix, e.g. if the
array is: row0[1,2,3,4], row1[5,6,7,8], then key is [1,2,3,4,5,6,7,8], value
is the min step to revert it back to [1,2,3,4,5,6,7,8], put in [1,2,3,4,5,6
,7,8], 0 into the map.
2. write a recursive method,
int min(matrix)
{
if (map.contains(matrix.sequence)) return map.get(...);
opt1 = matrix.copy().swaprow();
int result = Integer.maxValue;;
if (!map.contains(op1))
{
map.put(opt1, min(opt1));
}
result = Math.min(result, 1 + map.get(opt1));

//do the same for rotate 90d, etc.
//forget you also need a visited set so if you see the sequence you
already tried, you can return immediately
}

【在 l*******t 的大作中提到】

: (3) 一个 2 ＊4 的数组不重复包含1-8这些整数，有3种操作
: a) 上下两个row交换.
: b) 所有元素向右shift一个位置
: c) 中间4个元素，顺时针旋转90度
: 现在随便给一个这样的数组，最小复员到1234，5678的步骤。
: 在一亩三分地上看到的，求指点...

s*c2015-08-26 07:08

3 楼

从输入数组开始，recursive在3种操作上一个个的试，直到出现12345678为止。
记录出现过的，防止死环

【在 l*******t 的大作中提到】

x*92015-08-26 07:08

4 楼

BFS

l*t2015-08-26 07:08

5 楼

value
,6

【在 b******b 的大作中提到】

: i will try the brute force way first:
: 1. create a hashmap, whose key is the sequence of the matrix, e.g. if the
: array is: row0[1,2,3,4], row1[5,6,7,8], then key is [1,2,3,4,5,6,7,8], value
: is the min step to revert it back to [1,2,3,4,5,6,7,8], put in [1,2,3,4,5,6
: ,7,8], 0 into the map.
: 2. write a recursive method,
: int min(matrix)
: {
: if (map.contains(matrix.sequence)) return map.get(...);
: opt1 = matrix.copy().swaprow();

l*t2015-08-26 07:08

6 楼

thanks!

【在 s***c 的大作中提到】

: 从输入数组开始，recursive在3种操作上一个个的试，直到出现12345678为止。
: 记录出现过的，防止死环