LeetCode题解_搜索
Contents
搜索
BFS
leetcode_1091_middle
-
问题描述
n*n矩阵求解从左上角到右下角的最短路径长度，0为可走路径，行进方向为相邻的8个方向[[0,1], [1,0]] 输入：grid = [[0,1],[1,0]] 输出：2 -
解法：BFS广度优先搜索
BFS常用于求解无权图最短路径问题，实现时注意两点：
- 1、队列存储每一轮的节点；
- 2、标记遍历过的节点防止重复。
-
原理
使用队列存储节点，形式为[行,列,当前路径长度]
将初始节点压入队列，当队列未空时，逐层往外进行搜索遍历，并标记已经遍历过的节点，这是因为如果其他路径经过该点时，表示此前已经有长度小于等于的路径经过了，因此不需要重复遍历。
-
代码
//8个方向 int[][] directions=new int[][] {{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}}; public int BFS(int[][] grid) { Queue<int[]> queue = new LinkedList<int[]>(); if (grid[0][0] == 0) { //标记 grid[0][0] = 1; int[] mark = new int[] { 0, 0, 1 }; queue.add(mark); } else return -1; while (!queue.isEmpty()) { int[] mark = queue.poll(); int row = mark[0], col = mark[1], length = mark[2]; if (row == grid.length - 1 && col == grid.length - 1) { return mark[2]; } else { for(int[] d:directions) { int next_r=row+d[0],next_c=col+d[1]; if(next_r>=grid.length||next_r<0||next_c>=grid.length||next_c<0) { continue; } else { if (grid[next_r][next_c] == 0) { grid[next_r][next_c] = 1; int[] tmp = new int[] { next_r, next_c, length + 1 }; queue.add(tmp); } } } } } return -1; } public int shortestPathBinaryMatrix(int[][] grid) { return BFS(grid); }
leetcode_279_middle
-
问题描述
给你一个整数n，返回 和为n的完全平方数的最少数量 。输入：n = 13 输出：2 解释：13 = 4 + 9 -
解法：BFS广度优先搜索
-
原理
使用队列存储节点，形式为[n,当前路径长度]
问题等价于从节点n开始直到节点0，经过的最短路径长度，若
n-x满足完全平方数s*s的话，则n到x存在一条边。 -
代码
public int BFS(int n) { int x = (int) Math.sqrt(1.0 * n); // 平方数 List<Integer> squares = new ArrayList<Integer>(); while (x != 0) { squares.add(x); x--; } // 初始节点n Queue<int[]> queue = new LinkedList<int[]>(); queue.add(new int[] { n, 0 }); // 遍历标记 boolean[] marks = new boolean[n + 1]; marks[n] = true; while (!queue.isEmpty()) { int[] arr = queue.poll(); int curn = arr[0], curnum = arr[1]; if (curn == 0) { return curnum; } for (Integer square : squares) { if (square * square <= curn) { if (marks[curn - square * square]) { continue; } queue.add(new int[] { curn - square * square, curnum + 1 }); marks[curn - square * square] = true; } } } return n; } public int numSquares(int n) { return BFS(n); }
leetcode_127_hard
-
问题描述
给定单词beginWord和endWord和一个字典 wordList ，返回 从beginWord到endWord的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 输出：5 解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。 -
解法：BFS广度优先搜索
-
原理
问题等价于从节点beginWord开始直到节点endWord，经过的最短路径长度，若当前节点单词与wordList中某一单词存在一个字母的差别则表示存在一条边。
超时优化：
- 1、
compareWord判断函数应当在count>1时直接返回 - 2、
wordList的for循环应当使用index形式而不是for each，避免过多使用mark[wordList.indexOf(s)每次查询标记的下标 - 3、官方题解存在将
wordList放到哈希表里和双向BFS等优化，未实现。
- 1、
-
代码
public class word{ String s; int length; public word(String s,int l) { this.s=s; this.length=l; } } public boolean compareWord(String a,String b) { int count=0; for(int i=0;i<a.length()&&count<=1;i++) { if(a.charAt(i)!=b.charAt(i)) { count++; } } return count<=1; } public int ladderLength(String beginWord, String endWord, List<String> wordList) { if(!wordList.contains(endWord)) { return 0; } word w=new word(beginWord,1); Queue<word> queue=new LinkedList<word>(); queue.add(w); boolean[] marks=new boolean[wordList.size()]; while(!queue.isEmpty()) { word curw=queue.poll(); if(endWord.equals(curw.s)) { return curw.length; } for(int i=0;i<wordList.size();i++) { if(marks[i]) { continue; } if(compareWord(curw.s, wordList.get(i))) { queue.add(new word(wordList.get(i), curw.length+1)); marks[i]=true; } } } return 0; }
DFS
leetcode_695_middle
-
问题描述
岛屿的面积是岛上值为 1 的单元格的数目。上下左右的相邻面积可以相连。 计算并返回m*n矩阵grid中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。[[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 -
解法：DFS深度优先搜索
DFS常用于求解不需要特定路径的图问题即可达性问题，实现时注意两点：
- 栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。
- 标记：和 BFS 一样同样需要对已经遍历过的节点进行标记。
-
原理
本题也可以用BFS进行求解，只需要记录所有的出队数目总和即可。使用DFS的递归方法可以大量节省时间。
使用递归时，通过函数的调用来表示接下来想要遍历哪些土地，让下一层函数来访问这些土地，并设定一个条件停止递归地调用，本题为下一层函数的土地值
grid[i][j]为0时return 0; -
代码
//4个方向 public static final int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; public int DFS(int[][] grid, int r, int c) { if (grid[r][c] == 0) { return 0; } int area = 1; grid[r][c] = 0; for (int[] dir : directions) { int nextr = r + dir[0], nextc = c + dir[1]; if (nextr < 0 || nextr >= grid.length || nextc < 0 || nextc >= grid[0].length) { continue; } area += DFS(grid, nextr, nextc); } return area; } public int maxAreaOfIsland(int[][] grid) { 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; }
leetcode_200_middle
-
问题描述
岛屿的面积是岛上值为 1 的单元格的数目。上下左右的相邻面积可以相连。 计算并返回m*n矩阵grid中的岛屿数量。如果没有岛屿，则返回为 0 。[ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3 -
解法：DFS深度优先搜索
-
原理
本题也可以用BFS进行求解。使用DFS的递归方法可以大量节省时间。
递归与上一道类似，需要注意函数传参grid矩阵的知识。
这里的代码采用了BFS的队列方法，为了避免超时，需要在找到下一个值为1的面积时直接置0，防止其他重复访问。
-
代码
//4个方向 public static final int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; public int numIslands(char[][] grid) { int r=grid.length,c=grid[0].length,num=0; Queue<int[]> queue=new LinkedList<int[]>(); for(int i=0;i<r;i++){ for(int j=0;j<c;j++) { if(grid[i][j]=='1') { num++; queue.add(new int[] {i,j}); grid[i][j]='0';//找到直接标记，节省消耗防止超时 while(!queue.isEmpty()) { int[] cur=queue.poll(); int curi=cur[0],curj=cur[1]; for (int[] dir : directions) { int nexti = curi + dir[0], nextj = curj + dir[1]; if (nexti < 0 || nexti >= r || nextj < 0 || nextj >= c) { continue; } if(grid[nexti][nextj]=='1') { queue.add(new int[] {nexti,nextj}); grid[nexti][nextj]='0';//找到直接标记，节省消耗防止超时 } } } } } } return num; }
leetcode_547_middle
-
问题描述
有n个城市间接或直接相连称为一个省份。给你一个n x n的矩阵isConnected，其中isConnected[i][j] = 1表示第i个城市和第j个城市直接相连。 返回矩阵中 省份 的数量。[[1,1,0],[1,1,0],[0,0,1]] 输出：2 -
解法：DFS深度优先搜索
-
原理
城市关系可以看成一个无向图，若ab相连则对称位置也应为1，因此遍历时需要标记两次边。
-
代码
void DFS(int[][] isConnected,int row) { //该if可以省略 if(isConnected[row][row]==0) { return; } isConnected[row][row]=0;//标记节点 for(int i=0;i<isConnected.length;i++) { if(isConnected[row][i]==1) { isConnected[row][i]=0;//标记边 isConnected[i][row]=0;//标记对称边 DFS(isConnected,i); } } return; } public int findCircleNum(int[][] isConnected) { int num=0,n=isConnected.length; for(int i=0;i<n;i++) { if(isConnected[i][i]==1) { num++; DFS(isConnected,i); } } return num; }
leetcode_130_middle
-
问题描述
m x n的矩阵board，找到所有被'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"]] -
解法：DFS深度优先搜索
-
原理
只有上下左右都被
X包围的O才需要填充，因此只需对与最外圈的O连通的路径标记即可。没被标记的O就是需要填充的。注意别忘了重复标记marks；
-
代码
//4个方向 int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; public void DFS(char[][] board, int m, int n, boolean[][] marks) { int row = board.length, col = board[0].length; for (int[] dir : directions) { int next_m = dir[0] + m, next_n = dir[1] + n; if (next_m < 0 || next_m >= row || next_n < 0 || next_n >= col) { continue; } if (board[next_m][next_n] == 'O'&&marks[next_m][next_n]==false) { marks[next_m][next_n] = true; DFS(board, next_m, next_n, marks); } } } public void solve(char[][] board) { int row = board.length, col = board[0].length; boolean[][] marks = new boolean[row][col]; for (int i = 0; i < row; i++) { if (i == 0 || i == row - 1) { for (int j = 0; j < col; j++) { if (board[i][j] == 'O'&&marks[i][j]==false) { marks[i][j] = true; DFS(board, i, j, marks); } } } else { if (board[i][0] == 'O'&&marks[i][0]==false) { marks[i][0] = true; DFS(board, i, 0, marks); } if (board[i][col - 1] == 'O'&&marks[i][col - 1]==false) { marks[i][col - 1] = true; DFS(board, i, col - 1, marks); } } } // 填充 for (int i = 1; i < row - 1; i++) { for (int j = 1; j < col - 1; j++) { if (board[i][j] == 'O' && marks[i][j] == false) { board[i][j] = 'X'; } } } }
BackTrack
leetcode_17_middle
-
问题描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合,按九键字母对应。答案可以按 任意顺序 返回。输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] -
解法：BackTrack回溯
DFS常用解决可达性问题，而BackTrack主要用于求解排列组合问题 BackTrack并不是立即返回，而要回溯上一层继续求解，因此在程序实现时，需要注意对元素的标记问题：
- 1、在一次递归调用时需要标记访问元素，与DFS类似；
- 2、递归返回上一层（回溯）时，需要将元素标记为未访问，使得下一次递归调用能够重复访问。
-
原理
该题为排列组合问题，因此需要将遍历的所有可能性加入解集中。
由于涉及到修改字符串，使用
StringBuffer，不仅作为解，也起到标记的作用；每次
back_track后需要调用s.deleteCharAt(len)进行回溯取消标记。实际实现过程中发现这种回溯类似于二叉树的前序遍历，因此也可以用队列求解，每个数字的所有字母对应一层节点，逐层遍历将每层字母加上下一层的字母作为新的队列（下一层），这样遍历到最后一层的队列就是所得解集。
-
代码
char[][] num_letter_map=new char[][] {{},{},{'a','b','c'},{'d','e','f'}, {'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'}, {'w','x','y','z'}}; private void back_track(StringBuffer s,String digits,int len,List<String> combines) { if(len==digits.length()) { combines.add(s.toString()); return; } int num=digits.charAt(len)-'0'; for(int i=0;i<num_letter_map[num].length;i++) { s.append(String.valueOf(num_letter_map[num][i])); back_track(s, digits, len+1, combines); s.deleteCharAt(len); } } public List<String> letterCombinations(String digits) { List<String> combines=new ArrayList<String>(); if(digits.equals("")||digits==null) { return combines; } back_track(new StringBuffer(),digits,0,combines); return combines; }
leetcode_93_middle
-
问题描述
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。给定一个只包含数字的字符串 s ，通过在 s 中插入 ‘.’ 返回所有可能的有效 IP 地址，。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"] -
解法：BackTrack回溯
-
原理
在调用back_track的时候需要确认好判断条件，即段数为
4或者小数点为3。同时需要注意0开头的特殊字段只有单独一段才作数。每次遍历的情况只需要考虑三位以内即可
自己实现的代码有些粗糙，参考其他做法进行更改，包括将拼接放入循环中，主函数就不需要再一层循环。
-
代码
public void back_track(StringBuffer sb, String s, int lastp, int p, int dotnum, List<String> ips) { String subString = s.substring(lastp, p); // 大于三位 if (subString.length() > 3 || (subString.charAt(0) == '0' && subString.length() > 1)) { return; } // 大于255 int num = Integer.valueOf(subString); if (num > 255 || num < 0) { return; } int end = sb.length();//回溯位置 sb.append(subString); sb.append('.'); //满足条件 if (dotnum == 3) { sb.deleteCharAt(sb.length() - 1);//删除末尾小数点 ips.add(sb.toString()); return; } if (dotnum == 2) { back_track(sb, s, p, s.length(), dotnum + 1, ips); } else { for (int i = 1; i < s.length() - p && i < 4; i++) { back_track(sb, s, p, p + i, dotnum + 1, ips); } } sb.delete(end, sb.length()); } public List<String> restoreIpAddresses(String s) { List<String> ips = new ArrayList<String>(); if (s.length() < 4) { return ips; } for (int i = 1; i < 4; i++) { back_track(new StringBuffer(), s, 0, i, 0, ips); } return ips; }
leetcode_79_middle
-
问题描述
给定一个m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。输入：board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], word = "ABCCED" 输出：true -
解法：BackTrack回溯
-
原理
自己的方法在主函数等于也进行了一次回溯，可能需要修改函数使得判断条件和回溯标记都在回溯函数里面。考虑在back_track内再判断标记和单词匹配
注意回溯函数和主函数只要有一次找到单词路径就直接返回true
-
代码
int[][] directions=new int[][] {{0,1},{0,-1},{1,0},{-1,0}}; public boolean back_track(char[][] board,String word,int index,int i,int j,boolean[][] marks) { int m=board.length,n=board[0].length; boolean res=false; if(index==word.length()-1) { return true; } for(int[] dir:directions) { int next_i=dir[0]+i,next_j=dir[1]+j; if(next_i>=m||next_i<0||next_j>=n||next_j<0) { continue; } index++; if(board[next_i][next_j]==word.charAt(index)&&marks[next_i][next_j]==false) { marks[next_i][next_j]=true; res=back_track(board,word,index,next_i,next_j,marks); marks[next_i][next_j]=false; } index--; //注意一次回溯成功则直接返回true if(res==true) { return res; } } return res; } public boolean exist(char[][] board, String word) { boolean flag=false; int m=board.length,n=board[0].length; boolean[][] marks=new boolean[m][n];//回溯标记 for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(board[i][j]==word.charAt(0)&&marks[i][j]==false) { marks[i][j]=true; flag=back_track(board,word,0,i,j,marks); marks[i][j]=false; } //注意一次回溯成功则直接返回true if(flag==true) { return flag; } } } return flag; }
leetcode_257_easy
-
问题描述
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"] -
解法：BackTrack回溯
-
原理
基础的回溯问题/遍历树路径问题
本题树已经构建好，需要复习一下树的相关知识。
-
代码
private void back_track(TreeNode node, StringBuffer sb,List<String> paths) { if(sb.length()>0) { sb.append("->"); } sb.append(node.val); //找到叶子 if(node.left==null&&node.right==null) { paths.add(sb.toString()); } int end=sb.length(); if(node.left!=null) { back_track(node.left, sb, paths); } sb.delete(end, sb.length()); if(node.right!=null) { back_track(node.right, sb, paths); } } public List<String> binaryTreePaths(TreeNode root) { List<String> paths = new ArrayList<String>(); if(root==null) { return paths; } back_track(root, new StringBuffer(),paths); return paths; }
leetcode_46_middle
-
问题描述
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] -
解法：BackTrack回溯
-
原理
添加列表时需要new一个arraylist，这是因为java的值传递导致的，否则结果会都为空指向同一个地址（回溯完成后的空列表）
-
代码
private void back_track(int[] nums,boolean[] marks,List<Integer> list,List<List<Integer>> res) { if(list.size()==nums.length) { res.add(new ArrayList<Integer>(list)); return; } for(int i=0;i<nums.length;i++) { if(marks[i]==true) { continue; } list.add(nums[i]); marks[i]=true; back_track(nums,marks,list,res); marks[i]=false; list.remove(list.size()-1); } } public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res=new ArrayList<List<Integer>>(); if(nums.length==0) { return res; } List<Integer> list=new ArrayList<Integer>(); boolean[] marks=new boolean[nums.length]; back_track(nums,marks,list,res); return res; }
leetcode_77_middle
-
问题描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] -
解法：BackTrack回溯
-
原理
与排列回溯问题类似，不同的是组合将位置不同、数字相同的列表视作一个元素，因此需要修改回溯的标记
取消marks[]数组标记，改用每次的搜索起点作为标记。
遍历可以通过当前已经存好的list长度与所需k长度做差得到一个搜索起点的上界，以此达到剪枝效果。
-
代码
private void back_track(int n,int k,int curindex,List<Integer> combine,List<List<Integer>> res) { if(combine.size()==k) { res.add(new ArrayList<Integer>(combine)); return; } //n-(k-combine.size())+1为剪枝，即搜索起点的上界不能小于n-当前剩余list数目+1,往后的搜索起点长度必然不足。 for(int i=curindex;i<=n-(k-combine.size())+1;i++) { combine.add(i); back_track(n, k,i+1, combine, res); combine.remove(combine.size()-1); } } public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res=new ArrayList<List<Integer>>(); if(k<=0||n<k) { return res; } List<Integer> combine=new ArrayList<Integer>(); back_track(n, k, 1, combine, res); return res; }
leetcode_90_middle
-
问题描述
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]] -
解法：BackTrack回溯
-
原理
为了防止子集重复，考虑用hashset也并不是很方便，因此直接先对数组排序。
简单的回溯是直接对每次的curset判断是否已经存在subsets中，否则插入，但是时间慢。
更好的方法是进行树层重复判断，通过marks标记判断两个相同的取值是否是同一树层取的，marks[i]=false表示同一层，因此剪枝，否则表示同一树枝，允许迭代。
-
代码
private void back_track(int[] nums,List<Integer> curset,List<List<Integer>> subsets,boolean[] marks,int len) { subsets.add(new ArrayList<Integer>(curset)); if(len>=nums.length) { return; } for(int i=len;i<nums.length;i++) { //剪枝，不允许树层重复 if(i>0&&nums[i]==nums[i-1]&&marks[i-1]==false) { continue; } marks[i]=true; curset.add(nums[i]); back_track(nums, curset, subsets,marks, i+1); curset.remove(curset.size()-1); marks[i]=false; } } public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums);//排序用于后面防止重复 List<List<Integer>> subsets=new ArrayList<List<Integer>>(); List<Integer> curset=new ArrayList<Integer>(); if(nums.length<0) { return new ArrayList<List<Integer>>(); } boolean[] marks=new boolean[nums.length]; back_track(nums,curset,subsets,marks,0); return subsets; }
leetcode_51_hard
-
问题描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
输入：n = 4 输出： [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。 -
解法：BackTrack回溯
-
原理
这边我自己用的标记方式是行（后来发现行标记不需要，N皇后每行必定只有一个）列斜线一起考虑，对标记数组每次加一，回溯每次减一，大于0就是true，官方使用了三个标记，分别是列、左斜、右斜。
求解时每行只记录Q的位置，在找出单个解后(curn==n)再统一进行String赋值加入列表，可以节省求解时间。
难点在于标记方法和回溯标记的方式。
-
代码
private void back_track(int n,int curn,int[][] marks,int[] ans,List<List<String>> result) { if(curn==n) { List<String> solve=new ArrayList<String>(); for(int i=0;i<n;i++) { char[] c=new char[n]; Arrays.fill(c, '.'); c[ans[i]]='Q'; String s=new String(c); solve.add(s); } result.add(solve); return; } //对当前行的每个元素 for(int i=0;i<n;i++) { if(marks[curn][i]>0) { continue; } //设置每行的Q位置 ans[curn]=i; //标记列，行不需要标记 for(int j=0;j<n;j++) { marks[j][i]++; } //标记斜线 for(int k=curn+1;k<n;k++) { if(i-Math.abs(curn-k)>=0){ marks[k][i-Math.abs(curn-k)]++; } if(i+Math.abs(curn-k)<n) { marks[k][i+Math.abs(curn-k)]++; } } back_track(n, curn+1, marks, ans, result); ans[curn]=0; //取消行列标记 for(int j=0;j<n;j++) { marks[j][i]--; } //标记斜线 for(int k=curn+1;k<n;k++) { if(i-Math.abs(curn-k)>=0){ marks[k][i-Math.abs(curn-k)]--; } if(i+Math.abs(curn-k)<n) { marks[k][i+Math.abs(curn-k)]--; } } } } public List<List<String>> solveNQueens(int n) { List<List<String>> result=new ArrayList<List<String>>(); int[][] marks=new int[n][n]; int[] ans=new int[n]; if(n<=0) { return result; } back_track(n,0,marks,ans,result); return result; }