fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
如何用 BFS 算法秒杀各种智力题 :: labuladong的算法小抄
如752打开锁的那一题的双端回溯解法 需要注意：双端回溯需要在内部检查 q2 中是否存在 cur，意思就是从前往后 和从后往前碰到一起了，就是找到了，既需要返回step了，这个思路前文中提到过。
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);
}
}
比楼主写的复杂点，但是应该更清晰直观吧？
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;
}
}
我想问下，“邻居”数组里的元素顺序应该不重要，为啥我的顺序不对，导致结果不对呢？ {1,3}, {0,4,2}, {2,5}, {4,0}, {3,5,1}, {4,2} 这样不行
