DFS+回溯算法专题
基础知识
回溯法是一种选优搜索法(试探法),被称为通用的解题方法,这种方法适用于解一些组合数相当大的问题。通过剪枝(约束+限界)可以大幅减少解决问题的计算量(搜索量)。
深度优先搜索(Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。
回溯和深度优先搜索的区别
回溯是一种更通用的算法。可以用于任何类型的结构,其中可以消除域的部分 ——无论它是否是逻辑树。
深度优先搜索是与搜索树或图结构相关的特定回溯形式。它使用回溯作为其使用树的方法的一部分,但仅限于树/图结构。
回溯法采用的是深度优先搜索的策略,当搜索到解空间树的某一结点时,用约束条件判断对该结点是否需要剪枝,如果结点不可行需要剪枝,则跳过以当前结点为根节点的子树的搜索,回溯到父结点;否则,继续按DFS策略搜索子树。
单纯的DFS以深度为关键词进行搜索时,不会对约束条件进行判断,而是在搜索完成(到达边界)时才会判断是否满足约束条件,进而判断是否形成一个可行解。
总的来说:回溯算法 = 树的深度优先搜索 + 剪枝函数
参考博客
参考博客
解题技巧
1、 一般矩阵或者棋盘的题,当数据范围比较小的时候用搜索算法(DFS || BFS),当数据范围比较大的时候用动态规划算法。
2、dfs + 回溯解题框架
dfs算法的过程其实就是一棵递归树,所有的dfs算法的步骤大概有以下几步:
- 找到终止条件,即递归树从根节点走到叶子节点时的返回条件,此时一般情况下已经遍历完了从根节点到叶子结点的一条路径,往往就是我们需要存下来的一种合法方案;
- 如果还没有走到底,那么我们需要对当前层的所有可能选择方案进行枚举,加入路径中,然后走向下一层;
- 在枚举过程中,有些情况下需要对不可能走到底的情况进行预判,例如一些不满足基本规则的情况,如果已经知道这条路不可能到达我们想去的地方,那我们干嘛还要一条路走到黑呢,这就是我们常说的剪枝的过程;
- 当完成往下层的递归后,我们需要将当前层的选择状态进行清零,它下去之前是什么样子,我们现在就要让它恢复初始状态,也叫恢复现场。该过程就是回溯,目的是回到最初选择路口的起点,好再试试其他的路。
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;如果不满足基本规则,则剪枝dfs(路径,选择列表); // 递归回溯,撤销处理结果}
}
3、dfs中最重要的是确定搜索顺序,做到不重不漏!!!
4、涉及到的排列组合这样的问题,也就是一堆数(或字符)中选数要求不重复使用(或者说满足某种规则,本质还是不能重复),通常可以通过设置额外的布尔数组记录每个数(字符)的使用状态,如46,47,90,51,52,37等都是这样的题目;
5、在写代码前务必理清楚满足题目要求的基本规则并制定出相应的剪枝策略!!如51,37,473
题目练习
17. 电话号码的字母组合
题目链接
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
题目分析
DFS + 回溯
搜索顺序:依次枚举每个组合由给定的按键中哪些字符组成
代码实现
class Solution {//回溯算法 时间复杂度为O(3^m + 4^n),证明见官方//初始对应所有的数字,为了直接对应2-9,新增了两个无效的字符串""String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};//涉及大量的字符串拼接,选择更为高效的StringBuilderStringBuilder combination = new StringBuilder();//存储结果List<String> result = new ArrayList<String>();public List<String> letterCombinations(String digits) {if (digits.length() == 0) {return result;}backTracking(digits, 0);return result;}public void backTracking(String digits, int index) {//终止条件 if (index == digits.length()) {result.add(combination.toString());return;}//获取对应的字符String chars = numString[digits.charAt(index) - '0'];//遍历字符for (int i = 0; i < chars.length(); i++) {combination.append(chars.charAt(i));//继续递归获取下一个号码对应的字符并组合backTracking(digits, index + 1);//回溯,去除已经遍历的字符,//如digits="23" ,初始时遍历'a',递归获得"ad",index=1,继续递归,index=2,加入result,//回溯到index=1这一层,执行下方代码,删除'd',继续执行,获得"ae","af",//回溯到index=0这一层,删除'a',i++,遍历'b',以此类推。combination.deleteCharAt(index);}}
}
79. 单词搜索
题目链接
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
题目分析
代码实现
class Solution {//dfs 时间复杂度是O(n^2 3^k)//从单词矩阵中枚举每个单词的起点,从该起点出发往四周dfs搜索目标单词,并记录当前枚举到第几个单词,//若当前搜索到的位置(i,j)的元素恰好是word单词第depth个字符,则继续dfs搜索,//直到depth到最后一个字符则表示有了符合的方案,返回trueint[] dx = new int[]{0, -1, 0, 1};int[] dy = new int[]{-1, 0, 1, 0};int m, n;public boolean exist(char[][] board, String word) {//获取单词矩阵的行列数m = board.length; //行数n = board[0].length; //列数//遍历矩阵每个字符for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){//如果是目标单词首字母,则从该字符出发向四周搜索目标单词if(board[i][j] == word.charAt(0)){if(dfs(board, word, 0, i, j)){return true;}}}}//如果遍历完所有字符都没有目标单词首字母,说明不存在return false;}//向四周搜索目标单词 index表示单词位public boolean dfs(char[][] board, String word, int index, int x, int y){//终止条件 如果所遍历的矩阵字符与对应单词位上的字符不等 和 搜索完单词所有字符if(board[x][y] != word.charAt(index)) return false;if(index == word.length() - 1) return true;char c = board[x][y];//标记已遍历的字符board[x][y] = '*';//获取当前字符上下左右的相邻字符for(int i = 0; i < 4; i++){int u = x + dx[i];int v = y + dy[i];//如果超出矩阵边界if(u < 0 || u >= m || v < 0 || v >= n) continue;//已使用过的字符不能重复再用 剪枝if(board[u][v] == '*') continue;//如果匹配上了,则继续匹配单词其他字符,直到匹配完或匹配失败if(dfs(board, word, index + 1, u, v)) return true;}//回溯 恢复初始状态board[x][y] = c;return false;}
}
46. 全排列
题目链接
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
题目分析
第一种顺序:
第二种顺序:
这里给出的搜索顺序为:依次枚举每个位置放什么数
代码实现
class Solution {//DFS+回溯 时间复杂度O(n∗n!) 每个位置放什么数int len; //数组长度List<Integer> res = new ArrayList<>(); //每次排列的结果List<List<Integer>> result = new ArrayList<>(); //全排列boolean[] state; //标志排列时是否使用过该数字public List<List<Integer>> permute(int[] nums) {len = nums.length;if(nums == null || len == 0) return result;state = new boolean[len];dfs(nums, 0);return result;}public void dfs(int[] nums, int index){//终止条件if(index == len){//必须新建ArrayList对象存储此时res的值,//否则因为存入的是res的引用地址,最后回溯清空后,未存入任何结果result.add(new ArrayList<>(res));return;}//遍历nums中的每个数字 枚举每个位置放什么数for(int i = 0; i < len; i++){if(!state[i]){ //剪枝 不满足条件则跳过//标记该数字本次排列已经使用过state[i] = true;res.add(nums[i]);//递归继续遍历其他数字dfs(nums, index + 1);//回溯 恢复初始状态state[i] = false;res.remove(res.size() - 1);}}}
}
47. 全排列 II
题目链接
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列
题目分析
1、对数组从小到大排序,使得相同的数都是相邻的;
2、从前往后枚举当前数组中没有选过的元素,由于相同的数保证从第一个开始用,直到最后一个,才会保证枚举的顺序不会出现重复的情况,若nums[i] == nums[i - 1]
,并且i - 1
位置元素未使用过,则表示前面的枚举顺序已经存在了该枚举情况,造成重复;
3、将枚举到的元素插入到当前存数字的链表t中,并标记为已使用过,递归到下一层,直到枚举完所有数为止(u == n)
,把当前链表t加入到存列表的result列表中,并进行回溯,恢复现场,把使用过的标记为未使用过。
参考博客
这里给出的搜索顺序为:依次枚举每个位置放什么数
代码实现
class Solution {//DFS+回溯+去重 时间复杂度 O(n∗n!) 每个位置放什么数//关键在于如何去重:首先对数组从小到大排序,使得相同的数都是相邻的;//然后从前往后枚举当前数组中没有选过的元素,由于相同的数保证从第一个开始用,直到最后一个,//才会保证枚举的顺序不会出现重复的情况,若nums[i]==nums[i - 1],并且i-1位置元素状态为未使用,//则表示前面的枚举顺序已经存在了该枚举情况,造成重复int len;List<Integer> res = new ArrayList<Integer>();List<List<Integer>> result = new ArrayList<List<Integer>>();boolean[] state;public List<List<Integer>> permuteUnique(int[] nums) {len = nums.length;state = new boolean[len];Arrays.sort(nums);dfs(nums, 0);return result;}public void dfs(int[] nums, int index){//终止条件 index表示当前排列的长度if(index == len){ result.add(new ArrayList<>(res)); return;}//遍历nums中的每个数字for(int i = 0; i < len; i++){//如果与前一个数字相等且前一个数字的状态为true,说明刚被使用,不会重复排列,继续//如果与前一个数字相等且前一个数字的状态为false,说明前一个数字在上一轮已使用并回溯为未使用状态,//继续递归得到的排列是和上一轮重复的,因此剪枝去重if(i > 0 && nums[i] == nums[i - 1] && !state[i - 1]) continue;//未使用if(!state[i]){ //不满足未使用该数的条件则不执行 剪枝//标记该数字本次排列已经使用state[i] = true;res.add(nums[i]);dfs(nums, index + 1); //回溯,恢复初始状态state[i] = false;res.remove(res.size() - 1); }}}
}
78. 子集
题目链接
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
题目分析
搜索顺序为:依次枚举数组中每个位置的数 选 还是 不选,
不断递归到下一层,当index == nums.length
时,表示有一种满足题意的情况看,加入到result 列表中
代码实现
class Solution {//DFS+回溯 枚举每个位置的数选还是不选,并递归到下一层//时间复杂度:O(n×2^n )。一共 2^n个状态,每种状态需要O(n) 的时间来构造子集。空间复杂度:O(n)List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {result.clear();dfs(nums, 0);return result;}public void dfs(int[] nums, int index){//终止条件if(index == nums.length) {result.add(new ArrayList(path));return;}//不选 直接跳过该数 执行下方语句得到[]dfs(nums, index + 1);//选 初始时index=2 得到[3]path.add(nums[index]);//继续递归,对下一个数进行选择dfs(nums, index + 1);//回溯path.remove(path.size() - 1);}
}
90. 子集 II
题目链接
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
题目分析
搜索顺序为:依次枚举数组中每个位置的数 选 还是 不选,
先对数组从小到大排序,每个数有选和不选两种情况,若选的话,假设上一个数与当前数一致,且上一个数没有选,则当前数一定不能选,否则会产生重复情况
需要注意的是先做不选,因此index索引是由大到小执行选择的。
代码实现
class Solution {//DFS + 回溯 + 去重 时间复杂度:O(n×2^n)//先对数组从小到大排序,每个数有选和不选两种情况,//若选的话,假设上一个数与当前数一致,且上一个数状态为未选,则当前数一定不能选,否则会产生重复情况List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();boolean[] state;public List<List<Integer>> subsetsWithDup(int[] nums) {state = new boolean[nums.length];Arrays.sort(nums); //O(nlogn)dfs(nums, 0);return result;}public void dfs(int[] nums, int index){//终止条件 index表示自己长度,也表示访问nums的索引if(index == nums.length){result.add(new ArrayList(path));return;}//先考虑不选 dfs(nums, index + 1);//选 index由大到小 如1 2 2 index=2 跳过 index = 1 选得到[2]、[2,2]//去重 如果上一个数与当前数相等,且上一个数状态为未选,当前数一定不能选,否则重复if(index > 0 && nums[index] == nums[index - 1] && !state[index - 1]) return;if(!state[index]){ //剪枝state[index] = true;path.add(nums[index]);//继续递归dfs(nums, index + 1);//回溯path.remove(path.size() - 1);state[index] = false;}}
}
216. 组合总和 III *****
题目链接
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
所有数字都是正整数。
解集不能包含重复的组合。
题目分析
1、搜索顺序为:依次枚举每个数从哪个位置选;
2、考虑参数dfs(int k, int n, int index, int count, int sum)
:k表示只能用k个数,n表示题目给定需要用k个数凑出来的总值,index表示从哪个数开始往下枚举,避免重复,count表示目前用的数的个数,sum表示当前已经凑出来的总值
3、如果当前用了数是x,那下一次枚举的位置 index 就需要从x + 1(或index+1)开始枚举,避免重复操作;
代码实现
class Solution {//DFS + 回溯 依次枚举每个数从哪个位置(1-9)上选List<Integer> path = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum3(int k, int n) {//小优化if(n < k || k > 9 || n > 45) return result;dfs(k, n, 1, 0, 0);return result;}//需要的参数(k, n,开始枚举的位置, 枚举到第几个数,当前选择的数的总和)public void dfs(int k, int n, int index, int count, int sum){//终止条件if(sum > n) return; //剪枝if(k == count){if(sum == n) result.add(new ArrayList(path));return;}//枚举每个数for(int i = index; i <= 9; i++){path.add(i);//继续枚举凑和dfs(k, n, i + 1, count + 1, sum + i);//回溯 恢复初始状态path.remove(path.size() - 1);}}
}
51. N 皇后 *****
题目链接
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
题目分析
皇后,是国际象棋中的棋子,意味着国王的妻子。皇后只做一件事,那就是“吃子”。当她遇见可以吃的棋子时,就迅速冲上去吃掉棋子。当然,她横、竖、斜都可走一到七步,可进可退。
搜索顺序: 依次枚举确定每行皇后的位置
DFS + 回溯 ,注意顺序!!!
1、递归终止条件:当皇后来到martix.length - 1的位置的时候,就已经是摆放皇后的最后一个位置了,然后用一个变量来记录当前皇后的递归深度:y,所以递归终止条件: y == n 时退出递归。
2、利用for 循环来遍历二维矩阵的所有列,使得皇后在每个列上作为开头找到对应的组合方案(递归)
3、题目中说到,在摆放的当前皇后的位置的同一行,同一列,同一斜率的方向都不能摆放其他皇后,这就是剪枝条件了。
- 首先是不让皇后在同一行上,只要我们成功摆放了一个皇后,就进入递归,去到下一行摆放新皇后的位置。
- 然后是不让皇后在同一列上:定义一个标志各列是否有皇后的布尔型数组column[],只要成功摆放一个皇后的位置,就把当前列对应的数组索引元素置为true,后面的皇后只要发现此列为true,说明后面的皇后与前面的皇后处于同一列,当前列位置不能进行摆放。
- 最后是同一斜率,其实就是过当前位置的45度斜线和135斜线,如下图;通过当前位置可以就得参数c1和c2,若其他位置执行两个斜线函数的结果也等于c1,c2,说明在这两条斜线上,不能放置皇后(这里使用两个数组分别标志c1和c2)。
代码实现
class Solution {//DFS + 回溯 排列枚举(见官方) 时间复杂度:O(N!),其中N是皇后数量,空间复杂度:O(N)//具有如下标准:不能同行 不能同列 不能同斜线 (45度和135度)int N = 20; //后面y-x+n可能为9-0+9=18因此设为20 写为20是为了避免处理越界的情况boolean[] column = new boolean[N]; //标志当前列是否有皇后boolean[] dg = new boolean[N]; //45度斜线boolean[] udg = new boolean[N]; //135度斜线char[][] chessboard = new char[N][N];List<List<String>> result = new ArrayList<>();public List<List<String>> solveNQueens(int n) {result.clear();//构造棋盘 先用空位填满for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){chessboard[i][j] = '.';}}dfs(n, 0);return result;}//明确两点:一次根节点到叶子节点就代表一种解法;总解法数不会超过npublic void dfs(int n, int y){//终止条件 y表示当前行数if(y == n){//存储当前解法List<String> path = new ArrayList<>();for(int i = 0; i < n; i++){String temp = "";for(int j = 0; j < n; j++){//存储具体的每种解法temp += chessboard[i][j];}path.add(temp);}result.add(path);return;}//确定皇后的位置 x表示当前列for(int x = 0; x < n; x++){//剪枝//y+x-c1=0经过棋盘每个点(i,index)的135度斜线,c2=y-x经过棋盘每个点的45度斜线//由y和x可以求出参数c1,c2,从而可以判断其他点是否在斜线上,若在,则不能放皇后if(!column[x] && !dg[y - x + n] && !udg[y + x]){ //这里+n是为了便于存储(y-x可能为负数)//标志该列以及两条斜线上不能放皇后column[x] = dg[y - x + n] = udg[y + x] = true;//放皇后chessboard[y][x] = 'Q';//当确定一个皇后就进入递归确定本解法中下一行皇后的位置,从而保证皇后不再同一行上dfs(n, y + 1);//回溯 便于寻找下一种解法chessboard[y][x] = '.';column[x] = dg[y - x + n] = udg[y + x] = false;}}}
}
52. N皇后 II
题目链接
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。
题目分析
和51解法基本一致,分析这里给出另一种参考代码,对斜线的处理相对更容易理解
参考
代码实现
class Solution {//DFS + 回溯 排列枚举(见官方) 时间复杂度:O(N!),其中N是皇后数量,空间复杂度:O(N)//具有如下标准:不能同行 不能同列 不能同斜线 (45度和135度)int result = 0;int N = 20; //这里写为20是为了避免处理越界的情况boolean[] dg = new boolean[N]; //45度斜线boolean[] udg = new boolean[N]; //135度斜线boolean[] column = new boolean[N]; //列public int totalNQueens(int n) {dfs(n, 0);return result;}public void dfs(int n, int y){//终止条件if(y == n){ //y表示第几行 result++; //如果无解(如n=3,最后有y=2<n),根本不会执行这里的代码 return;}for(int x = 0; x < n; x++){ //x表示第几列//如果满足基本规则 不满足则跳过(剪枝)if(!column[x] && !dg[x+y] && !udg[y-x+n]){ //由于y-x可能为负数,+n便于存储//标志已经放了皇后,满足下方条件的位置不能放皇后了column[x] = dg[x+y] = udg[y-x+n] = true;//继续递归放置其他皇后,进入下一行dfs(n, y + 1);//回溯 恢复初始状态寻找下一种解法column[x] = dg[x+y] = udg[y-x+n] = false;}}}
}
37. 解数独
题目链接
编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 ‘.’ 表示。
题目分析
八皇后问题和本题中的解数独问题都可以归类于精确覆盖问题,使用Dancing Links算法可以完美解决
DFS + 回溯 搜索顺序为: 从前往后从上到下依次枚举每个空格该填哪个数
这道题还是按DFS+回溯框架解题就可以,但是要通过调试代码想清楚每一行代码的意义,特别是回溯部分,存在以下含义:
- 如果当前尝试的填法不满足基本规则,则恢复棋盘,重新填下一个暂时满足规则的数;
- 如果填完当前行还是不满足基本规则,就再次回溯,直到找到当前行正确的填数顺序,再开始填下一行;
- 如果当前行始终找不到正确的填数顺序,则回到x-1的那一层进行回溯重填,也就是重填上一行,,直到正确
代码实现
class Solution {//DFS + 回溯 从前往后枚举每个空格该填哪个数//基本规则; 同行不能重复 同列不能重复 同一个九宫格内不能重复boolean[][] row = new boolean[10][10]; //记录每行中使用了哪些数 如row[0][5]=true表示第一行使用了5boolean[][] col = new boolean[10][10]; //记录每列中使用了哪些数 如col[0][5]=true表示第一列使用了5 这里写为10是为了防止越界//记录每个九宫格中使用了哪些数 如cell[4/3][4/3][8]=true表示第1行第1列的九宫格中使用了8boolean[][][] cell = new boolean[3][3][10]; public void solveSudoku(char[][] board) {//初始化for(int i = 0; i < 9; i++){ //遍历行for(int j = 0; j < 9; j++){ //遍历列//分别在row,col,cell中记录已经有数的位置并记录是哪个数,避免重复if(board[i][j] != '.'){ int temp = board[i][j] - '0';row[i][temp] = col[j][temp] = cell[i / 3][j / 3][temp] = true;}}}//从(0,0)开始依次枚举每个空格该填哪个数dfs(board, 0, 0);}//递归枚举每个空格应该填什么数public boolean dfs(char[][] board, int x, int y){//判断边界if(y == 9){ //遍历完该行所有列则继续遍历下一行x++;y = 0;//终止条件,遍历完所有行所有列,说明已完成填数if(x == 9) return true;}//跳过已经填了数的位置if(board[x][y] != '.'){return dfs(board, x, y + 1);}//在递归所枚举的空格处 枚举1-9中的每个数 尝试填数for(int i = 1; i <= 9; i++){//如果待填数不满足基本规则,则跳过 剪枝if(row[x][i] || col[y][i] || cell[x / 3][y / 3][i]) continue;//填数 记得强转类型board[x][y] = (char)('0' + i);//更新状态row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;//继续填下一个空格if(dfs(board, x, y + 1)) return true;//回溯 //如果当前尝试的填法不满足基本规则,则恢复棋盘,重新填下一个暂时满足规则的数,//如果填完当前行还是不满足基本规则,就不断回溯重填,直到找到当前行正确的填数顺序,再开始填下一行;//如果当前行始终找不到正确的填数顺序,则回到x-1的那一层进行回溯重填,也就是重填上一行,直到正确board[x][y] = '.';row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;}//如果该空格处9个数都试完了都不行,说明无解,直接返回false,程序停止return false;}
}
473. 火柴拼正方形****
题目链接
还记得童话《卖火柴的小女孩》吗?现在,你知道小女孩有多少根火柴,请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴,可以把火柴连接起来,并且每根火柴都要用到。
输入为小女孩拥有火柴的数目,每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
题目分析
DFS + 回溯 且必须用好剪枝 搜索顺序为:依次拼正方形的每条边
本题是关于剪枝的经典问题,遵循以下策略:
1、总长度应是4的倍数,火柴个数不能小于4以及最长的火柴不能大于正方形边长;
2、将火柴从大到小排序,进行搜索,这样每次剪枝去掉的分支会更多;
3、如果当前木棍填充失败,那么跳过接下来所有相同长度的木棍;
4、如果当前木棍填充失败,且是当前边的第一个,则直接剪掉当前分支(直接返回false),因为这说明还没有使用的最长的火柴找不到可匹配的组合。
5、如果当前木棍填充失败,并且是当前边的最后一个,则直接剪掉当前分支,因为火柴已经被降序排列,当前火柴之后的火柴 和 当前边长度curLen 的和必然小于边的目标长度singleLen。
策略3、4、5可以让程序从100+ms,变成0-8ms。
代码实现
class Solution {//DFS + 回溯 时间复杂度:O(4^N)//基本规则:每条边目标长度固定不能超出(正方形每条边相等) 每根火柴都要使用且不重复使用 //本题重点是如何剪枝 遵循以下策略:// 1. 总长度应是4的倍数,火柴个数不能小于4以及最长的火柴不能大于正方形边长;// 2. 每条边的内部木棍长度从大到小填// 3. 如果当前木棍填充失败,那么跳过接下来所有相同长度的木棍// 4. 如果当前木棍填充失败,并且是当前边的第一个,则直接剪掉当前分支// 5. 如果当前木棍填充失败,并且是当前边的最后一个,则直接剪掉当前分支//策略3、4可以让程序从100+ms,变成0-8ms。boolean[] state;public boolean makesquare(int[] nums) {//首先考虑特殊情况if(nums.length < 4) return false;//求和 因为是正方形,总长度应该是4的倍数 如果最大的数大于正方形边长直接不满足基本规则int sum= IntStream.of(nums).sum();if(sum % 4 != 0 || nums[0] > sum / 4) return false;//使数组元素降序 2. 每条边的内部木棍长度从大到小填nums = IntStream.of(nums).boxed().sorted(Comparator.reverseOrder()).mapToInt(Integer::intValue).toArray();state = new boolean[nums.length];return dfs(nums, 0, 0, sum / 4);}//dfs(nums,当前边,每条边当前长度,每条边目标长度)public boolean dfs(int[] nums, int index, int curLen, int singleLen){//当前边达到目标长度就进入下一条边if(curLen == singleLen){index++;//终止条件if(index == 4) return true;curLen = 0;}//枚举每条边由哪些火柴组成for(int i = 0; i < nums.length; i++){//剪枝 保证火柴未使用或拼接该火柴后当前边长度小于目标长度if(!state[i] && curLen + nums[i] <= singleLen){//标记当前火柴已经使用过 state[i] = true;//继续寻找当前边的下一根火柴if(dfs(nums, index, curLen + nums[i], singleLen)) return true;//回溯 //如果当前尝试的拼法不满足基本规则,则去掉当前火柴,重新选择下一个暂时满足规则的火柴,//如果拼完当前边不满足基本规则,就不断回溯重拼,直到找到当前边正确拼法,再开始拼下一条边;//如果当前边无法正确拼接,则回到index-1的那一层进行回溯重填,也就是重拼上一条边,直到正确state[i] = false;//剪枝//3.如果当前火柴填充失败,那么跳过接下来所有相同长度的火柴while(i + 1 < nums.length && nums[i + 1] == nums[i]) i++;//4.执行到这里说明当前火柴填充失败,满足if条件说明当前火柴是当前边的第一个,//这说明未使用的最长的火柴找不到可匹配的组合,因此直接剪掉当前分支if(curLen == 0) return false;//5.执行到这里说明当前火柴填充失败,若满足if条件,由于火柴已被降序排列,//当前火柴之后的火柴 和 curLen 的和必然小于singleLen, 因此直接剪掉当前分支if(curLen + nums[i] == singleLen) return false;}}return false;}
}
如若内容造成侵权/违法违规/事实不符,请联系编程学习网邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
相关文章
- Linux dmidecode命令的使用
一、dmidecode简介 dmidecode是Linux系统中自带的硬件查询工具;dmidecode的作用是将DMI数据库中的信息进行解码,然后以可读的方式显示。DMI(Desktop Management Interface, DMI)就是帮助收集电脑系统信息的管理系统,D…...
2024/4/15 2:29:16 - c# 自定义List排序
自定义List排序sort返回排序的几种实现方式List.Sort(Comparison comparison)List.Sort(IComparer Comparer)刚使用sort排序又又又又又忘了,返回1(大于0即可),-1(小于0即可)是怎么排序了,果然是…...
2024/5/8 15:32:33 - selenium安装--谷歌(from selenium.webdriver import Chrome)
写代码有个习惯,什么类型的代码就以它定义文件名,这就导致遇到了这个错误。 百度了好多解决办法,但都没有得到解决。最后看到了这样一句话“ 看看自己报错的代码路径下是不是有一个叫selenium.py的文件,如果有,把名字…...
2024/4/13 23:03:45 - Apifox学习记录(一)
目录1.前言2.初识Apifox2.1 Apifox的名字2.2 Apifox是什么?2.3 功能特性2.4 学习途径3. 使用Apifox3.1 安装3.2 启动1.前言 偶然的机会发现接口测试工具Apifox,看到介绍说的是挺好用的接口调试、自动化测试的工具,因此进行学习。 2.初识Api…...
2024/5/8 12:40:31 - 什么是数据结构
文章目录前言一、线性表1.顺序表2.链表3.栈和队列二、数存储结构三、图存储结构总结前言 数据存储方式有哪几种呢?本节将对数据结构的学习内容做一个简要的总结。 数据结构大致包含以下几种存储结构: 线性表,还可以细分为顺序表、链表、栈和…...
2024/4/13 23:03:50 - 数据类型扩展及面试题
数据类型扩展及面试题讲解 整数拓展: 进制 二进制(0b开头) 十进制 八进制(0开头) 十六进制(0x开头) int y20; int y2020; int y30x20;浮点拓展: float double float g0.1f; //等…...
2024/5/1 18:21:26 - Java中数组的简单了解
数组 数组的基本格式 //先定义一个数组的类型,再创建数组的空间。 int num[]; num[]new int[10];//这里创建10个数组 //或者是将其合并在一起写 int num[]new int[10];例子: package com.method;public class Demo07 {public static void main(String…...
2024/4/13 23:03:45 - scrapy初体验之settings、spider、items、pipelines
Scrapy到目前为止依然是这个星球上最流行的爬虫框架. 摘一下官方给出对scrapy的介绍 An open source and collaborative framework for extracting the data you need from websites. In a fast, simple, yet extensible way. scrapy的特点: 速度快, 简单, 可扩展性强. 创建…...
2024/4/13 23:03:40 - leetcode每日一题1765. 地图中的最高点 简单的多源BFS最短路问题 模板题
📖本篇内容:leetcode每日一题1765. 地图中的最高点 简单的多源BFS最短路问题 模板题 📑 文章专栏:leetcode每日一题《打卡日常》 📆 最近更新:2022年1月28日 leetcode每日一题1996. 游戏中弱角色的数量 排…...
2024/4/15 22:34:02 - 班农注定落得如此下场
53岁的班农,凭借宣扬“白人至上”理念的班农无意间得到了默瑟家族基金会的青睐,在其支助下,班农担任上了一家英国公司“剑桥分析”的董事会副主席。该公司在之后参与推动英国脱欧及干涉2016年美国大选的政治活动,班农的政治履历又…...
2024/4/17 12:01:24 - 体验国际编程大赛(完成报名可抽奖)
第十届CodeVita国际编程大赛由世界500强塔塔集团旗下TCS(位于上海张江)举办,往届已吸引全球超100多万名学生参与,是个体验国际舞台、交流学习的好机会! 限20届-25届学生报名,参与初赛均可轻松获得TCS颁发的…...
2024/4/7 18:45:16 - Android Retrofit2随记
注解、反射、代理模式: Java:注解和反射 - opendragonhuang - 博客园 创建Retrofit使用 建造者模式 Retrofit其实是将OkHttp进行了封装; 解决了Okhttp请求完数据不能自动切回主线程的问题; 在build时,创建了一个主…...
2024/4/7 18:45:15 - C++中类的静态变量的特性及使用方法
静态成员变量 静态成员的提出是为了解决数据共享的问题。实现共享有许多方法,如:设置全局性的变量或对象是一种方法。但是,全局变量或对象是有局限性的。这一章里,我们主要讲述类的静态成员来实现数据的共享。 静态数据成员 在…...
2024/4/13 23:04:00 - 红帽 Linux Redhat6.4安装MySQL 5.1
[rootlocalhost /]# cat /etc/redhat-release Red Hat Enterprise Linux Server release 6.4 (Santiago) 指定yum源, [rootWebServer ~]# vi /etc/yum.repos.d/rhel-source.repo 区分大小写,不要出错 新建以下内容 固定格式:[rhel-source-l…...
2024/4/25 9:42:13 - 2021-2027中国宠物服装市场现状研究分析与发展前景预测报告
【报告篇幅】:118 【报告图表数】:161 【报告出版时间】:2021年12月 报告摘要 2021年中国宠物服装市场销售收入达到了 万元,预计2028年可以达到 万元,2022-2028期间年复合增长率(CAGR)为 %。中国市场核心厂商包括Hur…...
2024/4/13 23:03:35 - openLooKeng算子接口和执行流程
1 openLooKeng 算子接口 1.1 openLooKeng算子相关类 ▲ 图1-1 算子相关类 openLooKeng生成物理执行计划后,真正执行计划的是一个一个的算子(即Operator)。openLooKeng中将算子抽象为Operator接口,将算子工厂抽象为OperatorFacto…...
2024/4/7 18:45:11 - Android架构组件JetPack之Room(三),阿里P8架构师
Ignore 用于告诉Room需要忽略的字段或方法建立索引:在Entity注解的indices属性中添加索引字段。例如:indices {Index(value {"first_name", "last_name"}, unique true), ...}, unique true可以确保表中不会出现{"first_na…...
2024/4/13 23:03:30 - 【蓝桥杯】定时器的定时与计数功能使用
我们先来了解一下定时器中断是干什么的,这里举个例子 1、打个比喻 上课铃响,老师上课,下课铃响,老师下课,当然老师不听铃声上下课的也可以 这里的老师就是CPU,闹铃就是定时器,当闹铃计数到四十…...
2024/4/7 18:45:09 - SonarQube 未授权漏洞
0x01 漏洞影响产品概述 SonarQube是一款开源静态代码质量分析管理工具,支持Java、Python、PHP、JavaScript、CSS等27种以上目前极为流程的编程开发语言,同时它能够便捷集成在各种IDE、Jenkins、Git等服务中,方便及时查看代码质量分析报告。该…...
2024/4/15 14:14:18 - 【linux】进程控制
【linux】进程控制 01.进程号相关函数 getpid函数 pid_t getpid(void); 功能:获取本进程号(PID) 参数:无 返回值:本进程号getppid函数 pid_t getppid(void); 功能:获取调用此函数的进程的父进程号&…...
2024/4/13 23:04:36
最新文章
- 前端如何给特定的组件设置缓存并处理定位问题?
前端如何给某些组件设置缓存并处理定位? 最近有个需求就是a>b,b页面处理了些操作,返回a页面时, b页面若有操作则a页面需要刷新并定位到上次点击的位置,b若没有操作则无需刷新直接定位上次点击的位置 1.首先在store中存储缓存的组件 vuex代码: const cached {state: {ca…...
2024/5/8 17:23:02 - 梯度消失和梯度爆炸的一些处理方法
在这里是记录一下梯度消失或梯度爆炸的一些处理技巧。全当学习总结了如有错误还请留言,在此感激不尽。 权重和梯度的更新公式如下: w w − η ⋅ ∇ w w w - \eta \cdot \nabla w ww−η⋅∇w 个人通俗的理解梯度消失就是网络模型在反向求导的时候出…...
2024/5/7 10:36:02 - yolov9直接调用zed相机实现三维测距(python)
yolov9直接调用zed相机实现三维测距(python) 1. 相关配置2. 相关代码2.1 相机设置2.2 测距模块2.2 实验结果 相关链接 此项目直接调用zed相机实现三维测距,无需标定,相关内容如下: 1. yolov4直接调用zed相机实现三维测…...
2024/5/8 15:11:36 - 解决npm install安装node-sass包容易失败的问题
具体问题如下: npm ERR! code ERESOLVE npm ERR! ERESOLVE unable to resolve dependency tree npm ERR! npm ERR! While resolving: XXX3.4.0 npm ERR! Found: webpack5.31.2 npm ERR! node_modules/webpack npm ERR! peer webpack”^4.0.0 || ^5.0.0″ from html-…...
2024/5/8 2:37:22 - 【外汇早评】美通胀数据走低,美元调整
原标题:【外汇早评】美通胀数据走低,美元调整昨日美国方面公布了新一期的核心PCE物价指数数据,同比增长1.6%,低于前值和预期值的1.7%,距离美联储的通胀目标2%继续走低,通胀压力较低,且此前美国一季度GDP初值中的消费部分下滑明显,因此市场对美联储后续更可能降息的政策…...
2024/5/8 6:01:22 - 【原油贵金属周评】原油多头拥挤,价格调整
原标题:【原油贵金属周评】原油多头拥挤,价格调整本周国际劳动节,我们喜迎四天假期,但是整个金融市场确实流动性充沛,大事频发,各个商品波动剧烈。美国方面,在本周四凌晨公布5月份的利率决议和新闻发布会,维持联邦基金利率在2.25%-2.50%不变,符合市场预期。同时美联储…...
2024/5/7 9:45:25 - 【外汇周评】靓丽非农不及疲软通胀影响
原标题:【外汇周评】靓丽非农不及疲软通胀影响在刚结束的周五,美国方面公布了新一期的非农就业数据,大幅好于前值和预期,新增就业重新回到20万以上。具体数据: 美国4月非农就业人口变动 26.3万人,预期 19万人,前值 19.6万人。 美国4月失业率 3.6%,预期 3.8%,前值 3…...
2024/5/4 23:54:56 - 【原油贵金属早评】库存继续增加,油价收跌
原标题:【原油贵金属早评】库存继续增加,油价收跌周三清晨公布美国当周API原油库存数据,上周原油库存增加281万桶至4.692亿桶,增幅超过预期的74.4万桶。且有消息人士称,沙特阿美据悉将于6月向亚洲炼油厂额外出售更多原油,印度炼油商预计将每日获得至多20万桶的额外原油供…...
2024/5/7 14:25:14 - 【外汇早评】日本央行会议纪要不改日元强势
原标题:【外汇早评】日本央行会议纪要不改日元强势近两日日元大幅走强与近期市场风险情绪上升,避险资金回流日元有关,也与前一段时间的美日贸易谈判给日本缓冲期,日本方面对汇率问题也避免继续贬值有关。虽然今日早间日本央行公布的利率会议纪要仍然是支持宽松政策,但这符…...
2024/5/4 23:54:56 - 【原油贵金属早评】欧佩克稳定市场,填补伊朗问题的影响
原标题:【原油贵金属早评】欧佩克稳定市场,填补伊朗问题的影响近日伊朗局势升温,导致市场担忧影响原油供给,油价试图反弹。此时OPEC表态稳定市场。据消息人士透露,沙特6月石油出口料将低于700万桶/日,沙特已经收到石油消费国提出的6月份扩大出口的“适度要求”,沙特将满…...
2024/5/4 23:55:05 - 【外汇早评】美欲与伊朗重谈协议
原标题:【外汇早评】美欲与伊朗重谈协议美国对伊朗的制裁遭到伊朗的抗议,昨日伊朗方面提出将部分退出伊核协议。而此行为又遭到欧洲方面对伊朗的谴责和警告,伊朗外长昨日回应称,欧洲国家履行它们的义务,伊核协议就能保证存续。据传闻伊朗的导弹已经对准了以色列和美国的航…...
2024/5/4 23:54:56 - 【原油贵金属早评】波动率飙升,市场情绪动荡
原标题:【原油贵金属早评】波动率飙升,市场情绪动荡因中美贸易谈判不安情绪影响,金融市场各资产品种出现明显的波动。随着美国与中方开启第十一轮谈判之际,美国按照既定计划向中国2000亿商品征收25%的关税,市场情绪有所平复,已经开始接受这一事实。虽然波动率-恐慌指数VI…...
2024/5/7 11:36:39 - 【原油贵金属周评】伊朗局势升温,黄金多头跃跃欲试
原标题:【原油贵金属周评】伊朗局势升温,黄金多头跃跃欲试美国和伊朗的局势继续升温,市场风险情绪上升,避险黄金有向上突破阻力的迹象。原油方面稍显平稳,近期美国和OPEC加大供给及市场需求回落的影响,伊朗局势并未推升油价走强。近期中美贸易谈判摩擦再度升级,美国对中…...
2024/5/4 23:54:56 - 【原油贵金属早评】市场情绪继续恶化,黄金上破
原标题:【原油贵金属早评】市场情绪继续恶化,黄金上破周初中国针对于美国加征关税的进行的反制措施引发市场情绪的大幅波动,人民币汇率出现大幅的贬值动能,金融市场受到非常明显的冲击。尤其是波动率起来之后,对于股市的表现尤其不安。隔夜美国股市出现明显的下行走势,这…...
2024/5/6 1:40:42 - 【外汇早评】美伊僵持,风险情绪继续升温
原标题:【外汇早评】美伊僵持,风险情绪继续升温昨日沙特两艘油轮再次发生爆炸事件,导致波斯湾局势进一步恶化,市场担忧美伊可能会出现摩擦生火,避险品种获得支撑,黄金和日元大幅走强。美指受中美贸易问题影响而在低位震荡。继5月12日,四艘商船在阿联酋领海附近的阿曼湾、…...
2024/5/4 23:54:56 - 【原油贵金属早评】贸易冲突导致需求低迷,油价弱势
原标题:【原油贵金属早评】贸易冲突导致需求低迷,油价弱势近日虽然伊朗局势升温,中东地区几起油船被袭击事件影响,但油价并未走高,而是出于调整结构中。由于市场预期局势失控的可能性较低,而中美贸易问题导致的全球经济衰退风险更大,需求会持续低迷,因此油价调整压力较…...
2024/5/4 23:55:17 - 氧生福地 玩美北湖(上)——为时光守候两千年
原标题:氧生福地 玩美北湖(上)——为时光守候两千年一次说走就走的旅行,只有一张高铁票的距离~ 所以,湖南郴州,我来了~ 从广州南站出发,一个半小时就到达郴州西站了。在动车上,同时改票的南风兄和我居然被分到了一个车厢,所以一路非常愉快地聊了过来。 挺好,最起…...
2024/5/7 9:26:26 - 氧生福地 玩美北湖(中)——永春梯田里的美与鲜
原标题:氧生福地 玩美北湖(中)——永春梯田里的美与鲜一觉醒来,因为大家太爱“美”照,在柳毅山庄去寻找龙女而错过了早餐时间。近十点,向导坏坏还是带着饥肠辘辘的我们去吃郴州最富有盛名的“鱼头粉”。说这是“十二分推荐”,到郴州必吃的美食之一。 哇塞!那个味美香甜…...
2024/5/4 23:54:56 - 氧生福地 玩美北湖(下)——奔跑吧骚年!
原标题:氧生福地 玩美北湖(下)——奔跑吧骚年!让我们红尘做伴 活得潇潇洒洒 策马奔腾共享人世繁华 对酒当歌唱出心中喜悦 轰轰烈烈把握青春年华 让我们红尘做伴 活得潇潇洒洒 策马奔腾共享人世繁华 对酒当歌唱出心中喜悦 轰轰烈烈把握青春年华 啊……啊……啊 两…...
2024/5/4 23:55:06 - 扒开伪装医用面膜,翻六倍价格宰客,小姐姐注意了!
原标题:扒开伪装医用面膜,翻六倍价格宰客,小姐姐注意了!扒开伪装医用面膜,翻六倍价格宰客!当行业里的某一品项火爆了,就会有很多商家蹭热度,装逼忽悠,最近火爆朋友圈的医用面膜,被沾上了污点,到底怎么回事呢? “比普通面膜安全、效果好!痘痘、痘印、敏感肌都能用…...
2024/5/5 8:13:33 - 「发现」铁皮石斛仙草之神奇功效用于医用面膜
原标题:「发现」铁皮石斛仙草之神奇功效用于医用面膜丽彦妆铁皮石斛医用面膜|石斛多糖无菌修护补水贴19大优势: 1、铁皮石斛:自唐宋以来,一直被列为皇室贡品,铁皮石斛生于海拔1600米的悬崖峭壁之上,繁殖力差,产量极低,所以古代仅供皇室、贵族享用 2、铁皮石斛自古民间…...
2024/5/4 23:55:16 - 丽彦妆\医用面膜\冷敷贴轻奢医学护肤引导者
原标题:丽彦妆\医用面膜\冷敷贴轻奢医学护肤引导者【公司简介】 广州华彬企业隶属香港华彬集团有限公司,专注美业21年,其旗下品牌: 「圣茵美」私密荷尔蒙抗衰,产后修复 「圣仪轩」私密荷尔蒙抗衰,产后修复 「花茵莳」私密荷尔蒙抗衰,产后修复 「丽彦妆」专注医学护…...
2024/5/4 23:54:58 - 广州械字号面膜生产厂家OEM/ODM4项须知!
原标题:广州械字号面膜生产厂家OEM/ODM4项须知!广州械字号面膜生产厂家OEM/ODM流程及注意事项解读: 械字号医用面膜,其实在我国并没有严格的定义,通常我们说的医美面膜指的应该是一种「医用敷料」,也就是说,医用面膜其实算作「医疗器械」的一种,又称「医用冷敷贴」。 …...
2024/5/6 21:42:42 - 械字号医用眼膜缓解用眼过度到底有无作用?
原标题:械字号医用眼膜缓解用眼过度到底有无作用?医用眼膜/械字号眼膜/医用冷敷眼贴 凝胶层为亲水高分子材料,含70%以上的水分。体表皮肤温度传导到本产品的凝胶层,热量被凝胶内水分子吸收,通过水分的蒸发带走大量的热量,可迅速地降低体表皮肤局部温度,减轻局部皮肤的灼…...
2024/5/4 23:54:56 - 配置失败还原请勿关闭计算机,电脑开机屏幕上面显示,配置失败还原更改 请勿关闭计算机 开不了机 这个问题怎么办...
解析如下:1、长按电脑电源键直至关机,然后再按一次电源健重启电脑,按F8健进入安全模式2、安全模式下进入Windows系统桌面后,按住“winR”打开运行窗口,输入“services.msc”打开服务设置3、在服务界面,选中…...
2022/11/19 21:17:18 - 错误使用 reshape要执行 RESHAPE,请勿更改元素数目。
%读入6幅图像(每一幅图像的大小是564*564) f1 imread(WashingtonDC_Band1_564.tif); subplot(3,2,1),imshow(f1); f2 imread(WashingtonDC_Band2_564.tif); subplot(3,2,2),imshow(f2); f3 imread(WashingtonDC_Band3_564.tif); subplot(3,2,3),imsho…...
2022/11/19 21:17:16 - 配置 已完成 请勿关闭计算机,win7系统关机提示“配置Windows Update已完成30%请勿关闭计算机...
win7系统关机提示“配置Windows Update已完成30%请勿关闭计算机”问题的解决方法在win7系统关机时如果有升级系统的或者其他需要会直接进入一个 等待界面,在等待界面中我们需要等待操作结束才能关机,虽然这比较麻烦,但是对系统进行配置和升级…...
2022/11/19 21:17:15 - 台式电脑显示配置100%请勿关闭计算机,“准备配置windows 请勿关闭计算机”的解决方法...
有不少用户在重装Win7系统或更新系统后会遇到“准备配置windows,请勿关闭计算机”的提示,要过很久才能进入系统,有的用户甚至几个小时也无法进入,下面就教大家这个问题的解决方法。第一种方法:我们首先在左下角的“开始…...
2022/11/19 21:17:14 - win7 正在配置 请勿关闭计算机,怎么办Win7开机显示正在配置Windows Update请勿关机...
置信有很多用户都跟小编一样遇到过这样的问题,电脑时发现开机屏幕显现“正在配置Windows Update,请勿关机”(如下图所示),而且还需求等大约5分钟才干进入系统。这是怎样回事呢?一切都是正常操作的,为什么开时机呈现“正…...
2022/11/19 21:17:13 - 准备配置windows 请勿关闭计算机 蓝屏,Win7开机总是出现提示“配置Windows请勿关机”...
Win7系统开机启动时总是出现“配置Windows请勿关机”的提示,没过几秒后电脑自动重启,每次开机都这样无法进入系统,此时碰到这种现象的用户就可以使用以下5种方法解决问题。方法一:开机按下F8,在出现的Windows高级启动选…...
2022/11/19 21:17:12 - 准备windows请勿关闭计算机要多久,windows10系统提示正在准备windows请勿关闭计算机怎么办...
有不少windows10系统用户反映说碰到这样一个情况,就是电脑提示正在准备windows请勿关闭计算机,碰到这样的问题该怎么解决呢,现在小编就给大家分享一下windows10系统提示正在准备windows请勿关闭计算机的具体第一种方法:1、2、依次…...
2022/11/19 21:17:11 - 配置 已完成 请勿关闭计算机,win7系统关机提示“配置Windows Update已完成30%请勿关闭计算机”的解决方法...
今天和大家分享一下win7系统重装了Win7旗舰版系统后,每次关机的时候桌面上都会显示一个“配置Windows Update的界面,提示请勿关闭计算机”,每次停留好几分钟才能正常关机,导致什么情况引起的呢?出现配置Windows Update…...
2022/11/19 21:17:10 - 电脑桌面一直是清理请关闭计算机,windows7一直卡在清理 请勿关闭计算机-win7清理请勿关机,win7配置更新35%不动...
只能是等着,别无他法。说是卡着如果你看硬盘灯应该在读写。如果从 Win 10 无法正常回滚,只能是考虑备份数据后重装系统了。解决来方案一:管理员运行cmd:net stop WuAuServcd %windir%ren SoftwareDistribution SDoldnet start WuA…...
2022/11/19 21:17:09 - 计算机配置更新不起,电脑提示“配置Windows Update请勿关闭计算机”怎么办?
原标题:电脑提示“配置Windows Update请勿关闭计算机”怎么办?win7系统中在开机与关闭的时候总是显示“配置windows update请勿关闭计算机”相信有不少朋友都曾遇到过一次两次还能忍但经常遇到就叫人感到心烦了遇到这种问题怎么办呢?一般的方…...
2022/11/19 21:17:08 - 计算机正在配置无法关机,关机提示 windows7 正在配置windows 请勿关闭计算机 ,然后等了一晚上也没有关掉。现在电脑无法正常关机...
关机提示 windows7 正在配置windows 请勿关闭计算机 ,然后等了一晚上也没有关掉。现在电脑无法正常关机以下文字资料是由(历史新知网www.lishixinzhi.com)小编为大家搜集整理后发布的内容,让我们赶快一起来看一下吧!关机提示 windows7 正在配…...
2022/11/19 21:17:05 - 钉钉提示请勿通过开发者调试模式_钉钉请勿通过开发者调试模式是真的吗好不好用...
钉钉请勿通过开发者调试模式是真的吗好不好用 更新时间:2020-04-20 22:24:19 浏览次数:729次 区域: 南阳 > 卧龙 列举网提醒您:为保障您的权益,请不要提前支付任何费用! 虚拟位置外设器!!轨迹模拟&虚拟位置外设神器 专业用于:钉钉,外勤365,红圈通,企业微信和…...
2022/11/19 21:17:05 - 配置失败还原请勿关闭计算机怎么办,win7系统出现“配置windows update失败 还原更改 请勿关闭计算机”,长时间没反应,无法进入系统的解决方案...
前几天班里有位学生电脑(windows 7系统)出问题了,具体表现是开机时一直停留在“配置windows update失败 还原更改 请勿关闭计算机”这个界面,长时间没反应,无法进入系统。这个问题原来帮其他同学也解决过,网上搜了不少资料&#x…...
2022/11/19 21:17:04 - 一个电脑无法关闭计算机你应该怎么办,电脑显示“清理请勿关闭计算机”怎么办?...
本文为你提供了3个有效解决电脑显示“清理请勿关闭计算机”问题的方法,并在最后教给你1种保护系统安全的好方法,一起来看看!电脑出现“清理请勿关闭计算机”在Windows 7(SP1)和Windows Server 2008 R2 SP1中,添加了1个新功能在“磁…...
2022/11/19 21:17:03 - 请勿关闭计算机还原更改要多久,电脑显示:配置windows更新失败,正在还原更改,请勿关闭计算机怎么办...
许多用户在长期不使用电脑的时候,开启电脑发现电脑显示:配置windows更新失败,正在还原更改,请勿关闭计算机。。.这要怎么办呢?下面小编就带着大家一起看看吧!如果能够正常进入系统,建议您暂时移…...
2022/11/19 21:17:02 - 还原更改请勿关闭计算机 要多久,配置windows update失败 还原更改 请勿关闭计算机,电脑开机后一直显示以...
配置windows update失败 还原更改 请勿关闭计算机,电脑开机后一直显示以以下文字资料是由(历史新知网www.lishixinzhi.com)小编为大家搜集整理后发布的内容,让我们赶快一起来看一下吧!配置windows update失败 还原更改 请勿关闭计算机&#x…...
2022/11/19 21:17:01 - 电脑配置中请勿关闭计算机怎么办,准备配置windows请勿关闭计算机一直显示怎么办【图解】...
不知道大家有没有遇到过这样的一个问题,就是我们的win7系统在关机的时候,总是喜欢显示“准备配置windows,请勿关机”这样的一个页面,没有什么大碍,但是如果一直等着的话就要两个小时甚至更久都关不了机,非常…...
2022/11/19 21:17:00 - 正在准备配置请勿关闭计算机,正在准备配置windows请勿关闭计算机时间长了解决教程...
当电脑出现正在准备配置windows请勿关闭计算机时,一般是您正对windows进行升级,但是这个要是长时间没有反应,我们不能再傻等下去了。可能是电脑出了别的问题了,来看看教程的说法。正在准备配置windows请勿关闭计算机时间长了方法一…...
2022/11/19 21:16:59 - 配置失败还原请勿关闭计算机,配置Windows Update失败,还原更改请勿关闭计算机...
我们使用电脑的过程中有时会遇到这种情况,当我们打开电脑之后,发现一直停留在一个界面:“配置Windows Update失败,还原更改请勿关闭计算机”,等了许久还是无法进入系统。如果我们遇到此类问题应该如何解决呢࿰…...
2022/11/19 21:16:58 - 如何在iPhone上关闭“请勿打扰”
Apple’s “Do Not Disturb While Driving” is a potentially lifesaving iPhone feature, but it doesn’t always turn on automatically at the appropriate time. For example, you might be a passenger in a moving car, but your iPhone may think you’re the one dri…...
2022/11/19 21:16:57