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

单词搜索问题(涉及递归等)

目录

一·题目:

二·思路解释:

三·解答代码:


一·题目:

newcode题目链接: 单词搜索_牛客题霸_牛客网

二·思路解释:

思路:个人理解是找到word中的第一个元素,然后去递归的上下左右查找,最后根据word的下标变化等看是否返回true

下面具体说一下个人思路(也是根据大佬悟出来的):这里有点明显想考的是递归的使用,这里为了方便记录遍历到原数组位置

以及防止查找时候查到已经找到的原数组中元素(word中有连续重复元素在board中出现)等,因此不方便在原数组里面操作,因此重新建一个二维数组(这里个人称作真假表->主要记录遍历原数组找到元素位置,给它在真假表中用true标记,而默认是false,这里标记它的路径也能防止“走重的操作了”).

因此这里首先建立一个递归函数,首先要想完成这个操作需要哪些参数等呢? word和它的索引 ,board和它的下标i,j,以及我们的真假表(这里下标直接用board的i,j即可);

一开始先遍历原数组找到word首元素的位置,从它开始进行递归(当然这里有种特殊情况,下面会讲到)

1·首先不是递归嘛:然后先找递归终止条件这里可以根据遍历上下左右的时候出现的越界问题,总结了四个返回false的情况,根据后面的查找操作也不难找出另两个即可能出现查找了曾经找的元素+不是word中对应下标所指向的元素。-->这里就得到了递归不成立的六大终止条件。   如果我们根据实例1试到最后一次对归还会发现最后一次如果再次遍历,它应该设置一个返回真的条件 ,于是就得到了另一个返回真的条件--->也就是当word索引越界的情况

2·也就是如何递归,这里如果上面没有被返回也就是到了下面也就是找到了,因此可以在真假表对应映射位置填入true,然后接着往它左右递归即可,最后呢根据递归完往回溯可以看出这里最后返回的上下左右的bool类型值应该是或的关系。

3·这里可以考虑给真假表对应的当时填入true位置复原成false(当然这里对本题解无关系)

 

这里有一个细节问题;也就是上面说的,这里找到对应word[0],我们就返回这个递归函数,这里是错误的(表示掉过坑),这里可能是这种情况:["CAA","AAA","BCD"] "AAB"-->这里如果找到第一个A,然后递归下去最后返回的一定是false,然而此例子返回的应该是true,因此如果它是false就接着遍历board继续找,然后再次递归, 因此这里如果递归函数返回false不一定题解真实false,但是如果返回true则题解一定是true。,因此注意好这个基本到这就没什么问题了。

 

下面画图以实例1为例子解释如何递归的:

 

 

 

 

 

 

三·解答代码:

                  

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param board string字符串vector * @param word string字符串 * @return bool布尔型*/bool recursion_find(vector<string>& board,int i,int j, string word,int word_index,vector<vector<bool>>TF_graph){if(word_index==word.size()) return true;if(i<0||i>=board.size()||j<0||j>=board[0].size()||TF_graph[i][j]==true||board[i][j]!=word[word_index]) return false;TF_graph[i][j]=true;bool target_on=recursion_find(board,i-1,j,word,word_index+1,TF_graph);bool target_under=recursion_find(board,i+1,j,word,word_index+1,TF_graph);bool target_left=recursion_find(board,i,j-1,word,word_index+1,TF_graph);bool target_right=recursion_find(board,i,j+1,word,word_index+1,TF_graph);// TF_graph[i][j]=false;return  target_on||target_under||target_left|| target_right;}bool exist(vector<string>& board, string word) {int m=board.size();int n=board[0].size();vector<vector<bool>>TF_graph(m,vector<bool>(n,false));for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j]==word[0]){//return recursion_find(board,i,j,word,0,TF_graph);if (recursion_find(board,i,j,word,0,TF_graph)) {return true;}}}}return false;}
};

                     ​​​​​​​       若有补充希望大佬们留言.        

相关文章:

单词搜索问题(涉及递归等)

目录 一题目&#xff1a; 二思路解释&#xff1a; 三解答代码&#xff1a; 一题目&#xff1a; newcode题目链接&#xff1a; 单词搜索_牛客题霸_牛客网 二思路解释&#xff1a; 思路&#xff1a;个人理解是找到word中的第一个元素&#xff0c;然后去递归的上下左右查找&am…...

Redis的一些通用指令

首先我们需要先连接客户端服务器&#xff0c;此时我们需要通过redis-cli和redis服务器进行交互&#xff0c;输入ping来确保通路的流畅 &#xff08;一&#xff09;get和set redis中最核心的两个命令就是get和set&#xff0c;get就是根据key来取出对应value&#xff0c;set就是把…...

C++中vector类的使用

目录 1.vector类常用接口说明 1.1默认成员函数 1.1.1构造函数(constructor) 1.1.2 赋值运算符重载(operator()) 2. vector对象的访问及遍历操作(Iterators and Element access) 3.vector类对象的容量操作(Capacity) 4. vector类对象的修改及相关操作(Modifiers and Stri…...

cmaklist流程控制——调试及发布

cmaklist流程控制 目前只会配置-编译调试-打包发布&#xff0c;并且不会workflow控制 后续学习配置-编译调试-测试-打包发布&#xff0c;workflow控制&#xff0c;理解整个流程&#xff0c;目前对流程控制理解也不够。 1.CMake Presets 先于Cmakelist文件&#xff0c;指导项…...

制作一个能对话能跳舞的otto机器人

OTTO机器人是一个开源外壳&#xff0c;硬件和软件的桌面机器人项目&#xff0c;非常适合新手研究和拓展。记住&#xff0c;他是一个能移动有表情能声音的机器人。 b站有很多演示和组装的视频&#xff0c;我就不多说了&#xff0c;照着做就好&#xff0c;因为硬件我也是刚入门&…...

git配置SSH

1 打开cmd窗口 2 在窗口中输入如下命令&#xff1a; 配置用户名&#xff1a; git config --global user.name “gyk” 配置邮箱&#xff1a; git config --global user.email “247929163qq.com” 继续在Git命令窗口中输入如下命令&#xff0c;即可生成SSH公钥和私钥 ss…...

mozilla/pdf.js view.html加载指定页码

mozilla/pdf.js view.html加载指定页码 在Mozilla’s PDF.js中&#xff0c;如果你想要在viewer.html加载时直接跳转到指定的页码&#xff0c;你可以通过修改URL来实现。 PDF.js使用查询参数来处理URL&#xff0c;其中page参数用于指定页码。你可以通过修改URL的查询字符串来设…...

Qt之QFuture理解

结构 #mermaid-svg-J9J683RG8QjtEqoM {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-J9J683RG8QjtEqoM .error-icon{fill:#552222;}#mermaid-svg-J9J683RG8QjtEqoM .error-text{fill:#552222;stroke:#552222;}#merm…...

求二叉树的高度(递归和非递归)

假设二叉树采用二叉链表存储结构&#xff0c;设计一个算法求二叉树的高度。 递归&#xff1a; int getTreeHight(BiTree T){if(TNULL){return 0;}else {int lh getTreeHight(T->lchild);int rh getTreeHight(T->rchild);return (lh>rh?lh:rh)1;}}时间复杂度O(n)&a…...

Java查找算法——(四)分块查找(完整详解,附有代码+案例)

文章目录 分块查找1.1普通分块查找 分块查找 1.1普通分块查找 分块原则&#xff1a; 块内无序&#xff0c;块间有序:前一块中的最大数据&#xff0c;小于后一块中所有的数据&#xff0c;块与块之间不能有数据重复的交集。块的数量一般等于数字个数开根号 核心思路&#xff…...

进制数知识(2)—— 浮点数在内存中的存储 和 易混淆的二进制知识总结

目录 1. 浮点数在内存中的存储 1.1 浮点数的大V表示法 1.2 浮点数的存储格式 1.3 浮点数的存入规则 1.4 浮点数的读取规则 1.5 补充&#xff1a;移码与掩码 1.6 题目解析 2. 易错的二进制知识 2.0 符号位到底会不会参与运算&#xff1f; 2.0.1 存储前的编码变化运算 …...

类似QQ聊天功能的Java程序

实现一个类似QQ聊天功能的Java程序需要考虑以下几个关键点&#xff1a; 用户界面&#xff1a;用于展示消息和输入消息。网络通信&#xff1a;用于客户端之间的信息传输。用户管理&#xff1a;用于管理用户的登录、注册和状态。消息存储&#xff1a;用于存储聊天记录。 这里提…...

Redis 键值对数据库学习

目录 一、介绍 二、安装以及连接 三、设置连接密码 四、连接报错 五、redis 操作字符串以及过期时间 六、 redis 列表操作 七、redis 集合操作 八、hash 哈希操作 九、redis 发布和订阅操作 十、RDB和AOF的两种数据持久化机制 十一、 其他机器连接redis 十二、 pyt…...

逆向推理+ChatGPT,让论文更具说服力

学境思源&#xff0c;一键生成论文初稿&#xff1a; AcademicIdeas - 学境思源AI论文写作 使用ChatGPT辅助“逆向推理”技巧&#xff0c;可以显著提升论文的质量和说服力。逆向推理从结论出发&#xff0c;倒推所需的证据和论点&#xff0c;确保整个论证过程逻辑严密且无漏洞。…...

「JavaScript深入」一文说明白JS的执行上下文与作用域

JavaScript深入 — 执行上下文与作用域 上下文执行上下文生命周期创建阶段执行阶段回收阶段 执行栈作用域链作用域词法作用域&#xff08;静态作用域&#xff09; 上下文 变量或函数的上下文决定了它们可以访问哪些数据&#xff0c;以及它们的行为。 每个上下文都有一个关联的…...

Qt C++设计模式->组合模式

组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;允许你将对象组合成树形结构以表示部分与整体的层次关系。组合模式使得客户端可以以统一的方式对待单个对象和组合对象&#xff0c;简化了对复杂树形结构的操作。 组合模式的应用场景 组合…...

Acwing Bellman-Ford SPFA

1. Bellman-Ford 该算法适用于有负权边的情况&#xff0c;注意&#xff1a;如果有负权环的话&#xff0c;最短路就不一定存在了。时间复杂度 O ( m n ) . O(mn). O(mn).该算法可以求出来图中是否存在负权回路&#xff0c;但求解负权回路&#xff0c;通常用SPFA算法&#xff0c…...

我能禁止使用某协议的ip禁止访问我的资源吗

是的&#xff0c;你可以禁止使用某个协议的IP地址访问你的资源。这种操作通常涉及网络防火墙、服务器配置或应用程序设置&#xff0c;具体方法取决于你的网络环境和使用的技术。以下是一些常见的实现方法&#xff1a; 1. 使用防火墙 大多数防火墙&#xff08;硬件或软件&…...

快速理解TCP协议(二)——TCP协议中的拥塞控制机制详解

在计算机网络中&#xff0c;TCP&#xff08;传输控制协议&#xff09;是一种广泛使用的面向连接的、可靠的、基于字节流的传输层通信协议。TCP协议通过一系列复杂的机制来确保数据的可靠传输&#xff0c;其中拥塞控制是至关重要的一环。本文将深入探讨TCP协议中的拥塞控制机制&…...

Linux:debug: systemtap: ubacktrace

https://docs.huihoo.com/systemtap/sourceware.org/systemtap/SystemTap_Beginners_Guide/ustack.html 这个函数可以帮助将user level的backtrace打印出来。 stap -d /bin/ls --ldd \ -e probe process("ls").function("xmalloc") {print_usyms(ubacktra…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...

Java 与 MySQL 性能优化:MySQL 慢 SQL 诊断与分析方法详解

文章目录 一、开启慢查询日志&#xff0c;定位耗时SQL1.1 查看慢查询日志是否开启1.2 临时开启慢查询日志1.3 永久开启慢查询日志1.4 分析慢查询日志 二、使用EXPLAIN分析SQL执行计划2.1 EXPLAIN的基本使用2.2 EXPLAIN分析案例2.3 根据EXPLAIN结果优化SQL 三、使用SHOW PROFILE…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...

LINUX编译vlc

下载 VideoLAN / VLC GitLab 选择最新的发布版本 准备 sudo apt install -y xcb bison sudo apt install -y autopoint sudo apt install -y autoconf automake libtool编译ffmpeg LINUX FFMPEG编译汇总&#xff08;最简化&#xff09;_底部的附件列表中】: ffmpeg - lzip…...

Vue3学习(接口,泛型,自定义类型,v-for,props)

一&#xff0c;前言 继续学习 二&#xff0c;TS接口泛型自定义类型 1.接口 TypeScript 接口&#xff08;Interface&#xff09;是一种定义对象形状的强大工具&#xff0c;它可以描述对象必须包含的属性、方法和它们的类型。接口不会被编译成 JavaScript 代码&#xff0c;仅…...