网站特效怎么做的/seo小白入门教学

笔试中的BFS问题-LeetCode1091

在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, ..., C_k 组成：相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角）
C_1 位于 (0, 0)（即，值为 grid[0][0]）
C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）
如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）
返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。示例 1：输入：[[0,1],[1,0]]输出：2示例 2：输入：[[0,0,0],[1,1,0],[1,1,0]]输出：4提示：1 <= grid.length == grid[0].length <= 100
grid[i][j] 为 0 或 1

这是一个8联通（米字形）问题。并且这是求解无权图的最短路径长度。同样，我们可以不单独建图，直接在二维矩阵中进行计算。

import java.util.LinkedList;
import java.util.Queue;public class Solution {private int[][] grid;private int R, C;private boolean[][] visited;private int[][] dist;private int[][] dirs = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}};public int shortestPathBinaryMatrix(int[][] grid) {if(grid.length==0 || grid[0][0] ==1)return -1;this.grid = grid;R = grid.length;C = grid[0].length;visited = new boolean[R][C];pre = new int[R][C];bfs(0, 0);if (!visited[R - 1][C - 1])return -1;elsereturn pre[R - 1][C - 1];}// 从左上角进行一次广度优先遍历 入队，需要把二维坐标转换成1维坐标private void bfs(int x, int y) {visited[x][y] = true;dist[x][y] = 1;int start = x * C + y;// 初始起点 将二维转换成1维Queue<Integer> queue = new LinkedList<>();queue.offer(start);while (!queue.isEmpty()) {int v = queue.poll();int vx = v / C;int vy = v % C;for (int d = 0; d < 8; d++) {int newx = vx + dirs[d][0];int newy = vy + dirs[d][1];// 需要满足3个条件 不越界 没访问 不阻塞  不越界需要首先判断if (inArea(newx, newy) && !visited[newx][newy] && grid[newx]																	[newy] == 0) {queue.offer(newx * C + newy);visited[newx][newy] = true;dist[newx][newy] = dist[vx][vy] + 1;}}}}//判断坐标是否越界private boolean inArea(int x, int y) {return x >= 0 && x < R && y >= 0 && y < C;}}

如果需要我们计算 具体的路径是谁，那么，把二维坐标转换成1维也是一个可行的方式。只需要新开一个pre数组。

图论建模核心：状态表达LeetCode752

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为  '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。示例 1:输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。
示例 4:输入: deadends = ["0000"], target = "8888"
输出：-1提示：死亡列表 deadends 的长度范围为 [1, 500]。
目标数字 target 不会在 deadends 之中。
每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。

需要注意的一点是：如果0000 就是死亡数字，那么无论如何都到达不了target。我们要做的就是从一个状态到达另一个状态。 也就是说图的每一个顶点不是一个数字，而是一个状态。题目中已经给出了装态是如何转移的。每一个数字都有+1 或者-1 两种状态， 当然0-1 会变成9 因为是反向旋转。

一个状态可以由不同的状态转移得到（0000->0100->1100）与（0000->1000->1100）。 并且某些状态是不可达的（死亡数字）。

整个问题就是从初始状态到终止状态 的一个最短路径长度。我们需要明确的就是整个图中，顶点是谁，边是谁。状态有多少可能性，那么图中就有多少顶点。

求无权图的最短路径。

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;public class LeetCode752 {//deadends 死亡字符串 target目标字符串public int openLock(String[] deadends, String target) {HashSet<String> dead = new HashSet<>();// 死亡字符串集合 方便查询for (String s : deadends)dead.add(s);if (target.equals("0000")) return 0;//如果起点就是终点 直接返回0if (dead.contains(target) || dead.contains("0000")) return -1; //目标和起点任何之一是死亡数字 都是不能达到的HashMap<String, Integer> visited = new HashMap<>();//visite 承担两个功能， 是否访问过，步长为多少visited.put("0000", 0);Queue<String> queue = new LinkedList<>();queue.offer("0000");while (!queue.isEmpty()) {String cur = queue.poll();char[] curChar = cur.toCharArray();for (int i = 0; i < 4; i++) {// 找出当前状态对应的 下一个8种状态char o = curChar[i];curChar[i] = Character.forDigit((curChar[i] - '0' + 1) % 10, 10);String newString = new String(curChar);if (!dead.contains(newString) && !visited.containsKey(newString)) {queue.offer(newString);visited.put(newString, visited.get(cur) + 1);if (newString.equals(target))return visited.get(newString);}curChar[i] = o;curChar[i] = Character.forDigit((curChar[i] - '0' + 9), 10);String newString2 = new String(curChar);if (!dead.contains(newString2) && !visited.containsKey(newString2)) {queue.offer(newString2);visited.put(newString2, visited.get(cur) + 1);if (newString2.equals(target))return visited.get(newString2);}curChar[i] = o; // 每次改变完之后，要把字符串还原回去，进行下一次改变}}return -1;}public  static  void  main(String[] args){String[] deads = {"0201","0101","0102","1212","2002"};String target ="0202" ;LeetCode752 leetCode752 =new LeetCode752();int res =   leetCode752.openLock(deads, target) ;System.out.println(res);}
}

智力问题-装水

我们有两个桶，大桶的容积是5升，小桶的容积是3升，我们可以把桶装满水，也可以把桶中的水倒掉（可以直接倒掉，也可以倒向另一个桶），问怎样可以最快由这两个桶 得到一桶4升的水。

如果我们把两个桶称为A、 B 的话，初始时，A和B都是空的，我们可以定义这种状态为0 0 ， 那么我们就是在寻找一种状态之间的转移，也就是通过不断的装水倒水，达到 4？ 或者？4 (当然，这里？4是不可能形成的，因为B桶最大容积只有3升，装不下4升的水） 即初始时，两个桶都是空的，最后两个桶中任意一个桶中的水是4升，另一个桶中的水任意。

每一种状态都可以看做是图中的一个顶点，状态之间的转移可以看做是图中的边。 我们第一个需要解决的问题就是如何表示一个顶点。 我们知道在普通的图中，我们都是用一个整数来表示一个顶点。但是现在有两个数子，A和B(准确说，是A桶中的水和B桶中的水) 我们是不是也可以用一个数字就表示AB呢？答案是肯定的，我们用一个2位数字即可。比如A桶中的水为3升 B桶中的水为1升，我们就用 31 来表示当前两个桶中水量的状态。 （x,y） -> x*10+y 这其实就状态压缩，包括之前的文章中，把二维矩阵用一维数组表示，也是一种状态压缩。

import java.util.Queue;
import java.util.LinkedList;
import java.util.List;
import java.util.Collections;
import java.util.ArrayList;public class WaterPuzzle {private boolean[] visited;private int[] pre;private int res;public WaterPuzzle() {int Start = 0;visited = new boolean[100]; // 最多有54中装态00--53pre = new int[100]; // 记录每一种状态的前一种状态 初始时为0Queue<Integer> queue = new LinkedList<>();queue.offer(Start);visited[Start] = true;while (!queue.isEmpty()) {int cur = queue.poll(); // 获取当前的状态int A = cur / 10, B = cur % 10;List<Integer> nexts = new ArrayList<>(); // 存放当前状态的下一种状态nexts.add(53); //  两个桶都装满nexts.add(50 + B);// A装满 B不动nexts.add(A * 10 + 3);// B装满 A不动nexts.add(A * 10); // B桶中的水倒掉nexts.add(B); // A桶中的水倒掉int x = Math.min(A, 3 - B); // 将A中的水倒入B 最多能倒入的数量nexts.add((A - x) * 10 + (B + x));int y = Math.min(B, 5 - A);// 将B中的水倒入A 最多能倒入的数量nexts.add((A + y) * 10 + (B - y));//进行广度优先遍历的具体过程for (int next : nexts) {if (!visited[next]) {pre[next] = cur;queue.offer(next);visited[next] = true;}if (next % 10 == 4 || next / 10 == 4) {res = next;return;}}}}public Iterable<Integer> iterable() {List<Integer> list = new ArrayList<>();int cur = res;while (cur != 0) {list.add(cur);cur = pre[cur];}list.add(0);Collections.reverse(list);return list;}public static void main(String[] args) {System.out.println((new WaterPuzzle()).iterable());}
}

hard难度-LeetCode773 滑动谜题

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。示例：输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，1 步完成
输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜板
输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]
输入：board = [[3,2,4],[1,5,0]]
输出：14
提示：board 是一个如上所述的 2 x 3 的数组.
board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.

这个问题也是，每一个面板代表了一种状态，通过移动数组中的数子，进行状态之间的转换。而一个面板有6个数字，如何用一个变量方便地保存这6个数字的信息，这里我们可以使用字符串，也就是把数组中的元素 从左到右，从上到下依次放入一个字符串中。这样，每一个字符串就代表了一种状态。

我们用一个 map<String , Integer> 存放状态 和步长，既可以起到这种状态之前是否访问过，有可以保存从初始状态到当前状态中间经过了多少步。

对于状态之间的转换，无非是我们找出 数字0 在二维数组中的位置，然后把0 和它的前后左右 4个方向交换，得到新的状态。这其中的具体过程是： 首先从队列中取出一种状态，由于是字符串表示，交换位置不方便，因此，可以先转换成二维数组，然后进行数据交换，将交换后得到的数组 再转换成字符串。如果这个字符串不在visited中的话，我们就可以进行进一步的操作。

这其中要注意一些常见的细节，比如，状态转移的时候，数组坐标的合法性。在四个方向搜索时，需要交换数组元素的位置而得到一种新的状态，但是交换是在原数组上（上一个状态）直接该变的，下一个放向的搜所还是基于上一个状态，因此，我们在记性一次交换，得到一个新的状态后，需要把这个交换再换回来。

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;public class LeetCode773 {// 题目已经给出了面板大小为2*3 装载012345 6个数字 最后123450 时，谜题才被解开private HashMap<String, Integer> visited;private int[][] dirs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};public int slidingPuzzle(int[][] board) {Queue<String> queue = new LinkedList<>();String Init = boardTostring(board); // 初始状态if(Init .equals("123450"))return 0 ;visited  = new HashMap<>( );visited.put(Init, 0);queue.offer(Init);while (!queue.isEmpty()) {String cur = queue.poll(); // 当前的状态int zero = 0;for (; zero < 6; zero++) // 找出0所在的位置 然后去和它的上下左右进行交换if (cur.charAt(zero) == '0')break;int x = zero / 3, y = zero % 3; // 将一维index 转换为二维坐标int[][] curboard = StringToboard(cur); // 将当前的字符串转换成二维数组for (int d = 0; d < 4; d++) { //对4个方向进行一次搜索int nextx = x + dirs[d][0];int nexty = y + dirs[d][1];if (inArea(nextx, nexty)) {swap(curboard, x, y, nextx, nexty);String swapboard = boardTostring(curboard);if (!visited.containsKey(swapboard)) {queue.offer(swapboard);visited.put(swapboard, visited.get(cur) + 1);if (swapboard.equals("123450")) { // 如果此时找到答案return visited.get(swapboard);}}swap(curboard, x, y, nextx, nexty); // 不要忘记还原}}}return -1;}//交换数组中两个元素的位置private void swap(int[][] board, int x1, int y1, int x2, int y2) {int temp;temp = board[x1][y1];board[x1][y1] = board[x2][y2];board[x2][y2] = temp;}//将面板中的数字转换成字符串private String boardTostring(int[][] board) { StringBuilder stringBuilder = new StringBuilder();for (int i = 0; i < 6; i++) { //将1维转换为2维int x = i / 3;int y = i % 3;stringBuilder.append(board[x][y]);}return stringBuilder.toString();}//将字符串状态转换成二维数组private int[][] StringToboard(String s) { int[][] res = new int[2][3];for (int i = 0; i < 6; i++) {int x = i / 3;int y = i % 3;res[x][y] = s.charAt(i) - '0';}return res;}private boolean inArea(int x, int y) {// 判断给定的坐标是否合法return x >= 0 && x < 2 && y >= 0 && y < 3;}}