LeetCode刷题——搜索回溯相关题目

题目"/>

LeetCode刷题——搜索回溯相关题目

搜索相关问题

深度优先搜索和广度优先搜索是两种最常见的优先搜索方法，它们被广泛地运用在图和树等结构中进行搜索。

1.深度优先搜索问题

在搜索到一个新的节点时，立即对该新节点进行遍历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。深度优先搜索也可以用来检测环路：记录每个遍历过的节点的父节点，若一个节点被再次遍历且父节点不同，则说明有环。我们也可以用之后会讲到的拓扑排序判断是否有环路，若最后存在入度不为零的点，则说明有环。

695. Max Area of Island (Easy)

题目描述
给定一个二维的0-1 矩阵，其中0 表示海洋，1 表示陆地。单独的或相邻的陆地可以形成岛
屿，每个格子只与其上下左右四个格子相邻。求最大的岛屿面积。

输入输出样例
输入是一个二维数组，输出是一个整数，表示最大的岛屿面积。

Input:
[[1,0,1,1,0,1,0,1],
[1,0,1,1,0,1,1,1],
[0,0,0,0,0,0,0,1]]
Output: 6

思路
遍历所有元素，如果某元素不为0，从该位置深度优先遍历，记录与该位置相连的岛的数量。最后返回最大的岛的数量。一个tip:在遍历过某个岛时，只要将其设为0，就能记录其访问过，不需要另外的数组对其进行记录。

代码（非递归版）

public int maxAreaOfIsland(int[][] grid) {int m = grid.length;int n = grid[0].length;int max_area = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){ //是陆地,且没被访问过int area = 0;grid[i][j]=0; //表示该位置已经遍历过了Stack<int[]> stack = new Stack<>();stack.push(new int[]{i,j}); //把该位置进栈while (!stack.isEmpty()){int[] tem = stack.pop(); //出栈后进行访问int x = tem[0],y = tem[1];area++; //陆地数量+1if(x+1<m && grid[x+1][y]==1){grid[x+1][y]=0;stack.push(new int[]{x+1,y});}if(x-1>=0 && grid[x-1][y]==1){grid[x-1][y]=0;stack.push(new int[]{x-1,y});}if(y+1<n && grid[x][y+1]==1){grid[x][y+1]=0;stack.push(new int[]{x,y+1});}if(y-1>=0 && grid[x][y-1]==1){grid[x][y-1]=0;stack.push(new int[]{x,y-1});}}max_area = Math.max(max_area,area);}}}return max_area;}

代码（递归版）

class Solution {public int maxAreaOfIsland(int[][] grid) {int m = grid.length;int n = grid[0].length;int max_area = 0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if (grid[i][j]==1){max_area = Math.max(max_area,dfs(grid,new int[]{i,j}));}}}return max_area;}public int dfs(int[][] grid,int[] position){int area = 0;int m = grid.length,n = grid[0].length;int x = position[0],y = position[1];if(grid[x][y]==1){area++;grid[x][y]=0;}if(x+1<m && grid[x+1][y]==1){area+=dfs(grid,new int[]{x+1,y});}if(x-1>=0 && grid[x-1][y]==1){area+=dfs(grid,new int[]{x-1,y});}if(y+1<n && grid[x][y+1]==1){area+=dfs(grid,new int[]{x,y+1});}if(y-1>=0 && grid[x][y-1]==1){area+=dfs(grid,new int[]{x,y-1});}return area;}
}

547. Friend Circles (Medium)

题目描述
给定一个二维的0-1 矩阵，如果第(i, j) 位置是1，则表示第i 个人和第j 个人是朋友。已知
朋友关系是可以传递的，即如果a 是b 的朋友，b 是c 的朋友，那么a 和c 也是朋友，换言之这
三个人处于同一个朋友圈之内。求一共有多少个朋友圈。
输入输出样例
输入是一个二维数组，输出是一个整数，表示朋友圈数量。因为朋友关系具有对称性，该二
维数组为对称矩阵。同时，因为自己是自己的朋友，对角线上的值全部为1。

Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2

思路
是一个深度遍历的问题，寻找一共有多少个“环”。可以分别从不同且没被访问的人出发遍历，如果是朋友就会被遍历访问到，将其标记。最后统计一共开始出发遍历了多少次即可。
代码

class Solution {boolean[] visited;public int findCircleNum(int[][] isConnected) {int m = isConnected.length;int n = isConnected[0].length;visited = new boolean[m];for(int i=0;i<m;i++){visited[i]=false;}int count = 0;for(int i=0;i<m;i++){if(!visited[i]){count++;dfs(isConnected,i);}}return count;}public void dfs(int[][] isConnected,int i){if(!visited[i]){visited[i]=true;}for(int j=0;j<isConnected.length;j++){if(isConnected[i][j]==1 && !visited[j]){dfs(isConnected,j);}}   }
}

417. Pacific AtlanticWater Flow (Medium)

题目描述
给定一个二维的非负整数矩阵，每个位置的值表示海拔高度。假设左边和上边是太平洋，右边和下边是大西洋，求从哪些位置向下流水，可以流到太平洋和大西洋。水只能从海拔高的位置流到海拔低或相同的位置。
输入输出样例
输入是一个二维的非负整数数组，表示海拔高度。输出是一个二维的数组，其中第二个维度大小固定为2，表示满足条件的位置坐标。

输入: heights = [[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]]

示例 2：

输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

思路
如果从中间的元素正向搜索会比较麻烦，可以从数组最外层依次向里面深度优先遍历。分别用两个二维bool数组记录可以流入两个海洋的元素位置。之后，再遍历两个二维数组，利用这两个二维bool数组记录已经访问过的位置，最后如果某位置既能流入大西洋也能流入太平洋，输出该位置。

代码

class Solution {public List<List<Integer>> pacificAtlantic(int[][] heights) {//从边缘海洋四周反向深度优先遍历int m=heights.length;int n=heights[0].length;boolean[][] pacific = new boolean[m][n]; //记录可以流入太平洋的位置boolean[][] atlantic = new boolean[m][n]; //记录可以流入大西洋的位置for(int i=0;i<m;i++){for(int j=0;j<n;j++){pacific[i][j]=false;atlantic[i][j]=false;}}// 能流入太平洋的位置for(int i=0;i<n;i++){dfs(new int[]{0,i},heights,pacific);}for(int j=0;j<m;j++){dfs(new int[]{j,0},heights,pacific);}//能流入大西洋的位置for(int i=0;i<n;i++){dfs(new int[]{m-1,i},heights,atlantic);}for(int j=0;j<m;j++){dfs(new int[]{j,n-1},heights,atlantic);}List<List<Integer>>list = new ArrayList<>();//统计既能流入太平洋又能流入大西洋的位置for(int i=0;i<m;i++){for (int j = 0; j < n; j++) {if(pacific[i][j]&&atlantic[i][j]){List<Integer> result = new ArrayList<>();result.add(i);result.add(j);list.add(result);}}}return list;}public void dfs(int[]position,int[][] heights,boolean[][]visited){int m = visited.length;int n= visited[0].length;int x=position[0],y=position[1];if(visited[x][y])return;visited[x][y]=true;if(x+1<m && heights[x+1][y]>=heights[x][y]){dfs(new int[]{x+1,y},heights,visited);}if(x-1>=0 && heights[x-1][y]>=heights[x][y]){dfs(new int[]{x-1,y},heights,visited);}if(y+1<n && heights[x][y+1]>=heights[x][y]){dfs(new int[]{x,y+1},heights,visited);}if(y-1>=0 && heights[x][y-1]>=heights[x][y]){dfs(new int[]{x,y-1},heights,visited);}}
}

46. Permutations (Medium)

问题描述
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

输入输出样例
示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

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

示例 3：

输入：nums = [1]
输出：[[1]]

思路
假设有一个空的排列[]，每次将一个数放在start的位置，start递增+1，当start到末尾的位置时，这样一个排列就排好了。每次排一个位置时，将nums循环遍历一次，将没有访问过的元素放入该位置，并标记其访问过。一个排列完成后，需要将访问过的元素重新置为未访问。

代码

class Solution {public List<List<Integer>> permute(int[] nums) {List<Integer> list = new LinkedList<>();List<List<Integer>> result = new LinkedList<>();boolean[] visited = new boolean[nums.length];for (int i = 0; i < visited.length; i++) {visited[i]=false;}dfs(0,nums,visited,list,result);return result;}public void dfs(int start,int[]nums,boolean[]visited,List<Integer> list,List<List<Integer>> result){if(start == nums.length){result.add(new LinkedList<>(list));return;}for(int i=0;i<nums.length;i++){if(!visited[i]){ //将每一个未访问过的数都往start的位置放置list.add(nums[i]); //访问该位置visited[i]=true;dfs(start+1,nums,visited,list,result); //准备放置start+1位置list.remove(list.size()-1); //把上一个排好的回溯visited[i]=false;}}}
}

77. Combinations (Medium)

问题描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。
输入输出样例
示例 1：

输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

思路
这是一个组合问题，和排列问题有类似也有区别。
相当于一个深度优先搜索问题，先从start出发开始搜索，将当前位置的元素加入list表中，如果表长度为k则将该list结果放入result表中。之后从start+1开始遍历剩余数组，分别从剩余的数组进行深度优先搜索。（优化：遍历剩余数组时，剪枝优化，遍历范围为[start,n-(list.size()-k-1]左闭右闭区间）

class Solution {List<Integer> list;List<List<Integer>> result;public List<List<Integer>> combine(int n, int k) {result = new LinkedList<>();list = new LinkedList<>();dfs(1,n,k);return result;}public void dfs(int start,int n,int k){if(start>n-(k-list.size())+1) return; //剪枝优化if(list.size() == k){result.add(new LinkedList<>(list));return;}for(int i=start;i<=n;i++){list.add(i);dfs(i+1,n,k); //从剩余数组中搜索遍历list.remove(list.size()-1);}}
}

回溯算法模板：

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

79. Word Search (Medium)

问题描述
给定一个字母矩阵，所有的字母都与上下左右四个方向上的字母相连。给定一个字符串，求字符串能不能在字母矩阵中寻找到。

输入输出样例
示例 1：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true

示例 2：

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE”
输出：true

思路
遍历二维char数组，从board[i][j]==word.charAt(0)的位置开始深度优先搜索，每次搜索用一个指针指向字符串，如果字符串最后指向了string.length()的位置，则说明找到了全部的字符串，返回false。否则查找该字符字符相邻4个位置的字符，查找完一个位置，每次需要回溯。

代码

class Solution {char[][] board;int m,n;public boolean exist(char[][] board, String word) {m = board.length;n = board[0].length;this.board = board;boolean[][] visited = new boolean[m][n];boolean result;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j]==word.charAt(0)){result = dfs(i,j,0,word,visited);if(result) return true;}}}return false;}public boolean dfs(int i,int j,int current,String word,boolean[][] visited){ if(current == word.length()){//一直找到了最后一个return true;}if(i>=m || j>=n || i<0 || j<0)return false;boolean flag = false;if(!visited[i][j] && board[i][j]==word.charAt(current)){visited[i][j]=true;boolean right=false,left=false,down=false,up=false;right = dfs(i+1,j,current+1,word,visited);down = dfs(i,j+1,current+1,word,visited);left = dfs(i-1,j,current+1,word,visited);up = dfs(i,j-1,current+1,word,visited);visited[i][j]=false; //将搜索的位置回溯，注意字符串指针不用回溯flag = right || down || up || left;return flag;}return false;}
}

51. N-Queens (Hard)

问题描述
给定一个大小为n 的正方形国际象棋棋盘，求有多少种方式可以放置n 个皇后并使得她们互不攻击，即每一行、列、左斜、右斜最多只有一个皇后。

输入输出样例
示例1：

输入：n = 4
输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[[“Q”]]

思路
由于同行，同列，同对角线都不能同时有两个Queen，而且n*n的棋盘放n个，则肯定是每一行都有一个（或者每一列都有一个）。可以一行一行的去遍历，然后每一行再从左往右遍历搜索满足条件的位置。相当于深度优先搜索，如果某一行的位置无法满足条件，需要回溯到上一行的位置。

代码

class Solution {HashSet<Integer> column; //记录某列无法别访问HashSet<Integer> diag1; //记录对角线斜率，只要斜率在diag1，diag2就无法访问HashSet<Integer> diag2;public List<List<String>> solveNQueens(int n) {column = new HashSet<>();diag1 = new HashSet<>();diag2 = new HashSet<>();List<List<String>> result = new LinkedList<>();queensDFS(0,n,new LinkedList<>(),result);return result;}//list记录每行可行的列的索引集合public void queensDFS(int row,int n,List<Integer> list,List<List<String>> result){//用row遍历每一行if(row == n){ //遍历完List<String> strings = convert2board(list, n);result.add(strings);return;}for(int j=0;j<n;j++){ //遍历列if(!column.contains(j) && !diag1.contains(j+row) && !diag2.contains(j-row)){ //可以放置的位置column.add(j); //将这一列记录下来，标记diag1.add(j+row); //将这条副对角线记录下来diag2.add(j-row);//将这条主对角线记录下来list.add(j); //将当前行可以放的列位置记录queensDFS(row+1,n,list,result);//回溯list.remove(list.size()-1);column.remove(j);diag1.remove(j+row);diag2.remove(j-row);}}}//将记录可行的列的索引集合，转换为输出所需的List<String>类型public List<String> convert2board(List<Integer> list,int n){List<String> strings = new LinkedList<>();for(Integer i:list){char[] chars = new char[n];Arrays.fill(chars,'.');chars[i]='Q';strings.add(new String(chars));}return strings;}
}

广度优先搜索问题

934. Shortest Bridge (Medium)

问题描述
在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。
返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）

输入输出样例
示例 1：

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

示例 2：

输入：A = [[0,1,0],[0,0,0],[0,0,1]]
输出：2

示例 3：

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

思路
先从任意位置找到一个岛，然后使用深度优先搜索（也可以广度优先）找到一个完整岛链。然后可以在遍历的时候把访问过的位置置为2，这样我们找到的第一个岛链位置全部值都为2。之后使用广度优先搜索，相当于将现有岛链一层一层向外扩展，遇到值为0的位置，将其置为2（填岛），遇到值为1的位置，说明两个岛链相连了，此时返回扩展的层数即可。

代码

class Solution {int m;int n;public int shortestBridge(int[][] grid) {Deque<int[]> deque = new LinkedList<>();m = grid.length;n = grid[0].length;boolean flag = true;for(int i=0;i<m;i++){if(!flag)break;for (int j = 0; j < n; j++) {if(grid[i][j]==1){bridgeDFS(i,j,grid,deque);flag = false; //跳出外层循环break; //跳出当前循环}}}int level = 0; //记录遍历的层数int[][] arounds = {{0,1},{0,-1},{1,0},{-1,0}};while (!deque.isEmpty()){int len = deque.size();while(len-->0){ //将当前层遍历完int[] tem = deque.pollFirst();int x = tem[0],y = tem[1];//从四个方向再次搜索for(int[] around:arounds){int x1 = x+around[0];int y1 = y+around[1];if(x1<m && x1>=0 && y1<n && y1>=0){if(grid[x1][y1] == 0){grid[x1][y1]=2;deque.offerLast(new int[]{x1,y1});}if(grid[x1][y1] == 1){return level;}}}}level++; //扩展层+1}return -1;}public void bridgeDFS(int i,int j,int[][] grad,Deque<int[]> isLand){if(grad[i][j]==1){grad[i][j]=2; //标记访问isLand.offerLast(new int[]{i,j});if(i+1<grad.length){bridgeDFS(i+1,j,grad,isLand);}if(i-1>=0){bridgeDFS(i-1,j,grad,isLand);}if(j+1<grad[0].length){bridgeDFS(i,j+1,grad,isLand);}if(j-1>=0){bridgeDFS(i,j-1,grad,isLand);}}}
}

130. Surrounded Regions (Medium)

问题说明
给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

输入输出样例

输入：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置为X即可。

代码

class Solution {boolean[][] visited;public void solve(char[][] board) {int m = board.length;int n = board[0].length;visited = new boolean[m][n];for(int j=0;j<n;j++){boardDFS(0,j,board);//最上面boardDFS(m-1,j,board);//最下面}for(int i=0;i<m;i++){boardDFS(i,0,board);//最左侧boardDFS(i,n-1,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]=='A'){ //将周围暂做标记的A改回Oboard[i][j]='O';}}}}public void boardDFS(int i,int j,char[][]board){if(!visited[i][j] && board[i][j]=='O'){visited[i][j]=true;board[i][j]='A'; //用A暂做标记，表示周围相连的Oint[][]around = {{0,1},{0,-1},{-1,0},{1,0}};for (int[] tem : around) {int x = i+tem[0];int y = j+tem[1];if(x>=0 && x<board.length && y>=0 && y<board[0].length){boardDFS(x,y,board);}}}}
}

257. Binary Tree Paths (Easy)

问题描述
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。

输入输出样例
示例1：

输入：root = [1,2,3,null,5]
输出：[“1->2->5”,“1->3”]

示例 2：

输入：root = [1]
输出：[“1”]

思路
从根节点开始深度优先搜索，用一个list表记录遍历到的节点信息，如果当前是叶子节点的时候，将叶子节点加入list中，然后将list整体结果保存在result的list集合中。每次遍历完一个节点时，还要回溯，否则输出list结果就是先序遍历的结果了。

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<Integer> list = new LinkedList<>();List<String> result = new LinkedList<>();DFS(root,list,result);return result;}public void DFS(TreeNode root,List<Integer> list,List<String> result){if(root == null)return;if(root.left==null && root.right==null ) { //是叶子节点list.add(root.val); //叶子节点要加进去String strings = convert(list);result.add(strings);list.remove(list.size()-1); //回溯return;}list.add(root.val);DFS(root.left,list,result);DFS(root.right,list,result);list.remove(list.size()-1);  //回溯}//转化格式public String convert(List<Integer> list){ StringBuilder stringBuilder = new StringBuilder();for (int i = 0; i < list.size() - 1; i++) {stringBuilder.append(list.get(i) + "->");}stringBuilder.append(list.get(list.size() - 1));return new String(stringBuilder);}}

47. Permutations II (Medium)

问题描述
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路
和没有重复数字的全排列类似，只是在排某个位置时，如果访问的当前元素和上一个元素相等（有序），即上一个相同的元素已将访问过了，于是就可以跳过当前元素。

代码

class Solution { public List<List<Integer>> permuteUnique(int[] nums) {List<Integer> list = new LinkedList<>();List<List<Integer>> result = new LinkedList<>();boolean[] visited = new boolean[nums.length];Arrays.sort(nums);dfs(0,nums,visited,list,result);return result;}public void dfs(int start,int[]nums,boolean[]visited,List<Integer> list,List<List<Integer>> result){if(start == nums.length){result.add(new LinkedList<>(list));return;}for(int i=0;i<nums.length;i++){if(visited[i])continue;if(i>0 && nums[i]==nums[i-1] && visited[i-1]) continue;    list.add(nums[i]); //访问该位置visited[i]=true;dfs(start+1,nums,visited,list,result); //准备放置start+1位置list.remove(list.size()-1); //把上一个排好的回溯visited[i]=false;}}
}

使用一个set来过滤结果：

class Solution {public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> result = new LinkedList<>();List<Integer> list = new LinkedList<>();Set<Integer> set = new HashSet<>();boolean[] visited = new boolean[nums.length];backTrace_permuteUnique2(0,nums,visited,list,result);return result;}void backTrace_permuteUnique2(int start,int[] nums,boolean[] visited,List<Integer> list,List<List<Integer>> result){if(start == nums.length){result.add(new LinkedList<>(list));return;}Set<Integer> set = new HashSet<>();for(int i=0;i<nums.length;i++){if(!visited[i]){if(set.contains(nums[i]))continue;list.add(nums[i]);set.add(nums[i]);visited[i]=true;backTrace_permuteUnique2(start+1,nums,visited,list,result);list.remove(list.size()-1);visited[i]=false;}}}
}

40. Combination Sum II (Medium)

问题描述
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

输入输出样例
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

思路
和前面的组合问题类似，需要排除一些相同的情况。一种思路是最后再列表中清除相同的，另外一种思路是在组合的过程中跳过相同的情况。这里说第二种思路：排某一个空位时，从start的位置依次向后遍历放入，如果遇到前一个位置排过相同的元素，即 candidates[i-1]==candidates[i]的情况，就将当前元素跳过。

代码

class Solution {List<Integer> list;List<List<Integer>> result;public List<List<Integer>> combinationSum2(int[] candidates, int target){result = new LinkedList<>();list = new LinkedList<>();Arrays.sort(candidates);dfs(0,candidates,target);return result;}public void dfs(int start,int[] candidates,int k){if(sum(list) == k){result.add(new LinkedList<>(list));return;}if(sum(list)<k){for(int i=start;i<candidates.length;i++){//没有i>start条件，则1,1,6这种情况会被跳过//每次保证当前递归元素被访问，如果从下一个元素开始与前一个元素相同就跳过该元素if(i>start && candidates[i-1]==candidates[i])continue;list.add(candidates[i]);dfs(i+1,candidates,k); //将当前元素的下一个元素进行递归搜索list.remove(list.size()-1);}}}public int sum(List<Integer> list){int s=0;for(int a:list){s+=a;}return s;}
}

310. Minimum Height Trees (Medium)

问题描述
树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。
给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

输入输出样例

输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]

解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。

思路
方法一：直接使用广度优先遍历（或深度优先遍历）记录树的高度，最后统计最小的数的高度（思路没问题，但是复杂度太高会超时）

方法二：拓扑排序，观察可以得知最小高度树的根节点都在中间。输入是一个无环图，只需从最外层叶子节点开始遍历，每次删除一层叶子节点，最后剩下的一个或者两个叶子节点就是最小高度树的根节点。

代码

class Solution {public List<Integer> findMinHeightTrees(int n, int[][] edges) {List<List<Integer>> graph = new ArrayList<>();List<Integer> leaves = new ArrayList<>();if(n==1){leaves.add(0);return leaves;}for (int i = 0; i < n; i++) {graph.add(new ArrayList<>());}//构建邻接表for(int[] tem:edges){int x = tem[0],y = tem[1];graph.get(x).add(y);graph.get(y).add(x);}//用一个列表存储叶子节点for(int i=0;i<graph.size();i++){if(graph.get(i).size() == 1){leaves.add(i);}}while (n>2){n -= leaves.size();List<Integer> tem = new ArrayList<>();;for(int leaf:leaves){int delet = graph.get(leaf).remove(0); //从邻接表叶子节点所在列表弹出与它相邻结点graph.get(delet).remove(new Integer(leaf)); //从相邻结点列表中删除叶子节点if(graph.get(delet).size() == 1)tem.add(delet); //相邻结点删除后如果也成为了一个叶子节点，就用一个新的叶子节点列表添加进去}leaves = tem;}return leaves;}
}