【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…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
