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

剑指 Offer 12. 矩阵中的路径(回溯 DFS)

文章目录

  • 题目描述
  • 思路分析
  • 完整代码

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

在这里插入图片描述

例如,在下面的 3×4 的矩阵中包含单词 “ABCCED”(单词中的字母已标出)。
示例 1:
输入:board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出:true

示例 2:
输入:board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
输出:false

思路分析

一道非常经典的矩阵搜索题。

直接回溯。

1.确定循环体

肯定是要遍历矩阵中的每一个格子,以每一个格子为起点向外搜索。

for i in range(len(board)):for j in range(len(board[0])):

2.确定回溯体参数

显然需要当前遍历的格子下标i和j,还需要当前遍历的单词下标k。
def dfs(i,j,k):

3.确定回溯体

在回溯的过程中,如果遇到边界,则立即回退,遇到不符合单词的字符,也立即回退。

if not 0<=i<len(board) or not 0<= j<len(board[0])  or board[i][j] != word[k]:return False           

当前遍历单词的下标k如果遍历到最后了,说明此时找到了完整的单词:

if len(word)-1 == k:return True

后面就是连续的三步,
1,首先将所有遍历过的格子都弄成空,防止重复遍历。
2. 回溯寻找当前格子的四周。
3. 回退的时候将变空的格子变回原来的数值。

            board[i][j] = ' 'res = dfs(i-1,j,k+1) or dfs(i,j-1,k+1) or dfs(i+1,j,k+1) or dfs(i,j+1,k+1)board[i][j] = word[k]

完整代码

class Solution:def exist(self, board: List[List[str]], word: str) -> bool:# k为当前word遍历的下标def dfs(i,j,k):if not 0<=i<len(board) or not 0<= j<len(board[0])  or board[i][j] != word[k]:return Falseif len(word)-1 == k:return Trueboard[i][j] = ' 'res = dfs(i-1,j,k+1) or dfs(i,j-1,k+1) or dfs(i+1,j,k+1) or dfs(i,j+1,k+1)board[i][j] = word[k]return res for i in range(len(board)):for j in range(len(board[0])):if dfs(i,j,0):return Truereturn False

相关文章:

剑指 Offer 12. 矩阵中的路径(回溯 DFS)

文章目录 题目描述思路分析完整代码 题目描述 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 单词必须按照字母顺序&#xff0c;通过相邻的单元格内的字母构成&#xff…...

iceberg对比hive优势

1.事务性 从事务性上来说&#xff0c;iceberg具有更高的数据质量。 因为iceberg本质是一种table format&#xff0c;屏蔽了底层的存储细节&#xff0c;写入数据时候需要严格按照schema写入。而hive可以先写入底层数据&#xff0c;然后使用load partition的方式来加载分区。这样…...

ProgressBar基本使用

作用&#xff1a;进度条&#xff0c;用于展示某个任务的完成情况&#xff0c; 常用属性&#xff1a; 设定进度条的最大、最小值、自增步长 常用事件&#xff1a; 后台代码&#xff1a; private void progressBar1_Click(object sender, EventArgs e){Thread t;//使用线程执行…...

spring boot java使用XEasyPdf生成pdf文档

java使用XEasyPdf生成pdf文档 spring boot java使用XEasyPdf生成pdf文档第一步导入maven坐标,pom.xml全部贴上第二步编写代码代码实战&#xff1a; spring boot java使用XEasyPdf生成pdf文档 第一步导入maven坐标,pom.xml全部贴上 <?xml version"1.0" encoding…...

自定义elementui的主题

通常情况下&#xff0c;我们使用elementui框架的时候默认组件的主题都是白色的&#xff0c;比如&#xff1a; 但是如果想自定义主题&#xff0c;改变主题颜色&#xff0c;以及各种默认颜色&#xff0c;其实也不难&#xff1a; 配置默认主题&#xff0c;选好后点击下载 在vu…...

eNSP interface g0/0/0 报错解决办法

文章目录 1 报错截图2 解决办法2.1 排查设备是否有 GM 接口2.2 更换适合的路由器&#xff0c;并验证 1 报错截图 2 解决办法 2.1 排查设备是否有 GM 接口 查看下设备是否支持 GM 接口&#xff08;GigabitEthernet&#xff09; 方式一&#xff1a;右键路由器设备 - 设置 - 查看…...

Metric3D:Towards Zero-shot Metric 3D Prediction from A Single Image

参考代码&#xff1a;Metric3D 介绍 在如MiDas、LeReS这些文章中对于来源不同的深度数据集使用归一化深度作为学习目标&#xff0c;则在网络学习的过程中就天然失去了对真实深度和物体尺寸的度量能力。而这篇文章比较明确地指出了影响深度估计尺度变化大的因素就是焦距 f f f…...

k8s ingress获取客户端客户端真实IP

背景 在Kubernetes中&#xff0c;获取客户端真实IP地址是一个常见需求。这是因为在负载均衡架构中&#xff0c;原始请求的源IP地址会被替换成负载均衡器的IP地址。 获取客户端真实IP的需求背景包括以下几点&#xff1a; 安全性&#xff1a;基于客户端IP进行访问控制和认证授…...

Mysql主从搭建 基于DOCKER

创建目录 #主节点目录 mkdir -p /home/data/master/mysql/#从节点目录 mkdir -p /home/data/slave/mysql/创建配置文件 # 主节点配置 touch /home/data/master/mysql/my.cnf# 从节点配置 touch /home/data/slave/mysql/my.cnf编辑配置文件 主节点配置文件 vim /home/data/m…...

Leaflet入门,地图平移跳转到指定位置和飞行到指定位置效果

前言 本章讲解如何Leaflet如何实现操作地图平移到指定位置或者飞行到指定位置效果。 vue如何使用Leaflet vue2如何使用:《Leaflet入门,如何使用vue2-leaflet实现vue2双向绑定式的使用Leaflet地图,以及初始化后拿到leaflet对象,方便调用leaflet的api》 vue3如何使用:《L…...

iMX6ULL驱动开发 | 让imx6ull开发板支持usb接口FC游戏手柄

手边有一闲置的linux开发板iMX6ULL一直在吃灰&#xff0c;不用来搞点事情&#xff0c;总觉得对不住它。业余打发时间就玩起来吧&#xff0c;总比刷某音强。从某多多上买来一个usb接口的游戏手柄&#xff0c;让开发板支持以下它&#xff0c;后续就可以接着在上面玩童年经典游戏啦…...

Java 实现 SCP 携带密码拷贝文件

背景说明 涉及通过程序进行机器间的文件Copy的场景&#xff0c;我们一般会使用ssh连接机器&#xff0c;通过scp命令进行文件copy。 此种方案的前提是&#xff1a;机器间事先要配置免密码互通。 但是&#xff0c;如果客户现场机器数量过多&#xff0c;配置免密操作比较麻烦&a…...

Flink CEP(三)pattern动态更新

线上运行的CEP中肯定经常遇到规则变更的情况&#xff0c;如果每次变更时都将任务重启、重新发布是非常不优雅的。尤其在营销或者风控这种对实时性要求比较高的场景&#xff0c;如果规则窗口过长&#xff08;一两个星期&#xff09;&#xff0c;状态过大&#xff0c;就会导致重启…...

抽象工厂模式(C++)

定义 提供一个接口,让该接口负责创建一系列“相关或者相互依赖的对象”&#xff0c;无需指定它们具体的类。 使用场景 在软件系统中&#xff0c;经常面临着“一系列相互依赖的对象”的创建工作;同时,由于需求的变化&#xff0c;往往存在更多系列对象的创建工作。如何应对这种…...

程序员面试金典17.*

文章目录 17.01 不用加号的加法17.04 消失的数字17.05字母与数字17.06 2出现的次数17.07 婴儿名字17.08 马戏团人塔17.09 第k个数17.10 主要元素17.11 单词距离17.12 BiNode17.13 恢复空格&#xff08;未做&#xff0c;字典树dp&#xff09;17.14 最小K个数17.15 最长单词17.16…...

【瑞吉外卖项目复写】基本部分复写笔记

Day1 瑞吉外卖项目概述 mysql的数据源配置 spring:datasource:druid:driver-class-name: com.mysql.cj.jdbc.Driverurl: jdbc:mysql://localhost:3306/regie?serverTimezoneAsia/Shanghai&useUnicodetrue&characterEncodingutf-8&zeroDateTimeBehaviorconvertTo…...

用html+javascript打造公文一键排版系统15:一键删除所有空格

现在我们来实现一键删除所有空格的功能。 一、使用原有的代码来实现&#xff0c;测试效果并不理想 在这之前我们已经为String对象编写了一个使用正则表达式来删除所有空格的方法&#xff1a; //功能&#xff1a;删除字符串中的所有空格 //记录&#xff1a;20230726创建 Stri…...

苍穹外卖day12(完结撒花)——工作台+Spring_Apche_POI+导出运营数据Excel报表

工作台——需求分析与设计 产品原型 接口设计 工作台——代码导入 将提供的代码导入对应的位置。 工作台——功能测试 Apache POI_介绍 应用场景 Apache POI_入门案例 导入坐标 <!-- poi --><dependency><groupId>org.apache.poi</groupId><ar…...

SQL与NoSQL概念(详细介绍!!)

先搞清楚全称 SQL全称为Structured query language &#xff0c;即结构化查询语言&#xff0c;可以把他理解为一门特殊的编程语言。 那么nosql是什么意思呢&#xff1f;这里的no并不仅是not&#xff0c;而是not only的意思&#xff0c;所以nosql全称应该是Not Only Structure…...

node debian 镜像 new Date 获取时间少 8 小时问题

问题 在 node debian 镜像中&#xff0c;用 (new Date()).getHours() 与系统时间&#xff08;东 8 区&#xff09;少了 8 小时 系统时间 $ node > (new Date()).getHours() 11容器中的时间 $ node > (new Date()).getHours() 3原 Dockerfile FROM node:20.5-bullsey…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...