如何用 BFS 算法秒杀各种智力题 :: labuladong的算法小抄 #1080
Replies: 20 comments 5 replies
-
这题看了解法有点类似 752. Open the Lock |
Beta Was this translation helpful? Give feedback.
-
如752打开锁的那一题的双端回溯解法 class Solution {
public int slidingPuzzle(int[][] board) {
int m = board.length;
int n = board[0].length;
StringBuilder sb = new StringBuilder();
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
sb.append(board[i][j]);
}
}
String start = sb.toString();
String target = "123450";
//0 在各个位置的相邻节点的索引
int[][] neighbor = new int[][]{
{1,3},
{0,4,2},
{1,5},
{0,4},
{3,1,5},
{4,2}
};
Queue<String> q1 = new LinkedList<>();
Queue<String> q2 = new LinkedList<>();
//存储相同字符串是否被拜访过
HashSet<String> visited = new HashSet<>();
q1.offer(start);
q2.offer(target);
visited.add(start);
int step = 0;
while(!q1.isEmpty()&&!q2.isEmpty()){
Queue<String> temp = new LinkedList<>();
int size = q1.size();
for(int i = 0; i<size;i++){
String cur = q1.poll();
if(q2.contains(cur)){
return step;
}
visited.add(cur);
int index = 0;
for(;cur.charAt(index)!='0';index++);//找到0的索引位置
//0 和 其相邻的数字交换位置
for(int adj : neighbor[index]){
String new_board = swap(cur.toCharArray(),adj,index);
if(!visited.contains(new_board)){
temp.offer(new_board);
}
}
}
step++;
q1 = q2;
q2 = temp;
}
return -1;
}
private String swap(char[] chars,int i , int j ){
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
return new String(chars);
}
} |
Beta Was this translation helpful? Give feedback.
-
打卡,感谢楼主! |
Beta Was this translation helpful? Give feedback.
-
比楼主写的复杂点,但是应该更清晰直观吧? class Solution {
public int slidingPuzzle(int[][] board) {
LinkedList<String> pass = new LinkedList<>();
//记录个可能的字符串,以及对应 0 的位置
HashMap<String, Integer> visited = new HashMap<>();
StringBuilder sb = new StringBuilder();
//记录 0 在 一维字符串中的位置
int index = 0;
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(board[i][j] == 0) {
//初始位置
index = i * 3 + j;
}
sb.append(board[i][j]);
}
}
String str = sb.toString();
pass.add(str);
visited.put(str, index);
String target = "123450";
//步数
int step = 0;
int size;
//中间变量
char[] chars;
String s;
int idx;
while(!pass.isEmpty()) {
size = pass.size();
for(int i = 0; i < size; i++) {
str = pass.poll();
//最小步数
if(str.equals(target)) {
return step;
}
//当前字符串中 0 的位置
index = visited.get(str);
chars = str.toCharArray();
//向上移动,返回移动之后 0 的位置
idx = up(chars, index);
//移动成功,才进行后续操作
if(idx != index) {
s = new String(chars);
if(!visited.containsKey(s)) {
pass.add(s);
visited.put(s, idx);
}
}
chars = str.toCharArray();
//向下移动,返回移动之后 0 的位置
idx = down(chars, index);
if(idx != index) {
s = new String(chars);
if(!visited.containsKey(s)) {
pass.add(s);
visited.put(s, idx);
}
}
chars = str.toCharArray();
//向左移动,返回移动之后 0 的位置
idx = left(chars, index);
if(idx != index) {
s = new String(chars);
if(!visited.containsKey(s)) {
pass.add(s);
visited.put(s, idx);
}
}
chars = str.toCharArray();
//向右移动,返回移动之后 0 的位置
idx = right(chars, index);
if(idx != index) {
s = new String(chars);
if(!visited.containsKey(s)) {
pass.add(s);
visited.put(s, idx);
}
}
}
//增加步数
step++;
}
return -1;
}
//上
public int up(char[] strs, int index) {
if(index < 3) {
return index;
}
char c = strs[index - 3];
strs[index - 3] = strs[index];
strs[index] = c;
return index - 3;
}
//下
public int down(char[] strs, int index) {
if(index > 2) {
return index;
}
char c = strs[index + 3];
strs[index + 3] = strs[index];
strs[index] = c;
return index + 3;
}
//左
public int left(char[] strs, int index) {
if(index == 0 || index == 3) {
return index;
}
char c = strs[index - 1];
strs[index - 1] = strs[index];
strs[index] = c;
return index - 1;
}
//右
public int right(char[] strs, int index) {
if(index == 2 || index == 5) {
return index;
}
char c = strs[index + 1];
strs[index + 1] = strs[index];
strs[index] = c;
return index + 1;
}
} |
Beta Was this translation helpful? Give feedback.
-
@MarlonDML 朋友,你的实现代码的维护性如何?我有点审美疲劳,感觉你把简单事情复杂化了。 |
Beta Was this translation helpful? Give feedback.
-
牛皮牛皮,会不会有让你记录这个最短操作次数具体怎么操作的这种题 |
Beta Was this translation helpful? Give feedback.
-
@LebronHarden1 这也很好解决,自己包一个 |
Beta Was this translation helpful? Give feedback.
-
@labuladong 恍然大悟 |
Beta Was this translation helpful? Give feedback.
-
typescript跑不动.. OOM了 |
Beta Was this translation helpful? Give feedback.
-
我想问下,“邻居”数组里的元素顺序应该不重要,为啥我的顺序不对,导致结果不对呢? |
Beta Was this translation helpful? Give feedback.
-
@freeduser 你第三个数组错了,是{1, 5} 不是{2, 5} |
Beta Was this translation helpful? Give feedback.
-
请问楼主 为啥要把2维数组压缩为一维数组啊 |
Beta Was this translation helpful? Give feedback.
-
ruby版 # @param {Integer[][]} board
# @return {Integer}
def sliding_puzzle(board)
require 'set'
neighbour = [[1,3],[0,4,2],[1,5],[0,4],[3,1,5],[4,2]]
start = board.flatten.join
target = "123450"
queue = []
visited = Set.new
queue.push start
visited.add start
step = 0
until queue.empty? do
sz = queue.size
sz.times do
cur = queue.shift
return step if cur == target
idx = cur.index '0'
neighbour[idx].each do |nb|
new_board = swap cur, nb, idx
unless visited.include? new_board
queue.push new_board
visited.add new_board
end
end
end
step += 1
end
-1
end
def swap board, i, j
board_copy = board.dup
board_copy[i], board_copy[j] = board_copy[j], board_copy[i]
board_copy
end |
Beta Was this translation helpful? Give feedback.
-
2X3的数组还是比较小的,直接用数组交换数据,python实现: |
Beta Was this translation helpful? Give feedback.
-
想请教一下,将二维数组展平成一维数组是不是方便在后面 BFS 中更快地与 target 做对比,更快比较两者是否相等? |
Beta Was this translation helpful? Give feedback.
-
厉害, 写完之后 居然打败了 100% 的python 解法 |
Beta Was this translation helpful? Give feedback.
-
请问这个解法的时间和空间复杂度分别是多少呀? |
Beta Was this translation helpful? Give feedback.
-
用两维实现的代码。没有转换2D to 1D from typing import List
from collections import deque
class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
target = [[1, 2, 3], [4, 5, 0]]
m, n = len(board), len(board[0])
zero_pos = self.findZero(board, m, n)
q = deque([(board, zero_pos)])
visited = {str(board)}
moves = 0
dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)] # left, right, up, down
while q:
for i in range(len(q)):
board, zero_pos = q.popleft()
if board == target:
return moves
for dir in dirs:
i, j = zero_pos[0], zero_pos[1]
new_i, new_j = i + dir[0], j + dir[1]
new_zero_pos = (new_i, new_j)
if 0 <= new_i < m and 0 <= new_j < n:
new_board = [row[:] for row in board]
new_board[i][j], new_board[new_i][new_j] = new_board[new_i][new_j], new_board[i][j]
if str(new_board) not in visited:
q.append((new_board, new_zero_pos))
visited.add(str(new_board))
moves += 1
return -1
def findZero(self, board, m, n):
for i in range(m):
for j in range(n):
if board[i][j] == 0:
return (i, j)
board = [[4, 1, 2], [5, 0, 3]]
print('minMoves :', Solution().slidingPuzzle(board)) |
Beta Was this translation helpful? Give feedback.
-
文章链接点这里:如何用 BFS 算法秒杀各种智力题
评论礼仪 见这里,违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions