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

中企动力网站建设百度seo排名优化联系方式

中企动力网站建设,百度seo排名优化联系方式,徐州网站建设方案,个人做外贸网站平台本文目录 1 中文题目2 求解方法:递归回溯法2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目 编写一个程序,通过填充空格来解决数独问题。数独的解法需 遵循如下规则: 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只…

本文目录

  • 1 中文题目
  • 2 求解方法:递归+回溯法
    • 2.1 方法思路
    • 2.2 Python代码
    • 2.3 复杂度分析
  • 3 题目总结

1 中文题目

编写一个程序,通过填充空格来解决数独问题。数独的解法需 遵循如下规则:

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
  • 数独部分空格内已填入了数字,空白格用 ‘.’ 表示。

示例:
在这里插入图片描述

输入:board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出:[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释:输入的数独如上图所示,唯一有效的解决方案如下所示:

在这里插入图片描述

提示:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 ‘.
  • 题目数据 保证 输入数独仅有一个解

2 求解方法:递归+回溯法

2.1 方法思路

方法核心

使用回溯算法解决数独问题,使用三个二维数组记录数字使用情况,采用逐个位置填写的策略,通过位置编号简化行列索引计算。

实现步骤

(1)初始化阶段:

  • 创建三个二维数组记录每行、每列和每个3x3方块中数字的使用情况
  • 遍历数独板,标记已有数字的使用情况
  • 将问题转化为填写空位的问题

(2)回溯过程:

  • 使用位置编号(0-80)表示当前填写位置
  • 通过整除和取余计算行列索引
  • 如果当前位置已有数字,继续下一个位置。否则尝试填入1-9的数字

(3)验证过程:

  • 检查当前数字是否可以在行中使用,检查当前数字是否可以在列中使用,检查当前数字是否可以在3x3方块中使用
  • 所有检查都通过才能填入数字

方法示例

输入数独板示例:
[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]
]执行过程示例(以填写第一个空位为例):1. 定位第一个空位:- 位置 (0,2)- box_index = (0 // 3) * 3 + 2 // 3 = 02. 尝试填入数字:- 检查数字1:已在同行//方块使用- 检查数字2:已在同行//方块使用- 检查数字4:可以使用- 填入数字4并继续递归3. 如果后续填写失败:- 回溯到当前位置- 清除数字4- 尝试下一个可能的数字4. 递归和回溯过程继续,直到找到完整解答

2.2 Python代码

class Solution:def solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""# 初始化三个二维数组,分别记录行、列和3x3方块中数字的使用情况rows = [[False] * 9 for _ in range(9)]cols = [[False] * 9 for _ in range(9)]boxes = [[False] * 9 for _ in range(9)]# 遍历整个数独板,记录已有数字的使用情况for i in range(9):for j in range(9):if board[i][j] != '.':num = int(board[i][j]) - 1  # 转换为0-8的索引box_index = (i // 3) * 3 + j // 3rows[i][num] = Truecols[j][num] = Trueboxes[box_index][num] = Truedef backtrack(pos: int) -> bool:# 如果已经填完所有位置,返回Trueif pos == 81:return True# 计算当前位置的行列索引row, col = pos // 9, pos % 9# 如果当前位置已有数字,尝试填写下一个位置if board[row][col] != '.':return backtrack(pos + 1)# 计算当前位置所在的3x3方块索引box_index = (row // 3) * 3 + col // 3# 尝试填入1-9的数字for num in range(9):# 检查当前数字是否可以填入if not (rows[row][num] or cols[col][num] or boxes[box_index][num]):# 标记数字使用情况rows[row][num] = cols[col][num] = boxes[box_index][num] = Trueboard[row][col] = str(num + 1)# 递归尝试填写下一个位置if backtrack(pos + 1):return True# 回溯:恢复标记和数独板rows[row][num] = cols[col][num] = boxes[box_index][num] = Falseboard[row][col] = '.'# 当前位置无法填入任何数字return False# 从第一个位置开始解数独backtrack(0)

2.3 复杂度分析

  • 时间复杂度:O(9^m),m是空格的数量
    • 每个空格最多尝试9个数字
    • 实际运行时间因剪枝而大大减少
  • 空间复杂度:O(m),m是空格的数量(递归栈深度)
    • 三个固定大小的二维数组(81个布尔值)

3 题目总结

题目难度:困难
数据结构:矩阵
应用算法:回溯、递归

http://www.ritt.cn/news/19489.html

相关文章:

  • 做网站失败seo站长博客
  • 在线收录广州网站优化工具
  • 一个公司怎么做网站都放些什么seo网站推广培训
  • 爆推联盟官网企业网站seo多少钱
  • 做色情网站会怎么样百度推广关键词质量度
  • 深圳公司注册办理流程一键优化是什么意思
  • 上海外贸网站优化百度站内搜索
  • 做电商网站用什么软件seo关键词优化推广价格
  • 一个微信可以做两个网站支付semester是什么意思
  • 深圳seo优化服务商成都排名seo公司
  • dw模板制作网站的缺点济南网站seo公司
  • 浙江建设特种证书查询宁波seo排名外包
  • 做网站后付款北京seo排名服务
  • 网页平面设计作品seo综合查询工具
  • 重庆百科网站推广google adwords
  • 百度推广网站怎么做百度统计代码安装位置
  • 国外的b2b网站或者b2c网站seo是什么意思知乎
  • 通付盾 建设网站公司网络营销活动方案
  • 淄博网站建设制作seo经验是什么
  • 网站建设与维护期末试卷最新国际军事动态
  • 开发者选项开启好还是关闭好优化设计单元测试卷
  • 男女做吃动态网站关键词怎样做优化排名
  • 道滘做网站web设计一个简单网页
  • 音乐网站如何建立排名推广网站
  • 郸城网站建设拉新推广怎么做代理
  • 织梦做网站详细教程百度在线客服系统
  • 太原做网站页面的站长之家素材网
  • 潍坊做网站潍坊做网站b2b免费外链发布
  • 无法打开服务器上的网站茂名网络推广
  • shopex网站 css乱了广告网址