Java – gongel

DFS

130. 被围绕的区域

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X
解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

X X X X

X O O X

X X O X

X O X X

运行你的函数后，矩阵变为：

X X X X

X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

public class Onehundred_thirty {
    /**
     * dfs
     * 依次将与边界上O相邻的O全部标记为M，表示他们不会被包围；剩下的O一定是被包围的，所以最终将M节点标记为O，O节点标记为X
     */
    private int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0)
            return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1 && board[i][j] == 'O')
                    dfs(i, j, board);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == 'M') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs(int i, int j, char[][] board) {
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O')
            return;
        board[i][j] = 'M';
        for (int[] direction : directions) {
            dfs(i + direction[0], j + direction[1], board);
        }
    }
}

public class Onehundred_thirty {

/**

* dfs

* 依次将与边界上O相邻的O全部标记为M，表示他们不会被包围；剩下的O一定是被包围的，所以最终将M节点标记为O，O节点标记为X

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

public void solve(char[][] board) {

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

return;

int m = board.length;

int n = board[0].length;

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

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

if (i == 0 || i == m - 1 || j == 0 || j == n - 1 && board[i][j] == 'O')

dfs(i, j, board);

}

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

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

if (board[i][j] == 'O') {

board[i][j] = 'X';

}

if (board[i][j] == 'M') {

board[i][j] = 'O';

}

public void dfs(int i, int j, char[][] board) {

int m = board.length;

int n = board[0].length;

if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O')

return;

board[i][j] = 'M';

for (int[] direction : directions) {

dfs(i + direction[0], j + direction[1], board);

}

class Solution {
private:
    const vector<pair<int, int>> directions{{0,  1},
                                            {0,  -1},
                                            {1,  0},
                                            {-1, 0}};
public:
    void solve(vector<vector<char>> &board) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (i == 0 || i == board.size() - 1 || j == 0 || j == board[0].size() - 1 && board[i][j] == 'O')
                    dfs(board, i, j);
            }
        }
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';
                if (board[i][j] == 'M')
                    board[i][j] = 'O';
            }
        }
    }

    void dfs(vector<vector<char>> &board, int i, int j) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O')
            return;
        board[i][j] = 'M';
        for (auto direction:directions) {
            dfs(board, i + direction.first, j + direction.second);
        }
    }
};

class Solution {

private:

const vector<pair<int, int>> directions{{0, 1},

{0, -1},

{1, 0},

{-1, 0}};

public:

void solve(vector<vector<char>> &board) {

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

for (int j = 0; j < board[0].size(); j++) {

if (i == 0 || i == board.size() - 1 || j == 0 || j == board[0].size() - 1 && board[i][j] == 'O')

dfs(board, i, j);

}

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

for (int j = 0; j < board[0].size(); j++) {

if (board[i][j] == 'O')

board[i][j] = 'X';

if (board[i][j] == 'M')

board[i][j] = 'O';

}

void dfs(vector<vector<char>> &board, int i, int j) {

if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O')

return;

board[i][j] = 'M';

for (auto direction:directions) {

dfs(board, i + direction.first, j + direction.second);

}

};

200. 岛屿数量

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:

11110

11010

11000

00000

输出: 1

示例 2:

输入:

11000

00100

00011

输出: 3

package gongel_first;

public class Twohundred {
    /**
     * DFS
     * 极其类似130题
     */
    public void dfs(char[][] grid, int row, int col, int m, int n) {
        if (row >= m || row < 0 || col >= n || col < 0 || grid[row][col] != '1')//一定要加grid[row][col] == '0'，避免重复走
            return;
        grid[row][col] = '0';
        dfs(grid, row - 1, col, m, n);//上
        dfs(grid, row + 1, col, m, n);//下
        dfs(grid, row, col - 1, m, n);//左
        dfs(grid, row, col + 1, m, n);//右
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int m = grid.length;
        int n = grid[0].length;
        int numIsland = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {//没有被访问过
                    dfs(grid, i, j, m, n);
                    numIsland++;
                }
            }
        }
        return numIsland;
    }
}

package gongel_first;

public class Twohundred {

/**

* DFS

* 极其类似130题

public void dfs(char[][] grid, int row, int col, int m, int n) {

if (row >= m || row < 0 || col >= n || col < 0 || grid[row][col] != '1')//一定要加grid[row][col] == '0'，避免重复走

return;

grid[row][col] = '0';

dfs(grid, row - 1, col, m, n);//上

dfs(grid, row + 1, col, m, n);//下

dfs(grid, row, col - 1, m, n);//左

dfs(grid, row, col + 1, m, n);//右

}

public int numIslands(char[][] grid) {

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

return 0;

int m = grid.length;

int n = grid[0].length;

int numIsland = 0;

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

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

if (grid[i][j] == '1') {//没有被访问过

dfs(grid, i, j, m, n);

numIsland++;

}

return numIsland;

}

class Solution {
private:
    const vector<pair<int, int>> directions{{0,  1},
                                            {0,  -1},
                                            {1,  0},
                                            {-1, 0}};
public:
    int numIslands(vector<vector<char>> &grid) {
        int num_island = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    num_island++;
                    dfs(grid, i, j);
                }
            }
        }
        return num_island;
    }

    void dfs(vector<vector<char>> &grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != '1')
            return;
        grid[i][j] = '0';
        for (auto direction:directions) {
            dfs(grid, i + direction.first, j + direction.second);
        }
    }
};

class Solution {

private:

const vector<pair<int, int>> directions{{0, 1},

{0, -1},

{1, 0},

{-1, 0}};

public:

int numIslands(vector<vector<char>> &grid) {

int num_island = 0;

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

for (int j = 0; j < grid[0].size(); j++) {

if (grid[i][j] == '1') {

num_island++;

dfs(grid, i, j);

}

return num_island;

}

void dfs(vector<vector<char>> &grid, int i, int j) {

if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != '1')

return;

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

for (auto direction:directions) {

dfs(grid, i + direction.first, j + direction.second);

}

};

695. 岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

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

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

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

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

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

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

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

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

对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

public class Sixhundred_ninetyFive {
    /**
     * 和200题几乎完全一样，只是该题需要返回值而已
     */
    private int[][] directions = new int[][]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1)
                    maxArea = Math.max(maxArea, dfs(grid, i, j));
            }
        }
        return maxArea;
    }

    public int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0)
            return 0;
        int area = 1;
        grid[i][j] = 0;//不用回溯，下次从别的地方也不用再次访问
        for (int[] direction : directions) {
            area += dfs(grid, i + direction[0], j + direction[1]);
        }
        return area;
    }
}

public class Sixhundred_ninetyFive {

/**

* 和200题几乎完全一样，只是该题需要返回值而已

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

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

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

return 0;

int maxArea = 0;

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

for (int j = 0; j < grid[0].length; j++) {

if (grid[i][j] == 1)

maxArea = Math.max(maxArea, dfs(grid, i, j));

}

return maxArea;

}

public int dfs(int[][] grid, int i, int j) {

if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0)

return 0;

int area = 1;

grid[i][j] = 0;//不用回溯，下次从别的地方也不用再次访问

for (int[] direction : directions) {

area += dfs(grid, i + direction[0], j + direction[1]);

}

return area;

}

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        if (grid.empty() || grid[0].empty())
            return 0;
        int max_area = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    int temp = 0;
                    dfs(grid, i, j, temp);
                    if (max_area < temp)
                        max_area = temp;
                }
            }
        }
        return max_area;
    }

    void dfs(vector<vector<int>> &grid, int i, int j, int &temp) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != 1)
            return;
        temp += 1;
        grid[i][j] = 2;//避免再次访问；不能回溯
        dfs(grid, i + 1, j, temp);
        dfs(grid, i - 1, j, temp);
        dfs(grid, i, j + 1, temp);
        dfs(grid, i, j - 1, temp);
    }
};

class Solution {

public:

int maxAreaOfIsland(vector<vector<int>> &grid) {

if (grid.empty() || grid[0].empty())

return 0;

int max_area = 0;

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

for (int j = 0; j < grid[0].size(); j++) {

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

int temp = 0;

dfs(grid, i, j, temp);

if (max_area < temp)

max_area = temp;

}

return max_area;

}

void dfs(vector<vector<int>> &grid, int i, int j, int &temp) {

if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != 1)

return;

temp += 1;

grid[i][j] = 2;//避免再次访问；不能回溯

dfs(grid, i + 1, j, temp);

dfs(grid, i - 1, j, temp);

dfs(grid, i, j + 1, temp);

dfs(grid, i, j - 1, temp);

}

};

547. 朋友圈

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:

输入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
注意：

N 在[1,200]的范围内。
对于所有学生，有M[i][i] = 1。
如果有M[i][j] = 1，则有M[j][i] = 1。

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入:

[[1,1,0],

[1,1,0],

[0,0,1]]

输出: 2

说明：已知学生0和学生1互为朋友，他们在一个朋友圈。

第2个学生自己在一个朋友圈。所以返回2。

示例 2:

输入:

[[1,1,0],

[1,1,1],

[0,1,1]]

输出: 1

说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

注意：

N 在[1,200]的范围内。

对于所有学生，有M[i][i] = 1。

如果有M[i][j] = 1，则有M[j][i] = 1。

package gongel_first;

public class Fivehundred_fortySeven {
    /**
     * 法一：DFS
     * 求连通图的数量，可以画邻接表
     * 与 200 岛屿问题 有不同的地方，连通图问题和上色问题的区别
     * 本题：[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] ---->1
     * 200题：[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] ---->4
     */
    public void dfs(int[][] M, int i, boolean[] visited) {
        visited[i] = true;
        for (int j = 0; j < M.length; j++) {
            if (!visited[j] && M[i][j] == 1) {
                dfs(M, j, visited);
            }
        }
    }

    public int findCircleNum(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0)
            return 0;
        int m = M.length;
        int circleNums = 0;
        boolean[] visited = new boolean[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i]) {
                    circleNums += 1;
                    dfs(M, i, visited);
                }
            }
        }
        return circleNums;
    }

    /**
     * 法二：并查集：https://gongel.cn/?p=312
     */
    private int findFather(int[] father, int son) {
        while (son != father[son]) {//初始化时自己为自己的父亲，如果现在自己不是自己的父亲， 说明自己找到了真正的父亲，那需要一直循环找到祖先
            son = father[son];
        }
        return son;
    }

    public int findCircleNum2(int[][] M) {
        if (M == null || M.length == 0 || M[0].length == 0)
            return 0;
        int[] father = new int[200];
        int numFriends = 0;
        //初始化
        for (int i = 0; i < M.length; i++)
            father[i] = i;
        for (int i = 0; i < M.length; i++) {
            for (int j = i + 1; j < M.length; j++) {//只需要考虑上三角矩阵，因为这是无向图----对称矩阵
                if (M[i][j] == 1) {
                    int fatherI = findFather(father, i);
                    int fatherJ = findFather(father, j);
                    if (fatherI != fatherJ)
                        father[fatherI] = fatherJ;
                }
            }
        }
        for (int i = 0; i < M.length; i++) {
            if (father[i] == i)
                numFriends++;
        }
        return numFriends;
    }
}

package gongel_first;

public class Fivehundred_fortySeven {

/**

* 法一：DFS

* 求连通图的数量，可以画邻接表

* 与 200 岛屿问题有不同的地方，连通图问题和上色问题的区别

* 本题：[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] ---->1

* 200题：[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]] ---->4

public void dfs(int[][] M, int i, boolean[] visited) {

visited[i] = true;

for (int j = 0; j < M.length; j++) {

if (!visited[j] && M[i][j] == 1) {

dfs(M, j, visited);

}

public int findCircleNum(int[][] M) {

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

return 0;

int m = M.length;

int circleNums = 0;

boolean[] visited = new boolean[m];

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

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

if (!visited[i]) {

circleNums += 1;

dfs(M, i, visited);

}

return circleNums;

}

/**

* 法二：并查集：https://gongel.cn/?p=312

private int findFather(int[] father, int son) {

while (son != father[son]) {//初始化时自己为自己的父亲，如果现在自己不是自己的父亲，说明自己找到了真正的父亲，那需要一直循环找到祖先

son = father[son];

}

return son;

}

public int findCircleNum2(int[][] M) {

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

return 0;

int[] father = new int[200];

int numFriends = 0;

//初始化

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

father[i] = i;

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

for (int j = i + 1; j < M.length; j++) {//只需要考虑上三角矩阵，因为这是无向图----对称矩阵

if (M[i][j] == 1) {

int fatherI = findFather(father, i);

int fatherJ = findFather(father, j);

if (fatherI != fatherJ)

father[fatherI] = fatherJ;

}

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

if (father[i] == i)

numFriends++;

}

return numFriends;

}

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发。

说明:

如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
所有的机场都用三个大写字母表示（机场代码）。
假定所有机票至少存在一种合理的行程。
示例 1:

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
示例 2:

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发。

说明:

如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前

所有的机场都用三个大写字母表示（机场代码）。

假定所有机票至少存在一种合理的行程。

示例 1:

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]

输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]

示例 2:

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]

解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

/**
     * 用DFS回溯需要考虑一堆问题：
     * 1.目的地需要排序
     * 2.使用过的行程不能再使用
     */
    private List<String> ans;
    private Map<String, PriorityQueue<String>> map = new HashMap<>();//保存相同出发地的所有目的地（按字母序）

    public List<String> findItinerary(List<List<String>> tickets) {
        ans = new ArrayList<>();
        if (tickets == null || tickets.size() == 0)
            return ans;
        for (List<String> ticket : tickets) {
            String src = ticket.get(0);
            String dst = ticket.get(1);
            if (!map.containsKey(src)) {
                PriorityQueue<String> pq = new PriorityQueue<>();
                map.put(src, pq);
            }
            map.get(src).add(dst);
        }
        dfs("JFK");
        Collections.reverse(ans);
        return ans;

    }

    private void dfs(String src) {
        PriorityQueue<String> pq = map.get(src);
        if (pq != null) {
            while (!pq.isEmpty()) {
                dfs(pq.poll());
            }
        }
        ans.add(src);
    }

/**

* 用DFS回溯需要考虑一堆问题：

* 1.目的地需要排序

* 2.使用过的行程不能再使用

private List<String> ans;

private Map<String, PriorityQueue<String>> map = new HashMap<>();//保存相同出发地的所有目的地（按字母序）

public List<String> findItinerary(List<List<String>> tickets) {

ans = new ArrayList<>();

if (tickets == null || tickets.size() == 0)

return ans;

for (List<String> ticket : tickets) {

String src = ticket.get(0);

String dst = ticket.get(1);

if (!map.containsKey(src)) {

PriorityQueue<String> pq = new PriorityQueue<>();

map.put(src, pq);

}

map.get(src).add(dst);

}

dfs("JFK");

Collections.reverse(ans);

return ans;

}

private void dfs(String src) {

PriorityQueue<String> pq = map.get(src);

if (pq != null) {

while (!pq.isEmpty()) {

dfs(pq.poll());

}

ans.add(src);

}

class Solution {
public:
    //欧拉路径（https://www.cnblogs.com/vocaloid01/p/9514023.html）
    vector<string> findItinerary(vector<vector<string>> &tickets) {
        unordered_map<string, multiset<string>> from_to;//multiset相当于小根堆
        for (auto ticket:tickets)
            from_to[ticket[0]].insert(ticket[1]);
        vector<string> ans;
        dfs("JFK", from_to, ans);
        return vector<string>(ans.rbegin(), ans.rend());

    }

    void dfs(string from, unordered_map<string, multiset<string>> &from_to, vector<string> &ans) {
        while (from_to[from].size() != 0) {
            string next = *from_to[from].begin();
            from_to[from].erase(from_to[from].begin());//可能存在相同的地点，所以只能erase迭代器
            dfs(next, from_to, ans);
        }
        ans.push_back(from);//一定倒着存,将孤立节点放在最后访问。题目保证一定会有路径
    }
};

class Solution {

public:

//欧拉路径（https://www.cnblogs.com/vocaloid01/p/9514023.html）

vector<string> findItinerary(vector<vector<string>> &tickets) {

unordered_map<string, multiset<string>> from_to;//multiset相当于小根堆

for (auto ticket:tickets)

from_to[ticket[0]].insert(ticket[1]);

vector<string> ans;

dfs("JFK", from_to, ans);

return vector<string>(ans.rbegin(), ans.rend());

}

void dfs(string from, unordered_map<string, multiset<string>> &from_to, vector<string> &ans) {

while (from_to[from].size() != 0) {

string next = *from_to[from].begin();

from_to[from].erase(from_to[from].begin());//可能存在相同的地点，所以只能erase迭代器

dfs(next, from_to, ans);

}

ans.push_back(from);//一定倒着存,将孤立节点放在最后访问。题目保证一定会有路径

}

};

79. 单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =

[

['A','B','C','E'],

['S','F','C','S'],

['A','D','E','E']

]

给定 word = "ABCCED", 返回 true.

给定 word = "SEE", 返回 true.

给定 word = "ABCB", 返回 false.

public boolean exist2(char[][] board, String word) {
//和695、200差不多
        boolean result;
        boolean[][] visited=new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    result = dfs2(board, word, i, j, 0,visited);
                    if (result) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private static boolean dfs2(char[][] board, String word, int i, int j, int index,boolean[][] visited) {
        if (index == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length|| visited[i][j]) {
            return false;
        }
        if (board[i][j] != word.charAt(index)) {
            return false;
        }

        boolean result;
        visited[i][j]=true;//标记已经访问：不会回溯
        result = dfs2(board, word, i - 1, j, index + 1,visited)
                || dfs2(board, word, i + 1, j, index + 1,visited)
                || dfs2(board, word, i, j - 1, index + 1,visited)
                || dfs2(board, word, i, j + 1, index + 1,visited);
        visited[i][j]=false;//恢复未访问
        return result;
    }

public boolean exist2(char[][] board, String word) {

//和695、200差不多

boolean result;

boolean[][] visited=new boolean[board.length][board[0].length];

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

for (int j = 0; j < board[i].length; j++) {

if (board[i][j] == word.charAt(0)) {

result = dfs2(board, word, i, j, 0,visited);

if (result) {

return true;

}

return false;

}

private static boolean dfs2(char[][] board, String word, int i, int j, int index,boolean[][] visited) {

if (index == word.length()) {

return true;

}

if (i < 0 || i >= board.length || j < 0 || j >= board[i].length|| visited[i][j]) {

return false;

}

if (board[i][j] != word.charAt(index)) {

return false;

}

boolean result;

visited[i][j]=true;//标记已经访问：不会回溯

result = dfs2(board, word, i - 1, j, index + 1,visited)

|| dfs2(board, word, i + 1, j, index + 1,visited)

|| dfs2(board, word, i, j - 1, index + 1,visited)

|| dfs2(board, word, i, j + 1, index + 1,visited);

visited[i][j]=false;//恢复未访问

return result;

}

class Solution {
public:
    bool exist(vector<vector<char>> &board, string word) {
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (board[i][j] == word[0])
                    if (dfs(board, word.substr(0), i, j, visited))
                        return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>> &board, string word, int i, int j, vector<vector<bool>> &visited) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || word[0] != board[i][j] || visited[i][j])
            return false;
        if (word.size() == 1 && word[0] == board[i][j])
            return true;
        visited[i][j] = true;
        bool result = dfs(board, word.substr(1), i - 1, j, visited) || dfs(board, word.substr(1), i + 1, j, visited) ||
                      dfs(board, word.substr(1), i, j + 1, visited) || dfs(board, word.substr(1), i, j - 1, visited);
        visited[i][j] = false;
        return result;
    }
};

class Solution {

public:

bool exist(vector<vector<char>> &board, string word) {

vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));

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

for (int j = 0; j < board[0].size(); j++) {

if (board[i][j] == word[0])

if (dfs(board, word.substr(0), i, j, visited))

return true;

}

return false;

}

bool dfs(vector<vector<char>> &board, string word, int i, int j, vector<vector<bool>> &visited) {

if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || word[0] != board[i][j] || visited[i][j])

return false;

if (word.size() == 1 && word[0] == board[i][j])

return true;

visited[i][j] = true;

bool result = dfs(board, word.substr(1), i - 1, j, visited) || dfs(board, word.substr(1), i + 1, j, visited) ||

dfs(board, word.substr(1), i, j + 1, visited) || dfs(board, word.substr(1), i, j - 1, visited);

visited[i][j] = false;

return result;

}

};

417. 太平洋大西洋水流问题

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

 

提示：

输出坐标的顺序不重要
m 和 n 都小于150
 

示例：

 

给定下面的 5x5 矩阵:

  太平洋 ~   ~   ~   ~   ~ 
       ~  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  *
          *   *   *   *   * 大西洋

返回:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

提示：

输出坐标的顺序不重要

m 和 n 都小于150

示例：

给定下面的 5x5 矩阵:

太平洋 ~ ~ ~ ~ ~

~ 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 *

* * * * * 大西洋

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

public class Fourhundred_seventeen {
    /**
     *  反向思维---DFS
     *  依题意，最左边和最上面可以流向太平洋，最右边和最下面可以流向大西洋
     *  那么，可以从最左边和最上面开始dfs所有可以到达的山脉，即为可以流向太平洋的山脉
     *  从最右边和最下面开始dfs所有可以到达的山脉，即为可以流向大西洋的山脉
     *  注意：此时dfs的方向为从高度低的山脉向高度高的山脉走
     *  参考：https://leetcode-cn.com/problems/pacific-atlantic-water-flow/comments/36773
     */
    public List<List<Integer>> pacificAtlantic2(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return ans;
        m = matrix.length;
        n = matrix[0].length;
        boolean[][] reachPacific = new boolean[m][n];
        boolean[][] reachAtlantic = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(matrix, i, 0, reachPacific);//从最左出发判断是否可到达Pacific
            dfs(matrix, i, n - 1, reachAtlantic);//从最右出发判断是否可达到Atlantic
        }
        for (int j = 0; j < n; j++) {
            dfs(matrix, 0, j, reachPacific);//从最上出发判断是否可到到Pacific
            dfs(matrix, m - 1, j, reachAtlantic);//从最下出发判断是否可到达Atlantic
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (reachPacific[i][j] && reachAtlantic[i][j]) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    ans.add(temp);
                }
            }
        }
        return ans;
    }

    private void dfs(int[][] matrix, int startX, int startY, boolean[][] reach) {
        if (startX < 0 || startX > m || startY < 0 || startY > n || reach[startX][startY])
            return;
        reach[startX][startY] = true;
        for (int i = 0; i < 4; i++) {
            int newstartX = startX + direction[i][0];
            int newstartY = startY + direction[i][1];
            if (isValid(newstartX, newstartY) && matrix[newstartX][newstartY] >= matrix[startX][startY])
                dfs(matrix, newstartX, newstartY, reach);
        }
    }

}

public class Fourhundred_seventeen {

/**

* 反向思维---DFS

* 依题意，最左边和最上面可以流向太平洋，最右边和最下面可以流向大西洋

* 那么，可以从最左边和最上面开始dfs所有可以到达的山脉，即为可以流向太平洋的山脉

* 从最右边和最下面开始dfs所有可以到达的山脉，即为可以流向大西洋的山脉

* 注意：此时dfs的方向为从高度低的山脉向高度高的山脉走

* 参考：https://leetcode-cn.com/problems/pacific-atlantic-water-flow/comments/36773

public List<List<Integer>> pacificAtlantic2(int[][] matrix) {

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

return ans;

m = matrix.length;

n = matrix[0].length;

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

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

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

dfs(matrix, i, 0, reachPacific);//从最左出发判断是否可到达Pacific

dfs(matrix, i, n - 1, reachAtlantic);//从最右出发判断是否可达到Atlantic

}

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

dfs(matrix, 0, j, reachPacific);//从最上出发判断是否可到到Pacific

dfs(matrix, m - 1, j, reachAtlantic);//从最下出发判断是否可到达Atlantic

}

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

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

if (reachPacific[i][j] && reachAtlantic[i][j]) {

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

temp.add(i);

temp.add(j);

ans.add(temp);

}

return ans;

}

private void dfs(int[][] matrix, int startX, int startY, boolean[][] reach) {

if (startX < 0 || startX > m || startY < 0 || startY > n || reach[startX][startY])

return;

reach[startX][startY] = true;

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

int newstartX = startX + direction[i][0];

int newstartY = startY + direction[i][1];

if (isValid(newstartX, newstartY) && matrix[newstartX][newstartY] >= matrix[startX][startY])

dfs(matrix, newstartX, newstartY, reach);

}

class Solution {
private:
    const vector<pair<int, int>> directions{{0,  1},
                                            {0,  -1},
                                            {1,  0},
                                            {-1, 0}};
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>> &matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0)
            return vector<vector<int>>{};
        vector<vector<bool>> reach_pacific(matrix.size(), vector<bool>(matrix[0].size(), false));
        vector<vector<bool>> reach_atlantic(matrix.size(), vector<bool>(matrix[0].size(), false));
        for (int i = 0; i < matrix.size(); i++) {
            dfs(matrix, i, 0, reach_pacific);
            dfs(matrix, i, matrix[0].size() - 1, reach_atlantic);
        }
        for (int j = 0; j < matrix[0].size(); j++) {
            dfs(matrix, 0, j, reach_pacific);
            dfs(matrix, matrix.size() - 1, j, reach_atlantic);
        }
        vector<vector<int>> ans;
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (reach_atlantic[i][j] && reach_pacific[i][j]) {
                    ans.push_back({i, j});
                }
            }
        }
        return ans;
    }

    void dfs(vector<vector<int>> &matrix, int x, int y, vector<vector<bool>> &reach) {
        if (x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size() || reach[x][y])
            return;
        reach[x][y] = true;
        for (auto direction:directions) {
            int new_x = x + direction.first;
            int new_y = y + direction.second;
            if (new_x >= 0 && new_x < matrix.size() && new_y >= 0 && new_y < matrix[0].size()) {
                if (matrix[new_x][new_y] >= matrix[x][y])
                    dfs(matrix, new_x, new_y, reach);
            }
        }
    }
};

class Solution {

private:

const vector<pair<int, int>> directions{{0, 1},

{0, -1},

{1, 0},

{-1, 0}};

public:

vector<vector<int>> pacificAtlantic(vector<vector<int>> &matrix) {

if (matrix.size() == 0 || matrix[0].size() == 0)

return vector<vector<int>>{};

vector<vector<bool>> reach_pacific(matrix.size(), vector<bool>(matrix[0].size(), false));

vector<vector<bool>> reach_atlantic(matrix.size(), vector<bool>(matrix[0].size(), false));

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

dfs(matrix, i, 0, reach_pacific);

dfs(matrix, i, matrix[0].size() - 1, reach_atlantic);

}

for (int j = 0; j < matrix[0].size(); j++) {

dfs(matrix, 0, j, reach_pacific);

dfs(matrix, matrix.size() - 1, j, reach_atlantic);

}

vector<vector<int>> ans;

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

for (int j = 0; j < matrix[0].size(); j++) {

if (reach_atlantic[i][j] && reach_pacific[i][j]) {

ans.push_back({i, j});

}

return ans;

}

void dfs(vector<vector<int>> &matrix, int x, int y, vector<vector<bool>> &reach) {

if (x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size() || reach[x][y])

return;

reach[x][y] = true;

for (auto direction:directions) {

int new_x = x + direction.first;

int new_y = y + direction.second;

if (new_x >= 0 && new_x < matrix.size() && new_y >= 0 && new_y < matrix[0].size()) {

if (matrix[new_x][new_y] >= matrix[x][y])

dfs(matrix, new_x, new_y, reach);

}

};

133. 克隆图

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。

示例：



输入：
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解释：
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
 

提示：

节点数介于 1 到 100 之间。
无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
必须将给定节点的拷贝作为对克隆图的引用返回。

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int）和其邻居的列表（list[Node]）。

示例：

输入：

{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解释：

节点 1 的值是 1，它有两个邻居：节点 2 和 4 。

节点 2 的值是 2，它有两个邻居：节点 1 和 3 。

节点 3 的值是 3，它有两个邻居：节点 2 和 4 。

节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

提示：

节点数介于 1 到 100 之间。

无向图是一个简单图，这意味着图中没有重复的边，也没有自环。

由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。

必须将给定节点的拷贝作为对克隆图的引用返回。

package main.gongel_first;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
    }

    public Node(int _val, List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Onehundred_thirtyThree {
    /**
     * 深拷贝就是对于所有的指针成员，不能仅仅是赋值，还有重新分配空间
     */
    private Map<Node, Node> map;

    public Node cloneGraph(Node node) {
        map = new HashMap<>();
        return dfs(node);
    }

    public Node dfs(Node node) {
        if (!map.containsKey(node)) {//防止成环
            Node copy = new Node(node.val, new ArrayList<Node>());
            map.put(node, copy);
            for (Node neibor : node.neighbors) {
                copy.neighbors.add(dfs(neibor));
            }
        }
        return map.get(node);
    }
}

package main.gongel_first;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

class Node {

public int val;

public List<Node> neighbors;

public Node() {

}

public Node(int _val, List<Node> _neighbors) {

val = _val;

neighbors = _neighbors;

}

public class Onehundred_thirtyThree {

/**

* 深拷贝就是对于所有的指针成员，不能仅仅是赋值，还有重新分配空间

private Map<Node, Node> map;

public Node cloneGraph(Node node) {

map = new HashMap<>();

return dfs(node);

}

public Node dfs(Node node) {

if (!map.containsKey(node)) {//防止成环

Node copy = new Node(node.val, new ArrayList<Node>());

map.put(node, copy);

for (Node neibor : node.neighbors) {

copy.neighbors.add(dfs(neibor));

}

return map.get(node);

}

class Node {
public:
    int val;
    vector<Node *> neighbors;

    Node() {
        val = 0;
        neighbors = vector<Node *>();
    }

    Node(int _val) {
        val = _val;
        neighbors = vector<Node *>();
    }

    Node(int _val, vector<Node *> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

class Solution {
//和138. 复制带随机指针的链表 相似
private:
    unordered_map<Node *, Node *> map;//存着节点和他自己的拷贝
public:
    Node *cloneGraph(Node *node) {
        if (node == nullptr)
            return nullptr;
        return dfs(node);
    }

    Node *dfs(Node *node) {
        if (map.count(node) == 0) {
            Node *copy = new Node(node->val, vector<Node *>());
            map[node] = copy;
            for (Node *neighbor:node->neighbors) {
                copy->neighbors.push_back(dfs(neighbor));
            }
        }
        return map[node];
    }
};

class Node {

public:

int val;

vector<Node *> neighbors;

Node() {

val = 0;

neighbors = vector<Node *>();

}

Node(int _val) {

val = _val;

neighbors = vector<Node *>();

}

Node(int _val, vector<Node *> _neighbors) {

val = _val;

neighbors = _neighbors;

}

};

class Solution {

//和138. 复制带随机指针的链表相似

private:

unordered_map<Node *, Node *> map;//存着节点和他自己的拷贝

public:

Node *cloneGraph(Node *node) {

if (node == nullptr)

return nullptr;

return dfs(node);

}

Node *dfs(Node *node) {

if (map.count(node) == 0) {

Node *copy = new Node(node->val, vector<Node *>());

map[node] = copy;

for (Node *neighbor:node->neighbors) {

copy->neighbors.push_back(dfs(neighbor));

}

return map[node];

}

};

473. 火柴拼正方形

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:

输入: [3,3,3,3,4]
输出: false

解释: 不能用所有火柴拼成一个正方形。
注意:

给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

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

输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:

输入: [3,3,3,3,4]

输出: false

解释: 不能用所有火柴拼成一个正方形。

注意:

给定的火柴长度和在 0 到 10^9之间。

火柴数组的长度不超过15。

package gongel_first;

public class Fourhundred_seventyThree {
    /**
     * DFS自己去寻找最优解
     * 和494题相同
     */
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length == 0)
            return false;
        int sum = 0;
        for (int num : nums)
            sum += num;
        if (sum / 4 * 4 != sum)
            return false;
        //每个边的长度初始化为0
        return dfs(0, nums, 0, 0, 0, 0, sum / 4);
    }

    private boolean dfs(int i, int[] nums, int up, int down, int left, int right, int len) {
        if (i == nums.length)
            return up == len && down == len && left == len && right == len;
        if (up > len || down > len || left > len || right > len)
            return false;
        //对每个边进行加和，一旦满足则返回
        return dfs(i + 1, nums, up + nums[i], down, left, right, len) || dfs(i + 1, nums, up, down + nums[i], left, right, len) || dfs(i + 1, nums, up, down, left + nums[i], right, len) || dfs(i + 1, nums, up, down, left, right + nums[i], len);
    }
}

package gongel_first;

public class Fourhundred_seventyThree {

/**

* DFS自己去寻找最优解

* 和494题相同

public boolean makesquare(int[] nums) {

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

return false;

int sum = 0;

for (int num : nums)

sum += num;

if (sum / 4 * 4 != sum)

return false;

//每个边的长度初始化为0

return dfs(0, nums, 0, 0, 0, 0, sum / 4);

}

private boolean dfs(int i, int[] nums, int up, int down, int left, int right, int len) {

if (i == nums.length)

return up == len && down == len && left == len && right == len;

if (up > len || down > len || left > len || right > len)

return false;

//对每个边进行加和，一旦满足则返回

return dfs(i + 1, nums, up + nums[i], down, left, right, len) || dfs(i + 1, nums, up, down + nums[i], left, right, len) || dfs(i + 1, nums, up, down, left + nums[i], right, len) || dfs(i + 1, nums, up, down, left, right + nums[i], len);

}

class Solution {
public:
    bool makesquare(vector<int> &nums) {
        if (nums.empty())
            return false;
        int sum = 0;
        for (int num:nums)
            sum += num;
        if (sum / 4 * 4 != sum)
            return false;
        return dfs(0, nums, 0, 0, 0, 0, sum / 4);
    }

    bool dfs(int index, vector<int> &nums, int up, int down, int left, int right, int len) {
        if (index == nums.size())
            return up == len && down == len && left == len && right == len;
        if (up > len || down > len || left > len || right > len)
            return false;
        //不提前判断会超时
        return ((up + nums[index] <= len) && dfs(index + 1, nums, up + nums[index], down, left, right, len)) ||
               ((down + nums[index] <= len) && dfs(index + 1, nums, up, down + nums[index], left, right, len)) ||
               ((left + nums[index] <= len) && dfs(index + 1, nums, up, down, left + nums[index], right, len)) ||
               ((right + nums[index] <= len) && dfs(index + 1, nums, up, down, left, right + nums[index], len));
    }
};

class Solution {

public:

bool makesquare(vector<int> &nums) {

if (nums.empty())

return false;

int sum = 0;

for (int num:nums)

sum += num;

if (sum / 4 * 4 != sum)

return false;

return dfs(0, nums, 0, 0, 0, 0, sum / 4);

}

bool dfs(int index, vector<int> &nums, int up, int down, int left, int right, int len) {

if (index == nums.size())

return up == len && down == len && left == len && right == len;

if (up > len || down > len || left > len || right > len)

return false;

//不提前判断会超时

return ((up + nums[index] <= len) && dfs(index + 1, nums, up + nums[index], down, left, right, len)) ||

((down + nums[index] <= len) && dfs(index + 1, nums, up, down + nums[index], left, right, len)) ||

((left + nums[index] <= len) && dfs(index + 1, nums, up, down, left + nums[index], right, len)) ||

((right + nums[index] <= len) && dfs(index + 1, nums, up, down, left, right + nums[index], len));

}

};

494. 目标和

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。
注意:

数组的长度不会超过20，并且数组中的值全为正数。
初始的数组的和不会超过1000。
保证返回的最终结果为32位整数。

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3

输出: 5

解释:

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

注意:

数组的长度不会超过20，并且数组中的值全为正数。

初始的数组的和不会超过1000。

保证返回的最终结果为32位整数。

package gongel_first;

public class Fourhundred_ninetyFour {
    public int findTargetSumWays(int[] nums, int S) {
        /**
         * 法一：dp
         sum(P) 前面符号为加号的集合；sum(N) 前面符号为减号的集合
         * 所以题目可以转化为
         * sum(P) - sum(N) = target
         * => sum(nums) + sum(P) - sum(N) = target + sum(nums)
         * => 2 * sum(P) = target + sum(nums)
         * => sum(P) = (target + sum(nums)) / 2
         * 因此题目转化为01背包，也就是能组合成容量为sum(P)的方式有多少种*/
        if (nums == null || nums.length == 0)
            return 0;
        int sum = 0;
        for (int num : nums)
            sum += num;
        if (sum < S || (((S) + sum) & 1) == 1)//target + sum(nums)必须为偶数
            return 0;
        int w = (S + sum) / 2;
        int[] dp = new int[w + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = w; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[w];
    }

    /**
     * 法二：DFS，和473题相同
     */
    public int findTargetSumWays2(int[] nums, int S) {
        if (nums == null || nums.length == 0)
            return 0;
        return dfs(nums, 0, 0, S);
    }

    private int dfs(int[] nums, int index, int sum, int target) {
        if (index == nums.length)
            return target == sum ? 1 : 0;//找到则最终结果加1
        return dfs(nums, index + 1, sum + nums[index], target) + dfs(nums, index + 1, sum - nums[index], target);
    }
}

package gongel_first;

public class Fourhundred_ninetyFour {

public int findTargetSumWays(int[] nums, int S) {

/**

* 法一：dp

sum(P) 前面符号为加号的集合；sum(N) 前面符号为减号的集合

* 所以题目可以转化为

* sum(P) - sum(N) = target

* => sum(nums) + sum(P) - sum(N) = target + sum(nums)

* => 2 * sum(P) = target + sum(nums)

* => sum(P) = (target + sum(nums)) / 2

* 因此题目转化为01背包，也就是能组合成容量为sum(P)的方式有多少种*/

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

return 0;

int sum = 0;

for (int num : nums)

sum += num;

if (sum < S || (((S) + sum) & 1) == 1)//target + sum(nums)必须为偶数

return 0;

int w = (S + sum) / 2;

int[] dp = new int[w + 1];

dp[0] = 1;

for (int num : nums) {

for (int j = w; j >= num; j--) {

dp[j] += dp[j - num];

}

return dp[w];

}

/**

* 法二：DFS，和473题相同

public int findTargetSumWays2(int[] nums, int S) {

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

return 0;

return dfs(nums, 0, 0, S);

}

private int dfs(int[] nums, int index, int sum, int target) {

if (index == nums.length)

return target == sum ? 1 : 0;//找到则最终结果加1

return dfs(nums, index + 1, sum + nums[index], target) + dfs(nums, index + 1, sum - nums[index], target);

}

class Solution {
public:
    int findTargetSumWays(vector<int> &nums, int S) {
        if (nums.empty())
            return 0;
        return dfs(nums, 0, 0, S);
    }

    int dfs(vector<int> &nums, int index, int sum, int target) {
        if (index == nums.size())
            return sum == target ? 1 : 0;
        return dfs(nums, index + 1, sum + nums[index], target) + dfs(nums, index + 1, sum - nums[index], target);
    }
};

class Solution {

public:

int findTargetSumWays(vector<int> &nums, int S) {

if (nums.empty())

return 0;

return dfs(nums, 0, 0, S);

}

int dfs(vector<int> &nums, int index, int sum, int target) {

if (index == nums.size())

return sum == target ? 1 : 0;

return dfs(nums, index + 1, sum + nums[index], target) + dfs(nums, index + 1, sum - nums[index], target);

}

};

BFS

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

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

public class NInehundred_ninetyFour {
    private int[][] directions = new int[][]{{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;
        int m = grid.length;
        int n = grid[0].length;
        Deque<int[]> deque = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    int[] node = new int[]{i, j};
                    deque.addLast(node);
                }
            }
        }
        int ans = 0;
        while (!deque.isEmpty()) {
            ans++;
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                int[] node = deque.pollFirst();
                for (int[] direction : directions) {
                    int row = node[0] + direction[0];
                    int col = node[1] + direction[1];
                    if (row >= 0 && row < m && col >= 0 && col < n && grid[row][col] == 1) {
                        grid[row][col] = 2;//相当于visited防止再次访问
                        int[] newNode = new int[]{row, col};
                        deque.addLast(newNode);
                    }
                }
            }
        }
        for (int[] row : grid) {
            for (int v : row)
                if (v == 1)
                    return -1;
        }
        if (ans == 0)
            return 0;
        return ans - 1;
    }
}

import java.util.Deque;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.Map;

public class NInehundred_ninetyFour {

private int[][] directions = new int[][]{{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;

int m = grid.length;

int n = grid[0].length;

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

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

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

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

int[] node = new int[]{i, j};

deque.addLast(node);

}

int ans = 0;

while (!deque.isEmpty()) {

ans++;

int size = deque.size();

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

int[] node = deque.pollFirst();

for (int[] direction : directions) {

int row = node[0] + direction[0];

int col = node[1] + direction[1];

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

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

int[] newNode = new int[]{row, col};

deque.addLast(newNode);

}

for (int[] row : grid) {

for (int v : row)

if (v == 1)

return -1;

}

if (ans == 0)

return 0;

return ans - 1;

}

class Solution {
public:
    int orangesRotting(vector<vector<int>> &grid) {
        vector<pair<int, int>> directions{{0,  -1},
                                          {0,  1},
                                          {-1, 0},
                                          {1,  0}};
        queue<pair<int, int>> queue;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 2)
                    queue.push({i, j});
            }
        }
        int ans = 0;
        while (!queue.empty()) {
            ans++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                auto node = queue.front();
                queue.pop();
                for (auto direction:directions) {
                    int x = node.first + direction.first;
                    int y = node.second + direction.second;
                    if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == 1) {
                        grid[x][y] = 2;
                        queue.push({x, y});
                    }
                }
            }
        }
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1)
                    return -1;
            }
        }
        if (ans == 0)
            return 0;
        else
            return ans - 1;//本来就腐烂的也算在里面了
    }
};

class Solution {

public:

int orangesRotting(vector<vector<int>> &grid) {

vector<pair<int, int>> directions{{0, -1},

{0, 1},

{-1, 0},

{1, 0}};

queue<pair<int, int>> queue;

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

for (int j = 0; j < grid[0].size(); j++) {

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

queue.push({i, j});

}

int ans = 0;

while (!queue.empty()) {

ans++;

int size = queue.size();

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

auto node = queue.front();

queue.pop();

for (auto direction:directions) {

int x = node.first + direction.first;

int y = node.second + direction.second;

if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == 1) {

grid[x][y] = 2;

queue.push({x, y});

}

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

for (int j = 0; j < grid[0].size(); j++) {

if (grid[i][j] == 1)

return -1;

}

if (ans == 0)

return 0;

else

return ans - 1;//本来就腐烂的也算在里面了

}

};

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

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;
        Deque<int[]> deque = new LinkedList<>();
        deque.addLast(new int[]{0, 0});
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                int[] node = deque.pollFirst();
                if (node[0] == m - 1 && node[1] == n - 1)//从队列里拿出来判断比入队时判断要好
                    return depth;
                for (int[] direction : directions) {
                    int x = node[0] + direction[0];
                    int y = node[1] + direction[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0) {
                        deque.addLast(new int[]{x, y});
                        grid[x][y] = 1;
                    }
                }
            }
        }
        return -1;
    }
}

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;

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

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

int depth = 0;

while (!deque.isEmpty()) {

int size = deque.size();

depth++;

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

int[] node = deque.pollFirst();

if (node[0] == m - 1 && node[1] == n - 1)//从队列里拿出来判断比入队时判断要好

return depth;

for (int[] direction : directions) {

int x = node[0] + direction[0];

int y = node[1] + direction[1];

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

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

grid[x][y] = 1;

}

return -1;

}

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>> &grid) {
        if (grid[0][0] == 1)
            return -1;
        vector<pair<int, int>> directions{{0,  -1},
                                          {0,  1},
                                          {-1, 0},
                                          {1,  0},
                                          {1,  -1},
                                          {1,  1},
                                          {-1, 1},
                                          {-1, -1}};
        queue<pair<int, int>> queue;
        queue.push({0, 0});
        int ans = 0;
        while (!queue.empty()) {
            ans++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                auto node = queue.front();
                queue.pop();
                if (node.first == grid.size() - 1 && node.second == grid[0].size() - 1)
                    return ans;
                for (auto direction:directions) {
                    int x = node.first + direction.first;
                    int y = node.second + direction.second;
                    if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == 0) {
                        queue.push({x, y});
                        grid[x][y] = 1;//避免再次访问
                    }
                }
            }
        }
        return -1;
    }
};

class Solution {

public:

int shortestPathBinaryMatrix(vector<vector<int>> &grid) {

if (grid[0][0] == 1)

return -1;

vector<pair<int, int>> directions{{0, -1},

{0, 1},

{-1, 0},

{1, 0},

{1, -1},

{1, 1},

{-1, 1},

{-1, -1}};

queue<pair<int, int>> queue;

queue.push({0, 0});

int ans = 0;

while (!queue.empty()) {

ans++;

int size = queue.size();

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

auto node = queue.front();

queue.pop();

if (node.first == grid.size() - 1 && node.second == grid[0].size() - 1)

return ans;

for (auto direction:directions) {

int x = node.first + direction.first;

int y = node.second + direction.second;

if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == 0) {

queue.push({x, y});

grid[x][y] = 1;//避免再次访问

}

return -1;

}

};

279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.
示例 2:

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12

输出: 3

解释: 12 = 4 + 4 + 4.

示例 2:

输入: n = 13

输出: 2

解释: 13 = 4 + 9.

public class Twohundred_seventyNine {
    /**
     * 这里使用动态规划来做。时间复杂度O(nlogn)，空间复杂度O(n)
     * 定义一个函数f(n)表示我们要求的解。f(n)的求解过程为：
     * f(n) = 1 + min{
     * f(n-1^2), f(n-2^2), f(n-3^2), f(n-4^2), ... , f(n-k^2) //(k为满足k^2<=n的最大的k)
     * }
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; ++j)
                min = Math.min(min, dp[i - j * j]);
            dp[i] = min + 1;
        }
        return dp[n];
    }
}

public class Twohundred_seventyNine {

/**

* 这里使用动态规划来做。时间复杂度O(nlogn)，空间复杂度O(n)

* 定义一个函数f(n)表示我们要求的解。f(n)的求解过程为：

* f(n) = 1 + min{

* f(n-1^2), f(n-2^2), f(n-3^2), f(n-4^2), ... , f(n-k^2) //(k为满足k^2<=n的最大的k)

* }

public int numSquares(int n) {

int[] dp = new int[n + 1];

for (int i = 1; i <= n; ++i) {

int min = Integer.MAX_VALUE;

for (int j = 1; j * j <= i; ++j)

min = Math.min(min, dp[i - j * j]);

dp[i] = min + 1;

}

return dp[n];

}

    // BFS
    //图中节点存着剩余的n，每次n减去一些平方，然后将得到的合法差值入队
    //最小平方个数也就为：节点值为0的节点到根节点的最短路径
    public int numSquares2(int n) {
        if (n < 0)
            return -1;
        List<Integer> squares = generateSquares(n);
        boolean[] visited = new boolean[n + 1];
        Deque<Integer> deque = new LinkedList<>();
        deque.addLast(n);
        visited[n] = true;//可以不需要，因为出队不用判断
        int depth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            depth++;
            for (int i = 0; i < size; i++) {
                int restN = deque.pollFirst();
                for (int square : squares) {
                    if (restN - square == 0)
                        return depth;
                    else if (restN - square > 0) {
                        if (visited[restN - square] == false) {
                            deque.addLast(restN - square);
                            visited[restN - square] = true;
                        }
                    } else
                        break;
                }
            }
        }
        return depth;
    }

    public List<Integer> generateSquares(int n) {
        //平方数之间的差值构成d=2的等差数列
        //1、4、9、16 ==> 3、5、7
        List<Integer> ans = new ArrayList<>();
        int square = 1;
        int diff = 3;
        while (square <= n) {
            ans.add(square);
            square += diff;
            diff += 2;
        }
        return ans;
    }

// BFS

//图中节点存着剩余的n，每次n减去一些平方，然后将得到的合法差值入队

//最小平方个数也就为：节点值为0的节点到根节点的最短路径

public int numSquares2(int n) {

if (n < 0)

return -1;

List<Integer> squares = generateSquares(n);

boolean[] visited = new boolean[n + 1];

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

deque.addLast(n);

visited[n] = true;//可以不需要，因为出队不用判断

int depth = 0;

while (!deque.isEmpty()) {

int size = deque.size();

depth++;

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

int restN = deque.pollFirst();

for (int square : squares) {

if (restN - square == 0)

return depth;

else if (restN - square > 0) {

if (visited[restN - square] == false) {

deque.addLast(restN - square);

visited[restN - square] = true;

}

} else

break;

}

return depth;

}

public List<Integer> generateSquares(int n) {

//平方数之间的差值构成d=2的等差数列

//1、4、9、16 ==> 3、5、7

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

int square = 1;

int diff = 3;

while (square <= n) {

ans.add(square);

square += diff;

diff += 2;

}

return ans;

}

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            int min_val = INT_MAX;
            for (int j = 1; j * j < i; j++) {
                min_val = min(min_val, dp[i - j * j]);
            }
            dp[i] = min_val + 1;
        }
        return dp[n];
    }

    int numSquares2(int n) {
        vector<int> squares = generate_squares(n);
        vector<bool> visited(n + 1);
        queue<int> queue;
        queue.push(n);
        visited[n] = true;
        int depth = 0;
        while (!queue.empty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int node = queue.front();
                queue.pop();
                for (auto square:squares) {
                    if (node - square == 0)
                        return depth;
                    else if (node - square > 0) {
                        if (visited[node - square] == false) {
                            queue.push(node - square);
                            visited[node - square] = true;
                        }
                    } else
                        break;
                }
            }
        }
        return depth;
    }

    vector<int> generate_squares(int n) {
        vector<int> ans;
        int square = 1;
        int diff = 3;
        while (square <= n) {
            ans.push_back(square);
            square += diff;
            diff += 2;
        }
        return ans;
    }
};

class Solution {

public:

int numSquares(int n) {

vector<int> dp(n + 1);

for (int i = 1; i <= n; i++) {

int min_val = INT_MAX;

for (int j = 1; j * j < i; j++) {

min_val = min(min_val, dp[i - j * j]);

}

dp[i] = min_val + 1;

}

return dp[n];

}

int numSquares2(int n) {

vector<int> squares = generate_squares(n);

vector<bool> visited(n + 1);

queue<int> queue;

queue.push(n);

visited[n] = true;

int depth = 0;

while (!queue.empty()) {

depth++;

int size = queue.size();

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

int node = queue.front();

queue.pop();

for (auto square:squares) {

if (node - square == 0)

return depth;

else if (node - square > 0) {

if (visited[node - square] == false) {

queue.push(node - square);

visited[node - square] = true;

}

} else

break;

}

return depth;

}

vector<int> generate_squares(int n) {

vector<int> ans;

int square = 1;

int diff = 3;

while (square <= n) {

ans.push_back(square);

square += diff;

diff += 2;

}

return ans;

}

};

127. 单词接龙

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:

如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:

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

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。
示例 2:

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

输出: 0

解释: endWord "cog" 不在字典中，所以无法进行转换。

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。

转换过程中的中间单词必须是字典中的单词。

说明:

如果不存在这样的转换序列，返回 0。

所有单词具有相同的长度。

所有单词只由小写字母组成。

字典中不存在重复的单词。

你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

输入:

beginWord = "hit",

endWord = "cog",

wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",

返回它的长度 5。

示例 2:

输入:

beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log"]

输出: 0

解释: endWord "cog" 不在字典中，所以无法进行转换。

package main.gongel_first;

import javafx.util.Pair;

import java.util.*;

public class Onehundred_twentySeven {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Deque<Pair<String, Integer>> deque = new LinkedList<>();
        Map<String, List<String>> map = new HashMap<>();
        int len = beginWord.length();//所有单词相同长度
        for (String word : wordList) {
            for (int i = 0; i < len; i++) {
                //构造每个单词的通用结构 Dog-->*og/D*g/Do*
                //Dig-->*ig/D*g/Di*3
                //由于Dog和Dig都映射到D*g，那么它们之间应该存在一条边
                String newWord = word.substring(0, i) + "*" + word.substring(i + 1, len);
                List<String> temp = map.getOrDefault(newWord, new ArrayList<>());
                temp.add(word);
                map.put(newWord, temp);
            }
        }
        Map<String, Boolean> visited = new HashMap<>();
        visited.put(beginWord, true);
        deque.addLast(new Pair<>(beginWord, 1));
        while (!deque.isEmpty()) {
            Pair<String, Integer> node = deque.pollFirst();
            String word = node.getKey();
            int level = node.getValue();
            for (int i = 0; i < len; i++) {
                String newWord = word.substring(0, i) + "*" + word.substring(i + 1, len);
                List<String> temp = map.getOrDefault(newWord, new ArrayList<>());
                for (String tempWord : temp) {
                    if (tempWord.equals(endWord))
                        return level + 1;
                    if (!visited.containsKey(tempWord)) {
                        visited.put(tempWord, true);
                        deque.addLast(new Pair<>(tempWord, level + 1));
                    }
                }
            }
        }
        return 0;
    }
}

package main.gongel_first;

import javafx.util.Pair;

import java.util.*;

public class Onehundred_twentySeven {

public int ladderLength(String beginWord, String endWord, List<String> wordList) {

Deque<Pair<String, Integer>> deque = new LinkedList<>();

Map<String, List<String>> map = new HashMap<>();

int len = beginWord.length();//所有单词相同长度

for (String word : wordList) {

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

//构造每个单词的通用结构 Dog-->*og/D*g/Do*

//Dig-->*ig/D*g/Di*3

//由于Dog和Dig都映射到D*g，那么它们之间应该存在一条边

String newWord = word.substring(0, i) + "*" + word.substring(i + 1, len);

List<String> temp = map.getOrDefault(newWord, new ArrayList<>());

temp.add(word);

map.put(newWord, temp);

}

Map<String, Boolean> visited = new HashMap<>();

visited.put(beginWord, true);

deque.addLast(new Pair<>(beginWord, 1));

while (!deque.isEmpty()) {

Pair<String, Integer> node = deque.pollFirst();

String word = node.getKey();

int level = node.getValue();

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

String newWord = word.substring(0, i) + "*" + word.substring(i + 1, len);

List<String> temp = map.getOrDefault(newWord, new ArrayList<>());

for (String tempWord : temp) {

if (tempWord.equals(endWord))

return level + 1;

if (!visited.containsKey(tempWord)) {

visited.put(tempWord, true);

deque.addLast(new Pair<>(tempWord, level + 1));

}

return 0;

}

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string> &wordList) {
        queue<string> queue;
        unordered_map<string, bool> visited;
        unordered_map<string, vector<string>> word_wildcards;
        int len = beginWord.size();
        for (auto word:wordList) {
            for (int i = 0; i < len; i++) {
                string word_wildcard = word.substr(0, i) + '*' + word.substr(i + 1, len - i - 1);
                if (word_wildcards.find(word_wildcard) == word_wildcards.end()) {
                    vector<string> temp;
                    temp.push_back(word);
                    word_wildcards.insert({word_wildcard, temp});
                } else
                    word_wildcards[word_wildcard].push_back(word);
            }
        }
        visited.insert({beginWord, "true"});
        queue.push(beginWord);
        int ans = 0;
        while (!queue.empty()) {
            int size = queue.size();
            ans++;
            for (int i = 0; i < size; i++) {
                string node = queue.front();
                queue.pop();
                for (int j = 0; j < len; j++) {
                    string temp_wildcard = node.substr(0, j) + '*' + node.substr(j + 1, len - j - 1);
                    if (word_wildcards.find(temp_wildcard) != word_wildcards.end()) {
                        for (auto word:word_wildcards[temp_wildcard]) {
                            if (word == endWord)
                                return ans + 1;
                            if (visited.find(word) == visited.end()) {
                                visited.insert({word, "true"});
                                queue.push(word);
                            }
                        }
                    }
                }
            }
        }
        return 0;
    }
};

class Solution {

public:

int ladderLength(string beginWord, string endWord, vector<string> &wordList) {

queue<string> queue;

unordered_map<string, bool> visited;

unordered_map<string, vector<string>> word_wildcards;

int len = beginWord.size();

for (auto word:wordList) {

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

string word_wildcard = word.substr(0, i) + '*' + word.substr(i + 1, len - i - 1);

if (word_wildcards.find(word_wildcard) == word_wildcards.end()) {

vector<string> temp;

temp.push_back(word);

word_wildcards.insert({word_wildcard, temp});

} else

word_wildcards[word_wildcard].push_back(word);

}

visited.insert({beginWord, "true"});

queue.push(beginWord);

int ans = 0;

while (!queue.empty()) {

int size = queue.size();

ans++;

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

string node = queue.front();

queue.pop();

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

string temp_wildcard = node.substr(0, j) + '*' + node.substr(j + 1, len - j - 1);

if (word_wildcards.find(temp_wildcard) != word_wildcards.end()) {

for (auto word:word_wildcards[temp_wildcard]) {

if (word == endWord)

return ans + 1;

if (visited.find(word) == visited.end()) {

visited.insert({word, "true"});

queue.push(word);

}

return 0;

}

};

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;

}

class Solution {
public:
    bool isBipartite(vector<vector<int>> &graph) {
        vector<int> color(graph.size());
        for (int i = 0; i < graph.size(); i++) {
            if (color[i] == 0) {
                if (!bfs(graph, color, i))//有可能非连通图
                    return false;
            }
        }
        return true;
    }

    bool bfs(vector<vector<int>> &graph, vector<int> &color, int root) {
        color[root] = 1;
        queue<int> queue;
        queue.push(root);
        while (!queue.empty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int node = queue.front();
                queue.pop();
                for (auto neighbor:graph[node]) {
                    if (color[neighbor] == color[node])
                        return false;
                    if (color[neighbor] == 0) {
                        queue.push(neighbor);
                        color[neighbor] = -1 * color[node];
                    }
                }
            }
        }
        return true;
    }
};

class Solution {

public:

bool isBipartite(vector<vector<int>> &graph) {

vector<int> color(graph.size());

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

if (color[i] == 0) {

if (!bfs(graph, color, i))//有可能非连通图

return false;

}

return true;

}

bool bfs(vector<vector<int>> &graph, vector<int> &color, int root) {

color[root] = 1;

queue<int> queue;

queue.push(root);

while (!queue.empty()) {

int size = queue.size();

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

int node = queue.front();

queue.pop();

for (auto neighbor:graph[node]) {

if (color[neighbor] == color[node])

return false;

if (color[neighbor] == 0) {

queue.push(neighbor);

color[neighbor] = -1 * color[node];

}

return true;

}

};

690. 员工的重要性

给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。

比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。

现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。

示例 1:

输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出: 11
解释:
员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。
注意:

一个员工最多有一个直系领导，但是可以有多个直系下属
员工数量不超过2000。

给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度和直系下属的id。

比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。

现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。

示例 1:

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

输出: 11

解释:

员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。

注意:

一个员工最多有一个直系领导，但是可以有多个直系下属

员工数量不超过2000。

package gongel_first;

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

class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List<Integer> subordinates;
}

public class Sixhundred_ninety {
    /**
     * 层次遍历
     * 类似于N叉树的遍历
     */
    private Employee search(List<Employee> employees, int id) {
        for (Employee e : employees) {
            if (e.id == id)
                return e;
        }
        return null;
    }

    public int getImportance(List<Employee> employees, int id) {
        int ans = 0;
        if (employees == null || employees.size() == 0)
            return ans;
        Deque<Employee> deque = new LinkedList<>();
        Employee head = search(employees, id);
        deque.addLast(head);
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int j = 0; j < size; j++) {
                Employee employee = deque.pollFirst();
                ans += employee.importance;
                for (int eId : employee.subordinates)
                    deque.addLast(search(employees, eId));
            }
        }
        return ans;
    }
}

package gongel_first;

import java.util.Deque;

import java.util.LinkedList;

import java.util.List;

class Employee {

// It's the unique id of each node;

// unique id of this employee

public int id;

// the importance value of this employee

public int importance;

// the id of direct subordinates

public List<Integer> subordinates;

}

public class Sixhundred_ninety {

/**

* 层次遍历

* 类似于N叉树的遍历

private Employee search(List<Employee> employees, int id) {

for (Employee e : employees) {

if (e.id == id)

return e;

}

return null;

}

public int getImportance(List<Employee> employees, int id) {

int ans = 0;

if (employees == null || employees.size() == 0)

return ans;

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

Employee head = search(employees, id);

deque.addLast(head);

while (!deque.isEmpty()) {

int size = deque.size();

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

Employee employee = deque.pollFirst();

ans += employee.importance;

for (int eId : employee.subordinates)

deque.addLast(search(employees, eId));

}

return ans;

}

class Solution {
public:

    int getImportance(vector<Employee *> employees, int id) {
        queue<Employee *> queue;
        auto employee = search(employees, id);
        queue.push(employee);
        int importance = 0;
        while (!queue.empty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                employee = queue.front();
                queue.pop();
                importance += employee->importance;
                for (auto subordinate:employee->subordinates) {
                    queue.push(search(employees, subordinate));
                }
            }
        }
        return importance;
    }

    Employee *search(vector<Employee *> employees, int id) {
        for (auto employee:employees) {
            if (employee->id == id)
                return employee;
        }
        return nullptr;
    }
};

2020年六月
一	二	三	四	五	六	日
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