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

数据结构与算法之递归: LeetCode 37. 解数独 (Ts版)

解数独

  • https://leetcode.cn/problems/sudoku-solver/description/

描述

  • 编写一个程序,通过填充空格来解决数独问题
  • 数独的解法需 遵循如下规则:
    • 数字 1-9 在每一行只能出现一次
    • 数字 1-9 在每一列只能出现一次
    • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
  • 数独部分空格内已填入了数字,空白格用 ‘.’ 表示

示例 1

输入: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] 是一位数字或者 ‘.’
  • 题目数据 保证 输入数独仅有一个解

Typescript 版算法实现


1 ) 方案1: 回溯

/**Do not return anything, modify board in-place instead.*/
function solveSudoku(board: string[][]): void {const line: boolean[][] = Array.from({ length: 9 }, () => Array(9).fill(false));const column: boolean[][] = Array.from({ length: 9 }, () => Array(9).fill(false));const block: boolean[][][] = Array.from({ length: 3 }, () => Array.from({ length: 3 }, () => Array(9).fill(false)));const spaces: number[][] = [];// 初始化状态for (let i = 0; i < 9; i++) {for (let j = 0; j < 9; j++) {if (board[i][j] === '.') {spaces.push([i, j]);} else {const digit = parseInt(board[i][j]) - 1;line[i][digit] = true;column[j][digit] = true;block[Math.floor(i / 3)][Math.floor(j / 3)][digit] = true;}}}// 深度优先搜索函数function dfs(pos: number): boolean {if (pos === spaces.length) {return true;}const [i, j] = spaces[pos];for (let digit = 0; digit < 9; digit++) {if (!line[i][digit] && !column[j][digit] && !block[Math.floor(i / 3)][Math.floor(j / 3)][digit]) {line[i][digit] = true;column[j][digit] = true;block[Math.floor(i / 3)][Math.floor(j / 3)][digit] = true;board[i][j] = (digit + 1).toString();if (dfs(pos + 1)) {return true;}// 回溯line[i][digit] = false;column[j][digit] = false;block[Math.floor(i / 3)][Math.floor(j / 3)][digit] = false;board[i][j] = '.';}}return false;}dfs(0);
}

2 ) 方案2: 位运算优化

/**Do not return anything, modify board in-place instead.*/
function solveSudoku(board: string[][]): void {const line: number[] = Array(9).fill(0);const column: number[] = Array(9).fill(0);const block: number[][] = Array.from({ length: 3 }, () => Array(3).fill(0));const spaces: number[][] = [];// 翻转函数,用于设置或清除位function flip(i: number, j: number, digit: number) {const mask = 1 << digit;line[i] ^= mask;column[j] ^= mask;block[Math.floor(i / 3)][Math.floor(j / 3)] ^= mask;}// 初始化状态for (let i = 0; i < 9; i++) {for (let j = 0; j < 9; j++) {if (board[i][j] === '.') {spaces.push([i, j]);} else {const digit = parseInt(board[i][j]) - 1;flip(i, j, digit);}}}// 深度优先搜索函数function dfs(pos: number): boolean {if (pos === spaces.length) {return true;}const [i, j] = spaces[pos];let mask = 0x1ff & ~(line[i] | column[j] | block[Math.floor(i / 3)][Math.floor(j / 3)]);while (mask > 0) {const digit = Math.log2(mask & -mask); // 找到最右侧的 1 的位置flip(i, j, digit);board[i][j] = (digit + 1).toString();if (dfs(pos + 1)) {return true;}flip(i, j, digit);mask &= mask - 1; // 将最右侧的 1 置为 0}return false;}dfs(0);
}

3 ) 方案3: 枚举优化

/**Do not return anything, modify board in-place instead.*/
function solveSudoku(board: string[][]): void {const line: number[] = Array(9).fill(0);const column: number[] = Array(9).fill(0);const block: number[][] = Array.from({ length: 3 }, () => Array(3).fill(0));const spaces: number[][] = [];// 翻转函数,用于设置或清除位function flip(i: number, j: number, digit: number) {const mask = 1 << digit;line[i] ^= mask;column[j] ^= mask;block[Math.floor(i / 3)][Math.floor(j / 3)] ^= mask;}// 初始化已知数字的状态for (let i = 0; i < 9; i++) {for (let j = 0; j < 9; j++) {if (board[i][j] !== '.') {const digit = parseInt(board[i][j]) - 1;flip(i, j, digit);}}}// 尝试通过唯一解填充空格let modified: boolean;do {modified = false;for (let i = 0; i < 9; i++) {for (let j = 0; j < 9; j++) {if (board[i][j] !== '.') {continue;}let mask = 0x1ff & ~(line[i] | column[j] | block[Math.floor(i / 3)][Math.floor(j / 3)]);if ((mask & (mask - 1)) === 0 && mask !== 0) { // mask 的二进制表示仅有一个 1const digit = Math.log2(mask); // 找到最右侧的 1 的位置flip(i, j, digit);board[i][j] = (digit + 1).toString();modified = true;}}}} while (modified);// 记录剩余未填充的空格for (let i = 0; i < 9; i++) {for (let j = 0; j < 9; j++) {if (board[i][j] === '.') {spaces.push([i, j]);}}}// 深度优先搜索函数function dfs(pos: number): boolean {if (pos === spaces.length) {return true;}const [i, j] = spaces[pos];let mask = 0x1ff & ~(line[i] | column[j] | block[Math.floor(i / 3)][Math.floor(j / 3)]);while (mask > 0) {const digit = Math.log2(mask & -mask); // 找到最右侧的 1 的位置flip(i, j, digit);board[i][j] = (digit + 1).toString();if (dfs(pos + 1)) {return true;}flip(i, j, digit);mask &= mask - 1; // 将最右侧的 1 置为 0}return false;}dfs(0);
}

相关文章:

数据结构与算法之递归: LeetCode 37. 解数独 (Ts版)

解数独 https://leetcode.cn/problems/sudoku-solver/description/ 描述 编写一个程序&#xff0c;通过填充空格来解决数独问题数独的解法需 遵循如下规则&#xff1a; 数字 1-9 在每一行只能出现一次数字 1-9 在每一列只能出现一次数字 1-9 在每一个以粗实线分隔的 3x3 宫内…...

【氮化镓】香港科技大学陈Kevin-单片集成GaN比较器

一、引言(Introduction) GaN HEMT的重要性 文章开篇便强调了氮化镓(GaN)高电子迁移率晶体管(HEMT)在下一代功率转换系统中的巨大潜力。GaN HEMT具备高开关频率、低导通电阻、高击穿电压以及宽工作温度范围等优势,使其成为功率电子领域的热门研究对象。这些特性使得GaN…...

axios的使用总结

一、Axios 简介 Axios 是一个基于 Promise 的 HTTP 客户端&#xff0c;用于浏览器和 Node.js。在 Vue 项目中&#xff0c;它主要用于发送 HTTP 请求来获取数据&#xff08;如从 API 获取数据&#xff09;或者提交数据&#xff08;如用户登录、注册等表单数据&#xff09;。 二…...

革新未来:高效智能数字人技术引领多元化应用

随着科技的不断进步&#xff0c;数字人技术已逐渐成为企业数字化转型中的重要工具。数字人不仅能够优化客户体验&#xff0c;还可以显著提升企业运营效率。本文将详细介绍一种高性能、高质量、低延迟、快速响应以及安全稳定的数字人技术方案&#xff0c;帮助企业在多元化场景中…...

使用批处理文件清除系统垃圾

第一步&#xff1a;打开记事本&#xff0c;里面的命令如下 echo off echo 正在清理临时文件&#xff0c;请稍候...:: 清理系统临时文件 echo 清理系统临时文件... del /q /f /s "%TEMP%\*.*" del /q /f /s "%WINDIR%\Temp\*.*" rd /s /q "%WINDIR%\T…...

总结5..

#include<stdio.h> struct nb {//结构体列队 int x, y;//x为横坐标&#xff0c;y为纵坐标 int s, f;//s为步数&#xff0c;//f为方向 }link[850100]; int n, m, x, y, p, q, f; int hard 1, tail 1; int a[52][52], b[52][52], book[52][52][91]; int main() { …...

Java 在包管理与模块化中的优势:与其他开发语言的比较

在开发复杂的、规模庞大的软件系统时&#xff0c;包管理和模块化设计起着至关重要的作用。它们不仅决定了代码的组织和可维护性&#xff0c;还直接影响到团队协作效率、扩展性和性能。在众多编程语言中&#xff0c;Java 凭借其成熟的生态系统、强类型系统和标准化的包管理机制&…...

LLMs(大型语言模型)的多智能体:Auto-GPT

LLMs(大型语言模型)的多智能体:Auto-GPT 是指在一个系统中集成多个具有不同能力、角色和任务的智能体,这些智能体能够相互协作、沟通和交互,以共同完成复杂的任务或解决复杂的问题。每个智能体都可以被视为一个独立的实体,具有自己的策略、目标和知识库,通过相互之间的…...

CPU狂飙900%如何分析?怎么定位?怎么溯源处理

当你的服务器CPU飙升到900%&#xff0c;系统卡顿、响应迟缓、业务受阻&#xff0c;这种令人焦虑的场景是否让你束手无策&#xff1f;别慌&#xff0c;这并不是世界末日&#xff0c;只要掌握正确的分析与定位方法&#xff0c;就能快速找到问题根源&#xff0c;并有效解决。 CPU…...

Excel 技巧17 - 如何计算倒计时,并添加该倒计时的数据条(★)

本文讲如何计算倒计时&#xff0c;并添加该倒计时的数据条。 1&#xff0c;如何计算倒计时 这里也要用公式 D3 - TODAY() 显示为下面这个样子的 然后右键该单元格&#xff0c;选 设置单元格格式 然后点 常规 这样就能显示出还书倒计时的日数了。 下拉适用到其他单元格。 2&a…...

Java中的阻塞队列--以LinkedBlockingQueue为例

顾名思义&#xff0c;就是一种在对队列进行出队或者入队操作的时候会阻塞的队列。下面使用JDK17中的LinkedBlockingQuece进行简单的介绍。 LinkedBlockingQueue基本结构 LinkedBlockingQueue的主要结构以及构成的数据结构如下图所示。具体来说包括 存储元素的链表&#xff0…...

16.5万煤气柜柜位计故障分析

一、事故经过&#xff1a; 2015年8月1&#xff14;日20点45分&#xff0c;16.5万立煤气柜柜顶油封溢流口有大量油液溢出&#xff0c;此时雷达柜位计在计算机上示值为63.79米&#xff0c;由于接近傍晚天色较暗&#xff0c;岗位操作员并未及时发现这一异常状况。22点45分左右&…...

高效沟通驱动LabVIEW项目成功

在LabVIEW项目开发中&#xff0c;由于涉及软件、硬件及多方协作&#xff0c;项目沟通效率的高低直接影响开发进度与最终质量。不明确的需求、信息传递中的误解以及跨部门协作的阻碍&#xff0c;常导致项目延误甚至失败。因此&#xff0c;建立高效的沟通机制&#xff0c;确保信息…...

大模型之三十三- 开源Melo 语音合成

大模型之三十三- 开源Melo 语音合成 文本到语音(TTS)系统从基于基础音素的模型演变成复杂的端到端神经方法,这种方法可以直接将文本转换为语音。这一变革得益于深度学习的进步和计算能力的提升,已经在语音的自然度、韵律控制和跨语言能力方面取得了重大进展 。现代TTS系统…...

论文复现:四轮转向车辆后轮转角控制方法研究

写在前面&#xff0c;主要参考以下这篇文章&#xff0c;并复现了其中几种后轮转角控制方法。 一、什么是四轮转向 顾名思义&#xff0c;四轮转向指的是四个轮子都能转向&#xff0c;都能转动。当驾驶员操作方向盘进行前轮转向时&#xff0c;后轮按照特定算法给出的转角跟着转动…...

【UFEN】基于多层特征融合和多任务学习的多模态情感分析

abstract 当前多模态情感分析面临的主要挑战包括&#xff1a;1、模型如何在单一模态中提取情感信息&#xff0c;并实现多模态信息的互补传输&#xff1b;2、在单一模态中体现的情绪与多模态标签不一致的情况下&#xff0c;如何输出相对稳定的预测&#xff1b;3、当单模态信息不…...

uniapp的插件开发发布指南

Hbuilder创建项目 项目根目录创建uni_modules 开发组件 发布到插件市场 填写发布说明&#xff08;未登录需要登录&#xff09; 点击提交 在终端可以看到 发布成功&#xff01; 插件市场查看...

【Linux系统】—— 编译器 gcc/g++ 的使用

【Linux系统】—— 编译器 gcc/g 的使用 1 用 gcc 直接编译2 翻译环境2.1 预处理&#xff08;进行宏替换&#xff09;2.2 编译&#xff08;生成汇编&#xff09;2.3 汇编&#xff08;生成机器可识别代码&#xff09;2.4 链接2.5 记忆小技巧2.6 编译方式2.7 几个问题2.7.1 如何理…...

[微服务]注册中心优化

环境隔离 企业实际开发中&#xff0c;往往会搭建多个运行环境&#xff0c;例如&#xff1a; 开发环境测试环境预发布环境生产环境 这些不同环境之间的服务和数据之间需要隔离。 还有的企业中&#xff0c;会开发多个项目&#xff0c;共享nacos集群。此时&#xff0c;这些项目…...

C++ ——— 模拟实现 vector 类

目录 vector 类的框架 无参数的构造函数 析构函数 获取有效数据个数 获取容量 重载 [] 运算符 可读可写版本 只可读版本 扩容 尾插 实现迭代器 可读可写版本 只可读版本 自定义设置size长度和内容 在任意位置插入 删除任意位置的数据 赋值重载 vector 类的框…...

Jetson Orin Nano 升级jetpack5.1.2刷机过程记录

一.刷机起因 orin nano 接了个IMX477的摄像头,用 命令行DISPLAY:0.0 nvgstcapture-1.0 显示的画面有撕裂,让卖家查问题,卖家测试没有撕裂,对比环境,orin nano出厂默认的是jetpack5.1.1,卖家用的jetpack5.1.2版本,为了解决差异,要升级jetpack版本,前后搞了2天半,记录一下. 另外…...

如何删除论文脚注横线的方法——视图-草稿-引用——显示备注——删除脚注分隔符-即可。

如何删除论文脚注横线的方法——视图-草稿-引用——显示备注——删除脚注分隔符-即可。 Word中脚注线不会删&#xff1f;这里有妙招&#xff01;,教育,职业教育,好看视频...

Taotoken的TokenPlan套餐如何实现更经济的模型调用

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 Taotoken的TokenPlan套餐如何实现更经济的模型调用 1. 理解TokenPlan的计费模式 在模型应用开发过程中&#xff0c;成本的可预测性…...

HFSS仿真结果怎么看?以T型波导为例,读懂S参数与电场动态图

HFSS仿真结果深度解析&#xff1a;从S参数到电场动态图的实战指南当你第一次在HFSS中完成T型波导仿真后&#xff0c;面对满屏的曲线和彩色云图&#xff0c;是否感到既兴奋又困惑&#xff1f;那些起伏的S参数曲线究竟告诉你什么信息&#xff1f;电场图中跳跃的颜色又代表怎样的物…...

告别道路预测老套路:用ParkPredict+模型思路,解决停车场里的‘鬼探头’难题

破解泊车场景预测困局&#xff1a;ParkPredict模型的技术革新与实践停车场里的每一次转向、倒车和避让&#xff0c;都是对自动驾驶系统预测能力的极限挑战。与开放道路的规则明确不同&#xff0c;这里没有清晰的车道线指引&#xff0c;没有统一的行驶方向&#xff0c;只有随时可…...

我靠这个测试设计方法,把漏测率降低了80%

当“直觉测试”撞上南墙很长一段时间里&#xff0c;我和许多测试同行一样&#xff0c;测试用例的设计主要依靠两样东西&#xff1a;需求文档和“测试直觉”。这种模式在业务逻辑相对简单、迭代速度平缓时还能勉强应付。一旦面对复杂的企业级应用、高频的敏捷迭代&#xff0c;或…...

上线前最后一道防线,DeepSeek代码审查如何帮你拦截87%的CVE类缺陷?

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;上线前最后一道防线&#xff0c;DeepSeek代码审查如何帮你拦截87%的CVE类缺陷&#xff1f; 在软件交付生命周期末期&#xff0c;传统人工代码审计与通用SAST工具常因误报率高、上下文理解弱而漏检高危漏…...

pan-baidu-download:百度网盘多线程下载加速器架构解析与性能优化指南

pan-baidu-download&#xff1a;百度网盘多线程下载加速器架构解析与性能优化指南 【免费下载链接】pan-baidu-download 百度网盘下载脚本 项目地址: https://gitcode.com/gh_mirrors/pa/pan-baidu-download pan-baidu-download是一款基于Python开发的百度网盘命令行下载…...

危急时刻的六条基本安全提示

人机协作&#xff0c;AI模型&#xff1a;Deepseek 仅供参考 危急时刻的六条基本安全提示 以下内容仅为通用性安全建议&#xff0c;供在紧急情况下保持冷静、保护自身安全时参考。所有建议均基于常理和公共安全常识&#xff0c;不包含任何具体操作细节或可能被不当使用的信息…...

模拟电路实现自主循线机器人:无MCU的硬件逻辑设计

1. 项目概述&#xff1a;用最纯粹的模拟电路&#xff0c;造一台会“思考”的机器人每次看到那些在赛道上灵巧穿梭的循线小车&#xff0c;你是不是也手痒&#xff0c;想自己动手做一个&#xff1f;但一听到“单片机”、“编程”、“Arduino”这些词&#xff0c;又觉得门槛太高&a…...