2019年7月 – gongel-coder

路径和问题：腐烂的橘子BFS 二进制矩阵中的最短路径BFS

64. 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:

[

[1,3,1],

[1,5,1],

[4,2,1]

]

输出: 7

解释: 因为路径 1→3→1→1→1 的总和最小。

public class Sixty_four {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = grid[0][0];
                } else if (i > 0 && j == 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else if (i == 0 && j > 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

public class Sixty_four {

public int minPathSum(int[][] grid) {

int m = grid.length;

int n = grid[0].length;

int[][] dp = new int[m][n];

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (i == 0 && j == 0) {

dp[i][j] = grid[0][0];

} else if (i > 0 && j == 0) {

dp[i][j] = dp[i - 1][j] + grid[i][j];

} else if (i == 0 && j > 0) {

dp[i][j] = dp[i][j - 1] + grid[i][j];

} else {

dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];

}

return dp[m - 1][n - 1];

}

994. 腐烂的橘子

在给定的网格中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

 

示例 1：



输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：

输入：[[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
示例 3：

输入：[[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
 

提示：

1 <= grid.length <= 10
1 <= grid[0].length <= 10
grid[i][j] 仅为 0、1 或 2

在给定的网格中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；

值 1 代表新鲜橘子；

值 2 代表腐烂的橘子。

每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

示例 1：

输入：[[2,1,1],[1,1,0],[0,1,1]]

输出：4

示例 2：

输入：[[2,1,1],[0,1,1],[1,0,1]]

输出：-1

解释：左下角的橘子（第 2 行，第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

示例 3：

输入：[[0,2]]

输出：0

解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

1 <= grid.length <= 10

1 <= grid[0].length <= 10

grid[i][j] 仅为 0、1 或 2

package gongel_first;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class Ninehundred_ninetyFour {
    /**
     * BFS
     * 类似于1091
     */
    private int[][] directions = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return -1;
        Deque<int[]> deque = new LinkedList<>();
        Map<int[], Integer> depth = new HashMap<>();
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    int[] node = {i, j};
                    deque.addLast(node);
                    depth.put(node, 0);
                }
            }
        }
        int ans = 0;
        while (!deque.isEmpty()) {
            int[] node = deque.pollFirst();
            for (int i = 0; i < 4; i++) {
                int row = node[0] + directions[i][0];
                int col = node[1] + directions[i][1];
                if (0 <= row && row < m && 0 <= col && col < n && grid[row][col] == 1) {
                    grid[row][col] = 2;//相当于visited防止再次访问
                    int[] newNode = {row, col};//直接一次new即可
                    deque.addLast(newNode);//1.两次 new int[]{row,col}会有错误
                    depth.put(newNode, depth.get(node) + 1);//2.两次 new int[]{row,col}会有错误
                    ans = depth.get(newNode);
                }
            }
        }
        for (int[] row : grid) {
            for (int v : row) {
                if (v == 1)
                    return -1;
            }
        }
        return ans;
    }
}

package gongel_first;

import java.util.Deque;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.Map;

public class Ninehundred_ninetyFour {

/**

* BFS

* 类似于1091

private int[][] directions = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

public int orangesRotting(int[][] grid) {

if (grid == null || grid.length == 0 || grid[0].length == 0)

return -1;

Deque<int[]> deque = new LinkedList<>();

Map<int[], Integer> depth = new HashMap<>();

int m = grid.length;

int n = grid[0].length;

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (grid[i][j] == 2) {

int[] node = {i, j};

deque.addLast(node);

depth.put(node, 0);

}

int ans = 0;

while (!deque.isEmpty()) {

int[] node = deque.pollFirst();

for (int i = 0; i < 4; i++) {

int row = node[0] + directions[i][0];

int col = node[1] + directions[i][1];

if (0 <= row && row < m && 0 <= col && col < n && grid[row][col] == 1) {

grid[row][col] = 2;//相当于visited防止再次访问

int[] newNode = {row, col};//直接一次new即可

deque.addLast(newNode);//1.两次 new int[]{row,col}会有错误

depth.put(newNode, depth.get(node) + 1);//2.两次 new int[]{row,col}会有错误

ans = depth.get(newNode);

}

for (int[] row : grid) {

for (int v : row) {

if (v == 1)

return -1;

}

return ans;

}

1091. 二进制矩阵中的最短路径

在一个 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

在一个 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

package gongel_first;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class Ten_NinetyOne {
    /**
     * BFS：其实就是计算层次,不同的是八个方向
     * 类似于994
     */
    private int[][] directions = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}, {0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0 || grid[0][0] == 1 || grid[grid.length - 1][grid[0].length - 1] == 1)
            return -1;
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        Deque<int[]> deque = new LinkedList<>();
        Map<int[], Integer> depth = new HashMap<>();
        int[] root = new int[]{0, 0};
        deque.addLast(root);
        depth.put(root, 1);
        visited[0][0] = true;
        while (!deque.isEmpty()) {
            int[] node = deque.pollFirst();
            if (node[0] == m - 1 && node[1] == n - 1)
                return depth.get(node);
            for (int i = 0; i < 8; i++) {
                int row = node[0] + directions[i][0];
                int col = node[1] + directions[i][1];
                if (row >= 0 && row < m && col >= 0 && col < n && grid[row][col] == 0 && !visited[row][col]) {
                    int[] newNode = {row, col};//直接一次new即可
                    deque.addLast(newNode);//1.两次 new int[]{row,col}会有错误
                    depth.put(newNode, depth.get(node) + 1);//2.两次 new int[]{row,col}会有错误
                    visited[row][col] = true;
                }
            }
        }
        return -1;
    }
}

package gongel_first;

import java.util.Deque;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.Map;

public class Ten_NinetyOne {

/**

* BFS：其实就是计算层次,不同的是八个方向

* 类似于994

private int[][] directions = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}, {0, 1}, {0, -1}, {-1, 0}, {1, 0}};

public int shortestPathBinaryMatrix(int[][] grid) {

if (grid == null || grid.length == 0 || grid[0].length == 0 || grid[0][0] == 1 || grid[grid.length - 1][grid[0].length - 1] == 1)

return -1;

int m = grid.length;

int n = grid[0].length;

boolean[][] visited = new boolean[m][n];

Deque<int[]> deque = new LinkedList<>();

Map<int[], Integer> depth = new HashMap<>();

int[] root = new int[]{0, 0};

deque.addLast(root);

depth.put(root, 1);

visited[0][0] = true;

while (!deque.isEmpty()) {

int[] node = deque.pollFirst();

if (node[0] == m - 1 && node[1] == n - 1)

return depth.get(node);

for (int i = 0; i < 8; i++) {

int row = node[0] + directions[i][0];

int col = node[1] + directions[i][1];

if (row >= 0 && row < m && col >= 0 && col < n && grid[row][col] == 0 && !visited[row][col]) {

int[] newNode = {row, col};//直接一次new即可

deque.addLast(newNode);//1.两次 new int[]{row,col}会有错误

depth.put(newNode, depth.get(node) + 1);//2.两次 new int[]{row,col}会有错误

visited[row][col] = true;

}

return -1;

}

Python os(文件/文件夹遍历、删除)

对话系统的评价指标

对于某一轮对话而言，可以使用响应的适当性、流畅度、相关性；对于多轮对话而言，我们更关注流畅性、对话深度、多样性、一致连贯性等指标；而对于整个对话系统，我们则希望他可以涵盖更多的话题、回复真实可信等等。

一.词重叠评价指标

该指标认为回答应该和真实回答之间存在大量的词重叠

1.BLEU

candidate（Predicted）：机器生成的结果；reference（Gold Standard）：参考句，类似于参考答案，可以多句；

Step 1：Modified n-gram Precision计算（也即 $P_{n}$ ）

当n=1/2/3/4时的precision；首先统计候选译文里每个词（n-gram）出现的次数，然后统计每个词（n-gram）在参考译文中出现的次数，Max表示3个参考译文中的最大值，Min表示候选译文和Max两个的最小值。

以unigram为例，bigram、trigram、4-gram相同：

Step 2：Brevity Penalty 计算

if c > r: return 1 else: return math.exp(1 – r / c) c:候选句的长度；r：参考句的最大长度

Step 3：Pn * Bp

2.ROUGE

①ROUGE-N

②ROUGE-L

③ROUGE-W

④ROUGE-S

3.METEOR

二、词向量评价指标

词向量则是通过Word2Vec、Sent2Vec等方法将句子转换为向量表示，这样一个句子就被映射到一个低维空间，句向量在一定程度上表征了其含义，在通过余弦相似度等方法就可以计算两个句子之间的相似程度。

1.Greedy Matching

2.Embedding Average

3.Vector Extrema

跟上面的方法类似，也是先通过词向量计算出句向量，在使用句向量之间的余弦相似度表示二者的相似度。不过句向量的计算方法略有不同，这里采用向量极值法进行计算。

三、perplexity困惑度

四、人工指标

ref：

基于深度学习的对话系统

机器翻译评价指标之BLEU详细计算过程（已剪报）

学习笔记———《自动文档摘要评价方法—Edmundson和ROUGE》（已剪报）

二叉树中所有距离为 K 的结点BFS+DFS 二叉树的堂兄弟节点BFS/DFS

863. 二叉树中所有距离为 K 的结点

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。

返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

 

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

输出：[7,4,1]

解释：
所求结点为与目标结点（值为 5）距离为 2 的结点，
值分别为 7，4，以及 1



注意，输入的 "root" 和 "target" 实际上是树上的结点。
上面的输入仅仅是对这些对象进行了序列化描述。
 

提示：

给定的树是非空的，且最多有 K 个结点。
树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
目标结点 target 是树上的结点。
0 <= K <= 1000.出处。

给定一个二叉树（具有根结点 root），一个目标结点 target ，和一个整数值 K 。

返回到目标结点 target 距离为 K 的所有结点的值的列表。答案可以以任何顺序返回。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

输出：[7,4,1]

解释：

所求结点为与目标结点（值为 5）距离为 2 的结点，

值分别为 7，4，以及 1

注意，输入的 "root" 和 "target" 实际上是树上的结点。

上面的输入仅仅是对这些对象进行了序列化描述。

提示：

给定的树是非空的，且最多有 K 个结点。

树上的每个结点都具有唯一的值 0 <= node.val <= 500 。

目标结点 target 是树上的结点。

0 <= K <= 1000.出处。

package gongel_first;

import java.util.*;

public class Eighthundred_sixtyThree {
    /**
     * 图的层次遍历 BFS
     * 先按DFS建图（便于后面BFS），然后BFS遍历按层数取满足条件的节点
     * 题目说了 节点值是唯一的，所以graph/visited/deque中的TreeNode都可以用Integer代替
     */
    private Map<TreeNode, List<TreeNode>> graph;

    //注意这里的建图代码:只有一个节点时graph是为空的
    private void buidGraphDFS(TreeNode parent, TreeNode child) {
        if (child == null)
            return;
        if (parent != null) {
            List<TreeNode> neighborP = graph.getOrDefault(parent, new ArrayList<>());
            neighborP.add(child);
            graph.put(parent, neighborP);

            List<TreeNode> neighborC = graph.getOrDefault(child, new ArrayList<>());
            neighborC.add(parent);
            graph.put(child, neighborC);
        }
        buidGraphDFS(child, child.left);
        buidGraphDFS(child, child.right);
    }

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        if (root == null || target == null || K < 0)
            return new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        Set<TreeNode> visited = new HashSet<>();
        visited.add(target);//图的遍历和树的遍历差异
        graph = new HashMap<>();
        buidGraphDFS(null, root);
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(target);
        int level = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.pollFirst();
                if (level == K)
                    ans.add(node.val);
                if (graph.containsKey(node)) {//图有可能为空
                    for (TreeNode neighbor : graph.get(node)) {
                        if (!visited.contains(neighbor)) {
                            deque.addLast(neighbor);
                            visited.add(neighbor);
                        }
                    }
                }
            }
            level++;
        }
        return ans;
    }
}

package gongel_first;

import java.util.*;

public class Eighthundred_sixtyThree {

/**

* 图的层次遍历 BFS

* 先按DFS建图（便于后面BFS），然后BFS遍历按层数取满足条件的节点

* 题目说了节点值是唯一的，所以graph/visited/deque中的TreeNode都可以用Integer代替

private Map<TreeNode, List<TreeNode>> graph;

//注意这里的建图代码:只有一个节点时graph是为空的

private void buidGraphDFS(TreeNode parent, TreeNode child) {

if (child == null)

return;

if (parent != null) {

List<TreeNode> neighborP = graph.getOrDefault(parent, new ArrayList<>());

neighborP.add(child);

graph.put(parent, neighborP);

List<TreeNode> neighborC = graph.getOrDefault(child, new ArrayList<>());

neighborC.add(parent);

graph.put(child, neighborC);

}

buidGraphDFS(child, child.left);

buidGraphDFS(child, child.right);

}

public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {

if (root == null || target == null || K < 0)

return new ArrayList<>();

List<Integer> ans = new ArrayList<>();

Set<TreeNode> visited = new HashSet<>();

visited.add(target);//图的遍历和树的遍历差异

graph = new HashMap<>();

buidGraphDFS(null, root);

Deque<TreeNode> deque = new LinkedList<>();

deque.addLast(target);

int level = 0;

while (!deque.isEmpty()) {

int size = deque.size();

for (int i = 0; i < size; i++) {

TreeNode node = deque.pollFirst();

if (level == K)

ans.add(node.val);

if (graph.containsKey(node)) {//图有可能为空

for (TreeNode neighbor : graph.get(node)) {

if (!visited.contains(neighbor)) {

deque.addLast(neighbor);

visited.add(neighbor);

}

level++;

}

return ans;

}

993. 二叉树的堂兄弟节点

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。

 

示例 1：


输入：root = [1,2,3,4], x = 4, y = 3
输出：false
示例 2：


输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true
示例 3：



输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false
 

提示：

二叉树的节点数介于 2 到 100 之间。
每个节点的值都是唯一的、范围为 1 到 100 的整数。

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root，以及树中两个不同节点的值 x 和 y。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true。否则，返回 false。

示例 1：

输入：root = [1,2,3,4], x = 4, y = 3

输出：false

示例 2：

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4

输出：true

示例 3：

输入：root = [1,2,3,null,4], x = 2, y = 3

输出：false

提示：

二叉树的节点数介于 2 到 100 之间。

每个节点的值都是唯一的、范围为 1 到 100 的整数。

package gongel_first;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class Ninehundred_ninetyThree {
    /**
     * 法一：DFS
     * 给每个节点增加层次和父节点，最终比较是否是同层次不同父节点
     */
    private Map<Integer, Integer> depth;
    private Map<Integer, TreeNode> parent;

    private void dfs(TreeNode par, TreeNode child) {
        if (child != null) {
            depth.put(child.val, par == null ? 0 : depth.get(par.val) + 1);
            parent.put(child.val, par);
            dfs(child, child.left);
            dfs(child, child.right);
        }
    }

    public boolean isCousins(TreeNode root, int x, int y) {
        depth = new HashMap<>();
        parent = new HashMap<>();
        dfs(null, root);
        return (depth.get(x) == depth.get(y) && parent.get(x) != parent.get(y));
    }

    /**
     * 法二：BFS
     * 题解给的是DFS,我给个BFS的解法吧，根据BFS增加xPair和yPair数组；
     * xPair（大小为2）和yPair（大小为2）分别存储x和y各自的父节点和层次
     */
    public boolean isCousins2(TreeNode root, int x, int y) {
        Deque<TreeNode> deque = new LinkedList<>();
        int[] xPair = new int[]{101, 102};//初始化
        int[] yPair = new int[]{101, 103};//初始化
        deque.addLast(root);
        int level = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.pollFirst();
                if (node.left != null) {//先判断左子树
                    deque.addLast(node.left);
                    if (node.left.val == x) {//如果是x节点的话，更新xPair
                        xPair[0] = node.val;//更新父节点
                        xPair[1] = level;//更新层次
                    }
                    if (node.left.val == y) {//如果是y节点的话，更新yPair
                        yPair[0] = node.val;
                        yPair[1] = level;
                    }
                }
                if (node.right != null) {//判断右子树
                    deque.addLast(node.right);
                    if (node.right.val == x) {
                        xPair[0] = node.val;
                        xPair[1] = level;
                    }
                    if (node.right.val == y) {
                        yPair[0] = node.val;
                        yPair[1] = level;
                    }
                }
                if (xPair[0] <= 100 && xPair[1] <= 100 && yPair[0] <= 100 && yPair[1] <= 100 && xPair[0] != yPair[0] && xPair[1] == yPair[1])
                    return true;
            }
            level++;
        }
        return false;
    }
}

package gongel_first;

import java.util.Deque;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.Map;

public class Ninehundred_ninetyThree {

/**

* 法一：DFS

* 给每个节点增加层次和父节点，最终比较是否是同层次不同父节点

private Map<Integer, Integer> depth;

private Map<Integer, TreeNode> parent;

private void dfs(TreeNode par, TreeNode child) {

if (child != null) {

depth.put(child.val, par == null ? 0 : depth.get(par.val) + 1);

parent.put(child.val, par);

dfs(child, child.left);

dfs(child, child.right);

}

public boolean isCousins(TreeNode root, int x, int y) {

depth = new HashMap<>();

parent = new HashMap<>();

dfs(null, root);

return (depth.get(x) == depth.get(y) && parent.get(x) != parent.get(y));

}

/**

* 法二：BFS

* 题解给的是DFS,我给个BFS的解法吧，根据BFS增加xPair和yPair数组；

* xPair（大小为2）和yPair（大小为2）分别存储x和y各自的父节点和层次

public boolean isCousins2(TreeNode root, int x, int y) {

Deque<TreeNode> deque = new LinkedList<>();

int[] xPair = new int[]{101, 102};//初始化

int[] yPair = new int[]{101, 103};//初始化

deque.addLast(root);

int level = 0;

while (!deque.isEmpty()) {

int size = deque.size();

for (int i = 0; i < size; i++) {

TreeNode node = deque.pollFirst();

if (node.left != null) {//先判断左子树

deque.addLast(node.left);

if (node.left.val == x) {//如果是x节点的话，更新xPair

xPair[0] = node.val;//更新父节点

xPair[1] = level;//更新层次

}

if (node.left.val == y) {//如果是y节点的话，更新yPair

yPair[0] = node.val;

yPair[1] = level;

}

if (node.right != null) {//判断右子树

deque.addLast(node.right);

if (node.right.val == x) {

xPair[0] = node.val;

xPair[1] = level;

}

if (node.right.val == y) {

yPair[0] = node.val;

yPair[1] = level;

}

if (xPair[0] <= 100 && xPair[1] <= 100 && yPair[0] <= 100 && yPair[1] <= 100 && xPair[0] != yPair[0] && xPair[1] == yPair[1])

return true;

}

level++;

}

return false;

}

判断二分图BFS 最短的桥DFS+BFS

785. 判断二分图

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。


示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2
我们不能将节点分割成两个独立的子集。
注意:

graph 的长度范围为 [1, 100]。
graph[i] 中的元素的范围为 [0, graph.length - 1]。
graph[i] 不会包含 i 或者有重复的值。
图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

示例 1:

输入: [[1,3], [0,2], [1,3], [0,2]]

输出: true

解释:

无向图如下:

0----1

| |

3----2

我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2:

输入: [[1,2,3], [0,2], [0,1,3], [0,2]]

输出: false

解释:

无向图如下:

0----1

| \ |

3----2

我们不能将节点分割成两个独立的子集。

注意:

graph 的长度范围为 [1, 100]。

graph[i] 中的元素的范围为 [0, graph.length - 1]。

graph[i] 不会包含 i 或者有重复的值。

图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

package gongel_first;

import java.util.Deque;
import java.util.LinkedList;

public class Sevenhundred_eightyFive {
    /**
     * 层次遍历 上色问题
     * 如果可以分为二分图，说明每个节点的颜色和邻接点一定不同
     * 类似问题：130
     */
    private int[] color;

    private boolean bfs(int[][] graph, int node) {
        color[node] = 1;
        Deque<Integer> deque = new LinkedList<>();
        deque.addLast(node);
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                int head = deque.pollFirst();
                for (int neighbor : graph[head]) {
                    if (color[neighbor] == color[head])//和邻接点颜色相同，说明不是二分图
                        return false;
                    if (color[neighbor] == 0) {//如果没有上色，那么加入到队列，并且上色为相反颜色
                        deque.addLast(neighbor);
                        color[neighbor] = -color[head];
                    }
                }
            }
        }
        return true;
    }

    public boolean isBipartite(int[][] graph) {
        if (graph == null || graph.length == 0)
            return false;
        color = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            if (color[i] == 0 && !bfs(graph, i)) {//上过色的不需要bfs，因为已经判断过了
                return false;
            }
        }
        return true;
    }
}

package gongel_first;

import java.util.Deque;

import java.util.LinkedList;

public class Sevenhundred_eightyFive {

/**

* 层次遍历上色问题

* 如果可以分为二分图，说明每个节点的颜色和邻接点一定不同

* 类似问题：130

private int[] color;

private boolean bfs(int[][] graph, int node) {

color[node] = 1;

Deque<Integer> deque = new LinkedList<>();

deque.addLast(node);

while (!deque.isEmpty()) {

int size = deque.size();

for (int i = 0; i < size; i++) {

int head = deque.pollFirst();

for (int neighbor : graph[head]) {

if (color[neighbor] == color[head])//和邻接点颜色相同，说明不是二分图

return false;

if (color[neighbor] == 0) {//如果没有上色，那么加入到队列，并且上色为相反颜色

deque.addLast(neighbor);

color[neighbor] = -color[head];

}

return true;

}

public boolean isBipartite(int[][] graph) {

if (graph == null || graph.length == 0)

return false;

color = new int[graph.length];

for (int i = 0; i < graph.length; i++) {

if (color[i] == 0 && !bfs(graph, i)) {//上过色的不需要bfs，因为已经判断过了

return false;

}

return true;

}

934. 最短的桥

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目。（可以保证答案至少是 1。）

 

示例 1：

输入：[[0,1],[1,0]]
输出：1
示例 2：

输入：[[0,1,0],[0,0,0],[0,0,1]]
输出：2
示例 3：

输入：[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1
 

提示：

1 <= A.length = A[0].length <= 100
A[i][j] == 0 或 A[i][j] == 1

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目。（可以保证答案至少是 1。）

示例 1：

输入：[[0,1],[1,0]]

输出：1

示例 2：

输入：[[0,1,0],[0,0,0],[0,0,1]]

输出：2

示例 3：

输入：[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]

输出：1

提示：

1 <= A.length = A[0].length <= 100

A[i][j] == 0 或 A[i][j] == 1

package gongel_first;

import java.util.Deque;
import java.util.LinkedList;

public class Ninehundred_thirtyFour {
    /**
     * DFS+BFS
     * 题意理解：其实就是将二维数组中由1组成的两个连通图通过“变0为1”将它们连接起来
     * 解法：先DFS找到其中一个连通图，变1为2，记为连通图2，然后从另外一个连通图BFS（记为连通图1）一层一层遍历，第一次触碰到连通图2的节点的当前层数即为答案
     * [[0,1,0],       [[0,2,0],
     * [0,0,0],------>[0,0,0],,------>求1到2的层次距离：2
     * [0,0,1]]       [0,0,1]]
     * 相似题目；200,542,752
     */
    private int[][] directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

    private void dfs(int[][] A, int i, int j) {
        if (i < 0 || i >= A.length || j < 0 || j >= A[0].length || A[i][j] != 1)//为0则不是连通图(否则不连通)，为2则已经dfs过了(否则堆栈溢出)
            return;
        A[i][j] = 2;
        dfs(A, i - 1, j);
        dfs(A, i + 1, j);
        dfs(A, i, j - 1);
        dfs(A, i, j + 1);
    }

    public int shortestBridge(int[][] A) {
        if (A == null || A.length == 0 || A[0].length == 0)
            return 0;
        int m = A.length;
        int n = A[0].length;
        boolean found = false;
        Deque<int[]> deque = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!found && A[i][j] == 1) {//只将其中一个连通图变为2，即为连通图2
                    dfs(A, i, j);
                    found = true;
                } else if (found && A[i][j] == 1) {//另外一个连通图（即为连通图1）直接入队
                    deque.addLast(new int[]{i, j});
                }
            }
        }
        int ans = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                int[] head = deque.pollFirst();
                for (int[] d : directions) {
                    int x = head[0] + d[0];
                    int y = head[1] + d[1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        if (A[x][y] == 0) {
                            A[x][y] = 1;
                            deque.addLast(new int[]{x, y});
                        } else if (A[x][y] == 2)
                            return ans;
                    }
                }
            }
            ans++;
        }
        return 1;
    }
}

package gongel_first;

import java.util.Deque;

import java.util.LinkedList;

public class Ninehundred_thirtyFour {

/**

* DFS+BFS

* 题意理解：其实就是将二维数组中由1组成的两个连通图通过“变0为1”将它们连接起来

* 解法：先DFS找到其中一个连通图，变1为2，记为连通图2，然后从另外一个连通图BFS（记为连通图1）一层一层遍历，第一次触碰到连通图2的节点的当前层数即为答案

* [[0,1,0], [[0,2,0],

* [0,0,0],------>[0,0,0],,------>求1到2的层次距离：2

* [0,0,1]] [0,0,1]]

* 相似题目；200,542,752

private int[][] directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

private void dfs(int[][] A, int i, int j) {

if (i < 0 || i >= A.length || j < 0 || j >= A[0].length || A[i][j] != 1)//为0则不是连通图(否则不连通)，为2则已经dfs过了(否则堆栈溢出)

return;

A[i][j] = 2;

dfs(A, i - 1, j);

dfs(A, i + 1, j);

dfs(A, i, j - 1);

dfs(A, i, j + 1);

}

public int shortestBridge(int[][] A) {

if (A == null || A.length == 0 || A[0].length == 0)

return 0;

int m = A.length;

int n = A[0].length;

boolean found = false;

Deque<int[]> deque = new LinkedList<>();

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (!found && A[i][j] == 1) {//只将其中一个连通图变为2，即为连通图2

dfs(A, i, j);

found = true;

} else if (found && A[i][j] == 1) {//另外一个连通图（即为连通图1）直接入队

deque.addLast(new int[]{i, j});

}

int ans = 0;

while (!deque.isEmpty()) {

int size = deque.size();

for (int i = 0; i < size; i++) {

int[] head = deque.pollFirst();

for (int[] d : directions) {

int x = head[0] + d[0];

int y = head[1] + d[1];

if (x >= 0 && x < m && y >= 0 && y < n) {

if (A[x][y] == 0) {

A[x][y] = 1;

deque.addLast(new int[]{x, y});

} else if (A[x][y] == 2)

return ans;

}

ans++;

}

return 1;

}

相似的题目引用：

单词接龙DFS 被围绕的区域DFS 岛屿数量DFS

N叉树的层序遍历 01矩阵 BFS

N叉树的最大深度打开转盘锁层次遍历

一	二	三	四	五	六	日
« 6月				8月 »
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

一.词重叠评价指标

1.BLEU

Step 1：Modified n-gram Precision计算（也即Pn）

Step 2：Brevity Penalty 计算

Step 3：Pn * Bp

2.ROUGE

3.METEOR

二、词向量评价指标

1.Greedy Matching

2.Embedding Average

3.Vector Extrema

三、perplexity困惑度

四、人工指标

Step 1：Modified n-gram Precision计算（也即 $P_{n}$ ）