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'。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
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);
        }
    }
};

200. 岛屿数量

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

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
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;
    }
}
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。
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;//temp也不能回溯,因为主程序是全部遍历
        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。
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"]。但是它自然排序更大更靠后。
/**
     * 用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);//一定倒着存,将孤立节点放在最后访问。题目保证一定会有路径
    }
};

79. 单词搜索

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

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

示例:

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;
    }
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]] (上图中带括号的单元).
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);
            }
        }
    }
};

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 的邻居。
必须将给定节点的拷贝作为对克隆图的引用返回。
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];
    }
};

473. 火柴拼正方形

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

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

示例 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);
    }
}
class Solution {
public:
    bool makesquare(vector<int> &nums) {
        if (nums.empty())
            return false;
        //剪枝: 大的先放,减少比较次数
        sort(nums.rbegin(), nums.rend());
        int sum = 0;
        for (auto num:nums)
            sum += num;
        if (sum % 4 != 0)
            return false;
        int len = sum / 4;
        return helper(nums, 0, 0, 0, 0, 0, len);

    }

    bool helper(vector<int> &nums, int index, int left, int right, int up, int down, int len) {
        if (index > nums.size() || left > len || right > len || up > len || down > len)
            return false;
        if (index == nums.size()) {
            if (left == len && right == len && up == len && down == len)
                return true;
            else
                return false;
        }
        //剪枝: 提前判断长度
        return (left + nums[index] <= len && helper(nums, index + 1, left + nums[index], right, up, down, len)) ||
               (right + nums[index] <= len && helper(nums, index + 1, left, right + nums[index], up, down, len)) ||
               (up + nums[index] <= len && helper(nums, index + 1, left, right, up + nums[index], down, len)) ||
               (down + nums[index] <= len && helper(nums, index + 1, left, right, up, down + 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位整数。
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);
    }
};

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
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;//本来就腐烂的也算在里面了
    }
};

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

279. 完全平方数

给定正整数 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];
    }
}
    // 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;
    }
};

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" 不在字典中,所以无法进行转换。
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;
    }
};

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]里边。
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;
    }
};

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

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。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。
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;
    }
};

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' 中产生。
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;
    }
};

课程表 拓扑排序

路径(和)

120. 三角形最小路径和

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

例如,给定三角形:

[
     [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);
    }
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
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];
    }
};

64. 最小路径和

给定一个包含非负整数的 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];
    }
}
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];
    }
};

return the last

不同的二叉搜索树

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

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

return the last

解码方法

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) 。
   /*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()];
    }
};

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'。
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()];
    }
};

return the last