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

百度收录软件武汉seo和网络推广

百度收录软件,武汉seo和网络推广,旅游外贸网站建设推广,加强政府门户网站建设重要性题目 力扣题目链接 思路 卡哥的思路,注意看他解释为什么是“二维回溯”。我的思路,类似y总解决 N 皇后问题时的第二种方法,即从左上到右下枚举棋盘的每个位置。 至于为什么与 N 皇后问题不一样,我认为是因为它每一行不止放一个…

题目

力扣题目链接

思路

  1. 卡哥的思路,注意看他解释为什么是“二维回溯”。
  2. 我的思路,类似y总解决 N 皇后问题时的第二种方法,即从左上到右下枚举棋盘的每个位置。
    至于为什么与 N 皇后问题不一样,我认为是因为它每一行不止放一个,每一行的每个位置都要进行考虑。

代码

  1. 卡哥代码见上方思路。
  2. 我的代码:
class Solution {
private:bool isValid(int row, int col, char val, vector<vector<char>>& board) {// 判断该行是否有重复for (int i = 0; i < 9; i++) {if (board[row][i] == 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;}// 有返回值是因为只需要找到一种可行的方案,好好理解一下bool backtracking(int x, int y, vector<vector<char>>& board) {// 遍历到一行的末尾了,就开始遍历下一行if (y == 9) {y = 0;x++;}// x == 9说明 0~8 这9行都遍历完了if (x == 9) {return true;}// 如果该位置还没填数的if (board[x][y] == '.') {// 遍历9种可能for (char i = '1'; i <= '9'; i++) {if (isValid(x, y, i, board)) {board[x][y] = i;if (backtracking(x, y + 1, board)) {return true;}board[x][y] = '.';}}// 9种都不行,就返回falsereturn false;}else {return backtracking(x, y + 1, board);}}public:void solveSudoku(vector<vector<char>>& board) {backtracking(0, 0, board);}
};

对于回溯函数为什么需要返回值的解释

ChatGPT:

你原来的代码(返回值为void)在找到一个解之后,会继续尝试其他可能的填充选项,并继续回溯,这样会导致找到的解可能会被覆盖,从而使最终输出的可能不是第一个找到的解,甚至可能无法正确地保留一个有效解。

详细分析

  1. 回溯的本质

    • 你的回溯算法会从左上角开始遍历整个数独网格。如果在某个位置找到了一个有效的填充数字,算法会继续前进,直到填满整个网格,或者无法找到合适的数字为止。
    • 如果算法到达了一个无法继续的状态(即当前路径不再可行),它会回退到上一个状态并尝试其他可能的数字。
  2. 没有提前终止

    • 你的代码中没有检测到第一个有效解后提前终止的机制。
    • 当回溯算法在最后一格填上数字时,虽然它找到了一个有效解,但是它不会立即返回,而是继续尝试回溯,试图寻找其他可能的解。
    • 由于继续回溯,它可能会更改已经填好的数字,尝试其他路径,结果导致解被覆盖,或者递归无限循环而导致栈溢出(如你之前遇到的无限递归问题)。
  3. 覆盖问题

    • 在回溯过程中,每当你在一个位置填入一个数字后,都会立即调用递归函数进入下一步。
    • 如果在某个位置找到的第一个有效数字满足所有条件,继续前进,最后递归完成一整次操作后,如果继续回溯,这个数字可能会被回溯掉,并试图用下一个数字替换。
    • 因为没有及时终止,算法会尝试其他可能的数字组合,可能覆盖掉第一个找到的有效解。

解决方法

为了避免上述问题,关键在于:找到第一个有效解后立即终止进一步的回溯和搜索。这可以通过让递归函数在找到一个有效解时返回true来实现,以阻止后续的任何修改。

http://www.tj-hxxt.cn/news/83807.html

相关文章:

  • 轻淘客 轻网站怎么做深圳谷歌seo推广
  • 易语言 做的网站谷歌google play官网
  • 做网站用新域名还是老域名免费b站动漫推广网站2023
  • 网站教学地推网app推广平台
  • 网站建设自seo网络营销技巧
  • 2018年企业网站优化如何做创建自己的网站怎么弄
  • wordpress火车头添加媒体seo推广任务小结
  • 怎样上网站建设接广告的平台
  • 江安县建设招标网站培训班有哪些课程
  • 网站备案身份核验金戈西地那非片
  • 自己做的网站抬头在哪里改看广告赚钱一天50元
  • 一级a做爰片免费网站偷拍厕所免费好用的网站
  • 成都互联网营销师培训windows优化
  • 交城有做网站的吗品牌seo推广
  • 做开箱的网站南宁百度seo软件
  • 西安网站建设哪家好品牌网络营销策划方案
  • 福州网站建设加q479185700seo优化专员编辑
  • 申请做网站编辑组长的工作设想腾讯域名
  • 西安企业网站设计哪家专业淘宝运营培训课程
  • 上海网站群建设seo是干什么的
  • 视频网站做cpa电商seo是什么意思啊
  • 哪里有给网站做优化师培训机构
  • 永兴网站制作公司的seo是什么意思
  • 四川学校网站建设google安卓版下载
  • 什么网站做专利检索报告推广软文模板
  • asp做的网站怎么发布推广软文是什么意思
  • 网站开发技术服务费合同范本最近军事新闻热点大事件
  • 容桂新网站建设制作网页多少钱
  • 建设网站考证做微商怎么找客源加人
  • 免费个人简历表格空白word内蒙古seo优化