5、搜索

BFS

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

| 给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
- 路径途经的所有单元格都的值都是 0 。
- 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
畅通路径的长度 是该路径途经的单元格总数。

示例 1：

输入：grid = [[0,1],[1,0]]
输出：2 | | —- |

题解思路：题目要求为求解最短路径问题，那么优先选择的肯定是广度优先算法（一层一层的遍历，达到目的地就退出），如果使用DFS必然需要遍历所有的路径然后选择最短的，时间复杂度较高。

在实现BFS时需要考虑以下问题
1、队列：用于存储每一轮遍历得到的节点
2、标记：对于遍历过的节点，应该将它标记，防止重复遍历

class Solution {
    //八个方向移动的数组
    private static int[][] directions = {{0, 1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {-1, -1}, {-1, 0}, {-1, 1}};
    //行数和列数
    private static int m, n;
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return -1;
        m = grid.length;
        n = grid[0].length;
        int count = 0;//结果集
        //起始点与终止点为0的话直接退出，无法满足题目描述
        if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1)
            return -1;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int size = queue.size();//当前层的节点的数量
            count++;//每一层就+1；
            //遍历获取当前层
            for (int i = 0; i < size; i++) {
                int[] arr = queue.poll();
                int x = arr[0], y = arr[1];
               /* if (grid[x][y] == 1)
                    continue;*/
                //如果到达最后一个坐标的话就返回结果
                if (x == m - 1 && y == n - 1) {
                    return count;
                }
                //标识已经访问过（也可以在这标识，加入时不做判断）
                //向八个方向进行扩散
                for (int j = 0; j < directions.length; j++) {
                    int nr = x + directions[j][0], nc = y + directions[j][1];
                    //判断前往的方向是否满足条件
                    if (!getRegin(nr, nc)) {
                        continue;
                    }
                    if (grid[nr][nc] == 1)
                        continue;
                    queue.add(new int[]{nr, nc});
                    //标识已经访问过
                    grid[nr][nc] = 1;
                }
            }
        }
        return -1;
    }
    public boolean getRegin(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

注：1、创建一个方向数组，通过遍历的方式实现8个方向的移动
2、在加入时判断且加入后置1，可以在很大程度上优化时间消耗。因为置位后导致相同的路径不会被重复加入。

279. 完全平方数

题解思路：1、将每个整数看成图中的一个节点，如果两个整数之差为一个平方数，那么两个整数所在的节点就有一条边。
2、要求解最小的平方数数量 ，就是求解从节点n到节点0的最短路径。

    class Solution {
    public int numSquares(int n) {
        //1、获取所有的小于n的平方数
        List<Integer> squares = generateSquares(n);
        Queue<Integer> queue = new LinkedList<>();//创建队列
        boolean[] marked = new boolean[n + 1];    //标识数组
        queue.add(0);
        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            count++;
            for (int i = 0; i < size; i++) {
                int num = queue.poll();
                //终止条件
                if (num == n)
                    return count - 1;
                //判断入队
                for (int x : squares) {
                    if (x + num <= n && !marked[x + num]) {
                        queue.add(x + num);
                        marked[x + num] = true;
                    }
                }
            }
        }
        return -1;
    }
    private List<Integer> generateSquares(int n) {
        List<Integer> squares = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i * i <= n) {
                squares.add(i * i);
            } else {
                break;
            }
        }
        return squares;
    }

注：这里要创建一个marked标识的数组，因为如果这个数曾经进入过的话，那么后面再进入后的操作必然时重复的。不标识的话就会超时。

127. 单词接龙

| 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列是一个按下述规格形成的序列：
- 序列中第一个单词是 beginWord 。
- 序列中最后一个单词是 endWord 。
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
示例 1：
输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
输出：5
解释：一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。 | | —- |

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //依旧是BFS的套路，但是这里多了一步处理，就是需要判断当前字符可以转换为哪些字符。
        //创建队列
        Queue<String> queue = new LinkedList<>();
        int count = 0;
        queue.add(beginWord);
        Map<String, Boolean> marked = new HashMap<>();
        for (String s : wordList) {
            marked.put(s, false);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            count++;
            while (size-- > 0) {
                String s = queue.poll();
                if (s.equals(endWord))
                    return count;
                List<String> strList = ValidList(wordList, s);
                for (String str : strList) {
                    if (!marked.get(str)) {
                        queue.add(str);
                        marked.put(str, true);
                    }
                }
            }
        }
        return 0;
    }
    public List<String> ValidList(List<String> wordList, String s) {
        List<String> list = new ArrayList<>();
        for (String str : wordList) {
            if (str.length() != s.length())
                continue;
            int count = 0;
            int index = 0;
            while (index < str.length()) {
                if (str.charAt(index) != s.charAt(index)) {
                    count++;
                }
                index++;
            }
            if (count <= 1)
                list.add(str);
        }
        return list;
    }
}

注：进一步优化的思路：提前创建图，不要每次都去判断字符可以跳到下一步的有哪些字符，而是一步创建到位，之后依次获取即可。

DFS

695. 岛屿的最大面积

题解思路：其实这道题的基本思想和岛屿数量是一样的，就在dfs中稍微的不同以及对于结果选取的不同

private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int maxAreaOfIsland(int[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }
    m = grid.length;
    n = grid[0].length;
    int maxArea = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            maxArea = Math.max(maxArea, dfs(grid, i, j));
        }
    }
    return maxArea;
}
private int dfs(int[][] grid, int r, int c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
        return 0;
    }
    grid[r][c] = 0;
    int area = 1;
    for (int[] d : direction) {
        area += dfs(grid, r + d[0], c + d[1]);
    }
    return area;
}

注：一开始自己没有想通dfs中的值要怎么返回（记）
int area = 1;
for (int[] d : direction) {
area += dfs(grid, r + d[0], c + d[1]);
}

200. 岛屿数量

方法一：深度优先搜索
我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
最终岛屿的数量就是我们进行深度优先搜索的次数。

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }
        return num_islands;
    }
     void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;
        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }
        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    } 
}

方法二：广度优先搜索
同样地，我们也可以使用广度优先搜索代替深度优先搜索。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。
最终岛屿的数量就是我们进行广度优先搜索的次数。

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    grid[r][c] = '0';
                    Queue<Integer> neighbors = new LinkedList<>();
                    neighbors.add(r * nc + c);
                    while (!neighbors.isEmpty()) {
                        int id = neighbors.remove();
                        int row = id / nc;
                        int col = id % nc;
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
                            neighbors.add((row-1) * nc + col);
                            grid[row-1][col] = '0';
                        }
                        if (row + 1 < nr && grid[row+1][col] == '1') {
                            neighbors.add((row+1) * nc + col);
                            grid[row+1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
                            neighbors.add(row * nc + col-1);
                            grid[row][col-1] = '0';
                        }
                        if (col + 1 < nc && grid[row][col+1] == '1') {
                            neighbors.add(row * nc + col+1);
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }
        return num_islands;
    }
}

547. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。 返回矩阵中 省份 的数量。 示例 1： 输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]] 输出：2

题解思路1：深度优先算法
遍历所有城市，对每个城市，如果该城市尚未被访问过，则从该城市开始深度优先搜索，通过矩阵isConnectd得到与该成是直接相连的城市有哪些，这些城市和该城市属于同一个连通分量，然后对这些城市继续深度优先搜索，直到同一个连通分量的所有城市都被访问到，即可得到一个省份，遍历完所有城市即可得到结果。

class Solution {
    private static int n;
    public int findCircleNum(int[][] isConnected) {
        n = isConnected.length;
        boolean[] used = new boolean[n];//标记该城市已经访问过
        int res=0;  //结果
        //从第一个城市开始遍历，如果没有访问过的话就开始搜索
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                dfs(isConnected, i, used);
                res++;
            }     
        }
        return res;
    }
    private void dfs(int[][] isConnected, int i, boolean[] used) {
        used[i] = true;
        //遍历是否有与第i个城市连接的城市且没有被访问过
        for (int j = 0; j < n; j++) {
            if (isConnected[i][j] == 1 && !used[j]) {
                dfs(isConnected, j, used);
            }
        }
    }
}

时间复杂度：O(n2)

题解思路2：广度优先搜索
对于每个城市，如果该城市尚未被访问过，则从该城市开始广度优先搜索，直到一个连通分量中所有的城市都被访问到，得到一个城市。

class Solution {
    private static int n;

    public int findCircleNum(int[][] isConnected) {
        n = isConnected.length;
        boolean[] used = new boolean[n];//标记该城市已经访问过
        int res = 0;  //结果

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    used[j] = true;
                    for (int k = 0; k < n; k++) {
                        if (isConnected[j][k] == 1 && !used[k])
                            queue.offer(k);
                    }
                }
                //一次广度优先搜索结束
                res++;
            }
        }
        //遍历完所有的城市
        return res;
    }
}

注：res++;要放在for循环体内。

题解思路3：并查集

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind unionFind = new UnionFind(n);
        int res=0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    res=unionFind.union(i, j);
                }
            }
        }
        return unionFind.size;
    }

    class UnionFind {
        int[] roots;
        int size;

        public UnionFind(int n) {
            roots = new int[n];
            for (int i = 0; i < n; i++) {
                roots[i] = i;
            }
            size = n;
        }

        public int find(int index) {
            if (index != roots[index]) {
                return find(roots[index]);
            }
            return index;
        }

        public int union(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);

            if (pRoot != qRoot) {
                roots[pRoot] = qRoot;
                size--;
            }
            return size;
        }
    }
}

130. 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。 示例 1： 输入：board = [[“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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

题解思路：深度优先搜索
由题意可知，与边界相连的O不需要被改变，那么我们就可以考虑从边界的O出发，找到与它们相连的O，剩下的O就是需要被改变的

class Solution {
    private static int m;
    private static int n;
    private static int[][] ps = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public void solve(char[][] board) {
        m = board.length;
        n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean isEdge = i == 0 || i == m - 1 || j == 0 || j == n - 1;
                if (isEdge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }

        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] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == 'X'||board[i][j]=='#')
            return;

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

        for (int[] p : ps) {
            dfs(board, i + p[0], j + p[1]);
        }
    }
}

207. 课程表

| 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。 | | —- |

题解思路1：BFS
1、统计课程安排图中每个节点的入度，生成 入度表 indegrees。
2、借助一个队列 queue，将所有入度为 0 的节点入队。
3、当 queue 非空时，依次将队首节点出队，在课程安排图中删除此节点 pre：
并不是真正从邻接表中删除此节点 pre，而是将此节点对应所有邻接节点 cur 的入度 -1，即 indegrees[cur] -= 1。
当入度 -1后邻接节点 cur 的入度为 0，说明 cur 所有的前驱节点已经被 “删除”，此时将 cur 入队。
4、在每次 pre 出队时，执行 numCourses—；

• 若整个课程安排图是有向无环图（即可以安排），则所有节点一定都入队并出队过，即完成拓扑排序。换个角度说，若课程安排图中存在环，一定有节点的入度始终不为 0。

• 因此，拓扑排序出队次数等于课程个数，返回 numCourses == 0 判断课程是否可以成功安排。

  class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //题解思路：题目要求先修条件问题。考虑将可以修的课程先加入到队列中。什么情况下是可以修的呢，就是当前依赖的课程都已经修完了。
        //为了记录这个修完的目标值，创建入度表
        int[] indegrees = new int[numCourses];
        //如何保证当前课程修完后与之关联的课程的入度表能够跟随修改呢（邻接表）
        List<List<Integer>> adjacency = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<>());
        }
        for (int[] cp : prerequisites) {
            indegrees[cp[0]]++;
            adjacency.get(cp[1]).add(cp[0]);
        }
  
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < indegrees.length; i++) {
            if (indegrees[i] == 0)
                queue.add(i);
        }
  
        while (!queue.isEmpty()) {
            int pre = queue.poll();
            numCourses--;
            for (int cur : adjacency.get(pre)) {
                indegrees[cur]--;
                if (indegrees[cur] == 0)
                    queue.add(cur);
            }
        }
        return numCourses == 0;
    }
  }
  

题解思路2：DFS
1、借助一个标志列表 flags，用于判断每个节点 i （课程）的状态：

• 未被 DFS 访问：i == 0；
• 已被其他节点启动的 DFS 访问：i == -1；
• 已被当前节点启动的 DFS 访问：i == 1。

2、对 numCourses 个节点依次执行 DFS，判断每个节点起步 DFS 是否存在环，若存在环直接返回 False。
DFS 流程；

• 终止条件：
  • 当 flag[i] == -1，说明当前访问节点已被其他节点启动的 DFS 访问，无需再重复搜索，直接返回 True。
  • 当 flag[i] == 1，说明在本轮 DFS 搜索中节点 i 被第 2次访问，即 课程安排图有环 ，直接返回 False。
• 将当前访问节点 i 对应 flag[i] 置 1，即标记其被本轮 DFS 访问过；
• 递归访问当前节点 i 的所有邻接节点 j，当发现环直接返回 False；
• 当前节点所有邻接节点已被遍历，并没有发现环，则将当前节点 flag 置为 -1 并返回 True。

3、若整个图 DFS 结束并未发现环，返回 True。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }
        for (int[] cp : prerequisites) {
            list.get(cp[1]).add(cp[0]);
        }
        int[] flag = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(list, flag, i)) return false;
        }
        return true;
    }

    public boolean dfs(List<List<Integer>> adjacency, int[] flags, int i) {
        if (flags[i] == -1) return true;
        if (flags[i] == 1) return false;
        flags[i] = 1;
        for (int cur : adjacency.get(i)) {
            if (!dfs(adjacency, flags, cur)) return false;
        }
        flags[i] = -1;
        return true;
    }
}

注：当处理这种有值与值之间的对应关系的题目的时候，优选不一定是map，也可以考虑通过list的下标+索引的方式。

回溯

回溯算法题解思路
解决回溯问题（决策树）需要考虑三个问题：

回溯算法的框架

result=[]
def backtrack(路径，选择列表)；
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        //可能需要排除不可达的解
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核心就是for循环里面的递归，在递归调用之前做出选择，在递归调用之后取消选择。

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例 1： 输入：digits = “23” 输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

题解思路：
1、考虑到数字对应的字符串会被重复利用，所以考虑选择通过Map存储，一开始我考虑的方法是通过switch获取，但是代码不够简洁。
2、题目中出现“所有组合”字样时，考虑使用回溯算法。回溯算法的思想在于：不断的向下寻找每一个可能的解，假设出现解不可行，则需要舍弃不可行的解，并进行状态的回溯。

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations=new ArrayList<>();
        if(digits.length()==0) return combinations;

         Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};

        backTrack(combinations,phoneMap,digits,0,new StringBuffer());
        return combinations;
    }

    public void backTrack(List<String> combinations,Map<Character,String> phoneMap,String digits,int index,StringBuffer combination){
        if(index==digits.length()){
            combinations.add(combination.toString());
        }else{
            char c=digits.charAt(index);
            String letters=phoneMap.get(c);
            int count=letters.length();
            for(int i=0;i<count;i++){
                combination.append(letters.charAt(i));
                backTrack(combinations,phoneMap,digits,index+1,combination);
                combination.deleteCharAt(index);//删除StringBuffer中的字母，方便下一次的组合
            }
        }
    }
}

注意：在上面这段代码中，要学习的两个点是，这个题解的思路类似八皇后的问题，一层一层的获取每一个可能，但是由于这里没有不可解，所以只是获取了所有的可能。代码中的StringBuffer作为了状态变量，在成功后需要重置。
StringBuffer删除指定的位置上的元素： stringBuffer.deleteCharAt( int index)；

93. 复原 IP 地址

题解思路：获取所有的可能性（回溯算法）
分析剪枝条件
1、一开始，字符串的长度小于4或者大于12都不能凑出合理的IP地址。
2、每一个节点最多可以有三种截取方法：截1位、截2位、截3位，因此每一个节点可以生长出的分支最多只有3条分支。
3、由于ip段最多就4个段，因此这棵三叉树最多4层，这个条件是递归终止条件之一
4、每个节点表示了求解这个问题的不同阶段，需要的状态变量有

• splitTimes：已经分割出多少个IP段
• begin：截取ip段的起始位置
• path：记录从根节点到叶子节点的一个路径

• res：记录结果集的变量，常规变量

  class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();//结果集
        StringBuilder tempAddress = new StringBuilder();//存储中间值
        doRestore(0, tempAddress, res, s);
        return res;
    }
  
    //截取到哪个片段（k）
    //tempAddress 存储中间结果集
    //address(结果)
    //s 原来的字符串
    private void doRestore(int k, StringBuilder tempAddress, List<String> addresses, String s) {
        if (k == 4 || s.length() == 0) {
            if (k == 4 && s.length() == 0) {
                addresses.add(tempAddress.toString());
            }
            return;
        }
  
        for (int i = 0; i < s.length() && i <= 2; i++) {
            if (i != 0 && s.charAt(0) == '0') {
                break;
            }
  
            String part = s.substring(0, i + 1);
            if (Integer.valueOf(part) <= 255) {
                if (tempAddress.length() != 0) {
                    part = "." + part;
                }
                tempAddress.append(part);
                doRestore(k + 1, tempAddress, addresses, s.substring(i + 1));
                tempAddress.delete(tempAddress.length() - part.length(),tempAddress.length());
            }
        }
    }
  }
  

  选择——》递归——》回溯

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例 1： 输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED” 输出：true

题解思路1：DFS（深度优先搜索）+回溯

class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (backtrace(board, word, i, j, 0))
                        return true;
                }
            }
        }
        return false;
    }

    public boolean backtrace(char[][] board, String word, int m, int n, int index) {
        if (index == word.length()) return true;

        if (m < 0 || n < 0 || m >= board.length || n >= board[0].length) return false;

        if (board[m][n] != word.charAt(index)) return false;

        char tem = board[m][n];
        board[m][n] = '0';
        boolean res = ( backtrace(board, word, m - 1, n, index + 1) ||
                        backtrace(board, word, m + 1, n, index + 1) ||
                        backtrace(board, word, m, n + 1, index + 1) ||
                        backtrace(board, word, m, n - 1, index + 1));
        board[m][n]=tem;
        return res;
    }
}

注：注意判定的条件 m >= board.length不可以等于，其次在哪里回溯。

257. 二叉树的所有路径

public List<String> binaryTreePaths(TreeNode root) {
    List<String> paths = new ArrayList<>();
    if (root == null) {
        return paths;
    }
    List<Integer> values = new ArrayList<>();
    backtracking(root, values, paths);
    return paths;
}

private void backtracking(TreeNode node, List<Integer> values, List<String> paths) {
    if (node == null) {
        return;
    }
    values.add(node.val);
    if (isLeaf(node)) {
        paths.add(buildPath(values));
    } else {
        backtracking(node.left, values, paths);
        backtracking(node.right, values, paths);
    }
    values.remove(values.size() - 1);
}

private boolean isLeaf(TreeNode node) {
    return node.left == null && node.right == null;
}

private String buildPath(List<Integer> values) {
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < values.size(); i++) {
        str.append(values.get(i));
        if (i != values.size() - 1) {
            str.append("->");
        }
    }
    return str.toString();
}

46. 全排列

题解思路：获取所有的可能结果（回溯算法）

class Solution {
    List<List<Integer>> res=new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> track=new LinkedList<>();
        backTrack(nums,track);
        return res;
    }
    void backTrack(int[] nums,LinkedList<Integer> track){
        if(nums.length==track.size()){
            res.add(new LinkedList(track));
            return;
        }

        for(int i=0;i<nums.length;i++){
            if(track.contains(nums[i]))
                continue;
            track.add(nums[i]);
            backTrack(nums,track);
            track.removeLast();
        }
    }
}

47. 全排列 II

class Solution {
    List<List<Integer>> res=new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        LinkedList<Integer> track=new LinkedList<>();
        Arrays.sort(nums);
        boolean[] used=new boolean[nums.length];
        backTrack(nums,track,used);
        return res;
    }

    void backTrack(int[] nums,LinkedList<Integer> track,boolean[] used){
        if(nums.length==track.size()){
            res.add(new LinkedList(track));
            return;
        }

        for(int i=0;i<nums.length;i++){
            if(used[i]||(i>0&&nums[i]==nums[i-1]&&!used[i-1]))
                continue;
            track.add(nums[i]);
            used[i]=true;
            backTrack(nums,track,used);
            track.removeLast();
            used[i]=false;
        }
    }
}

注：排序+相同值判断跳过。

77. 组合

class Solution {
    private static List<List<Integer>> res;
    public List<List<Integer>> combine(int n, int k) {
        res=new ArrayList<>();
        LinkedList<Integer> list=new LinkedList<>();
        backTrace(list,k,n,0);
        return res;
    }

    public void backTrace(LinkedList<Integer> list,int k,int n,int index){
        if(list.size()==k)
            res.add(new LinkedList<>(list));

        for(int i=index;i<n;i++){
            if(list.contains(i+1))        //不必要
                continue;
            //如果剩余的字符不足以构成k的话不需要继续判断
            list.add(i+1);
            backTrace(list,k,n,i+1);
            list.removeLast();
        }
    }
}

运行效率慢，观察程序，哪里的操作是不必要的，或者是可以优化的。
修改版

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> combinations = new ArrayList<>();
    List<Integer> combineList = new ArrayList<>();
    backtracking(combineList, combinations, 1, k, n);
    return combinations;
}

private void backtracking(List<Integer> combineList, List<List<Integer>> combinations, int start, int k, final int n) {
    if (k == 0) {
        combinations.add(new ArrayList<>(combineList));
        return;
    }
    for (int i = start; i <= n - k + 1; i++) {  // 剪枝
        combineList.add(i);
        backtracking(combineList, combinations, i + 1, k - 1, n);
        combineList.remove(combineList.size() - 1);
    }
}

39. 组合总和

| 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括 target）都是正整数。
- 解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7],target = 7,
所求解集为：
[
[7],
[2,2,3]
] | | —- |

题解思路：
1、回溯算法获取所有的情况。为了防止出现重复的解，对数组进行排序，索引指针不断移动。阻止解的重复。

    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int sum = 0;
        Arrays.sort(candidates);
        backtrace(candidates, target, sum,0);
        return res;
    }

    public void backtrace(int[] candidates, int targrt, int sum, int index) {
        if (sum == targrt) {
            res.add(new ArrayList<Integer>(list));
        }

        for (int i = index; i < candidates.length; i++) {        //index
            if (targrt - sum < candidates[i])
                continue;//这里可以使用break，进一步提高效率
            list.add(candidates[i]); 
            sum += candidates[i];
            backtrace(candidates, targrt, sum,index++);            //注意
               //backtrace(candidates, targrt, sum,i);
            list.removeLast();                                    //回溯
            sum -= candidates[i];
        }
    }

注：这里重点关注一下这个index++的操作。因为++写在后面，所以递归的参数还是index，但是在本方法中index已经变为了index+1
其实这种写法不是很好理解。

40. 组合总和 II

| 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
] | | —- |

class Solution {
    private List<List<Integer>> res;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        res=new ArrayList<>();
        LinkedList<Integer> list=new LinkedList<>();
        Arrays.sort(candidates);
        boolean[] used=new boolean[candidates.length];
        backTrace(list,candidates,target,0,used);
        return res;
    }

public void backTrace(LinkedList<Integer> list,int[] candidates,int target,int index, boolean[] used){
        if(target==0){
            res.add(new LinkedList<>(list));
            return; 
        }

        for(int i=index;i<candidates.length;i++){
            if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false)
                continue;
            if(target-candidates[i]<0)
                continue;
            list.add(candidates[i]);
            used[i]=true;
            backTrace(list,candidates,target-candidates[i],i+1,used);
            list.removeLast();
            used[i]=false;
        }
    }
}

216. 组合总和 III

| 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]] | | —- |

（DONE）

22. 括号生成

class Solution {
    List<String> res=new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if(n<=0)
            return res;
        getParenthesis("",n,n);
        return res;
    }

    private void getParenthesis(String str,int left,int right){
        if(left==0&&right==0){
            res.add(str);
            return;
        }

        if (left==right){
            //剩余的左括号等于右括号，下一次只能使用左括号
            getParenthesis(str+="(",left-1,right);
        }else if (left<right){
            if (left>0)
                getParenthesis(str+"(",left-1,right);
            getParenthesis(str+")",left,right-1);
        }
    }
}

class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder cur = new StringBuilder();
    public List<String> generateParenthesis(int n) {
        dfs(n,0,0);
        return res;
    }

    private void dfs(int max,int left,int right){
        if (left==max&&right==max){
            res.add(cur.toString());
            return;
        }

        if (left<max){
            cur.append("(");
            dfs(max,left+1,right);
            cur.deleteCharAt(cur.length()-1);
        }

        if(left>right){
            cur.append(")");
            dfs(max,left,right+1);
            cur.deleteCharAt(cur.length()-1);
        }

    }
}

698. 划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1]，k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

角度1：从n个数的角度来做回溯，每个数都要被遍历一边进入每一个桶一次，尝试是否可以成功。

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if(k>nums.length) return false;
        int sum=0;
        for(int num:nums)
            sum+=num;
        if(sum%k!=0) return false;

        int[] bucket=new int[k];
        int target=sum/k;

        return backtrack(nums,0,bucket,target);
    }

    boolean backtrack(int[] nums,int index,int[] bucket,int target){
        //在此处是需要进行一次判读的，是否会达成要求的条件。
        if (index==nums.length) {
            for (int i = 0; i < bucket.length; i++) {
                if (bucket[i]!=target)
                    return false;
            }
            return true;
        }

        for(int i=0;i<bucket.length;i++){
            //选择数值加入哪个桶中
            //剪枝
            if (bucket[i]+nums[index]>target)
                continue;
            bucket[i]+=nums[index];
            //进入下一次选择
            if(backtrack(nums,index+1,bucket,target)){
                return true;
            }
            //回溯，退回原来的状态
            bucket[i]-=nums[index];
        }
        return false;
    }
}

优化

public boolean canPartitionKSubsets(int[] nums, int k) {
    // 其他代码不变
    // ...
    /* 降序排序 nums 数组 */
    Arrays.sort(nums);
    int i = 0, j = nums.length - 1;
    for (; i < j; i++, j--) {
        // 交换 nums[i] 和 nums[j]
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    /*******************/
    return backtrack(nums, 0, bucket, target);
}

由于 Java 的语言特性，这段代码通过先升序排序再反转，达到降序排列的目的。

角度2：以桶的视角：每个桶都需要遍历nums中的所有的数字，决定是否将当前数字装入桶中，当装满一个桶后，还要装下一个桶，知道所有的桶都装完。

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        //排除一些特殊的情况
        if(k>nums.length)
            return false;
        int sum=0;
        for(int num:nums) sum+=num;
        if(sum%k!=0) return false;

        boolean[] used=new boolean[nums.length];
        int target=sum/k;
        return backtrack(k,0,nums,0,used,target);
    }

    boolean backtrack(int k,int bucket,int[] nums,int start,boolean[] used,int target){
        if (k==0)
            return true;

        if (bucket==target)
            return backtrack(k-1,0,nums,0,used,target);

        for(int i=start;i<nums.length;i++){
            if (bucket+nums[i]>target||used[i])
                continue;
            bucket+=nums[i];
            used[i]=true;
            if (backtrack(k,bucket,nums,i+1,used,target)){
                return true;
            }
            bucket-=nums[i];
            used[i]=false;
        }
        return false;
    }
}

注意：这里存在一个比较难想到的点：在于for循环中为了继续循环下去的话还是用了递归的方式来完成

78. 子集

回溯思想：对List进行回溯

class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        backtrack(0, nums,new ArrayList<>());
        return res;
    }

    private void backtrack(int index, int[] nums,ArrayList<Integer> list) {
        res.add(new ArrayList<>(list));

        for (int i = index; i < nums.length; i++) {
            list.add(nums[i]);
            backtrack(i+1, nums,list);                **
            list.remove(list.size() - 1);
        }
    }
}

注：一开始自己的思路是没有问题的，就是每次回溯函数里面只要一进来就将结果封装到res中。但是自己陷入寻找终止条件的思维定式中，一直想要通过什么条件来结束递归。但是其实for循环判断失败后，整个递归就算结束了。
1、在标记处，刚开始写的是index++，不仅会出现死循环，而且不应该使用index，会有重复解。

90. 子集 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        boolean[] used=new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(0, nums,new ArrayList<>(),used);

        return res;
    }

     private void backtrack(int index, int[] nums,ArrayList<Integer> list, boolean[] used) {
        res.add(new ArrayList<>(list));

        for (int i = index; i < nums.length; i++) {
            if(i>0&&nums[i-1]==nums[i]&&used[i-1]==false)
                continue;
            list.add(nums[i]);
            used[i]=true;
            backtrack(i+1, nums,list,used);                
            list.remove(list.size() - 1);
            used[i]=false;
        }
    }
}

131. 分割回文串

public List<List<String>> partition(String s) {
    List<List<String>> partitions = new ArrayList<>();
    List<String> tempPartition = new ArrayList<>();
    doPartition(s, partitions, tempPartition);
    return partitions;
}

private void doPartition(String s, List<List<String>> partitions, List<String> tempPartition) {
    if (s.length() == 0) {
        partitions.add(new ArrayList<>(tempPartition));
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        if (isPalindrome(s, 0, i)) {
            tempPartition.add(s.substring(0, i + 1));
            doPartition(s.substring(i + 1), partitions, tempPartition);
            tempPartition.remove(tempPartition.size() - 1);
        }
    }
}

private boolean isPalindrome(String s, int begin, int end) {
    while (begin < end) {
        if (s.charAt(begin++) != s.charAt(end--)) {
            return false;
        }
    }
    return true;
}

37. 解数独

| 编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
1. 数字 1-9 在每一行只能出现一次。
1. 数字 1-9 在每一列只能出现一次。
1. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。 | | —- |

题解思路：一个个元素尝试

class Solution {
    public void solveSudoku(char[][] board) {
        // 三个布尔数组 表明 行, 列, 还有 3*3 的方格的数字是否被使用过
        boolean[][] rowUsed = new boolean[9][10];
        boolean[][] colUsed = new boolean[9][10];
        boolean[][][] boxUsed = new boolean[3][3][10];
        // 初始化
        for(int row = 0; row < board.length; row++){
            for(int col = 0; col < board[0].length; col++) {
                int num = board[row][col] - '0';
                if(1 <= num && num <= 9){
                    rowUsed[row][num] = true;
                    colUsed[col][num] = true;
                    boxUsed[row/3][col/3][num] = true;
                }
            }
        }
        // 递归尝试填充数组
        recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, 0, 0);
    }

    private boolean recusiveSolveSudoku(char[][]board, boolean[][]rowUsed, boolean[][]colUsed, boolean[][][]boxUsed, int row, int col){
        // 边界校验, 如果已经填充完成, 返回true, 表示一切结束
        //如果列到了最后，但是行没有的话
        if(col == board[0].length){
            //重新将列置为第一列
            col = 0;
            //行+1；
            row++;
            if(row == board.length){
                return true;
            }
        }
        // 是空则尝试填充, 否则跳过继续尝试填充下一个位置
        if(board[row][col] == '.') {
            // 尝试填充1~9
            for(int num = 1; num <= 9; num++){
                boolean canUsed = !(rowUsed[row][num] || colUsed[col][num] || boxUsed[row/3][col/3][num]);
                if(canUsed){
                    rowUsed[row][num] = true;
                    colUsed[col][num] = true;
                    boxUsed[row/3][col/3][num] = true;

                    board[row][col] = (char)('0' + num);
                    if(recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1)){
                        return true;
                    }
                    board[row][col] = '.';

                    rowUsed[row][num] = false;
                    colUsed[col][num] = false;
                    boxUsed[row/3][col/3][num] = false;
                }
            }
        } else {
            return recusiveSolveSudoku(board, rowUsed, colUsed, boxUsed, row, col + 1);
        }
        return false;
    }
}

51. N 皇后

题解思路：每行每列每斜线都不可以重复
private boolean[] colUsed;
private boolean[] diagonals45Used;//45度角的节点
private boolean[] diagonals135Used;//135度角的节点
行数一行一行的填充自然不会有重复的情况。

class Solution {
    private List<List<String>> solutions;
    private char[][] nQueens;
    private boolean[] colUsed;
    private boolean[] diagonals45Used;//45度角的节点
    private boolean[] diagonals135Used;//135度角的节点
    private int n;

    public List<List<String>> solveNQueens(int n) {
        solutions=new ArrayList<>();
        nQueens=new char[n][n];
        for(int i=0;i<n;i++){
            Arrays.fill(nQueens[i],'.');//初始化棋盘
        }

        colUsed=new boolean[n];
        diagonals45Used=new boolean[2*n-1];//斜对角线的条数
        diagonals135Used=new boolean[2*n-1];
        this.n=n;
        backtracking(0);
        return solutions;
    }

    private void backtracking(int row){
        if(row==n){
            List<String> list=new ArrayList<>();
            for(char[] chars:nQueens){
                list.add(new String(chars));
            }
            solutions.add(list);
            return;
        }

        for(int col=0;col<n;col++){
            int diagonals45Idx=row+col;
            int diagonals135Idx=n-1-(row-col);
            if (colUsed[col] || diagonals45Used[diagonals45Idx] || diagonals135Used[diagonals135Idx]) {
                continue;
            }
            nQueens[row][col]='Q';
            colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = true;
            backtracking(row+1);
            colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = false;
            nQueens[row][col] = '.';
        } 
    }
}

1849. 将字符串拆分为递减的连续值

| 给你一个仅由数字组成的字符串 s 。
请你判断能否将 s 拆分成两个或者多个 非空子字符串 ，使子字符串的 数值 按 降序 排列，且每两个 相邻子字符串 的数值之 差 等于 1 。
- 例如，字符串 s = "0090089" 可以拆分成 ["0090", "089"] ，数值为 [90,89] 。这些数值满足按降序排列，且相邻值相差 1 ，这种拆分方法可行。
- 另一个例子中，字符串 s = "001" 可以拆分成 ["0", "01"]、["00", "1"] 或 ["0", "0", "1"] 。然而，所有这些拆分方法都不可行，因为对应数值分别是 [0,1]、[0,1] 和 [0,0,1] ，都不满足按降序排列的要求。
如果可以按要求拆分 s ，返回 true ；否则，返回 false 。
子字符串 是字符串中的一个连续字符序列。

示例 1：
输入：s = “1234”
输出：false
解释：不存在拆分 s 的可行方法。 | | —- |

class Solution {
    public boolean splitString(String s) {
        //枚举第一个数字的值，因为s长度为20，所以会超过int，要用long类型
        long t = 0;     
        //因为必须要分割成两个子串，所以最后一个字符不可能是组成第一个数字的字符，我们这里也是为了防止刚好20位导致long也会溢出的情况
        for (int i = 0; i < s.length() - 1; i++) {  
            //把当前字符加入到组成第一个数字的字符集中
            t = t * 10 + (s.charAt(i) - '0');
            //如果t大于10^10那么后面最多还有9位数，所以不可能组成递减的连续值
            if(t > 10000000000L)    
                return false;
            //把t当作第一个数字，找寻后面递减的数
            if (dfs(s, t, i + 1))   
                return true;
        }
        return false;
    }

    //s:要分割的字符串；pre:前面一个数的值；k:当前字符串已经用到了哪个位置
    private boolean dfs(String s, long pre, int k) {
        //遍历到字符串的最后一个元素，表示能组成递减的连续值
        if (k == s.length())    
            return true;
        //枚举pre后面的一个数字的值
        long t = 0;    
        for (int i = k; i < s.length(); i++) {  //从第k个字符开始组成数字
            t = t * 10 + s.charAt(i) -'0';
            if(t > 10000000000L)
                return false;
            //如果前面一个数字和当前数组相差为1，则继续往下面寻找满足条件的数组
            if (pre - 1 == t && dfs(s, t, i + 1))   
                return true;
            //当前组成的数大于前面的数表示不符合要求，直接返回false 
            if (t >= pre)  
                return false;
        }
        return false;
     }
}

注：1、在回溯的过程中保证数字是不断增加的：原来的数字*10+当前的数字。
2、注意long值越界的问题。

其他

128. 最长连续序列

题解思路1：找到最左端的最小数字开始向上查找。

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

题解思路2：HashMap
注：这里有两个点需要注意：
1、如果产生连接关系的话需要更新两个端点的值
2、不可以重复key 的操作，不然会产生叠加效。

class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        int res=0;
        for(int num:nums){
            if(!map.containsKey(num)){
                int pre=map.getOrDefault(num-1,0);
                int next=map.getOrDefault(num+1,0);
                int sum=pre+next+1;
                if(sum>res)
                    res=sum;
                map.put(num,sum);
                map.put(num-pre,sum);
                map.put(num+next,sum);
            }
        }
        return res;
    }
}