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

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...