private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
//留意这里没有写终止条件,不是说递归一定要有终止条件的吗,这里怎样没写,其实这里的终止条件
//隐含在for循环中了,当然我们也可以写if(start>nums.length) rerurn;只不过这里省略了。
list.add(new ArrayList<>(tempList));
for (int i = start; i < nums.length; i++) {
//做出选择
tempList.add(nums[i]);
//递归
backtrack(list, tempList, nums, i + 1);
//撤销选择
tempList.remove(tempList.size() - 1);
}
}
所以相似这种题基本上也就是这个套路,就是先做出选择,然后递归,最后再撤销选择。在讲第一道示例的时分提到过撤销的缘由是避免把前一个分支的结果带到下一个分支形成结果错误。不过他们不同的是,一个是终止条件的判别,还一个就是for循环的起始值,这些都要详细成绩详细剖析。下面再来看最后一到题解数独。
解数独
数独大家都玩过吧,他的规则是这样的
一个数独的解法需遵照如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
进程就不在剖析了,直接看代码,代码中也有详细的注释,这篇讲的是回溯算法,这里主要看一下backTrace办法即可,其他的可以先不用看
//回溯算法
public static boolean solveSudoku(char[][] board) {
return backTrace(board, 0, 0);
}//留意这里的参数,row表示第几行,col表示第几列。private static boolean backTrace(char[][] board, int row, int col) {
//留意row是从0末尾的,当row等于board.length的时分表示数独的
//最后一行全部读遍历完了,阐明数独中的值是有效的,直接前往true
if (row == board.length)
return true;
//假设以后行的最后一列也遍历完了,就从下一行的第一列末尾。这里的遍历 //顺序是从第1行的第1列不断到最后一列,然后第二行的第一列不断到最后
//一列,然后第三行的…… if (col == board.length)
return backTrace(board, row + 1, 0);
//假设以后位置曾经有数字了,就不能再填了,直接到这一行的下一列 if (board[row][col] != '.')
return backTrace(board, row, col + 1);
//假设下面条件都不满足,我们就从1到9中选择一个适宜的数字填入到数独中
(责任编辑:admin)