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

【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

深搜、暴搜、回溯、剪枝&#xff08;C&#xff09;3 一、解数独1、题目描述2、代码3、解析 二、单词搜索1、题目描述2、代码3、解析 三、黄金矿工1、题目描述2、代码3、解析 四、不同路径III1、题目描述2、代码3、解析 一、解数独 1、题目描述 leetcode链接 2、代码 class…...

社区养老|社区养老服务系统|基于springboot社区养老服务系统设计与实现(源码+数据库+文档)

社区养老服务系统目录 目录 基于springboot社区养老服务系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员部分功能 &#xff08;1&#xff09; 用户管理 &#xff08;2&#xff09;服务种类管理 &#xff08;3&#xff09;社区服务管理 &#xff08…...

云计算基础-存储虚拟化(深信服aSAN分布式存储)

什么是存储虚拟化 分布式存储是利用虚拟化技术 “池化”集群存储卷内通用X86服务器中的本地硬盘&#xff0c;实现服务器存储资源的统一整合、管理及调度&#xff0c;最终向上层提供NFS、ISCSI存储接口&#xff0c;供虚拟机根据自身的存储需求自由分配使用资源池中的存储空间。…...

数学实验第三版(主编:李继成 赵小艳)课后练习答案(十二)(3)

实验十二&#xff1a;微分方程模型 练习三 1.分别用数值解命令ode23t和ode45 计算示例3中微分方程的数值解,同用命令ode23 算得的数值解以及解析解比较,哪种方法精度较高?你用什么方法比较它们之间的精度? clc;clear; f(x,y)2*yx2; figure(1) [x,y]ode23t(f,[1,2],1); plo…...

CSS Transition:为网页元素增添优雅过渡效果

随着互联网的发展&#xff0c;网页的视觉效果和用户体验变得尤为重要。CSS Transition作为一种能够让网页元素在状态改变时呈现平滑过渡效果的工具&#xff0c;受到了广大前端开发者的青睐。本文将详细介绍CSS Transition的基本概念、使用方法以及常见应用&#xff0c;帮助读者…...

JDK 17 新特性 (一)

既然 Springboot 3.0 强制使用 JDK 17 那就看看 JDK17 有哪些新特性吧 参考链接 介绍一下 新特性的历史渊源 JDK 17是Java Development Kit&#xff08;JDK&#xff09;的一个版本&#xff0c;它是Java编程语言的一种实现。JDK 17于2021年9月14日发布&#xff0c;并作为Java …...

杨中科 ASP.NET DI综合案例

综合案例1 需求说明 1、目的:演示DI的能力; 2、有配置服务、日志服务&#xff0c;然后再开发一个邮件发送器服务。可以通过配置服务来从文件、环境变量、数据库等地方读取配置&#xff0c;可以通过日志服务来将程序运行过程中的日志信息写入文件、控制台、数据库等。 3、说明…...

蓝桥杯嵌入式第12届真题(完成) STM32G431

蓝桥杯嵌入式第12届真题(完成) STM32G431 题目 程序 main.c /* USER CODE BEGIN Header */ /********************************************************************************* file : main.c* brief : Main program body**************************…...

C#系列-多线程(4)

在C#中&#xff0c;多线程编程主要涉及使用System.Threading命名空间下的类和接口来创建和管理线程。以下是一些C#多线程编程的基本用法和示例&#xff1a; 1. 使用Thread类创建线程 csharp代码 using System; using System.Threading; class Program { static void …...

VS如何调试C运行时库

C运行时库(简称crt)是C标准库等组件的基础, 其会在进入main函数之前运行一些代码, 包括但不限于初始化堆栈, 内存分配等操作     这些代码是可以随着VC工具集一起安装到我们本地的。看一下这个情况, 就是VS调试器没找到对应的crt源码的情况, 调用堆栈是空的。为了解决这个问…...

软件工程师,超过35岁怎么办

概述 随着科技行业的飞速发展&#xff0c;软件开发工程师的职业道路充满了各种机遇和挑战。对于已经在这个行业摸爬滚打了十多年的软件开发工程师来说&#xff0c;当他们步入35岁这个年纪时&#xff0c;可能会感到一些迷茫和焦虑。许多人担忧&#xff0c;在以创新、活力、快速迭…...

通过 Prometheus 编写 TiDB 巡检脚本(脚本已开源,内附链接)

作者丨 caiyfc 来自神州数码钛合金战队 神州数码钛合金战队是一支致力于为企业提供分布式数据库 TiDB 整体解决方案的专业技术团队。团队成员拥有丰富的数据库从业背景&#xff0c;全部拥有 TiDB 高级资格证书&#xff0c;并活跃于 TiDB 开源社区&#xff0c;是官方认证合作伙…...

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】交友软件上照片的遮罩是如何做的

笑谈 我不知道大家有没有在夜深人静的时候感受到孤苦难耐&#xff0c;&#x1f436;。于是就去下了一些交友软件来排遣寂寞。可惜的是&#xff0c;有些交友软件真不够意思&#xff0c;连一些漂亮小姐姐的图片都要进行遮罩&#xff0c;完全不考虑兄弟们的感受,&#x1f620;。所…...

【Java EE初阶十二】网络编程TCP/IP协议(一)

1. 网络编程 通过网络&#xff0c;让两个主机之间能够进行通信->就这样的通信来完成一定的功能&#xff0c;进行网络编程的时候&#xff0c;需要操作系统给咱们提供一组API&#xff0c;通过这些API来完成编程&#xff1b;API可以认为是应用层和传输层之间交互的路径&#xf…...

element-ui解决上传文件时需要携带请求数据的问题

一、问题描述 在前端使用element-ui进行文件上传时&#xff0c;需要携带请求头信息&#xff0c;比如Token。 二、问题解决 1. 表单实现 action置空添加:http-request属性覆盖默认的上传行为&#xff0c;实现自定义上传文件。注意:src后的图片路径如果是个网络请求(外链)&…...

【AI视野·今日NLP 自然语言处理论文速览 第七十九期】Thu, 18 Jan 2024

AI视野今日CS.NLP 自然语言处理论文速览 Thu, 18 Jan 2024 Totally 35 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers Deciphering Textual Authenticity: A Generalized Strategy through the Lens of Large Language Semantics …...

Docker容器运行

1、通过--name参数显示地为容器命名&#xff0c;例如:docker run --name “my_http_server” -d httpd 2、容器重命名可以使用docker rename。 3、两种进入容器的方法&#xff1a; 3.1、Docker attach 例如&#xff1a; 每间隔一秒打印”Hello World”。 Sudo docker run…...

【计算机网络】网络层之IP协议

文章目录 1.基本概念2.协议头格式3.网段划分4.特殊的IP地址5.IP地址的数量限制6.私有IP地址和公网IP地址7.路由 1.基本概念 IP地址是定位主机的&#xff0c;具有一个将数据报从A主机跨网络可靠的送到B主机的能力。 但是有能力就一定能做到吗&#xff0c;只能说有很大的概率。…...

2024/2/17 图论 最短路入门 dijkstra 1

目录 算法思路 Dijkstra求最短路 AcWing 849. Dijkstra求最短路 I - AcWing 850. Dijkstra求最短路 II - AcWing题库 最短路 最短路 - HDU 2544 - Virtual Judge (vjudge.net) 【模板】单源最短路径&#xff08;弱化版&#xff09; P3371 【模板】单源最短路径&#xf…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...