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

刷题记录 HOT100回溯算法-6:79. 单词搜索

题目:79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1:

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true

示例 2:

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出:true

示例 3:

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出:false

提示:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

一、模式识别

1.棋盘格:回溯法

棋盘格问题,回溯法典型应用,用回溯算法

层间:word内顺序访问

层内:board遍历或上一个字母上下左右

无需找到所有结果,找到第一个结果后返回

2.搜索方式

1.word首字母在board中二维遍历

2.word内(层间)顺序访问,剩余字母分别搜索上一个字母的上下左右

3.访问过的字母不可以重复访问

二.代码实现

1.基础实现

class Solution:def get_candidate(self, board, visited, i, j):candidate = []if i - 1 >= 0 and not visited[i - 1][j]:candidate.append((board[i - 1][j], i - 1, j))if j - 1 >= 0 and not visited[i][j - 1]:candidate.append((board[i][j - 1], i, j - 1))if i + 1 < len(board) and not visited[i + 1][j]:candidate.append((board[i + 1][j], i + 1, j))if j + 1 < len(board[0]) and not visited[i][j + 1]:candidate.append((board[i][j + 1], i, j + 1))return candidatedef backtracking(self, board, word, visited, start_idx, i, j):if start_idx == len(word):return Trueif start_idx == 0:for i in range(len(board)):for j in range(len(board[i])):if board[i][j] == word[0]:visited[i][j] = Trueif self.backtracking(board, word, visited, 1, i, j):return Truevisited[i][j] = Falseelse:for ch, a, b in self.get_candidate(board, visited, i, j):if ch == word[start_idx]:visited[a][b] = Trueif self.backtracking(board, word, visited, start_idx + 1, a, b):return Truevisited[a][b] = Falsereturn Falsedef exist(self, board: List[List[str]], word: str) -> bool:visited = [[False] * len(board[0]) for _ in range(len(board))]return self.backtracking(board, word, visited, 0, -1, -1)

start_idx记录访问顺序

visited用于标记访问过的字母

首字母二维遍历board

剩余字母层间顺序访问,层内访问上一个字母在board中的上下左右

耗时:2000ms-4000ms

2.启发式搜索

class Solution:def get_candidate(self, board, i, j):candidate = []if i - 1 >= 0 and board[i - 1][j]:candidate.append((board[i - 1][j], i - 1, j))if j - 1 >= 0 and board[i][j - 1]:candidate.append((board[i][j - 1], i, j - 1))if i + 1 < len(board) and board[i + 1][j]:candidate.append((board[i + 1][j], i + 1, j))if j + 1 < len(board[0]) and board[i][j + 1]:candidate.append((board[i][j + 1], i, j + 1))return candidatedef backtracking(self, board, word, start_idx, i, j):if start_idx == len(word):return Trueif start_idx == 0:for i in range(len(board)):for j in range(len(board[i])):if board[i][j] == word[0]:board[i][j] = Falseif self.backtracking(board, word, 1, i, j):return Trueboard[i][j] = word[0]else:for ch, a, b in self.get_candidate(board, i, j):if ch == word[start_idx]:board[a][b] = Falseif self.backtracking(board, word, start_idx + 1, a, b):return Trueboard[a][b] = word[start_idx]return Falsedef exist(self, board: List[List[str]], word: str) -> bool:# visited = [[False] * len(board[0]) for _ in range(len(board))]cnt=Counter(c for row in board for c in row)if not cnt>=Counter(word):return Falseif cnt[word[-1]]<cnt[word[0]]:word=word[::-1]return self.backtracking(board, word, 0, -1, -1)

在提交排行榜中看到的启发式搜索

思路:主要搜索开销都在第一步的board的遍历,于是从第一步开刀

实现逻辑:如果尾端字母在board出现频率低于首端则word反序

计算开销直接降到0ms-3ms

相关文章:

刷题记录 HOT100回溯算法-6:79. 单词搜索

题目&#xff1a;79. 单词搜索 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 单词必须按照字母顺序&#xff0c;通过相邻的单元格内的字母构成&#xff0c;其中“相邻…...

JavaScript系列(52)--编译优化技术详解

JavaScript编译优化技术详解 &#x1f680; 今天&#xff0c;让我们深入探讨JavaScript的编译优化技术。通过理解和应用这些技术&#xff0c;我们可以显著提升JavaScript代码的执行效率。 编译优化基础概念 &#x1f31f; &#x1f4a1; 小知识&#xff1a;JavaScript引擎通常…...

Ollama+DeepSeek本地大模型部署

1、Ollama 官网&#xff1a;https://ollama.com/ Ollama可以干什么&#xff1f; 可以快速在本地部署和管理各种大语言模型&#xff0c;操作命令和dokcer类似。 mac安装ollama&#xff1a; # 安装ollama brew install ollama# 启动ollama服务&#xff08;默认11434端口&#xf…...

在 WSL2 中重启 Ubuntu 实例

在 WSL2 中重启 Ubuntu 实例&#xff0c;可以按照以下步骤操作&#xff1a; 方法 1: 使用 wsl 命令 关闭 Ubuntu 实例: 打开 PowerShell 或命令提示符&#xff0c;运行以下命令&#xff1a; wsl --shutdown这会关闭所有 WSL2 实例。 重新启动 Ubuntu: 再次打开 Ubuntu&#x…...

【ts + java】古玩系统开发总结

src别名的配置 开发中文件和文件的关系会比较复杂&#xff0c;我们需要给src文件夹一个别名吧 vite.config.js import { defineConfig } from vite import vue from vitejs/plugin-vue import path from path// https://vitejs.dev/config/ export default defineConfig({pl…...

机器学习周报-文献阅读

文章目录 摘要Abstract 1 相关知识1.1 WDN建模1.2 掩码操作&#xff08;Masking Operation&#xff09; 2 论文内容2.1 WDN信息的数据处理2.2 使用所收集的数据构造模型2.2.1 Gated graph neural network2.2.2 Masking operation2.2.3 Training loss2.2.4 Evaluation metrics 2…...

LabVIEW微位移平台位移控制系统

本文介绍了基于LabVIEW的微位移平台位移控制系统的研究。通过设计一个闭环控制系统&#xff0c;针对微位移平台的通信驱动问题进行了解决&#xff0c;并提出了一种LabVIEW的应用方案&#xff0c;用于监控和控制微位移平台的位移&#xff0c;从而提高系统的精度和稳定性。 项目背…...

fpga系列 HDL:XILINX Vivado ILA FPGA 在线逻辑分析

ILA为内置逻辑分析仪&#xff0c;通过JTAG与FPGA连接&#xff0c;程序在真实硬件中运行&#xff0c;功能类似Quaruts的SignalTap II 。 ip创建ila 使用ila ip核 timescale 1ns / 1ps module HLSLED(input wire clk ,input wire rst_n ,output wire led);// reg led_o_i 1…...

刷题记录 贪心算法-2:455. 分发饼干

题目&#xff1a;455. 分发饼干 难度&#xff1a;简单 假设你是一位很棒的家长&#xff0c;想要给你的孩子们一些小饼干。但是&#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i&#xff0c;都有一个胃口值 g[i]&#xff0c;这是能让孩子们满足胃口的饼干的最小尺寸&a…...

Android --- CameraX讲解

预备知识 surface surfaceView SurfaceHolder surface 是什么&#xff1f; 一句话来说&#xff1a; surface是一块用于填充图像数据的内存。 surfaceView 是什么&#xff1f; 它是一个显示surface 的View。 在app中仍在 ViewHierachy 中&#xff0c;但在wms 中可以理解为…...

ElasticSearch view

基础知识类 elasticsearch和数据库之间区别&#xff1f; elasticsearch&#xff1a;面向文档&#xff0c;数据以文档的形式存储&#xff0c;即JSON格式的对象。更强调数据的搜索、索引和分析。 数据库&#xff1a;更侧重于事务处理、数据的严格结构化和完整性&#xff0c;适用于…...

list的使用,及部分功能的模拟实现(C++)

目录&#xff08;文章中"节点"和"结点"是同一个意思&#xff09; 1. list的介绍及使用 1.1 list的介绍 1.2 list的使用 1.2.1 list的构造 1.2.2 list iterator的使用 1.2.3 list capacity 1.2.4 list element access 1.2.5 list modifiers 1.2.6 list…...

联想Y7000+RTX4060+i7+Ubuntu22.04运行DeepSeek开源多模态大模型Janus-Pro-1B+本地部署

直接上手搓了&#xff1a; conda create -n myenv python3.10 -ygit clone https://github.com/deepseek-ai/Janus.gitcd Januspip install -e .pip install webencodings beautifulsoup4 tinycss2pip install -e .[gradio]pip install pexpect>4.3python demo/app_januspr…...

[Spring] Gateway详解

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏: &#x1f9ca; Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm1001.2014.3001.5482 &#x1f355; Collection与…...

音叉模态分析

目录 0 序言 1 自由状态下模态求解 1.1 添加模态项目 1.2 生成网格 1.3 设置最大模态阶数 1.4 求解 1.5 结果查看 1.6 结果分析 2 音叉能否释放频率440Hz的音调 3 预应力模态求解 3.1 静态结构分析 3.1.1 添加静态结构项目 3.1.2生成网格 3.1.3添加边界条件 3.1…...

BW AO/工作簿权限配置

场景&#xff1a; 按事业部配置工作簿权限&#xff1b; 1、创建用户 事务码&#xff1a;SU01&#xff0c;用户主数据的维护&#xff0c;可以创建、修改、删除、锁定、解锁、修改密码等 用户设置详情页 2、创建权限角色 用户的权限菜单是通过权限角色分配来实现的 2.1、自定…...

C++ 字母大小写转换两种方法统计数字字符的个数

目录 题目&#xff1a; 代码1&#xff1a; 代码2&#xff1a; 题目描述输入一行字符&#xff0c;统计出其中数字字符的个数。 代码如下&#xff1a; 判断⼀个字符是否是数字字符有⼀个函数是 isdigit ,可以直接使⽤。 代码如下&#xff1a; 题目&#xff1a; 大家都知道…...

如何使用 ChatBox AI 简化本地模型对话操作

部署模型请看上一篇帖子&#xff1a;本地部署DeepSeek教程&#xff08;Mac版本&#xff09;-CSDN博客 使用 ChatBox AI 简化本地模型对话操作&#xff1a; 打开 ChatBox AI 官网&#xff1a;Chatbox AI官网&#xff1a;办公学习的AI好助手&#xff0c;全平台AI客户端&#xf…...

前端面试笔试题目(一)

以下模拟了大厂前端面试流程&#xff0c;并给出了涵盖HTML、CSS、JavaScript等基础和进阶知识的前端笔试题目&#xff0c;以帮助你更好地准备面试。 面试流程模拟 1. 自我介绍&#xff08;5 - 10分钟&#xff09;&#xff1a;面试官会请你进行简单的自我介绍&#xff0c;包括…...

Docker Hello World

Docker Hello World 引言 Docker 是一个开源的应用容器引擎,可以让开发者打包他们的应用以及应用的依赖包到一个可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化。本文将带领您从零开始,学习如何使用 Docker 运行一个简单的 "Hello World"…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

解析“道作为序位生成器”的核心原理

解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制&#xff0c;重点解析"道作为序位生成器"的核心原理与实现框架&#xff1a; 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...