回溯算法01------全排列 + N皇后问题
2021/5/18 12:25:14
本文主要是介绍回溯算法01------全排列 + N皇后问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
参考 https://labuladong.gitee.io/algo/1/4/
对于模板的理解
找出可选择的列表, 遍历选择,然后递归,最后回溯也就是撤销选择
结束条件 for(选择:选择列表){ 加入选择 递归 撤销选择 }
46. 全排列
class Solution { private List<List<Integer>> res = new LinkedList<>(); public List<List<Integer>> permute(int[] nums) { LinkedList<Integer> track = new LinkedList<>(); backtrack(nums, track); return res; } public void backtrack(int[] nums, LinkedList<Integer> track){ // 结束条件 if(track.size() == nums.length){ res.add(new LinkedList<Integer>(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(); } } }
51. N 皇后
class Solution { private List<List<String>> res = new ArrayList<>(); public List<List<String>> solveNQueens(int n) { List<String> track = new ArrayList<>(); StringBuilder sb = new StringBuilder(); // 全部填充 for(int i = 0; i < n; i++){ sb.append("."); } for(int i = 0; i < n; i++){ track.add(sb.toString()); } backtrack(track, 0, n); return res; } public void backtrack(List<String> track, int row, int n){ // 结束条件 if(row == n){ res.add(new ArrayList<String>(track)); return; } // 选择列表, row这一行中所有列的位置 for(int i = 0; i < n; i++){ // 判断这些列是否能放置皇后 boolean flag = isValid(track, row, i, n); if(!flag){ continue; } // 将.替换为Q change(track, row, i, "Q"); backtrack(track, row + 1, n); change(track, row, i, "."); } } public void change(List<String>track, int row, int col, String str){ StringBuilder sb = new StringBuilder(track.get(row)); track.remove(row); sb.replace(col, col + 1, str); track.add(row, sb.toString()); } public boolean isValid(List<String>track, int row, int col, int n){ // 同一列 for(int i = 0; i < n; i++){ if(i == row){ continue; } if(track.get(i).charAt(col) == 'Q'){ return false; } } // 左上方的对角线 for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){ if(track.get(i).charAt(j) == 'Q'){ return false; } } // 右上方的对角线 for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){ if(track.get(i).charAt(j) == 'Q'){ return false; } } return true; } }
这篇关于回溯算法01------全排列 + N皇后问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南