DFS和BFS讲解及Leetcode刷题小结（2）（JAVA）

上一篇文章解决了DFS的问题，这次来解决BFS的问题就简单多了

DFS实现重要依赖于堆栈/递归 ，较为简单的解决了如何遍历所有元素，以及寻求“终点”的问题。

但是，DFS虽然可以查找到到达路径，但是却找不到最短的路径，针对这一问题，给出了BFS(广度优先遍历)的算法。

首先，先给出BFS的基本过程：

与DFS不同的是，这次不再是每个分叉路口一个一个走了，而是全部，同时遍历，直到找到终点，所对应的“层数”便是最短路径所需要的步数，BFS像是在剥洋葱，一层一层的拨开，最后到达终点。

如何实现呢？

我们利用队列来实现BFS，伪代码如下：

int BFS(Node root, Node target) {
    Queue<Node> queue;  // 建立队列
    int step = 0;       // 建立行动步数
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // 记录此时的队列大小
        int size = queue.size();
        for (int i = 0; i < size; ++i) { //遍历队列中的元素，并将新元素加入到队列中
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                add next to queue;       //加入查找的方向
            }
            remove the first node from queue;
        }
    }
    return -1;          // 没有找到目标返回-1
}

 队列整体由两个循环构成：外层循环查看队列是否为空（为空表示元素已经遍历完毕），内层循环用于对当前节点的遍历，以及加入新节点，这里要注意：内层循环的次数size应为queue.size()赋予，而不能直接使用queue.size()，因为在内循环中会对队列进行操作，从而使得队列的长度不停变化。

内层循环代表着一层遍历“一层洋葱皮”，所以在外层遍历与内层遍历直接需要加入步数的记录，最后算法结束时对应步数就是最短路径。

下面来看几道例题：

#1  Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

仍然是那道找小岛的题目，下面来用BFS来进行求解：

public int numIslands(char[][] grid) {
        Queue<Integer> queue = new LinkedList<>();　　　　　　//建立队列
        int num = 0 ;
        for(int i = 0 ; i < grid.length ; i ++)
        {
            for(int j = 0 ; j < grid[0].length ; j ++)
            {
                if(grid[i][j] == '1')
                {
                    bfs(i,j,queue,grid) ; 　　　　//使用BFS来进行遍历
                    num ++ ;
                }
            }
        }
        return num ;
    }
    public void bfs(int p , int q , Queue<Integer> queue,char[][] grid)
    {
        int m = grid.length ;
        int n = grid[0].length ;
        int t = Math.max(m,n) ;　　　　　　　　　　//这里要使用一维队列来表示二维的数组，对原来的数组进行重新编码，为了避免译码的错误，
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//　这里求出二维数组行列的最大值
        int w = p*t + q ; //对数组进行编码
        queue.offer(w) ;
        grid[p][q] = '0' ;
        while(!queue.isEmpty())
        {
            int s = queue.poll() ;　　　　　　　　　　//由于所需要解决的问题不在于求最短路径，而在于遍历，使用没有记录步数
            int i = s/t ;　　　　//对行进行译码
            int j = s%t ;　　　　//对列进行译码
            if(i + 1 < m && grid[i+1][j] != '0')　　　　//上
            {
                queue.offer((i+1)*t + j);
                grid[i+1][j] = '0';
            }
            if(i - 1 >= 0  && grid[i-1][j] != '0')　　　　　　//下
            {
                queue.offer((i-1)*t + j);
                grid[i-1][j] = '0';
            }
            if(j - 1 >= 0  && grid[i][j-1] != '0')　　　　　　//左
            {
                queue.offer(i*t + j-1);
                grid[i][j-1] = '0';
            }
            if(j + 1 < n && grid[i][j+1] != '0')　　　　　　//右
            {
                queue.offer(i*t + j+1);
                grid[i][j+1] = '0';
            }
        }
    }
}

可以看到在遍历的问题上，BFS相对于DFS并没有什么优势，编写起来反而比较麻烦，因此，在遍历元素的问题上使用DFS比较好

#2 Open the Lock

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.

Example 4:

Input: deadends = ["0000"], target = "8888"
Output: -1

Note:

1. The length of deadends will be in the range [1, 500].
2. target will not be in the list deadends.
3. Every string in deadends and the string target will be a string of 4 digits from the 10,000 possibilities '0000' to '9999'.

 这道问题要求找到最短的搜索路径，显然使用BFS比较好，代码如下：

class Solution {
    public int openLock(String[] deadends, String target) {
        if(target == null) return -1 ;
        Queue<String> queue = new LinkedList<>();
        HashSet<String> set = new HashSet<String>(Arrays.asList(deadends)); 　　　　//建立hashset来存储deadends和访问过的节点
        int times = -1 ;
        queue.offer("0000") ;　　　　//将初始起点入队
        while(!queue.isEmpty())　　　　//开始遍历相邻的各个节点
        {
            times ++ ;
            int size = queue.size() ;
            for(int t = 0 ; t < size ; t ++)
            {
                String cur = queue.poll();
                if(set.contains(cur)) continue ;
                if(cur.compareTo(target) == 0) return times;
                set.add(cur) ;
                for(int i = 0 ; i < 4 ; i++)
                {
                    for(int j = -1 ; j < 2 ; j += 2)　　　　//4个数位进行+，- 1运算，共有8个方向
                    {
                        char[] temp = cur.toCharArray();
                        temp[i] = (char)((temp[i] - '0' + j + 10)%10 + '0'); // 将字符转化为数字
                        queue.offer(new String(temp));
                    }
                }
            }

        }
        return -1;
    }
}

#3  Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

代码如下：

class Solution {
    public int numSquares(int n) {
        Queue<Integer> queue = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();
        int res = 0 ;
        queue.offer(0) ;
        while(!queue.isEmpty())
        {
            res ++;
            int size = queue.size();
            for(int i = 0 ; i < size ; i ++)
            {
                int cur = queue.poll() ;
                int j = 1 ;
                while(cur + j*j <= n)　　　　　　//平方和小于目标数字的都是节点的相邻节点
                {
                    int temp = cur + j*j ;
                    if(temp == n) return res ;
                    j ++ ;
                    if(set.contains(temp)) continue ;
                    queue.offer(temp) ;
                    set.add(temp) ;　　　　　　//set用作记录路径
                }
            }
        }
        return -1 ;
    }
}