【LeetCode-中等题】79. 单词搜索
文章目录
- 题目
- 方法一:递归 +回溯
题目

方法一:递归 +回溯
- 需要一个标记数组 来标志格子字符是否被使用过了
- 先找到word 的第一个字符在表格中的位置,再开始递归
- 递归的结束条件是如果word递归到了最后一个字符了,说明能在矩阵中找到单词
- 剪枝条件 就是如果已经找到单词了 res = true 了 后面就不需要递归了,还有如果下标越界、当前格子被使用过了、 或者当前格子字符不和当前wordIdenx相同 都直接剪枝 不往下递归了
- 并且在对当前位置进行四个方向递归的时候,需要将该位置标志数组置为true代表使用过了
- 在将四个方向递归完了,要把当前位置的标志位修改回来,回溯
class Solution {boolean res = false;//结果标志位int r = 0;//全局 矩阵长宽int c = 0;boolean[][] usered = null;public boolean exist(char[][] board, String word) {r = board.length;c = board[0].length;// 同一个单元格内的字母不允许被重复使用!!!// 标识字母是否被使用usered = new boolean[r][c];char[] chars = word.toCharArray();// 将字符串转换为字符数组//在矩阵中找到word第一个字符再进行递归for(int i = 0 ; i < r ; i++)for(int j = 0 ; j < c ; j++){ if(board[i][j] == chars[0]) backtrack(board,i,j,chars,0,usered); // 0代表word第一个字符 usered 标记已经使用过的表格}return res;}public void backtrack(char[][] board,int i,int j,char[] chars,int wordIndex,boolean[][] usered){if(res) return;// 已找到答案直接结束if(wordIndex == chars.length) {res = true ; return;}// 越界 或者不相等// i 和 j 要在矩阵范围内 并且标志位要是fasle 并且当前矩阵格子的字符要是 word当前的字符相等 才会往下递归 否则returnif(i < 0 || j < 0 || i > r-1 || j > c-1 || usered[i][j] || board[i][j] != chars[wordIndex]) return;// 往下递归 说明符合条件// 标记已经被使用usered[i][j] = true;//四个方向递归backtrack(board,i-1,j,chars,wordIndex+1,usered); backtrack(board,i+1,j,chars,wordIndex+1,usered); backtrack(board,i,j-1,chars,wordIndex+1,usered); backtrack(board,i,j+1,chars,wordIndex+1,usered); // 回溯恢复状态usered[i][j] = false;}}
相关文章:
【LeetCode-中等题】79. 单词搜索
文章目录 题目方法一:递归 回溯 题目 方法一:递归 回溯 需要一个标记数组 来标志格子字符是否被使用过了先找到word 的第一个字符在表格中的位置,再开始递归递归的结束条件是如果word递归到了最后一个字符了,说明能在矩阵中找到单…...
揭秘iPhone 15 Pro Max:苹果如何战胜三星
三星Galaxy S23 Ultra在我们的最佳拍照手机排行榜上名列前茅有几个原因,但iPhone 15 Pro Max正在努力夺回榜首——假设它有一个特定的功能。别误会我的意思,苹果一直在追赶三星,因为它的iPhone 14 Pro和14 Pro Max都表现强劲。尽管如此&#…...
分布式秒杀方案--java
前提:先把商品详情和秒杀商品缓存redis中,减少对数据库的访问(可使用定时任务) 秒杀商品无非就是那几步(前面还可能会有一些判断,如用户是否登录,一人一单,秒杀时间验证等࿰…...
高频golang面试题:简单聊聊内存逃逸?
文章目录 问题怎么答举例 问题 知道golang的内存逃逸吗?什么情况下会发生内存逃逸? 怎么答 golang程序变量会携带有一组校验数据,用来证明它的整个生命周期是否在运行时完全可知。如果变量通过了这些校验,它就可以在栈上分配。…...
【2023年数学建模国赛C题解题思路】
第一问 要求分析分析蔬菜各品类及单品销售量的分布规律及相互关系。该问题可以拆分成三个角度进行剖析。 1)各种类蔬菜的销售量分布、蔬菜种类与销售量之间的关系;2)各种类蔬菜的销售量的月份分布、各种类蔬菜销售量与月份之间的相关关系&a…...
Jenkins+Allure+Pytest的持续集成
一、配置 allure 环境变量 1、下载 allure是一个命令行工具,可以去 github 下载最新版:https://github.com/allure-framework/allure2/releases 2、解压到本地 3、配置环境变量 复制路径如:F:\allure-2.13.7\bin 环境变量、Path、添加 F:\a…...
yo!这里是进程控制
目录 前言 进程创建 fork()函数 写时拷贝 进程终止 退出场景 退出方法 进程等待 等待原因 等待方法 1.wait函数 2.waitpid函数 等待结果(status介绍) 进程替换 替换原理 替换函数 进程替换例子 shell简易实现 后记 前言 学习完操作…...
多线程快速入门
线程与进程区别 每个正在系统上运行的程序都是一个进程。每个进程包含一到多个线程。线程是一组指令的集合,或者是程序的特殊段,它可以在程序里独立执行。也可以把它理解为代码运行的上下文。所以线程基本上是轻量级的进程,它负责在单个程序里…...
Redis 7 第七讲 哨兵模式(sentinal)架构篇
哨兵模式 哨兵巡查监控后台master主机是否故障,如果出现故障根据投票时自动将某一个从库转换成新的主库,继续对外服务。 作用 1. 监控redis运行状态,包括master和slave 2. 当master down机,能自动将salve切换成新的master 应用场景 主从监控监控主从redis库运行的状态…...
laravel框架系列(一),Dcat Admin 安装
介绍 Laravel 是一个流行的 PHP 开发框架,它提供了一套简洁、优雅的语法和丰富的功能,用于快速构建高质量的 Web 应用程序。 以下是 Laravel 的一些主要特点和功能: MVC 架构:Laravel 使用经典的模型-视图-控制器(MV…...
Linux:工具(vim,gcc/g++,make/Makefile,yum,git,gdb)
目录 ---工具功能 1. vim 1.1 vim的模式 1.2 vim常见指令 2. gcc/g 2.1 预备知识 2.2 gcc的使用 3.make,Makefile make.Makefile的使用 4.yum --yum三板斧 5.git --git三板斧 --Linux下提交代码到远程仓库 6.gdb 6.1 gdb的常用指令 学习目标: 1.知道…...
小节1:Python字符串打印
1、字符串拼接 用可以将两个字符串拼接成一个字符串 print("你好 " "这是一串代码") 输出: 2、单双引号转义 当打印的字符串中带有引号或双引号时,使用\或\"表示 print("He said \"Let\s go!\"") 输…...
2023国赛C题解题思路代码及图表:蔬菜类商品的自动定价与补货决策
2023国赛C题:蔬菜类商品的自动定价与补货决策 C题表面上看上去似乎很简单,实际上23题非常的难,编程难度非常的大,第二题它是一个典型的动态规划加仿真题目,我们首先要计算出销量与销售价格,批发价格之间的…...
数据可视化工具中的显眼包:奥威BI自带方案上阵
根据经验来看,BI数据可视化分析项目是由BI数据可视化工具和数据分析方案两大部分共同组成,且大多数时候方案都需从零开始,反复调整,会耗费大量时间精力成本。而奥威BI数据可视化工具别具匠心,将17年经验凝聚成标准化、…...
LeetCode算法心得——生成特殊数字的最少操作(贪心找规律)
大家好,我是晴天学长,这是一个简单贪心思维技巧题,主要考察的还是临场发挥的能力。需要的小伙伴可以关注支持一下哦!后续会继续更新的。 2) .算法思路 0 00 50 25 75 末尾是这两个的才能被45整除 思路:分别找&#x…...
【2023高教社杯】B题 多波束测线问题 问题分析、数学模型及参考文献
【2023高教社杯】B题 多波束测线问题 问题分析、数学模型及参考文献 1 题目 1.1 问题背景 多波束测深系统是利用声波在水中的传播特性来测量水体深度的技术,是在单波束测深的基础上发展起来的,该系统在与航迹垂直的平面内一次能发射出数十个乃至上百个…...
如何处理异步编程中的回调地狱问题?
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 解决回调地狱问题的方法⭐使用 Promise⭐使用 async/await⭐ 使用回调函数库⭐模块化⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端…...
什么是Lambda表达式?
Lambda表达式是Java 8引入的一个重要特性,用于简化函数式编程中的匿名函数的定义和使用。它可以被视为一种轻量级的匿名函数,可以作为参数传递给方法或存储在变量中。 Lambda表达式的语法形式如下: (parameters) -> expression 或 (para…...
公式trick备忘录
增大不同class feature之间的距离用hinge loss 相关, similarity learning, svm https://www.youtube.com/watch?vQtAYgtBnhws https://www.youtube.com/watch?vbM4_AstaBZo&t286s...
向量数据库Milvus Cloud核心组件再升级,主打就是一个低延迟、高准确度
支持 ScaNN 索引 Faiss 实现的 ScaNN,又名 FastScan,使用更小的 PQ 编码和相应的指令集可以更为友好地访问 CPU 寄存器,从而使其拥有优秀的索引性能。该索引在 Cohere 数据集,Recall 约 95% 的时候,Milvus 使用 Knowhere 2.x 版本端到端的 QPS 是 IVF_FLAT 的 7 倍,HN…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
