b**********1
发帖数: 215 | 1 begin: 1 2 3 0 4
0 2 3 1 4
3 2 0 1 4
3 2 1 0 4
3 2 1 4 0
3 2 0 4 1
end: 3 2 0 4 1
Move(int[] begin, int[] end) {
}
begin 表示 5个停车位， 0是空的，要求每次只能和 空车位 进行交换，最后达到 最
终的结果end. 请教 如何 解答。 | j******3
发帖数: 16 | 2 乱序的麻烦一点，从最初的位置开始，0的位置最终是4，就和当前的4交换，4就不动了
，0再找，这次是1，0就和1交换，so on。
实际操作起来要建立两个hashmap,纪录最初和最终的index－value的mapping，并且是
根据index进行，而不是value，当然每次还是和0换。复杂度是(logn)吧 | b******b
发帖数: 713 | 3 dfs or bfs, only tricky part is to how to keep track which state you already
visited, one easy way is just concatenate it into string, e.g. start will
be "12304", and just put this into map so you know you already visited this
state.
【在 b**********1 的大作中提到】
: begin: 1 2 3 0 4
: 0 2 3 1 4
: 3 2 0 1 4
: 3 2 1 0 4
: 3 2 1 4 0
: 3 2 0 4 1
:
: end: 3 2 0 4 1
: Move(int[] begin, int[] end) {
: }
| s****3
发帖数: 270 | 4 每个停车位的数字initail都不同吗会有44044这样的case吗? | z****8
发帖数: 5023 | | w*****1
发帖数: 6807 | 6 正常思维应该就是这样了
【在 j******3 的大作中提到】
: 乱序的麻烦一点，从最初的位置开始，0的位置最终是4，就和当前的4交换，4就不动了
: ，0再找，这次是1，0就和1交换，so on。
: 实际操作起来要建立两个hashmap,纪录最初和最终的index－value的mapping，并且是
: 根据index进行，而不是value，当然每次还是和0换。复杂度是(logn)吧
| y********g
发帖数: 6 | 7 写了个O(n)的，有更优的解法么？
public void swap(int[] A, int i, int j, int[] map) {
map[A[i]] = j;
map[A[j]] = i;
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
public void move(int[] begin, int[] end) {
int n = end.length;
int[] map = new int[n]; // value->position in begin array
for(int i=0; i
map[begin[i]] = i;
}
for(int i=0; i
if(begin[i] == end[i]) continue;
swap(begin, i, map[0], map); // swap current number with empty
position
swap(begin, map[end[i]], map[0], map); // swap target number
with empty position
}
} |
|
