当前位置: 首页 > 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…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

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

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

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

如何把工业通信协议转换成http websocket

1.现状 工业通信协议多数工作在边缘设备上&#xff0c;比如&#xff1a;PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发&#xff0c;当设备上用的是modbus从站时&#xff0c;采集设备数据需要开发modbus主站&#xff1b;当设备上用的是西门子PN协议时&#xf…...

验证redis数据结构

一、功能验证 1.验证redis的数据结构&#xff08;如字符串、列表、哈希、集合、有序集合等&#xff09;是否按照预期工作。 2、常见的数据结构验证方法&#xff1a; ①字符串&#xff08;string&#xff09; 测试基本操作 set、get、incr、decr 验证字符串的长度和内容是否正…...

StarRocks 全面向量化执行引擎深度解析

StarRocks 全面向量化执行引擎深度解析 StarRocks 的向量化执行引擎是其高性能的核心设计&#xff0c;相比传统行式处理引擎&#xff08;如MySQL&#xff09;&#xff0c;性能可提升 5-10倍。以下是分层拆解&#xff1a; 1. 向量化 vs 传统行式处理 维度行式处理向量化处理数…...