Codes – gongel

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;
    }
};

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;

}

};

542. 01 矩阵

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:
输入:

0 0 0
0 1 0
0 0 0
输出:

0 0 0
0 1 0
0 0 0
示例 2:
输入:

0 0 0
0 1 0
1 1 1
输出:

0 0 0
0 1 0
1 2 1
注意:

给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:

输入:

0 0 0

0 1 0

0 0 0

输出:

0 0 0

0 1 0

0 0 0

示例 2:

输入:

0 0 0

0 1 0

1 1 1

输出:

0 0 0

0 1 0

1 2 1

注意:

给定矩阵的元素个数不超过 10000。

给定矩阵中至少有一个元素是 0。

矩阵中的元素只在四个方向上相邻: 上、下、左、右。

package gongel_first;

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

public class Fivehundred_fortyTwo {
    /**
     * BFS+队列
     * 最终结果直接在原数组上进行修改
     * ref：https://leetcode-cn.com/problems/01-matrix/solution/java-si-lu-jie-xi-bfsyan-du-you-xian-suan-fa-by-wa/
     */
    private int[][] directions = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

    public int[][] updateMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return new int[][]{};
        Deque<int[]> deque = new LinkedList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0)
                    deque.addLast(new int[]{i, j});
                else
                    matrix[i][j] = 10001;
            }
        }
        while (!deque.isEmpty()) {//类似于二叉树的层次遍历
            int len = deque.size();
            while (len > 0) {
                len--;
                int[] head = deque.pollFirst();
                int min = matrix[head[0]][head[1]];
                for (int[] dir : directions) {
                    int x = head[0] + dir[0];
                    int y = head[1] + dir[1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        min = Math.min(min, matrix[x][y] + 1);//当前结点距离0的距离肯定是四周邻居节点距离0节点的最小值+1
                        if (matrix[x][y] == 10001)
                            deque.addLast(new int[]{x, y});
                    }
                }
                matrix[head[0]][head[1]] = min;
            }
        }
        return matrix;
    }
}

package gongel_first;

import java.util.Deque;

import java.util.LinkedList;

public class Fivehundred_fortyTwo {

/**

* BFS+队列

* 最终结果直接在原数组上进行修改

* ref：https://leetcode-cn.com/problems/01-matrix/solution/java-si-lu-jie-xi-bfsyan-du-you-xian-suan-fa-by-wa/

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

public int[][] updateMatrix(int[][] matrix) {

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

return new int[][]{};

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

int m = matrix.length;

int n = matrix[0].length;

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

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

if (matrix[i][j] == 0)

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

else

matrix[i][j] = 10001;

}

while (!deque.isEmpty()) {//类似于二叉树的层次遍历

int len = deque.size();

while (len > 0) {

len--;

int[] head = deque.pollFirst();

int min = matrix[head[0]][head[1]];

for (int[] dir : directions) {

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

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

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

min = Math.min(min, matrix[x][y] + 1);//当前结点距离0的距离肯定是四周邻居节点距离0节点的最小值+1

if (matrix[x][y] == 10001)

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

}

matrix[head[0]][head[1]] = min;

}

return matrix;

}

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>> &matrix) {
        if (matrix.empty() || matrix.empty())
            return vector<vector<int>>{};
        vector<pair<int, int>> directions{{0,  1},
                                          {0,  -1},
                                          {1,  0},
                                          {-1, 0}};
        queue<pair<int, int>> queue;
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] == 0)
                    queue.push({i, j});
                else
                    matrix[i][j] = 10001;//初始化距离为10001
            }
        }
        while (!queue.empty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                auto node = queue.front();
                queue.pop();
                int min_distance = matrix[node.first][node.second];
                for (auto direction:directions) {
                    int x = node.first + direction.first;
                    int y = node.second + direction.second;
                    if (x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size()) {
                        min_distance = min(min_distance, matrix[x][y] + 1);
                        if (matrix[x][y] == 10001)//需要修改距离，为0不需要修改
                            queue.push({x, y});
                    }
                }
                matrix[node.first][node.second] = min_distance;
            }
        }
        return matrix;
    }
};

class Solution {

public:

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

if (matrix.empty() || matrix.empty())

return vector<vector<int>>{};

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

{0, -1},

{1, 0},

{-1, 0}};

queue<pair<int, int>> queue;

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

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

if (matrix[i][j] == 0)

queue.push({i, j});

else

matrix[i][j] = 10001;//初始化距离为10001

}

while (!queue.empty()) {

int size = queue.size();

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

auto node = queue.front();

queue.pop();

int min_distance = matrix[node.first][node.second];

for (auto direction:directions) {

int x = node.first + direction.first;

int y = node.second + direction.second;

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

min_distance = min(min_distance, matrix[x][y] + 1);

if (matrix[x][y] == 10001)//需要修改距离，为0不需要修改

queue.push({x, y});

}

matrix[node.first][node.second] = min_distance;

}

return matrix;

}

};

752. 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为  '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

 

示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:

输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。
示例 4:

输入: deadends = ["0000"], target = "8888"
输出：-1
 

提示：

死亡列表 deadends 的长度范围为 [1, 500]。
目标数字 target 不会在 deadends 之中。
每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"

输出：6

解释：

可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。

注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，

因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2:

输入: deadends = ["8888"], target = "0009"

输出：1

解释：

把最后一位反向旋转一次即可 "0000" -> "0009"。

示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"

输出：-1

解释：

无法旋转到目标数字且不被锁定。

示例 4:

输入: deadends = ["0000"], target = "8888"

输出：-1

提示：

死亡列表 deadends 的长度范围为 [1, 500]。

目标数字 target 不会在 deadends 之中。

每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。

public class Sevenhundred_fiftyTwo {
    /**
     * 遇到给定的数字，直接返回当前深度，由于是一层一层(每层只对每位数字+1或者-1，所以每次getNext会得到大小为8的List)往下遍历，最先遇到的节点肯定是路径最短的
     */
    private List<String> getNext(String str) {
        List<String> ans = new ArrayList<>();
        char[] chars = str.toCharArray();
        for (int i = 0; i < 4; i++) {
            char[] newchars = chars.clone();
            newchars[i] = (char) ((((chars[i] - '0') + 1) % 10) + '0');//数字+1
            ans.add(new String(newchars));//toString()有问题
            newchars[i] = (char) ((((chars[i] - '0') - 1 + 10) % 10) + '0');//数字-1
            ans.add(new String(newchars));
        }
        return ans;
    }

    public int openLock(String[] deadends, String target) {
        Set<String> visited = new HashSet<>(Arrays.asList(deadends));//存入不妨访问的节点和访问过的节点
        Deque<String> deque = new LinkedList<>();
        if (target == null || target.length() == 0 || visited.contains(target) || visited.contains("0000"))
            return -1;
        deque.addLast("0000");
        visited.add("0000");
        int depth = 0;
        while (!deque.isEmpty()) {
            depth++;
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                String str = deque.pollFirst();
                if (str.equals(target))
                    return depth;
                for (String temp : getNext(str)) {
                    if (!visited.contains(temp)) {
                        visited.add(temp);
                        deque.add(temp);
                    }
                }
            }
        }
        return -1;
    }
}

public class Sevenhundred_fiftyTwo {

/**

* 遇到给定的数字，直接返回当前深度，由于是一层一层(每层只对每位数字+1或者-1，所以每次getNext会得到大小为8的List)往下遍历，最先遇到的节点肯定是路径最短的

private List<String> getNext(String str) {

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

char[] chars = str.toCharArray();

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

char[] newchars = chars.clone();

newchars[i] = (char) ((((chars[i] - '0') + 1) % 10) + '0');//数字+1

ans.add(new String(newchars));//toString()有问题

newchars[i] = (char) ((((chars[i] - '0') - 1 + 10) % 10) + '0');//数字-1

ans.add(new String(newchars));

}

return ans;

}

public int openLock(String[] deadends, String target) {

Set<String> visited = new HashSet<>(Arrays.asList(deadends));//存入不妨访问的节点和访问过的节点

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

if (target == null || target.length() == 0 || visited.contains(target) || visited.contains("0000"))

return -1;

deque.addLast("0000");

visited.add("0000");

int depth = 0;

while (!deque.isEmpty()) {

depth++;

int size = deque.size();

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

String str = deque.pollFirst();

if (str.equals(target))

return depth;

for (String temp : getNext(str)) {

if (!visited.contains(temp)) {

visited.add(temp);

deque.add(temp);

}

return -1;

}

class Solution {
public:
    int openLock(vector<string> &deadends, string target) {
        unordered_set<string> visited{deadends.begin(), deadends.end()};//不能访问+访问过的
        if (visited.count(target) > 0 || visited.count("0000") > 0)
            return -1;
        queue<string> queue;
        queue.push("0000");
        visited.insert("0000");
        int depth = 0;
        while (!queue.empty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                auto node = queue.front();
                queue.pop();
                if (node == target)//需要拿到外面判断
                    return depth - 1;
                for (auto next:generate_next(node)) {
                    if (visited.find(next) == visited.end()) {
                        queue.push(next);
                        visited.insert(next);
                    }
                }
            }
        }
        return -1;
    }

    vector<string> generate_next(string current) {
        vector<string> next;
        for (int i = 0; i < current.size(); i++) {
            string clone = current;
            clone[i] = (current[i] - '0' + 1) % 10 + '0';
            next.push_back(clone);
            clone[i] = (current[i] - '0' - 1 + 10) % 10 + '0';
            next.push_back(clone);
        }
        return next;
    }
};

class Solution {

public:

int openLock(vector<string> &deadends, string target) {

unordered_set<string> visited{deadends.begin(), deadends.end()};//不能访问+访问过的

if (visited.count(target) > 0 || visited.count("0000") > 0)

return -1;

queue<string> queue;

queue.push("0000");

visited.insert("0000");

int depth = 0;

while (!queue.empty()) {

depth++;

int size = queue.size();

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

auto node = queue.front();

queue.pop();

if (node == target)//需要拿到外面判断

return depth - 1;

for (auto next:generate_next(node)) {

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

queue.push(next);

visited.insert(next);

}

return -1;

}

vector<string> generate_next(string current) {

vector<string> next;

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

string clone = current;

clone[i] = (current[i] - '0' + 1) % 10 + '0';

next.push_back(clone);

clone[i] = (current[i] - '0' - 1 + 10) % 10 + '0';

next.push_back(clone);

}

return next;

}

};

课程表拓扑排序

路径(和)

120. 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[

[2],

[3,4],

[6,5,7],

[4,1,8,3]

]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

//自底向上：每次取下一层左右两个节点的值的最小值与当前节点的值之和来更新当前节点
//    [11],
//   [9,10], 
//  [7,6,10], 
// [4,1,8,3]
 public int minimumTotal(List<List<Integer>> triangle) {
        for (int i = triangle.size() - 2; i >= 0; --i) {
            for (int j = 0; j < triangle.get(i).size(); ++j) {
                int ans=Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1))+triangle.get(i).get(j);
                triangle.get(i).set(j,ans);
            }
        }
        return triangle.get(0).get(0);
    }

//自底向上：每次取下一层左右两个节点的值的最小值与当前节点的值之和来更新当前节点

// [11],

// [9,10],

// [7,6,10],

// [4,1,8,3]

public int minimumTotal(List<List<Integer>> triangle) {

for (int i = triangle.size() - 2; i >= 0; --i) {

for (int j = 0; j < triangle.get(i).size(); ++j) {

int ans=Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1))+triangle.get(i).get(j);

triangle.get(i).set(j,ans);

}

return triangle.get(0).get(0);

}

class Solution {
public:
    int minimumTotal(vector<vector<int>> &triangle) {
        if (triangle.empty() || triangle[0].empty())
            return 0;
        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle[i].size(); j++) {
                int temp = min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j];
                triangle[i][j] = temp;
            }
        }
        return triangle[0][0];
    }
};

class Solution {

public:

int minimumTotal(vector<vector<int>> &triangle) {

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

return 0;

for (int i = triangle.size() - 2; i >= 0; i--) {

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

int temp = min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j];

triangle[i][j] = temp;

}

return triangle[0][0];

}

};

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？
说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:

输入: m = 7, n = 3
输出: 28

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2

输出: 3

解释:

从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下

2. 向右 -> 向下 -> 向右

3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3

输出: 28

public class Sixty_two {
    //动态规划
    public int uniquePaths(int m, int n) {
        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] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

public class Sixty_two {

//动态规划

public int uniquePaths(int m, int n) {

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] = 1;

} else {

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

}

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

}

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0)
            return 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0)//只能👉或者👇按直线走
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

class Solution {

public:

int uniquePaths(int m, int n) {

if (m <= 0 || n <= 0)

return 0;

vector<vector<int>> dp(m, vector<int>(n, 0));

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

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

if (i == 0 || j == 0)//只能👉或者👇按直线走

dp[i][j] = 1;

else

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

}

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

}

};

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];

}

class Solution {
public:
    int minPathSum(vector<vector<int>> &grid) {
        if (grid.empty() || grid[0].empty())
            return 0;
        vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(), 0));
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (i == 0 && j == 0)
                    dp[i][j] = grid[0][0];
                else if (i == 0 & j > 0)
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                else if (i > 0 & j == 0)
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                else
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[grid.size() - 1][grid[0].size() - 1];
    }
};

class Solution {

public:

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

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

return 0;

vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(), 0));

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

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

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

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

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

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

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

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

else

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

}

return dp[grid.size() - 1][grid[0].size() - 1];

}

};

不同的二叉搜索树

96. 不同的二叉搜索树(DP)

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3

输出: 5

解释:

给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

1 3 3 2 1

\ / / / \ \

3 2 1 1 3 2

/ / \ \

2 1 2 3

  //catalan数:https://baike.baidu.com/item/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/6125746?fr=aladdin
    public int numTrees(int n) {
        /*1.结果超出int范围*/
//        if(n==0)
//            return 1;
//        return numTrees(n-1)*(4*n-2)/(n+1);

        /*2.超时*/
//        if(n==0||n==1)
//            return 1;
//        int ans=0;
//        for(int i=0;i<n;i++){
//            ans+=numTrees(i)*numTrees(n-i-1);
//        }
//        return ans;

        if (n <= 0)
            return -1;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] + dp[i - j - 1];
            }
        }
        return dp[n];
    }

//catalan数:https://baike.baidu.com/item/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/6125746?fr=aladdin

public int numTrees(int n) {

/*1.结果超出int范围*/

// if(n==0)

// return 1;

// return numTrees(n-1)*(4*n-2)/(n+1);

/*2.超时*/

// if(n==0||n==1)

// return 1;

// int ans=0;

// for(int i=0;i<n;i++){

// ans+=numTrees(i)*numTrees(n-i-1);

// }

// return ans;

if (n <= 0)

return -1;

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

dp[0] = 1;

dp[1] = 1;

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

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

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

}

return dp[n];

}

class Solution {
    /**
     * 假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数
     * 即有:G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)
     * n为根节点，当i为根节点时，其左子树节点个数为[1,2,3,...,i-1]，右子树节点个数为[i+1,i+2,...n]，
     * 所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，即f(i) = G(i-1)*G(n-i),
     * 上面两式可得:G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)*/
public:
    int numTrees(int n) {
        if (n <= 0)
            return 0;
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++)
                dp[i] += dp[j] * dp[i - j - 1];
        }
        return dp[n];
    }
};

class Solution {

/**

* 假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数

* 即有:G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)

* n为根节点，当i为根节点时，其左子树节点个数为[1,2,3,...,i-1]，右子树节点个数为[i+1,i+2,...n]，

* 所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，即f(i) = G(i-1)*G(n-i),

* 上面两式可得:G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)*/

public:

int numTrees(int n) {

if (n <= 0)

return 0;

vector<int> dp(n + 1);

dp[0] = 1;

dp[1] = 1;

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

for (int j = 0; j < i; j++)

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

}

return dp[n];

}

};

95. 不同的二叉搜索树 II (分治)

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例:

输入: 3

输出:

[

[1,null,3,2],

[3,2,null,1],

[3,1,null,null,2],

[2,1,3],

[1,null,2,null,3]

]

解释:

以上的输出对应以下 5 种不同结构的二叉搜索树：

1 3 3 2 1

\ / / / \ \

3 2 1 1 3 2

/ / \ \

2 1 2 3

public class Solution {
    private void helper(int left, int right, List<TreeNode> ans) {
        if (left > right) {
            ans.add(null);
            return;
        }
        for (int i = left; i <= right; i++) {
            List<TreeNode> leftNodes = new ArrayList<>();
            helper(left, i - 1, leftNodes);
            List<TreeNode> rightNodes = new ArrayList<>();
            helper(i + 1, right, rightNodes);
            for (TreeNode leftNode : leftNodes) {
                for (TreeNode rightNode : rightNodes) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    ans.add(root);
                }
            }
        }
    }

    public List<TreeNode> generateTrees(int n) {
        if (n <= 0)
            return new ArrayList<>();
        List<TreeNode> ans = new ArrayList<>();
        helper(1, n, ans);
        return ans;
    }
}

public class Solution {

private void helper(int left, int right, List<TreeNode> ans) {

if (left > right) {

ans.add(null);

return;

}

for (int i = left; i <= right; i++) {

List<TreeNode> leftNodes = new ArrayList<>();

helper(left, i - 1, leftNodes);

List<TreeNode> rightNodes = new ArrayList<>();

helper(i + 1, right, rightNodes);

for (TreeNode leftNode : leftNodes) {

for (TreeNode rightNode : rightNodes) {

TreeNode root = new TreeNode(i);

root.left = leftNode;

root.right = rightNode;

ans.add(root);

}

public List<TreeNode> generateTrees(int n) {

if (n <= 0)

return new ArrayList<>();

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

helper(1, n, ans);

return ans;

}

#define NULL 0
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        if (n <= 0)
            return vector<TreeNode *>{};//返回空vector
        else
            return generate(1, n);
    }

    vector<TreeNode *> generate(int left, int right) {
        vector<TreeNode *> ans;
        if (left > right) {
            ans.push_back(NULL);
            return ans;
        }
        for (int i = left; i <= right; i++) {
            vector<TreeNode *> left_nodes = generate(left, i - 1);
            vector<TreeNode *> right_nodes = generate(i + 1, right);
            for (TreeNode *left_node:left_nodes) {
                for (TreeNode *right_node:right_nodes) {
                    TreeNode *root = new TreeNode(i);
                    root->left = left_node;
                    root->right = right_node;
                    ans.push_back(root);
                }

            }
        }
        return ans;
    }
};

#define NULL 0

#include <vector>

using namespace std;

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

vector<TreeNode *> generateTrees(int n) {

if (n <= 0)

return vector<TreeNode *>{};//返回空vector

else

return generate(1, n);

}

vector<TreeNode *> generate(int left, int right) {

vector<TreeNode *> ans;

if (left > right) {

ans.push_back(NULL);

return ans;

}

for (int i = left; i <= right; i++) {

vector<TreeNode *> left_nodes = generate(left, i - 1);

vector<TreeNode *> right_nodes = generate(i + 1, right);

for (TreeNode *left_node:left_nodes) {

for (TreeNode *right_node:right_nodes) {

TreeNode *root = new TreeNode(i);

root->left = left_node;

root->right = right_node;

ans.push_back(root);

}

return ans;

}

};

解码方法

91. 解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1

'B' -> 2

...

'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"

输出: 2

解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

输入: "226"

输出: 3

解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

   /*DP问题：dp[i]表示第i个结点(i≥1)，所有的解码方法总数   
   比如一组输入数据（12021）,得到解码数[1, 1, 2, 1, 1, 2]，第一个1仅起辅助作用
    */
    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0')
            return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;  // 辅助线,没有意义
        dp[1] = 1;
        for (int i = 2; i <= s.length(); i++) {
            String a = s.substring(i - 2, i);
            // 计算单独解码数
            if (s.charAt(i - 1) != '0') {
                // 只要当前的字符不是0，就表示通过独立可以实现继承前面的解码数（不考虑合体，合体是后面的事情）
                dp[i] = dp[i - 1];
            }
            // 计算合体解码数
            if (Integer.parseInt(a) <= 26 && Integer.parseInt(a) >= 10) {
                // 有合体的可能性，加上潜在合体数，即前一个的前一个
                dp[i] += dp[i - 2];
                //10,20相当于继承dp[i-2]，不满足s.charAt(i - 1) != '0'
            }
        }
        return dp[s.length()];
    }

/*DP问题：dp[i]表示第i个结点(i≥1)，所有的解码方法总数

比如一组输入数据（12021）,得到解码数[1, 1, 2, 1, 1, 2]，第一个1仅起辅助作用

public int numDecodings(String s) {

if (s == null || s.length() == 0 || s.charAt(0) == '0')

return 0;

int[] dp = new int[s.length() + 1];

dp[0] = 1; // 辅助线,没有意义

dp[1] = 1;

for (int i = 2; i <= s.length(); i++) {

String a = s.substring(i - 2, i);

// 计算单独解码数

if (s.charAt(i - 1) != '0') {

// 只要当前的字符不是0，就表示通过独立可以实现继承前面的解码数（不考虑合体，合体是后面的事情）

dp[i] = dp[i - 1];

}

// 计算合体解码数

if (Integer.parseInt(a) <= 26 && Integer.parseInt(a) >= 10) {

// 有合体的可能性，加上潜在合体数，即前一个的前一个

dp[i] += dp[i - 2];

//10,20相当于继承dp[i-2]，不满足s.charAt(i - 1) != '0'

}

return dp[s.length()];

}

class Solution {
public:
    int numDecodings(string s) {
        if (s.size() == 0 || s[0] == '0')
            return 0;
        vector<int> dp(s.size() + 1);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= s.size(); i++) {
            string sub_str = s.substr(i - 2, 2);
            if (s[i - 1] != '0')
                dp[i] = dp[i - 1];
            if (stoi(sub_str) <= 26 && stoi(sub_str) >= 10)
                dp[i] += dp[i - 2];
        }
        return dp[s.size()];
    }
};

class Solution {

public:

int numDecodings(string s) {

if (s.size() == 0 || s[0] == '0')

return 0;

vector<int> dp(s.size() + 1);

dp[0] = 1;

dp[1] = 1;

for (int i = 2; i <= s.size(); i++) {

string sub_str = s.substr(i - 2, 2);

if (s[i - 1] != '0')

dp[i] = dp[i - 1];

if (stoi(sub_str) <= 26 && stoi(sub_str) >= 10)

dp[i] += dp[i - 2];

}

return dp[s.size()];

}

};

639. 解码方法 2

一条包含字母 A-Z 的消息通过以下的方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26
除了上述的条件以外，现在加密字符串可以包含字符 '*'了，字符'*'可以被当做1到9当中的任意一个数字。

给定一条包含数字和字符'*'的加密信息，请确定解码方法的总数。

同时，由于结果值可能会相当的大，所以你应当对109 + 7取模。（翻译者标注：此处取模主要是为了防止溢出）

示例 1 :

输入: "*"
输出: 9
解释: 加密的信息可以被解密为: "A", "B", "C", "D", "E", "F", "G", "H", "I".
示例 2 :

输入: "1*"
输出: 9 + 9 = 18（翻译者标注：这里1*可以分解为1,* 或者当做1*来处理，所以结果是9+9=18）
说明 :

输入的字符串长度范围是 [1, 105]。
输入的字符串只会包含字符 '*' 和 数字'0' - '9'。

一条包含字母 A-Z 的消息通过以下的方式进行了编码：

'A' -> 1

'B' -> 2

...

'Z' -> 26

除了上述的条件以外，现在加密字符串可以包含字符 '*'了，字符'*'可以被当做1到9当中的任意一个数字。

给定一条包含数字和字符'*'的加密信息，请确定解码方法的总数。

同时，由于结果值可能会相当的大，所以你应当对109 + 7取模。（翻译者标注：此处取模主要是为了防止溢出）

示例 1 :

输入: "*"

输出: 9

解释: 加密的信息可以被解密为: "A", "B", "C", "D", "E", "F", "G", "H", "I".

示例 2 :

输入: "1*"

输出: 9 + 9 = 18（翻译者标注：这里1*可以分解为1,* 或者当做1*来处理，所以结果是9+9=18）

说明 :

输入的字符串长度范围是 [1, 105]。

输入的字符串只会包含字符 '*' 和数字'0' - '9'。

public class Sixhundred_thirtyNine {
    /**
     * 星号*代表1-9，且可以出现多次
     * 先从当前字符s.charAt(i-1)是不是*开始分支
     */
    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0')
            return 0;
        long[] dp = new long[s.length() + 1];
        int M = 1000000007;
        dp[0] = 1;//辅助线
        dp[1] = s.charAt(0) == '*' ? 9 : 1;
        for (int i = 2; i <= s.length(); i++) {
            //当前字符下标i-1
            if (s.charAt(i - 1) == '*') {
                dp[i] = 9 * dp[i - 1];//不考虑合并，只考虑单身
                if (s.charAt(i - 2) == '1')
                    dp[i] = (dp[i] + 9 * dp[i - 2]) % M;//合并一：1*=11-19（9种可能）
                else if (s.charAt(i - 2) == '2')
                    dp[i] = (dp[i] + 6 * dp[i - 2]) % M;//合并二：2*=21-26（6种可能）
                else if (s.charAt(i - 2) == '*')
                    dp[i] = (dp[i] + 15 * dp[i - 2]) % M;//合并三：**=前面两种合并的加和=9+6=15种可能
            } else {//这个分支同91题
                if (s.charAt(i - 1) != '0')//不考虑合并，单身继承
                    dp[i] = dp[i - 1];
                else
                    dp[i] = 0;
                if (s.charAt(i - 2) == '1')//合并一：合并求和
                    dp[i] = (dp[i] + dp[i - 2]) % M;
                else if (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6')//合并二：合并求和
                    dp[i] = (dp[i] + dp[i - 2]) % M;
                else if (s.charAt(i - 2) == '*') {//合并三：合并求和
                    if (s.charAt(i - 1) <= '6')//1#或者2#（#为确定的字符，不同于*）
                        dp[i] = (dp[i] + 2 * dp[i - 2]) % M;
                    else//只能为1#
                        dp[i] = (dp[i] + dp[i - 2]) % M;
                }

            }
        }
        return (int) dp[s.length()];
    }
}

public class Sixhundred_thirtyNine {

/**

* 星号*代表1-9，且可以出现多次

* 先从当前字符s.charAt(i-1)是不是*开始分支

public int numDecodings(String s) {

if (s == null || s.length() == 0 || s.charAt(0) == '0')

return 0;

long[] dp = new long[s.length() + 1];

int M = 1000000007;

dp[0] = 1;//辅助线

dp[1] = s.charAt(0) == '*' ? 9 : 1;

for (int i = 2; i <= s.length(); i++) {

//当前字符下标i-1

if (s.charAt(i - 1) == '*') {

dp[i] = 9 * dp[i - 1];//不考虑合并，只考虑单身

if (s.charAt(i - 2) == '1')

dp[i] = (dp[i] + 9 * dp[i - 2]) % M;//合并一：1*=11-19（9种可能）

else if (s.charAt(i - 2) == '2')

dp[i] = (dp[i] + 6 * dp[i - 2]) % M;//合并二：2*=21-26（6种可能）

else if (s.charAt(i - 2) == '*')

dp[i] = (dp[i] + 15 * dp[i - 2]) % M;//合并三：**=前面两种合并的加和=9+6=15种可能

} else {//这个分支同91题

if (s.charAt(i - 1) != '0')//不考虑合并，单身继承

dp[i] = dp[i - 1];

else

dp[i] = 0;

if (s.charAt(i - 2) == '1')//合并一：合并求和

dp[i] = (dp[i] + dp[i - 2]) % M;

else if (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6')//合并二：合并求和

dp[i] = (dp[i] + dp[i - 2]) % M;

else if (s.charAt(i - 2) == '*') {//合并三：合并求和

if (s.charAt(i - 1) <= '6')//1#或者2#（#为确定的字符，不同于*）

dp[i] = (dp[i] + 2 * dp[i - 2]) % M;

else//只能为1#

dp[i] = (dp[i] + dp[i - 2]) % M;

}

return (int) dp[s.length()];

}

#define LL long long

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0')
            return 0;
        int M = 1000000007;
        vector<LL> dp(s.size() + 1);
        dp[0] = 1;
        dp[1] = s[0] == '*' ? 9 : 1;
        for (int i = 2; i <= s.size(); i++) {
            if (s[i - 1] == '*') {
                dp[i] = 9 * dp[i - 1];
                if (s[i - 2] == '1')
                    dp[i] = (dp[i] + 9 * dp[i - 2]) % M;
                else if (s[i - 2] == '2')
                    dp[i] = (dp[i] + 6 * dp[i - 2]) % M;
                else if (s[i - 2] == '*')
                    dp[i] = (dp[i] + 15 * dp[i - 2]) % M;
            } else {
                if (s[i - 1] != '0')
                    dp[i] = dp[i - 1];
                else
                    dp[i] = 0;
                if (s[i - 2] == '1')
                    dp[i] = (dp[i] + dp[i - 2]) % M;
                else if (s[i - 2] == '2' && s[i - 1] <= '6')
                    dp[i] = (dp[i] + dp[i - 2]) % M;
                else if (s[i - 2] == '*') {
                    if (s[i - 1] <= '6')
                        dp[i] = (dp[i] + 2 * dp[i - 2]) % M;
                    else
                        dp[i] = (dp[i] + dp[i - 2]) % M;
                }
            }
        }
        return (int) dp[s.size()];
    }
};

#define LL long long

class Solution {

public:

int numDecodings(string s) {

if (s.empty() || s[0] == '0')

return 0;

int M = 1000000007;

vector<LL> dp(s.size() + 1);

dp[0] = 1;

dp[1] = s[0] == '*' ? 9 : 1;

for (int i = 2; i <= s.size(); i++) {

if (s[i - 1] == '*') {

dp[i] = 9 * dp[i - 1];

if (s[i - 2] == '1')

dp[i] = (dp[i] + 9 * dp[i - 2]) % M;

else if (s[i - 2] == '2')

dp[i] = (dp[i] + 6 * dp[i - 2]) % M;

else if (s[i - 2] == '*')

dp[i] = (dp[i] + 15 * dp[i - 2]) % M;

} else {

if (s[i - 1] != '0')

dp[i] = dp[i - 1];

else

dp[i] = 0;

if (s[i - 2] == '1')

dp[i] = (dp[i] + dp[i - 2]) % M;

else if (s[i - 2] == '2' && s[i - 1] <= '6')

dp[i] = (dp[i] + dp[i - 2]) % M;

else if (s[i - 2] == '*') {

if (s[i - 1] <= '6')

dp[i] = (dp[i] + 2 * dp[i - 2]) % M;

else

dp[i] = (dp[i] + dp[i - 2]) % M;

}

return (int) dp[s.size()];

}

};

等差数列划分

413. 等差数列划分

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，以下数列为等差数列:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。

1, 1, 2, 5, 7
 

数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。

如果满足以下条件，则称子数组(P, Q)为等差数组：

元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

函数要返回数组 A 中所有为等差数组的子数组个数。

 

示例:

A = [1, 2, 3, 4]

返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，以下数列为等差数列:

1, 3, 5, 7, 9

7, 7, 7, 7

3, -1, -5, -9

以下数列不是等差数列。

1, 1, 2, 5, 7

数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。

如果满足以下条件，则称子数组(P, Q)为等差数组：

元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

函数要返回数组 A 中所有为等差数组的子数组个数。

示例:

A = [1, 2, 3, 4]

返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

public class Fourhundred_thirteen {
    /**
     * dp[i]记录以元素A[i]结尾的等差数列的个数。
     * <p>
     * 如果[1,2,3,4,5,6]是一个等差数列，则
     * 以A[2]结尾的等差数列 [1,2,3]
     * 以A[3]结尾的等差数列 [1,2,3,4],[2,3,4]
     * 以A[4]结尾的等差数列 [1,2,3,4,5],[2,3,4,5],[3,4,5]
     * 以A[5]结尾的等差数列 [1,2,3,4,5,6],[2,3,4,5,6],[3,4,5,6],[4,5,6]
     * <p>
     * 转移方程： dp[i] = dp[i - 1] + 1
     */
    public int numberOfArithmeticSlices(int[] A) {
        if (A == null || A.length <= 2)
            return 0;
        int[] dp = new int[A.length];
        int ans = 0;
        for (int i = 2; i < A.length; i++) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                dp[i] = dp[i - 1] + 1;
                ans += dp[i];
            }
        }
        return ans;
    }
}

public class Fourhundred_thirteen {

/**

* dp[i]记录以元素A[i]结尾的等差数列的个数。

* <p>

* 如果[1,2,3,4,5,6]是一个等差数列，则

* 以A[2]结尾的等差数列 [1,2,3]

* 以A[3]结尾的等差数列 [1,2,3,4],[2,3,4]

* 以A[4]结尾的等差数列 [1,2,3,4,5],[2,3,4,5],[3,4,5]

* 以A[5]结尾的等差数列 [1,2,3,4,5,6],[2,3,4,5,6],[3,4,5,6],[4,5,6]

* <p>

* 转移方程： dp[i] = dp[i - 1] + 1

public int numberOfArithmeticSlices(int[] A) {

if (A == null || A.length <= 2)

return 0;

int[] dp = new int[A.length];

int ans = 0;

for (int i = 2; i < A.length; i++) {

if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {

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

ans += dp[i];

}

return ans;

}

class Solution {
public:
    int numberOfArithmeticSlices(vector<int> &A) {
        if (A.empty() || A.size() < 3)
            return 0;
        vector<int> dp(A.size(), 0);
        int ans = 0;
        for (int i = 2; i < A.size(); i++) {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
                dp[i] = dp[i - 1] + 1;
                ans += dp[i];
            }
        }
        return ans;
    }
};

class Solution {

public:

int numberOfArithmeticSlices(vector<int> &A) {

if (A.empty() || A.size() < 3)

return 0;

vector<int> dp(A.size(), 0);

int ans = 0;

for (int i = 2; i < A.size(); i++) {

if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {

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

ans += dp[i];

}

return ans;

}

};

446. 等差数列划分 II – 子序列

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，以下数列为等差数列:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。

1, 1, 2, 5, 7
 

数组 A 包含 N 个数，且索引从 0 开始。该数组子序列将划分为整数序列 (P0, P1, ..., Pk)，P 与 Q 是整数且满足 0 ≤ P0 < P1 < ... < Pk < N。

 

如果序列 A[P0]，A[P1]，...，A[Pk-1]，A[Pk] 是等差的，那么数组 A 的子序列 (P0，P1，…，PK) 称为等差序列。值得注意的是，这意味着 k ≥ 2。

函数要返回数组 A 中所有等差子序列的个数。

输入包含 N 个整数。每个整数都在 -231 和 231-1 之间，另外 0 ≤ N ≤ 1000。保证输出小于 231-1。

 

示例：

 

输入：[2, 4, 6, 8, 10]

输出：7

解释：
所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，以下数列为等差数列:

1, 3, 5, 7, 9

7, 7, 7, 7

3, -1, -5, -9

以下数列不是等差数列。

1, 1, 2, 5, 7

数组 A 包含 N 个数，且索引从 0 开始。该数组子序列将划分为整数序列 (P0, P1, ..., Pk)，P 与 Q 是整数且满足 0 ≤ P0 < P1 < ... < Pk < N。

如果序列 A[P0]，A[P1]，...，A[Pk-1]，A[Pk] 是等差的，那么数组 A 的子序列 (P0，P1，…，PK) 称为等差序列。值得注意的是，这意味着 k ≥ 2。

函数要返回数组 A 中所有等差子序列的个数。

输入包含 N 个整数。每个整数都在 -231 和 231-1 之间，另外 0 ≤ N ≤ 1000。保证输出小于 231-1。

示例：

输入：[2, 4, 6, 8, 10]

输出：7

解释：

所有的等差子序列为：

[2,4,6]

[4,6,8]

[6,8,10]

[2,4,6,8]

[4,6,8,10]

[2,4,6,8,10]

[2,6,10]

public class Fourhundred_fortySix {
    /**
     * f[i][d] ，代表以 A[i] 结束且公差为 d 的等差数列个数。
     * 转移方程：j < i，f[i][A[i] - A[j]] += (f[j][A[i] - A[j]] + 1)
     * 用map而不用数组是因为公差diff不知道有多大
     */
    public int numberOfArithmeticSlices(int[] A) {
        if (A == null || A.length < 3)
            return 0;
        long ans = 0;
        Map<Integer, Integer>[] cnt = new HashMap[A.length];
        for (int i = 0; i < A.length; i++) {
            cnt[i] = new HashMap<>();
            for (int j = 0; j < i; j++) {
                long delta = (long) A[i] - (long) A[j];//先转化再求差，否则会溢出
                if (delta < Integer.MIN_VALUE || delta > Integer.MAX_VALUE)
                    continue;
                int diff = (int) delta;
                int iCnt = cnt[i].getOrDefault(diff, 0);
                int jCnt = cnt[j].getOrDefault(diff, 0);
                cnt[i].put(diff, iCnt + jCnt + 1);
                ans += jCnt;
            }
        }
        return (int) ans;
    }
}

public class Fourhundred_fortySix {

/**

* f[i][d] ，代表以 A[i] 结束且公差为 d 的等差数列个数。

* 转移方程：j < i，f[i][A[i] - A[j]] += (f[j][A[i] - A[j]] + 1)

* 用map而不用数组是因为公差diff不知道有多大

public int numberOfArithmeticSlices(int[] A) {

if (A == null || A.length < 3)

return 0;

long ans = 0;

Map<Integer, Integer>[] cnt = new HashMap[A.length];

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

cnt[i] = new HashMap<>();

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

long delta = (long) A[i] - (long) A[j];//先转化再求差，否则会溢出

if (delta < Integer.MIN_VALUE || delta > Integer.MAX_VALUE)

continue;

int diff = (int) delta;

int iCnt = cnt[i].getOrDefault(diff, 0);

int jCnt = cnt[j].getOrDefault(diff, 0);

cnt[i].put(diff, iCnt + jCnt + 1);

ans += jCnt;

}

return (int) ans;

}

#define LL long long

class Solution {
public:
    int numberOfArithmeticSlices(vector<int> &A) {
        if (A.empty() || A.size() < 3)
            return 0;
        vector<unordered_map<int, int>> cnt(A.size());
        LL ans = 0;
        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j < i; j++) {
                LL delta = (LL) A[i] - (LL) A[j];
                if (delta < INT_MIN || delta > INT_MAX)
                    continue;
                int diff = (int) delta;
                int j_cnt = 0;
                if (cnt[j].find(diff) != cnt[j].end())
                    j_cnt = cnt[j][diff];
                cnt[i][diff] += j_cnt + 1;
                ans += j_cnt;
            }
        }
        return (int) ans;
    }
};

#define LL long long

class Solution {

public:

int numberOfArithmeticSlices(vector<int> &A) {

if (A.empty() || A.size() < 3)

return 0;

vector<unordered_map<int, int>> cnt(A.size());

LL ans = 0;

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

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

LL delta = (LL) A[i] - (LL) A[j];

if (delta < INT_MIN || delta > INT_MAX)

continue;

int diff = (int) delta;

int j_cnt = 0;

if (cnt[j].find(diff) != cnt[j].end())

j_cnt = cnt[j][diff];

cnt[i][diff] += j_cnt + 1;

ans += j_cnt;

}

return (int) ans;

}

};

子序列和子数组

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