JZ12 矩阵中的路径

剑指Offer编程链接:JZ12

题目描述:
在这里插入图片描述
思路:递归+回溯的方法,总结一下什么情况需要使用递归:

递归在解决问题时,通常涉及以下情况:

  1. 问题可被分解为较小的相似子问题。
  2. 子问题与原问题具有相同的结构,只是规模更小。
  3. 每个子问题的解可以通过递归调用来获得。
  4. 存在基本情况,当问题足够小时可以直接求解。

递归适用于许多问题,如数学运算(如阶乘、斐波那契数列)、树结构遍历、图算法、字符串处理等。然而,使用递归时要注意合适的终止条件和避免出现无限递归。

具体做法:
step 1:优先处理矩阵为空的特殊情况。
step 2:设置flag数组记录某一次路径中矩阵中的位置是否被经过,因此一条路径不能回头。
step 3:遍历矩阵,对每个位置进行递归。
step 4:递归查找的时候,到了矩阵的边界或者是下一个字符与这个位置的字符不匹配,或者节点已经访问过了,或者字符串匹配完成都结束递归。
step 5:访问节点,修改flag数组,向其他四个方向延伸,回溯的时候修改flag数组。

代码:

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    //i代表数组行,j代表列,matrix代表矩阵,n*m 矩阵,word代表要匹配的字符串,k代表当前第几个字符
    private boolean dfs(char[][] matrix,int n,int m,int i,int j,String word,int k,boolean[][] flag){
        //下标越界、字符不匹配、已经遍历过不能重复
        if(i<0||i>=n||j<0||j>=m||(matrix[i][j]!=word.charAt(k))||(flag[i][j]==true)){
            return false;
        }
        if(k==word.length()-1){
            return true;
        }
        flag[i][j] = true;
        //该结点四个方向
        if(dfs(matrix,n,m,i-1,j,word,k+1,flag)||dfs(matrix,n,m,i+1,j,word,k+1,flag)||dfs(matrix,n,m,i,j-1,word,k+1,flag)||dfs(matrix,n,m,i,j+1,word,k+1,flag)){
            return true;
        }
        //此格未被占用
        flag[i][j] = false;
        return false;
    }
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        if(matrix.length == 0){
            return false;
        }
        int n = matrix.length;
        int m = matrix[0].length;
        boolean[][] flag = new boolean[n][m];
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(dfs(matrix,n,m,i,j,word,0,flag)){
                    return true;
                }
            }
        }
        return false;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/101057.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

记录--前端使用a链接下载内容增加loading效果

这里给大家分享我在网上总结出来的一些知识&#xff0c;希望对大家有所帮助 问题描述&#xff1a;最近工作中出现一个需求&#xff0c;纯前端下载 Excel 数据&#xff0c;并且有的下载内容很多&#xff0c;这时需要给下载增加一个 loading 效果。 代码如下&#xff1a; // util…

[dasctf]misc3 chrchrchr.pcapng

webshell 流量分析 php代码部分没啥看的&#xff0c;主要在标黄的部分&#xff0c;裁剪掉前面的字符可base解码 能看到在向a.txt中写入数据 wp # tshark.exe -r chrchrchr.pcapng -T fields -e urlencoded-form.value -Y "urlencoded-form.keyzd2ebbfb26dd" >…

【设计模式】Head First 设计模式——桥模式 C++实现

设计模式最大的作用就是在变化和稳定中间寻找隔离点&#xff0c;然后分离它们&#xff0c;从而管理变化。将变化像小兔子一样关到笼子里&#xff0c;让它在笼子里随便跳&#xff0c;而不至于跳出来把你整个房间给污染掉。 设计思想 桥模式。将抽象部分(业务功能)与实现部分(平…

vr健康管理服务情景化教学弥补现代医学教学中的诸多不足之处

高职高专临床医学院校以培养岗位胜任力为目的&#xff0c;该专业是一门专业性、实践性较强的医学学科&#xff0c;要求培养出来的学生具有较强的临床实践能力&#xff0c;医学生所学的全部知识&#xff0c;都应与实践相结合&#xff0c;解决临床的实际问题&#xff0c;为患者解…

Android 手游聚合SDK小知识(一)

Android 手游聚合SDK小知识(一) Android 手游聚合SDK小知识(二) 聚合分包 前言 回头想想&#xff0c;在安卓游戏SDK这个领域&#xff0c;我也呆了4年了&#xff0c;从啥都不懂的小菜鸟&#xff0c;逐渐靠自己不断学习&#xff0c;对这个行业也算有了一些理解&#xff0c;趁着…

Qt应用开发(基础篇)——颜色选择器 QColorDialog

一、前言 QColorDialog类继承于QDialog&#xff0c;是一个设计用来选择颜色的对话框部件。 对话框窗口 QDialog QColorDialog颜色选择器一般用来让用户选择颜色&#xff0c;比如画图工具中选择画笔的颜色、刷子的颜色等。你可以使用静态函数QColorDialog::getColor()直接显示对…

vue集成mars3d后,basemaps加不上去

首先&#xff1a; <template> <div id"centerDiv" class"mapcontainer"> <mars-map :url"configUrl" οnlοad"onMapload" /> </div> </template> <script> import MarsMap from ../component…

Golang:微服务常用代码分层结构

1.代码结构 代码分层结构是一个老生常谈的话题&#xff0c;好的代码结构能够使得系统易于理解、开发及维护&#xff0c;如果代码结构很混乱就会使得不同层级的代码块耦合&#xff0c;导致难以维护和拓展。 比较经典的代码结构&#xff08;宏观&#xff09;有Web的MVC模式分层结…

Spring Cloud Foundry上使用通配符模式匹配进行的安全绕过漏洞 CVE-2023-20873

文章目录 0.前言1.参考文档2.基础介绍描述如果满足以下任一条件&#xff0c;应用程序就不会有太大风险&#xff1a;受影响的Spring产品和版本 3.解决方案3.1. 升级版本3.2. 替代方案 0.前言 背景&#xff1a;公司项目扫描到 Spring Cloud Foundry上使用通配符模式匹配进行的安全…

tp5使用redis及redis7.2安装到window系统上面

redis安装教程 redis7.2安装到window系统上面 https://download.csdn.net/download/qq_39161501/88269037 解决方案&#xff1a;修改配置php.ini文件 打开Apache目录下的php.ini文件&#xff0c;搜索extension&#xff0c;在空白处加上下列代码&#xff1a; 注&#xff1a;e…

2019CVPR Semantic Graph Convolutional Networks for 3D Human Pose Regression

基于语义图卷积网络的三维人体姿态回归 源码 https://github.com/garyzhao/SemGCN 摘要 在本文中&#xff0c;我们研究了学习图卷积网络&#xff08;GCN&#xff09;回归的问题。GCN的当前体系结构受限于卷积滤波器和共享的变换矩阵为的小感受野。为了解决这些限制&#xff…

并发 04(Callable,CountDownLatch)详细讲解

并发 Callable 1 可以返回值 2可以抛出异常 泛型指的是返回值的类型 public class Send {public static void main(String[] args) {//怎么启动Callable//new Thread().start();Aaa threadnew Aaa();FutureTask futureTasknew FutureTask(thread);new Thread(futureTask,&qu…

划分字母区间【贪心算法】

划分字母区间 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段&#xff0c;同一字母最多出现在一个片段中。 注意&#xff0c;划分结果需要满足&#xff1a;将所有划分结果按顺序连接&#xff0c;得到的字符串仍然是 s 。返回一个表示每个字符串片段的长度的列表。…

深度学习6:自然语言处理-Natural language processing | NLP

目录 NLP 为什么重要&#xff1f; 什么是自然语言处理 – NLP NLP 的2大核心任务 自然语言理解 – NLU|NLI 自然语言生成 – NLG NLP(自然语言处理) 的5个难点 NLP 的4个典型应用 NLP 的 2 种途径、3 个核心步骤 总结 自然语言处理 NLP 为什么重要&#xff1f; “语言…

Unity3D下如何采集camera场景数据并推送RTMP服务?

Unity3D使用场景 Unity3D是非常流行的游戏开发引擎&#xff0c;可以创建各种类型的3D和2D游戏或其他互动应用程序。常见使用场景如下&#xff1a; 游戏开发&#xff1a;Unity3D是一个广泛用于游戏开发的环境&#xff0c;适用于创建各种类型的游戏&#xff0c;包括动作游戏、角…

汽车电子笔记之:基于AUTOSAR的多核监控机制

目录 1、概述 2、系统监控的目标 2.1、任务的状态机 2.2、任务服务函数 2.3、任务周期性事件 2.4、时间监控的指标 2.5、时间监控的原理 2.6、CPU负载率监控原理 2.6.1、设计思路 2.6.2、监控方法的评价 3、基于WDGM模块热舞时序监控方法 3.1、活跃监督 3.2、截至时…

wireshark 流量抓包例题

一、题目一(1.pcap) 题目要求&#xff1a; 1.黑客攻击的第一个受害主机的网卡IP地址 2.黑客对URL的哪一个参数实施了SQL注入 3.第一个受害主机网站数据库的表前缀&#xff08;加上下划线例如abc&#xff09; 4.第一个受害主机网站数据库的名字 看到题目SQL注入&#xff0c…

Modbus通信协议

Modbus通信协议 一、概述 Modbus通信协议是一种工业现场总线协议标准&#xff0c;常用的Modbus协议有以下三种类型&#xff1a;Modbus TCP、Modbus RTU、Modbus ASCll。 Modbus通信协议解决了通过串行线路在电子设备之间发送信息的问题。该协议在遵循该协议的体系结构中实现主…

CSAPP的Lab学习——BombLab

文章目录 前言一、一号炸弹&#xff08;小试牛刀&#xff09;二、二号炸弹&#xff08;六重循环&#xff09;三、三号炸弹&#xff08;不同输入&#xff0c;不同答案&#xff09;四、四号炸弹&#xff08;判断语句的实现&#xff09;五、五号炸弹&#xff08;跳转&#xff0c;循…

【MTK平台】根据kernel log分析wifi scan的时候流程

一 概要: 本文主要讲解根据kernel log分析下 当前路径下(vendor/mediatek/kernel_modules/connectivity/wlan/core/gen4m/)wifi scan的时候代码流程 二. Log分析: 先看Log: 2.1)在Framework层WifiManager.java 方法中,做了一个标记,可以精准的确认时间 这段log可以…