【leetcode】深搜、暴搜、回溯、剪枝(C++)3
深搜、暴搜、回溯、剪枝(C++)3
- 一、解数独
- 1、题目描述
- 2、代码
- 3、解析
- 二、单词搜索
- 1、题目描述
- 2、代码
- 3、解析
- 三、黄金矿工
- 1、题目描述
- 2、代码
- 3、解析
- 四、不同路径III
- 1、题目描述
- 2、代码
- 3、解析
一、解数独
1、题目描述
leetcode链接

2、代码
class Solution
{
public:// 全局变量bool row[9][10]; // 行bool col[9][10]; // 列bool grid[3][3][10]; // 小格子void solveSudoku(vector<vector<char>>& board) {// 初始化for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] != '.') // 是数就填进去{int num = board[i][j] - '0'; // 记录一下数row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true; // 记录被用过了}}}dfs(board);}bool dfs(vector<vector<char>>& board){for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){// 填数if(board[i][j] == '.'){for(int num = 1; num <= 9; num++) // 从1-9一个个遍历填数{if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]){board[i][j] = num + '0'; // 填入进去row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true; // 标记用过了if(dfs(board) == true) return true; // 表示可以填进去// 恢复现场board[i][j] = '.';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false; // 标记没用}}return false; // 1-9都不行}}}return true; // 走完了,填完了,返回true}
};
3、解析

二、单词搜索
1、题目描述
leetcode链接

2、代码
class Solution
{
public:// 全局变量bool visit[7][7];int m, n;bool exist(vector<vector<char>>& board, string word) {m = board.size(); // 总共有多少行n = board[0].size(); // 一行有多少个for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){// 匹配if(word[0] == board[i][j]){visit[i][j] = true; // 标记该点已经被访问过了if(dfs(board, i, j, word, 1/*从第一个位置往下走*/)) return true; // 递归到下一层visit[i][j] = false; // 第一个点位置错误,找下一个第一个对应的点}}}return false; // 没有访问到}// 定义一个上下左右移动的向量int dx[4] = {0, 0, -1, 1}; // x x x-1 x+1int dy[4] = {1, -1, 0, 0}; // y+1 y-1 y ybool dfs(vector<vector<char>>& board, int i, int j, string word, int pos){// 递归出口if(pos == word.size()){return true;}for(int k = 0; k < 4; k++){int x = dx[k] + i; // x坐标int y = dy[k] + j; // y坐标// 不越界,当前visit数组未被访问过,当前字符和word相对应字符相同if(x >= 0 && x < m && y >=0 && y < n && visit[x][y] == false && word[pos] == board[x][y]){visit[x][y] = true; // 先定义到访问过if(dfs(board, x, y, word, pos + 1)) return true; // 递归下一层visit[x][y] = false; // 恢复现场}}return false;}
};
3、解析

三、黄金矿工
1、题目描述
leetcode链接

2、代码
class Solution
{
public:// 全局变量bool visit[16][16]; // 标记是否访问过int m, n; // m是行,n是列int sum; // 总和int path; // 每次走的路径int getMaximumGold(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] != 0) // 先找到第一个非零元素{visit[i][j] = true; // 标记一下访问过了path += grid[i][j]; // 路径加上dfs(grid, i, j, path); // 递归visit[i][j] = false; // 找下一个非零元素path -= grid[i][j];} }}return sum;}int dx[4] = {0, 0, 1, -1}; // 上下左右int dy[4] = {1, -1, 0, 0}; // 上下左右void dfs(vector<vector<int>>& grid, int i, int j, int path){// 递归出口sum = max(sum, path); // 这里直接用算法max找最大值for(int k = 0; k < 4; k++){int x = dx[k] + i; // 向量xint y = dy[k] + j; // 向量yif(x >= 0 && x < m && y >= 0 && y < n && visit[x][y] == false && grid[x][y] != 0){visit[x][y] = true;path = path + grid[x][y]; // 路径加上dfs(grid, x, y, path);visit[x][y] = false; // 恢复现场path = path - grid[x][y];}}}
};
3、解析

四、不同路径III
1、题目描述
leetcode链接

2、代码
class Solution
{
public:// 全局变量int m, n;bool visit[21][21]; // 用来记录位置是否被访问过int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int ret; // 统计总路数int step; // 记录总共有几个0int uniquePathsIII(vector<vector<int>>& grid) {m = grid.size(); // 行n = grid[0].size(); // 列int x = 0; // 记录1的横坐标int y = 0; // 记录1的纵坐标for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 0){step++; // 统计有几个0}else if(grid[i][j] == 1) // 找到开头{x = i;y = j;}}}step += 2; // 包含上首尾visit[x][y] = true; // 标记一下当前位置被使用过dfs(grid, x, y, 1); // 从第一层开始往后递归return ret;}void dfs(vector<vector<int>>& grid, int i, int j, int count/*用来记录每一条路线的0的个数*/){// 递归出口if(grid[i][j] == 2){if(count == step){ret++;}return;}for(int k = 0; k < 4; k++){int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && grid[x][y] != -1){visit[x][y] = true;dfs(grid, x, y, count + 1);visit[x][y] = false;}}}
};
3、解析

相关文章:
【leetcode】深搜、暴搜、回溯、剪枝(C++)3
深搜、暴搜、回溯、剪枝(C)3 一、解数独1、题目描述2、代码3、解析 二、单词搜索1、题目描述2、代码3、解析 三、黄金矿工1、题目描述2、代码3、解析 四、不同路径III1、题目描述2、代码3、解析 一、解数独 1、题目描述 leetcode链接 2、代码 class…...
社区养老|社区养老服务系统|基于springboot社区养老服务系统设计与实现(源码+数据库+文档)
社区养老服务系统目录 目录 基于springboot社区养老服务系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员部分功能 (1) 用户管理 (2)服务种类管理 (3)社区服务管理 (…...
云计算基础-存储虚拟化(深信服aSAN分布式存储)
什么是存储虚拟化 分布式存储是利用虚拟化技术 “池化”集群存储卷内通用X86服务器中的本地硬盘,实现服务器存储资源的统一整合、管理及调度,最终向上层提供NFS、ISCSI存储接口,供虚拟机根据自身的存储需求自由分配使用资源池中的存储空间。…...
数学实验第三版(主编:李继成 赵小艳)课后练习答案(十二)(3)
实验十二:微分方程模型 练习三 1.分别用数值解命令ode23t和ode45 计算示例3中微分方程的数值解,同用命令ode23 算得的数值解以及解析解比较,哪种方法精度较高?你用什么方法比较它们之间的精度? clc;clear; f(x,y)2*yx2; figure(1) [x,y]ode23t(f,[1,2],1); plo…...
CSS Transition:为网页元素增添优雅过渡效果
随着互联网的发展,网页的视觉效果和用户体验变得尤为重要。CSS Transition作为一种能够让网页元素在状态改变时呈现平滑过渡效果的工具,受到了广大前端开发者的青睐。本文将详细介绍CSS Transition的基本概念、使用方法以及常见应用,帮助读者…...
JDK 17 新特性 (一)
既然 Springboot 3.0 强制使用 JDK 17 那就看看 JDK17 有哪些新特性吧 参考链接 介绍一下 新特性的历史渊源 JDK 17是Java Development Kit(JDK)的一个版本,它是Java编程语言的一种实现。JDK 17于2021年9月14日发布,并作为Java …...
杨中科 ASP.NET DI综合案例
综合案例1 需求说明 1、目的:演示DI的能力; 2、有配置服务、日志服务,然后再开发一个邮件发送器服务。可以通过配置服务来从文件、环境变量、数据库等地方读取配置,可以通过日志服务来将程序运行过程中的日志信息写入文件、控制台、数据库等。 3、说明…...
蓝桥杯嵌入式第12届真题(完成) STM32G431
蓝桥杯嵌入式第12届真题(完成) STM32G431 题目 程序 main.c /* USER CODE BEGIN Header */ /********************************************************************************* file : main.c* brief : Main program body**************************…...
C#系列-多线程(4)
在C#中,多线程编程主要涉及使用System.Threading命名空间下的类和接口来创建和管理线程。以下是一些C#多线程编程的基本用法和示例: 1. 使用Thread类创建线程 csharp代码 using System; using System.Threading; class Program { static void …...
VS如何调试C运行时库
C运行时库(简称crt)是C标准库等组件的基础, 其会在进入main函数之前运行一些代码, 包括但不限于初始化堆栈, 内存分配等操作 这些代码是可以随着VC工具集一起安装到我们本地的。看一下这个情况, 就是VS调试器没找到对应的crt源码的情况, 调用堆栈是空的。为了解决这个问…...
软件工程师,超过35岁怎么办
概述 随着科技行业的飞速发展,软件开发工程师的职业道路充满了各种机遇和挑战。对于已经在这个行业摸爬滚打了十多年的软件开发工程师来说,当他们步入35岁这个年纪时,可能会感到一些迷茫和焦虑。许多人担忧,在以创新、活力、快速迭…...
通过 Prometheus 编写 TiDB 巡检脚本(脚本已开源,内附链接)
作者丨 caiyfc 来自神州数码钛合金战队 神州数码钛合金战队是一支致力于为企业提供分布式数据库 TiDB 整体解决方案的专业技术团队。团队成员拥有丰富的数据库从业背景,全部拥有 TiDB 高级资格证书,并活跃于 TiDB 开源社区,是官方认证合作伙…...
sql语句学习(一)--查询
【有道云笔记】基本sql语句2—查询基础 数据库表结构 DROP TABLE IF EXISTS class; CREATE TABLE class (id int(11) NOT NULL AUTO_INCREMENT,class_num varchar(11) CHARACTER SET utf8mb4 COLLATE utf8mb4_bin NOT NULL COMMENT 班级号,class_name varchar(255) CHARACTE…...
【HTML】交友软件上照片的遮罩是如何做的
笑谈 我不知道大家有没有在夜深人静的时候感受到孤苦难耐,🐶。于是就去下了一些交友软件来排遣寂寞。可惜的是,有些交友软件真不够意思,连一些漂亮小姐姐的图片都要进行遮罩,完全不考虑兄弟们的感受,😠。所…...
【Java EE初阶十二】网络编程TCP/IP协议(一)
1. 网络编程 通过网络,让两个主机之间能够进行通信->就这样的通信来完成一定的功能,进行网络编程的时候,需要操作系统给咱们提供一组API,通过这些API来完成编程;API可以认为是应用层和传输层之间交互的路径…...
element-ui解决上传文件时需要携带请求数据的问题
一、问题描述 在前端使用element-ui进行文件上传时,需要携带请求头信息,比如Token。 二、问题解决 1. 表单实现 action置空添加:http-request属性覆盖默认的上传行为,实现自定义上传文件。注意:src后的图片路径如果是个网络请求(外链)&…...
【AI视野·今日NLP 自然语言处理论文速览 第七十九期】Thu, 18 Jan 2024
AI视野今日CS.NLP 自然语言处理论文速览 Thu, 18 Jan 2024 Totally 35 papers 👉上期速览✈更多精彩请移步主页 Daily Computation and Language Papers Deciphering Textual Authenticity: A Generalized Strategy through the Lens of Large Language Semantics …...
Docker容器运行
1、通过--name参数显示地为容器命名,例如:docker run --name “my_http_server” -d httpd 2、容器重命名可以使用docker rename。 3、两种进入容器的方法: 3.1、Docker attach 例如: 每间隔一秒打印”Hello World”。 Sudo docker run…...
【计算机网络】网络层之IP协议
文章目录 1.基本概念2.协议头格式3.网段划分4.特殊的IP地址5.IP地址的数量限制6.私有IP地址和公网IP地址7.路由 1.基本概念 IP地址是定位主机的,具有一个将数据报从A主机跨网络可靠的送到B主机的能力。 但是有能力就一定能做到吗,只能说有很大的概率。…...
2024/2/17 图论 最短路入门 dijkstra 1
目录 算法思路 Dijkstra求最短路 AcWing 849. Dijkstra求最短路 I - AcWing 850. Dijkstra求最短路 II - AcWing题库 最短路 最短路 - HDU 2544 - Virtual Judge (vjudge.net) 【模板】单源最短路径(弱化版) P3371 【模板】单源最短路径…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合
作者:来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布,Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明,Elastic 作为 …...
C++ 类基础:封装、继承、多态与多线程模板实现
前言 C 是一门强大的面向对象编程语言,而类(Class)作为其核心特性之一,是理解和使用 C 的关键。本文将深入探讨 C 类的基本特性,包括封装、继承和多态,同时讨论类中的权限控制,并展示如何使用类…...
