怎么做网站信息,wordpress黑暗,虚拟主机子网站,松岗网站开发代码随想录 (programmercarl.com) 总结
332.重新安排行程
欧拉通路和欧拉回路#xff1a;
欧拉通路#xff1a;对于图G来说#xff0c;如果存在一条通路包含G的所有边#xff0c;则该通路称为欧拉通路#xff0c;也称欧拉路径。欧拉回路#xff1a;如果欧拉路径是一条… 代码随想录 (programmercarl.com) 总结
332.重新安排行程
欧拉通路和欧拉回路
欧拉通路对于图G来说如果存在一条通路包含G的所有边则该通路称为欧拉通路也称欧拉路径。欧拉回路如果欧拉路径是一条回路那么称其为欧拉回路。欧拉图含有欧拉回路的图是欧拉图。
题目中说必然存在一条有效路径所以至少是半欧拉图也可以是欧拉图。
深度优先搜索DFS
对每一个可能的分支路径深入到不能再深入为止而且每个节点只能访问一次。
遍历欧拉图——Hierholzier算法
主要步骤从一个可能的起点出发进行深度优先搜索但是每次沿着辅助边从每个顶点移动到另外一个顶点的时候都需要删除这个辅助边。如果没有可移动的路径则将所在节点加入到栈中先进后出所以后面步骤4需要逆序输入并返回。
算法思路
1任选一点为起始点并记录
2从起点出发到达任意一个邻接点新到达的点成为新的起点删除经过的边删除孤立点记录经过的点
3重复步骤2直至回到初始点此时到达步骤1将本次记录的点和上次记录的点集合拼接。若本图成为空图到达步骤4
4逆序输出所有记录点。
只有入度与出度差为 1 的节点会导致死胡同 代码待更新
51.N皇后
皇后们的约束条件
不能同行不能同列不能同斜线
棋盘的宽度就是for循环的长度递归的深度就是棋盘的高度这样就可以套进回溯法的模板里了。
回溯算法主体里面需要放一个判断是否可以防止皇后Q的判断函数
其中对于不能同斜线需要判断45°和135°分别如下两种情况
i - 2, j - 2i - 1, j - 1i, j
i - 2, j 2i - 1, j 1i, j
Java中ArrayList与LinkedList的区别 - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/33141246补充一点ArrayList和LinkedList的区别
1、ArrayList的实现是基于数组LinkedList的实现是基于双向链表。
2、对于随机访问ArrayList优于LinkedList
3、对于插入和删除操作LinkedList优于ArrayList
4、LinkedList比ArrayList更占内存因为LinkedList的节点除了存储数据还存储了两个引用一个指向前一个元素一个指向后一个元素。
class Solution {ListListString res new ArrayList();//需要在一开始就声明因为后面res.add(Array2List(chessboard));会用到public ListListString solveNQueens(int n) {//初始化所有棋盘格为.char[][] chessboard new char[n][n];//注意此处的棋盘里面放的都是字符所以需要定义为char类型的数组for (char[] c : chessboard) {Arrays.fill(c, .);}backtracking(n, 0, chessboard);return res;}public void backtracking(int n, int row, char[][] chessboard){//n表示该棋盘格的规格大小row表示当前遍历到的行数if (row n){//表示递归终止条件开始收集结果res.add(Array2List(chessboard));return;}for (int col 0; col n; col) {if (isValid(n, row, col, chessboard)){chessboard[row][col] Q;backtracking(n, row 1, chessboard);chessboard[row][col] .;//回溯回去}}}public List Array2List(char[][] chessboard){//表示将数组类型的结果转为所需要的list的集合形式ListString list new ArrayList();for (char[] c : chessboard) {list.add(String.copyValueOf(c));}return list;}public boolean isValid(int n, int row, int col, char[][] chessboard){//以下操作相当于剪枝即如果有违反题目要求的情况出现直接就不进行回溯减少进入递归的次数//检查列以为此时调用该方法是固定列这时遍历行去检查列改变col去检查行for (int i 0; i row; i) {if (chessboard[i][col] Q){return false;}}//检查45°斜线for (int i row - 1, j col - 1; i 0 j 0; i--, j--) {if (chessboard[i][j] Q){return false;}}//检查135°斜线for (int i row - 1, j col 1; i 0 j n; i--, j) {if (chessboard[i][j] Q){return false;}}return true;}
}
37.解数独 class Solution {public void solveSudoku(char[][] board) {//没有new新的数组直接修改原来传入的数组所以返回值为voidbacktracking(board);}public boolean backtracking(char[][] board){//不需要终止条件因为一旦该数独没有解会直接返回false不会陷入死循环//一个for循环遍历棋盘的行一个for循环遍历棋盘的列//一行一列确定下来之后递归遍历这个位置放9个数字的可能性for (int i 0; i 9; i) {for (int j 0; j 9; j) {if (board[i][j] ! .){continue;//题目中初始的数独中空白部分是.此操作是为了跳过数独中的原始数字}for (char k 1; k 9; k) {if (isValid(i, j, k, board)){board[i][j] k;if (backtracking((board))){// 如果找到合适一组立刻返回return true;}board[i][j] .;}}return false;// 因为如果一行一列确定下来了这里尝试了9个数都不行说明这个棋盘找不到解决数独问题的解// 那么会直接返回这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去}}// 遍历完没有返回false说明找到了合适棋盘位置了return true;}public boolean isValid(int row, int col, char val, char[][] board){//检查同一行是否有重复for (int j 0; j 9; j) {if (board[row][j] val){return false;}}//检查同一列是否有重复for (int i 0; i 9; i) {if (board[i][col] val){return false;}}//检查同一个九宫格是否有重复int startRow (row / 3) * 3;int startCol (col / 3) * 3;for (int i startRow; i startRow 3; i) {for (int j startCol; j startCol 3; j) {if (board[i][j] val){return false;}}}return true;}
}
