【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…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...