【九章算法基础班】图与搜索

outline

• graph

  • Clone Graph
  • Topological Sorting

• Search

  • DFS

  • BFS:（O(m+n)m为边树，n为点数)

    • 遍历图

      树的BFS需要用队列，在图中除了要用队列还需要用到hash表，用来存储节点是否被访问过

      BFS还可以用于求深度，最短路径

    • 简单图求最短路径

    • 拓扑排序

BFS例题

1. Clone Graph

题目

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:

Nodes are labeled uniquely.

We use #as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

>        1
>       / \
>      /   \
>     0 --- 2
>          / \
>          \_/
>

给定图中的一个节点，克隆整个图

分析

考点：

1. 从一个点出发，把整张图的所有节点找到（BFS）nodes
2. 获得nodes之后复制所有的点，将新老节点建立映射关系，存入hashmap中
3. 根据老节点之间的关系和新老节点的映射关系，复制所有的边
4. 最后返回给定的node对应的新节点

还可以用DFS：

递归调用复制节点和邻居关系。

DFS的输入是旧结点，返回值是新节点。

代码

BFS:

import java.util.*;

public class GraphClone {
     class UndirectedGraphNode {
         int label;
         List<UndirectedGraphNode> neighbors;
         UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
     }
     HashMap<UndirectedGraphNode,UndirectedGraphNode> nodeMap = new HashMap<>();//用于存储新旧节点映射关系
     List<UndirectedGraphNode> oldNodes = new ArrayList<>();//旧结点
     List<UndirectedGraphNode> newNodes = new ArrayList<>();//新节点

    //bfs获取图中所有的点
    public void bfs(UndirectedGraphNode node){
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        HashSet<UndirectedGraphNode> set = new HashSet<>();
        queue.add(node);
        set.add(node);
        //BFS
        while(!queue.isEmpty()){
            UndirectedGraphNode temp = queue.poll();
            UndirectedGraphNode newNode = new UndirectedGraphNode(temp.label);
            oldNodes.add(temp);//加入旧点集
            newNodes.add(newNode);//加入新点集
            nodeMap.put(temp,newNode);//加入mapping

            //遍历当前节点的所有邻居
            for(UndirectedGraphNode neighbor : temp.neighbors){
                //如果已经加入结合了，跳过
                if(set.contains(neighbor)){
                    continue;
                }
                //如果还未加入
                queue.add(neighbor);
                set.add(neighbor);
            }
        }
    }


    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null){
            return null;
        }
        //获取图中所有的节点
        bfs(node);
        //复制所有的边
        for(UndirectedGraphNode oldNode : oldNodes){
            for(UndirectedGraphNode neighbor : oldNode.neighbors){
                nodeMap.get(oldNode).neighbors.add(nodeMap.get(neighbor));
            }
        }
        //返回node对应的新节点
        return nodeMap.get(node);
    }
}

DFS：

public UndirectedGraphNode dfs(UndirectedGraphNode node,HashMap<UndirectedGraphNode,UndirectedGraphNode> map){
    if(map.containsKey(node)){
        return map.get(node);
    }
    //新建节点
    UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
    map.put(node,newNode);
    //遍历邻居节点
    for(UndirectedGraphNode neighbor : node.neighbors){
        newNode.neighbors.add(dfs(neighbor,map));
    }
    return newNode;
}

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    HashMap<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<>();
    if(node == null){
        return null;
    }
    return dfs(node,map);
}

2. 拓扑排序

下面这个图假设是一种上课顺序，比如上1之前必须上0。求这个图的任意一个拓扑排序（按照这个顺序上课则可以上完所有课）

拓扑排序很好的参考资料：Topological Sort of a Graph

拓扑排序的思路如下：

1. 统计当前入度为0的点，加入队列
2. 将当前所有入度为0的点删掉，并将这些点的下一点的连线删掉，将其下一个节点的入度减1
3. 重复1和2，直到所有的点都被删掉
4. 如果不能拓扑排序说明图中一定有环

Topological Sorting

Given an directed graph, a topological order of the graph nodes is defined as follow:

• For each directed edge A -> B in graph, A must before B in the order list.
• The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

Example

For graph as follow:

The topological order can be:

> [0, 1, 2, 3, 4, 5]
> [0, 2, 3, 1, 5, 4]
> ...
>

核心就是根据拓扑排序给出一条合理的路径，能够遍历图中所有的点，且不违背箭头顺序

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    // write your code here
    HashMap<DirectedGraphNode,Integer> degreeIn = new HashMap<>();
    Queue<DirectedGraphNode> queue = new LinkedList<>();
    ArrayList<DirectedGraphNode> results = new ArrayList<>();

    //计算入度出度
    for(DirectedGraphNode nodeFrom : graph) {
        for (DirectedGraphNode nodeEnd : nodeFrom.neighbors) {
            //计算NodeEnd入度
            if (!degreeIn.containsKey(nodeEnd)) {
                degreeIn.put(nodeFrom, 1);
            } else {
                degreeIn.put(nodeEnd, degreeIn.get(nodeEnd) + 1);
            }
        }
    }

    //bfs
    //queue.add(graph.get(0));
    for(DirectedGraphNode node : graph){
        if(!degreeIn.containsKey(node)){
            queue.offer(node);
            results.add(node);
        }
    }
    while(!queue.isEmpty()){
        DirectedGraphNode node = queue.poll();
        //results.add(node);
        for(DirectedGraphNode neighbor : node.neighbors){
            degreeIn.put(neighbor,degreeIn.get(neighbor)-1);
            if(degreeIn.get(neighbor) == 0){
                queue.add(neighbor);
                results.add(neighbor);
                //numNodes--;
            }
        }
    }
    return results;
 }

Course Schedule

题目

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

> 2, [[1,0]]
>

>

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

> 2, [[1,0],[0,1]]
>

>

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

给定课程门数，和课程之间的依赖关系，判断是否可以无冲突完成课程。

分析

BFS和DFS都可以做

BFS：

拓扑排序的思想，如果最后所有的点都被访问到了，就是可以的，反之不可以。

DFS：

用DFS的核心思想就是遇到某条路径上有环就可以返回false，不用继续判断了。所以需要用一个visited数组来保存节点的访问状态。当沿着某一条路径前进时遇到之前已经访问过的节点，就返回false，如果一直没有出现环则在最后返回true。

代码

BFS:

import java.util.*;
public class CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] classDegreeIn = new int[numCourses];//记录入度
        int[] classDegreeOut = new int[numCourses];//记录出度
        HashMap<Integer,List<Integer>> edges = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        int counter = 0;
        //遍历所有的点记录入度和出度,加入边集和
        for(int i = 0; i < prerequisites.length;i++){
            int edgeFrom = prerequisites[i][0];
            int edgeEnd = prerequisites[i][1];
            classDegreeIn[edgeEnd]++;
            classDegreeOut[edgeFrom]++;
            List<Integer> listTemp = edges.getOrDefault(edgeFrom,new ArrayList<>());
            listTemp.add(edgeEnd);
            edges.put(edgeFrom,listTemp);
        }

        //寻找入度为0的点入栈
        for(int i = 0 ; i < numCourses;i++){
            if(classDegreeIn[i] == 0){
                queue.add(i);
                counter++;
                boolean[] hasVisited = new boolean[numCourses];
                hasVisited[i] = true;

            }
        }

        //bfs
        while(!queue.isEmpty()){
            int classID = queue.poll();
            if(edges.getOrDefault(classID,new ArrayList<>()).size() == 0){
                continue;
            }
            //遍历classID的所有邻居，将其入度-1
            for(Integer neighbor : edges.get(classID)){
                classDegreeIn[neighbor]--;
                //如果入度为0,入栈
                if(classDegreeIn[neighbor] == 0){
                    queue.add(neighbor);
                    counter++;
                }
            }
        }
        return counter == numCourses;
    }
}

DFS：

class Solution {
    boolean[] used;
    public boolean dfs(boolean[] used,HashMap<Integer, List<Integer>> edges,Integer node) {
        if(used[node]){
            return false;
        }
        if(edges.containsKey(node)) {
            used[node] = true;
            for(Integer next: edges.get(node)){
                if(!dfs(used,edges,next)){
                    return false;
                }
            }
            used[node] = false;
        }
        return true;
    }


    public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> edges = new HashMap<>();
        used = new boolean[numCourses];

        //遍历所有的点记录入度和出度,加入边集和
        for (int i = 0; i < prerequisites.length; i++) {
            int edgeFrom = prerequisites[i][0];
            int edgeEnd = prerequisites[i][1];
            List<Integer> listTemp = edges.getOrDefault(edgeFrom, new ArrayList<>());
            listTemp.add(edgeEnd);
            edges.put(edgeFrom, listTemp);
        }
        for(Integer node : edges.keySet()){
            if(!dfs(used,edges,node)){
                return false;
            }
        }
        return true;
    }
}

Word Ladder

题目

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

求从起点到终点的最短路径长度

分析

求路径长度一般用BFS，从起点开始把相差一个字母的单词一次入队列，知道遇到结束词时， 此时bfs的深度就是最短路径长度。

代码

class Solution {
    boolean[] isUsed;

    //判断两个单词是否只相差一个字母
    public boolean isValid(String word1, String word2){
        int diffSum = 0;
        for(int i = 0; i < word1.length();i++){
            if(word1.charAt(i) != word2.charAt(i)){
                diffSum++;
                if(diffSum > 1){
                    return false;
                }
            }
        }
        return true;
    }

    public int solve(String beginWord, String endWord, List<String> wordList){
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        int step = 2;
        while(!queue.isEmpty()){
            int queueSize = queue.size();
            for(int i = 0 ; i < queueSize;i++){
                String temp  = queue.peek();
                for(int j = 0 ; j <wordList.size();j++){
                    if(!isUsed[j] && isValid(temp,wordList.get(j))){
                        if(wordList.get(j).equals(endWord)){
                            return step;
                        }
                        queue.add(wordList.get(j));
                        isUsed[j] = true;
                    }
                }
                queue.poll();
            }
            step++;
        }
        return 0;
    }
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        isUsed = new boolean[wordList.size()];
        return solve(beginWord,endWord,wordList);
    }
}

Word Ladder II

题目

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Return

>   [
>     ["hit","hot","dot","dog","cog"],
>     ["hit","hot","lot","log","cog"]
>   ]
>

返回所有的路径长度最短的合法路径。

分析

找到合法路径，考虑用BFS，找到所有合法的路径，考虑用DFS，这道题目要求找到路径最短的所有合法路径，所以是一道BFS和DFS的综合题目。

如果只用DFS找的话，要遍历所有的路径，势必会超时（我试了，真的超时）

所以采用dfs和bfs结合的办法：

先从endWord到beginWord用BFS找到最短的路径是多少，同时标记经过的点到endWord的最短距离是多少

然后再用DFS从beginWord到endWord找到确定的路径，此时只需要遍历之前遍历过的点，其余的没有经过的点无需遍历，而且可以按距离顺序来遍历，将所有合法的路径加入的结果结合中。

代码

class Solution {
    List<List<String>> results = new ArrayList<>();
    List<String> result = new ArrayList<>();
    int[] disToBegin;//记录距离起点的距离

    //判断两个单词是否只相差一个字母
    public boolean isValid(String word1, String word2){
        if(word1.length() != word2.length()){
            return false;
        }
        int diffSum = 0;
        for(int i = 0; i < word1.length();i++){
            if(word1.charAt(i) != word2.charAt(i)){
                diffSum++;
                if(diffSum > 1){
                    return false;
                }
            }
        }
        return true;
    }

    //bfs从后向前寻找最短路径长度,标记点到终点的距离
    public int bfs(String beginWord, String endWord, List<String> wordList){
        Queue<String> queue = new LinkedList<>();
        queue.add(endWord);
        int depth = 0;//endword深度为0
        //bfs
        while (!queue.isEmpty()){
            depth++;
            int size = queue.size();
            while(size > 0){
                String temp = queue.poll();
                for(int i = 0;i <wordList.size();i++){
                    String word = wordList.get(i);
                    //如果单词已经加入过队列了，或者和当前节点相差不为1，跳过
                    if(word.equals(endWord) || disToBegin[i] > 0 || !isValid(temp,word)){
                        continue;
                    }
                    if(word.equals(beginWord)){
                        return depth;//begin节点深度
                    }
                    queue.add(word);
                    disToBegin[i] = depth;
                }
                size--;
            }
        }
        return -1;
    }

    //从前向后dfs确定具体路径
    public void dfs(String tempWord, String endWord,List<String> wordList,int depth){
        if(depth == 0){
            List<String> temp = new ArrayList<>();
            temp.addAll(result);
            temp.add(endWord);
            results.add(temp);
            return;
        }
        for(int i = 0; i < disToBegin.length;i++){
            String wordNext = wordList.get(i);
            //寻找深度和字母都符合的单词
            if(disToBegin[i] != depth || !isValid(tempWord,wordNext)){
                continue;
            }
            result.add(wordNext);
            dfs(wordNext,endWord,wordList,depth-1);
            result.remove(result.size()-1);
        }
    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord)){
            return results;
        }
        //List<String> words = new ArrayList<>(wordList);
        wordList.add(beginWord);
        disToBegin = new int[wordList.size()];
        int depth = bfs(beginWord,endWord,wordList);
        result.add(beginWord);
        dfs(beginWord,endWord,wordList,depth-1);
        return results;
    }
}

DFS排列组合

排列：

Permutations

Permutations II

组合：

Palindrome Partitioning

题目

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

分析

DFS，对字符串进行分割

代码

import java.util.ArrayList;
import java.util.List;

public class PalindromePartitioning {
    List<String> result = new ArrayList<>();
    List<List<String>> results = new ArrayList<>();

    public boolean Palindrome(String s){
        if(s.length() == 1){
            return true;
        }
        int i = 0;
        int j = s.length()-1;
        while (i < j){
            if (s.charAt(i) != s.charAt(j)){
                return false;
            }
            i++;j--;
        }
        return true;
    }

    public void helper(String s,int start,int end){
        if(start > end){
            List<String> temp = new ArrayList<>();
            temp.addAll(result);
            results.add(temp);
        }
        //规定左段包含i,右段不包含i
        for(int i = start; i <= end;i++){
            String left = s.substring(start,i+1);
            if(!Palindrome(left)){
                continue;
            }
            result.add(left);
            helper(s,i+1,end);
            result.remove(result.size()-1);
        }
    }

    public List<List<String>> partition(String s) {
        helper(s,0,s.length()-1);
        return results;
    }
}

Combination Sum

总结

找所有方案的问题一般都是DFS，90%的DFS是排列或者组合。

其他例题

01 Matrix

题目

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:
Input:

> 0 0 0
> 0 1 0
> 0 0 0
>
>

>

Output:

> 0 0 0
> 0 1 0
> 0 0 0
>
>

>

Example 2:
Input:

> 0 0 0
> 0 1 0
> 1 1 1
>
>

>

Output:

> 0 0 0
> 0 1 0
> 1 2 1
>

计算每个点距离最近的0的距离

思路

方法一:

用BFS，先将所有0的位置放入队列，然后出队列，将其周围点置位1，如队列，然后出队，将其周围点置为2，以此类推。

方法二：

动态规划，先从左上到右下计算每个点离最近的0的距离

然后从右下到左上再来一遍

代码

BFS:

public int[][] updateMatrix(int[][] matrix) {
  int rows = matrix.length;
  int cols = matrix[0].length;
  int[][] dist = new int[rows][cols];
  Queue<Integer> queue = new LinkedList<>();
  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (matrix[i][j] == 0){
        dist[i][j] = 0;
        queue.add(i*cols+j);
      }
      else {
        dist[i][j] = -1;
      }
    }
  }

  int depth = 0;
  while(!queue.isEmpty()){
    depth++;
    int size = queue.size();
    while (size>0){
      int location = queue.poll();
      int row = location/cols;
      int col = location%cols;
      int[] rdelta = {-1,0,0,1};
      int[] cdelta = {0,-1,1,0};
      for(int i = 0 ; i < 4;i++){
        int new_row = row+rdelta[i];
        int new_col = col+cdelta[i];
        if(new_row >=0 && new_row < rows && new_col >= 0 && new_col < cols && dist[new_row][new_col] == -1){
          dist[new_row][new_col] = depth;
          queue.add(new_row * cols + new_col);
        }
      }
      size--;
    }
  }
  return dist;
}

动态规划

class Solution {
    int[][] dist;
    public int[][] updateMatrix(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        dist = new int[rows][cols];
        //First pass: check for left and top
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0)
                    dist[i][j] = 0;
                else {
                    dist[i][j] = rows+cols;
                    if (i > 0)
                        dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
                    if (j > 0)
                        dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
                }
            }
        }

        //Second pass: check for bottom and right
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                if (i < rows - 1)
                    dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
                if (j < cols - 1)
                    dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
            }
        }
        return dist;
    }
}

Pacific Atlantic Water Flow

题目

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

1. The order of returned grid coordinates does not matter.
2. Both m and n are less than 150.

Example:

> Given the following 5x5 matrix:
>
>   Pacific ~   ~   ~   ~   ~ 
>        ~  1   2   2   3  (5) *
>        ~  3   2   3  (4) (4) *
>        ~  2   4  (5)  3   1  *
>        ~ (6) (7)  1   4   5  *
>        ~ (5)  1   1   2   4  *
>           *   *   *   *   * Atlantic
> Return:
> [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
>

矩阵左上是pacific 右下是atlantic,找出所有水能够同时流向两个ocean的位置

分析

用dfs，对pacific ocean从边缘的每一个点向内dfs搜索可以到达的点，就是考虑每一个点的上下左右四个邻居是否比自己高，如果比自己高而且之前还没有遍历过，就继续dfs。对atlantic做同样的操作。两边都可以到达的加入结果集。

代码

class Solution {
    public void dfs(int[][] matrix,int i,int j,boolean[][] pacific,boolean[][] used){
        int rows = matrix.length;
        int cols = matrix[0].length;
        if(i < 0 || j < 0 || i > rows || j > cols){
            return;
        }
        pacific[i][j] = true;
        used[i][j] = true;
        int[] r_delta = {-1,1,0,0};
        int[] c_delta = {0,0,-1,1};
        for(int id = 0 ; id  < 4; id++){
            int new_row = i + r_delta[id];
            int new_col = j + c_delta[id];
            if(new_row >= 0 && new_col >= 0 && new_row < rows && new_col < cols && !used[new_row][new_col] &&matrix[new_row][new_col] >= matrix[i][j]){
                //pacific[new_row][new_col] = true;
                dfs(matrix,new_row,new_col,pacific,used);
            }
        }
    }

    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> results = new ArrayList<>();
        int rows = matrix.length;
        if(rows == 0){
            return results;
        }
        int cols = matrix[0].length;
        boolean[][] pacific = n，ew boolean[rows][cols];
        boolean[][] atlantic = new boolean[rows][cols];
        boolean[][] used = new boolean[rows][cols];
        //处理pacific
        for (int i = 0 ; i < cols;i++){
            //pacific[0][i] = true;
            dfs(matrix,0,i,pacific,used);
        }
        for (int i = 0 ; i < rows;i++){
            //pacific[i][0] = true;
            dfs(matrix,i,0,pacific,used);
        }
        used = new boolean[rows][cols];
        //处理atlantic
        for (int i = 0 ; i < cols;i++){
            //pacific[rows-1][i] = true;
            dfs(matrix,rows-1,i,atlantic,used);
        }
        for (int i = 0 ; i < rows;i++){
            //pacific[i][cols-1] = true;
            dfs(matrix,i,cols-1,atlantic,used);
        }
        //两个都是true的位置
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (pacific[i][j] && atlantic[i][j]){
                    results.add(new int[]{i,j});
                }
            }
        }
        return results;
    }
}

Minesweeper

题目

给定棋盘和点击的点，返回点击之后的棋盘

分析

分两种情况讨论，如果点到的地雷，就显示地雷即可；

如果没有点到地雷，则要从这个点开始dfs计算其周围的每个点周围的8个点处有多少个地雷，如果没有就改成B，如果有的话显示数字。对于显示数字的点就无需继续dfs其周围的点了。

代码

public class Minesweeper {
    //计算某个位置周围有多少个地雷
    public int calSweeper(char[][] board,int i,int j){
        int rows = board.length;
        int cols = board[0].length;
        int[] x_delta = {-1,-1,-1,1,1,1,0,0};
        int[] y_delta = {-1,1,0,-1,1,0,-1,1};
        int sum = 0;
        for(int ii = 0; ii < 8;ii++){
            if(i+x_delta[ii] < 0 || j+y_delta[ii] < 0 || i+x_delta[ii] >= rows || j+y_delta[ii] >= cols){
                continue;
            }
            if(board[i+x_delta[ii]][j+y_delta[ii]] == 'M'){
                sum ++;
            }
        }
        return sum;
    }

    public void dfs(char[][] board,int i,int j){
        int rows = board.length;
        int cols = board[0].length;
        //如果出界了，返回
        if(i < 0 || j < 0 || i >= rows || j >= cols || board[i][j] == 'B'){
            return;
        }
        if(board[i][j] == 'E'){
            int sum = calSweeper(board,i,j);
            if(sum == 0){
                board[i][j] = 'B';
                int[] x_delta = {-1,-1,-1,1,1,1,0,0};
                int[] y_delta = {-1,1,0,-1,1,0,-1,1};
                for(int ii = 0; ii < 8;ii++){
                    //如果还没点过，计算它周围有多少个地雷
                    dfs(board,i+x_delta[ii],j+y_delta[ii]);
                }
            }
            else {
                board[i][j] = Integer.toString(sum).charAt(0);
            }
        }
    }
    public char[][] updateBoard(char[][] board, int[] click) {
        //如果点到地雷
        if(board[click[0]][click[1]] == 'M'){
            board[click[0]][click[1]] = 'X';
            return board;
        }
        //没点到地雷
        else{
            dfs(board,click[0],click[1]);
        }
        return board;
    }
    public static void main(String[] args){
        Minesweeper test = new Minesweeper();
        char[][] board = {{'E','E','E','E','E'},{'E','E','M','E','E'},{'E','E','E','E','E'},{'E','E','E','E','E'}};
        char[][] result = test.updateBoard(board,new int[]{3,0});
        System.out.print(result);
    }
}

Minimum Height Trees

题目

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

>         0
>         |
>         1
>        / \
>       2   3
>
>

>

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

>      0  1  2
>       \ | /
>         3
>         |
>         4
>         |
>         5
>
>

>

return [3, 4]

选取图中某一点作为root，使得形成的树高度最小，返回所有高度最小的root点。

思路

用BFS计算了每一个点作为root的深度，超时了。。。。

逐层去掉叶子节点，留下的就是作为root树高最小的节点。思路不难，但还是写了好久

步骤：

1. 存储图中节点的度数和点边关系
2. 把度数为1的节点加入叶子节点集合
3. 遍历叶子节点，将与之相连的节点的度数-1，然后将叶子节点删除，同时，如果有节点的度数为1，说明是下一层的叶子节点，加入新叶子集合
4. 当新叶子集合的大小<=2时，说明找到了最终的MHT的root

代码

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        //边界条件处理
        if(n == 1){
            List<Integer> res = new ArrayList<>();
            res.add(0);
            return res;
        }
        if(n == 2){
            List<Integer> res = new ArrayList<>();
            res.add(0);
            res.add(1);
            return res;
        }
        //存储点边关系
        List<HashSet<Integer>> map = new ArrayList<>(n);
        for (int i = 0; i < n;i++){
            map.add(new HashSet<>());
        }
      
        int[] edgesNum = new int[n];//存储节点的度数
        for(int i = 0; i <edges.length;i++){
            int node1 = edges[i][0];
            int node2 = edges[i][1];
            edgesNum[node1]++;
            edgesNum[node2]++;
            map.get(node1).add(node2);
            map.get(node2).add(node1);
        }
        int counter = n;
      //叶子节点加入结合
        List<Integer> leaves = new ArrayList<>();
        for(int i = 0; i < n;i++){
            if(edgesNum[i] == 1){
                leaves.add(i);
            }
        }
      //遍历叶子节点，将与之相连的点的度数-1，删去叶子节点
        while (counter > 2){
            counter -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();//存储下一轮的新叶子节点
            for(Integer leave : leaves){
                edgesNum[leave]--;
                for(Integer node : map.get(leave)){
                    edgesNum[node]--;
                    if(edgesNum[node] == 1){//遇到度数为1的节点就是下一轮的叶子节点
                        newLeaves.add(node);
                    }
                }
            }
            leaves = newLeaves;
        }
        return leaves;
    }
}

The Maze

代码

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the ball’s start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.

Example 1

> Input 1: a maze represented by a 2D array
>
> 0 0 1 0 0
> 0 0 0 0 0
> 0 0 0 1 0
> 1 1 0 1 1
> 0 0 0 0 0
>
> Input 2: start coordinate (rowStart, colStart) = (0, 4)
> Input 3: destination coordinate (rowDest, colDest) = (4, 4)
>
> Output: 12
> Explanation: One shortest way is : left -> down -> left -> down -> right -> down -> right.
>              The total distance is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.
>
>
>

>

Example 2

> Input 1: a maze represented by a 2D array
>
> 0 0 1 0 0
> 0 0 0 0 0
> 0 0 0 1 0
> 1 1 0 1 1
> 0 0 0 0 0
>
> Input 2: start coordinate (rowStart, colStart) = (0, 4)
> Input 3: destination coordinate (rowDest, colDest) = (3, 2)
>
> Output: -1
> Explanation: There is no way for the ball to stop at the destination.
>

矩阵中1是障碍，0是通的，小球从start滚到destination，不遇到障碍或者边界小球不会停下来，返回小球是否可以从start滚到end

分析

BFS，小球从起点开始可以向上下左右四个方向滚，每次滚到障碍或者边界处，滚到终点就返回true

另外需要一个数组记录小球是否到过该节点，如果到过，后续就无需再走这里了。

代码

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int rows = maze.length;
        if(rows == 0){
            return false;
        }
        int cols = maze[0].length;
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        Queue<int[]> queue = new LinkedList<>();
        int[] x_delta = {-1,1,0,0};//上下左右
        int[] y_delta = {0,0,-1,1};
        queue.add(start);
        visited[start[0]][start[1]] = true;
        while (!queue.isEmpty()){
            int[] node = queue.poll();
            if(node[0] == destination[0] && node[1] == destination[1]){
                return true;
            }
            for(int ii = 0 ; ii < 4;ii++){
                int newStartX = node[0] + x_delta[ii];
                int newStartY = node[1] + y_delta[ii];
                //走的通的方向，一直走到尽头
                while(newStartX >= 0 && newStartY >= 0 && newStartX < rows && newStartY < cols && maze[newStartX][newStartY] == 0){
                    newStartX += x_delta[ii];
                    newStartY += y_delta[ii];
                }
                if(!visited[newStartX-x_delta[ii]][newStartY-y_delta[ii]]){
                    queue.add(new int[]{newStartX - x_delta[ii],newStartY - y_delta[ii]});
                    visited[newStartX-x_delta[ii]][newStartY-y_delta[ii]] = true;
                }
            }
        }
        return false;
    }
}

The Maze II

题目

跟上一题一样，这个题要求返回从起点滚到终点的最短路径长度。如果滚不到就返回-1

分析

用一个二维数组记录地图中的点到start的距离。BFS更新计算start到能够到达的点的最小距离，最后返回二维数组中的终点的值。

代码

class Solution {
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int rows = maze.length;
        int cols = maze[0].length;
        int[][] distance = new int[maze.length][maze[0].length];
        for(int i = 0 ; i <distance.length;i++){
            for(int j = 0 ; j < distance[0].length;j++){
                distance[i][j] = Integer.MAX_VALUE;
            }
        }
        Queue<int[]> queue = new LinkedList<>();
        int[] x_delta = {-1,1,0,0};//上下左右
        int[] y_delta = {0,0,-1,1};
        queue.add(start);
        distance[start[0]][start[1]] = 0;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            for (int ii = 0; ii < 4; ii++) {
                int newStartX = node[0] + x_delta[ii];
                int newStartY = node[1] + y_delta[ii];
                //走的通的方向，一直走到尽头
                int count = 0;//记录走了多少步
                while (newStartX >= 0 && newStartY >= 0 && newStartX < rows && newStartY < cols && maze[newStartX][newStartY] == 0) {
                    newStartX += x_delta[ii];
                    newStartY += y_delta[ii];
                    count++;
                }
              //如果这条路径到达该点比之前的距离短，更新该点的最短距离
                if (distance[node[0]][node[1]] + count < distance[newStartX - x_delta[ii]][newStartY - y_delta[ii]]) {
                    distance[newStartX - x_delta[ii]][newStartY - y_delta[ii]] = distance[node[0]][node[1]] + count;
                    queue.add(new int[]{newStartX - x_delta[ii], newStartY - y_delta[ii]});
                }
            }
        }
        return distance[destination[0]][destination[1]] < Integer.MAX_VALUE ? distance[destination[0]][destination[1]] : -1;
    }
}