接帮人家做网站的网站网站制作新报价

当前位置： 首页 > news >正文

接帮人家做网站的网站,网站制作新报价,非标自动化外包平台,建设官网网站何为回溯法#xff1f; 在搜索到某一节点的时候#xff0c;如果我们发现目前的节点#xff08;及其子节点#xff09;并不是需求目标时#xff0c;我们回退到原来的节点继续搜索#xff0c;并且把在目前节点修改的状态还原。 记住两个小诀窍#xff0c;一是按引用传状态… 何为回溯法 在搜索到某一节点的时候如果我们发现目前的节点及其子节点并不是需求目标时我们回退到原来的节点继续搜索并且把在目前节点修改的状态还原。 记住两个小诀窍一是按引用传状态()二是所有的状态修改在递归完成后回改。 回溯法修改一般有两种情况一种是修改最后一位输出比如排列组合一种是修改访问标 记比如矩阵里搜字符串。 46.全排列 46. 全排列 题目 给定一个不含重复数字的数组 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]]提示 1 nums.length 6-10 nums[i] 10nums 中的所有整数 互不相同​​​​​​​ 题解 输出该数组的所有排序组合我们可以使用回溯法。 首先确定一个位置然后跟后面的每个位置进行交换。换完之后到下一个位置。然后这一系列步骤结束后需要将换了的换回来。即回溯法。 class Solution { public:vectorvectorint permute(vectorint nums) {vectorvectorint ans;back(nums,0,ans);return ans;}void back(vectorint nums,int n,vectorvectorint ans){int i;if(nnums.size()-1)ans.push_back(nums);for(in;inums.size();i){swap(nums[i],nums[n]);back(nums,n1,ans);swap(nums[i],nums[n]);}} }; 77.组合 77. 组合 题目 给定两个整数 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]] 提示 1 n 201 k n 题解 设定一个count计算每一个的数量当countk时候就放入数组。这是跟之前不太一样的之前的是进行排列组合。这个有点像选择排列。 从1-n开始设置一个额外的数组来存储每一次的结果。count动态变化将i赋给后count加一dfs中从i1n选一个数字。回溯后count–。 class Solution { public:vectorvectorint combine(int n, int k) {vectorvectorint ans;vectorint c(k,0);int count;dfs(n,k,1,ans,c,count);return ans;}void dfs(int n,int k,int level,vectorvectorint ans,vectorint c,int count){int i;if(countk){ans.push_back©;return ;}for(ilevel;in;i){c[count]i;dfs(n,k,i1,ans,c,count);–count;}} }; 79.单位搜索 79. 单词搜索 题目 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。 单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例 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示例 3 输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCB 输出false提示 m board.lengthn board[i].length1 m, n 61 word.length 15board 和 word 仅由大小写英文字母组成 题解 类似的套路。 dfs回溯法首先定义一个visit来标记每一次搜索的时候该位置是否被标记过防止同一个位置被多次访问。 对于一个位置要进行边界判断是否越界。接着判断是否已经访问过是否已经成功找到是否该位置的字母与目标字母不同。 dfs往四周搜索。 class Solution { public:bool exist(vectorvectorchar board, string word) {if(board.empty())return false;int mboard.size(),nboard[0].size();vectorvectorbool visit(m,vectorbool(n,false));int i,j;bool findfalse;for(i0;im;i){for(j0;jn;j)back(i,j,board,word,find,visit,0);}return find;}void back(int i,int j,vectorvectorchar board,string word,bool find,vectorvectorbool visit,int level){if(i0||iboard.size()||j0||jboard[0].size())return ;if(visit[i][j]||find||board[i][j]!word[level])return ;if(levelword.size()-1){findtrue;return ;}visit[i][j]true;back(i1,j,board,word,find,visit,level1);back(i-1,j,board,word,find,visit,level1);back(i,j1,board,word,find,visit,level1);back(i,j-1,board,word,find,visit,level1);visit[i][j]false;} }; 51.N皇后 51. N 皇后 题目 按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。 给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。 示例 1 输入n 4 输出[[.Q..,…Q,Q…,..Q.],[..Q.,Q…,…Q,.Q..]] 解释如上图所示4 皇后问题存在两个不同的解法。示例 2 输入n 1 输出[[Q]]提示 1 n 9 题意 N皇后需要三个标记函数一个是列一个是主对角线另外一个是副对角线。 因为每一行肯定会放一个皇后一行一行遍历当成功遍历到最后一行并且成功放好皇后即可。所以不需要设行的标记函数。 这个时候我们可以从第一行开始按列遍历。判断该列是否为false该主对角线是否为false副对角线是否为false。如果是则下一列如果不是就将该位置置为Q然后对下一行进行同样的寻找。回溯法找完后记得将位置和标记函数还原。 这个对角线和副对角线。可以画在坐标上一个为yxb一个为y-xb。 所以by-x为了使b0因此我们加上n。另外一个为yx。 class Solution { public:vectorvectorstring solveNQueens(int n) {vectorvectorstring ans;if(n0)return {};vectorstring board(n,string(n,.));vectorbool c(n,false),l(2*n-1,false),r(2*n-1,false);back(n,ans,board,c,l,r,0);return ans;}void back(int n,vectorvectorstring ans,vectorstring board,vectorbool c,vectorbool l,vectorbool r,int row){if(rown){ans.push_back(board);return ;}int i;for(i0;in;i){if(c[i]||l[row-in]||r[rowi]){continue;}board[row][i]Q;c[i]l[row-in]r[rowi]true;back(n,ans,board,c,l,r,row1);board[row][i].;c[i]l[row-in]r[rowi]false;}} }; 总结 对于回溯法首先找到边界条件以及结束的条件。一般为设置的i等于行数。 边界条件一般为不要越界。 一般还需要设置标记函数。然后一行一行进行访问或者一个位置一个位置的访问访问过的标记函数置为true。接着继续下一个或者下一行一般是递归。然后结束后还原上面的标记函数以及board一般会设置一个作为答案。符合的就push_back到ans数组中去。