LeetCode题解 20(17,79) 电话号码的字母组合,单词搜索<回溯>
文章目录
- 电话号码的字母组合(17)
- 代码解答
- 单词搜索(79)
- 代码解答
电话号码的字母组合(17)

思路: 根据题意我们必须根据数字获取对应的字符数组,因此我们先定义1个字符数组表示这个电话表
private String[] letters = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
接着我们定义结果集,同时我们对特殊case进行判断
List<String> res = new ArrayList<>();
if(digits == null || digits.length() == 0){return res;}
回溯部分的思路(helper):
我们需要传入一个可变的字符串StringBuilder,因为StringBuilder的性能比较高,还要我们输入的数字digits。
我们可以看到 当我们输入2位数,显示出来的字符串长度也就是2,因此将这这个条件作为退出递归的条件,当满足这个条件时就将可变字符串加入结果集,也就是我们要的答案。
public void helper(StringBuilder curr,String digits){if(curr.length() == digits.length()){res.add(curr.toString());return;}
我们要获取我们输入的每一个数字,从而获取对应的字符数组,
int num = digits.charAt(curr.length())-'0';String s1 = letters[num];
遍历我们获取的整个字符数组,将它们依次加入可变字符串curr中,重复以上操作。
for(char c : s1.toCharArray()){curr.append(c);helper(curr,digits);curr.deleteCharAt(curr.length()-1);}
代码解答
class Solution {private String[] letters = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};List<String> res = new ArrayList<>();public List<String> letterCombinations(String digits) {if(digits == null || digits.length() == 0){return res;}helper(new StringBuilder(),digits);return res;}public void helper(StringBuilder curr,String digits){if(curr.length() == digits.length()){res.add(curr.toString());return;}int num = digits.charAt(curr.length())-'0';String s1 = letters[num];for(char c : s1.toCharArray()){curr.append(c);helper(curr,digits);curr.deleteCharAt(curr.length()-1);}}
}
单词搜索(79)

这道题就是它给了我们一个二维数组,我们需要去根据我们输入的字符串去找在这个表格中接连出现的。如果有就返回true。
思路:
我需要先获取这个二位数组的长,宽,我们输入字符串的长度,并且我们将这个二维数组,变成布尔类型的字符数组,当检查到一个就将此位置置为true。我们定义方法search去搜索,传入的参数分别是i,j,(start)0为我们输入的字符串的字符数组的起始索引。

class Solution {//先定义长和宽int m;int n;int w;char[] letters;char[][] board;boolean[][] visted;public boolean exist(char[][] board, String word) {this.m = board.length;this.n = board[0].length;this.w = word.length();this.letters = word.toCharArray();this.board = board;this.visted = new boolean[m][n];for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){//0是字符串数组的起始索引boolean res = search(i,j,0);if(res){return true;}}}return false;}
当我们的start到达了数组的最大长度,就表示我们整个字符串都已经遍历完成,这时就返回true。
当我们的i,j不在二维数组里面也就是说出边界了,或者某个字符不等于二维数组里面的字符。这时通通返回false。
if(i<0 || j<0 || i>=m || j>=n || letters[start] != board[i][j]){return false;}
接着我们去遍历二维数组每四个方向
boolean res = search(i+1,j,start+1) || search(i,j+1,start+1) || search(i-1,j,start+1) ||search(i,j-1,start+1);
代码解答
class Solution {//先定义长和宽int m;int n;int w;char[] letters;char[][] board;boolean[][] visted;public boolean exist(char[][] board, String word) {this.m = board.length;this.n = board[0].length;this.w = word.length();this.letters = word.toCharArray();this.board = board;this.visted = new boolean[m][n];for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){//0是字符串数组的起始索引boolean res = search(i,j,0);if(res){return true;}}}return false;}public boolean search(int i,int j,int start){if(start >= w){return true;}if(i<0 || j<0 || i>=m || j>=n || letters[start] != board[i][j]){return false;}board[i][j] += 52;boolean res = search(i+1,j,start+1) || search(i,j+1,start+1) || search(i-1,j,start+1) ||search(i,j-1,start+1);board[i][j] -= 52;return res;}
}
相关文章:
LeetCode题解 20(17,79) 电话号码的字母组合,单词搜索<回溯>
文章目录电话号码的字母组合(17)代码解答单词搜索(79)代码解答电话号码的字母组合(17) 思路: 根据题意我们必须根据数字获取对应的字符数组,因此我们先定义1个字符数组表示这个电话表 private String[] letters {"","","abc","…...
路径之谜 蓝桥杯 89
题目描述小明冒充 X 星球的骑士,进入了一个奇怪的城堡。城堡里边什么都没有,只有方形石头铺成的地面。假设城堡地面是 nn 个方格。如下图所示。按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着走,也不…...
Mysql数据库如何调优
MYSQL数据库调优 索引 1、对于常用的查询字段加索引,但如果常用字段只有几个常量值就不需要加索引,或者使用索引会失效的情况; 2、索引失效的情况: 1、索引列使用函数,计算(加减乘除等) …...
CAN(FD)记录仪在新能源汽车整车控制器(VCU)、电池管理系统(BMS)、电机控制器(MCU)、发动机ECU中的应用,免去出差烦恼
今天介绍CAN(FD)记录仪在新能源汽车整车控制器(VCU)、电池管理系统(BMS)、电机控制器(MCU)、发动机ECU中的应用 第一步:新能源汽车整车控制器(VCU)先供上电,…...
【设计模式】23种设计模式之七大原则
【设计模式】23种设计模式之七大原则什么是设计模式的原则1、单一职责原则基本介绍案例分析注意事项2、接口隔离原则基本介绍案例分析代码实现3、依赖倒转原则基本介绍案例分析依赖传递的三种方式注意事项4、里氏替换原则关于继承性的思考和说明基本介绍案例分析5、开闭原则ocp…...
python - 文件操作
1. 概念 计算机内存通常分为两种类型:主存储器和辅助存储器。 主存储器是计算机中最重要的存储器类型之一。它是计算机中用于存储正在运行的程序和数据的存储器。主存储器通常是易失性的,这意味着当计算机关闭时,其中存储的数据将被删除。主存…...
docker打包golang应用
一、错误的打包方式在本地环境编译,然后将可执行程序放入 alpine(docker.io/alpine:latest)准备web程序package mainimport ("fmt""net/http" )func main() {server : &http.Server{Addr: ":8888",}http.HandleFunc("/"…...
redis 内容总结
目录redis 内容列举Redis和Memcached比较Redis简介1、Redis 数据结构2、Redis的持久化机制3、Redis 内容管理(淘汰策略/删除策略)4、Redis 事务5、Redis 缓存三大问题6、Redis 集群7、Redis 应用redis 内容列举 官网:https://redis.io/ 中文…...
贪心算法(一)
一、概念 贪心算法的核心思想是,在处理一个大问题时,划分为多个局部并在每个局部选择最优解,并且认为在每个局部选择最优解,那么最后全局的问题得到的就是最优解。 贪心算法可以解决一些问题,但是不适用于所有问题&a…...
【栈和队列OJ题】有效的括号用队列实现栈用栈实现队列设计循环队列
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯长路漫漫浩浩,万事皆有期待 文章目录OJ题1.有效的括号1.1…...
kuernetes 资源对象分析报错
文章目录1. pod 状态1.1 容器启动错误类型1.2 ImagePullBackOff 错误1.3 CrashLoopBackOff1.4 Pending2. Service 连接状态3. Ingress 连接状态1. pod 状态 创建一个 pod-status.yaml apiVersion: v1 kind: Pod metadata:name: runninglabels:app: nginx spec:containers:- na…...
动态内存的开辟
🐶博主主页:ᰔᩚ. 一怀明月ꦿ ❤️🔥专栏系列:线性代数,C初学者入门训练,题解C,C的使用文章,「初学」C 🔥座右铭:“不要等到什么都没有了,才下…...
【蓝桥杯-筑基篇】搜索
🍓系列专栏:蓝桥杯 🍉个人主页:个人主页 目录 递归树 1.递归构建二进制串 2.全排列的 DFS 解法 3.全排列的 BFS 解法 4.数的划分法 5.图书推荐 递归树 递归树是一种用于分析递归算法时间复杂度的工具。它可以将递归算法的执行过程可视化…...
week5-质数-最大公约数-快速幂-组合计数-博弈论
蓝桥 等差数列——欧几里得算法质数质数的判定——试除法分解质因数——试除法筛质数——埃氏筛法筛质数——线性筛法质数问题质数距离约数试除法求约数约数个数约数之和最大公约数-欧几里得算法(辗转相除法)扩展欧几里得算法裴蜀定理应用——线性同余方程消灭老鼠Hankson的趣…...
CloudCompare 二次开发(6)——插件中拖拽添加Qt窗口(区域生长算法为例)
目录 一、概述二、插件制作三、Cmake编译四、插件代码五、结果展示一、概述 手动拖拽的方式搭建Qt对话框界面的制作流程,以PCL中的点云区域生长算法为例进行制作。 二、插件制作 1、将....\plugins\example路径下的ExamplePlugin复制一份并修改名字为CCPointCloudProcess。 …...
2023值得推荐的高颜值Vue3.0 Web PC端UI框架,赶紧收藏学习!
Hello,我是前端胡说,本期给大家带来2023值得推荐的Vue3.0 UI组件库,希望大家喜欢! Vue3 正式发布已经有一段时间了,2022年2月也正式变成 Vue 项目的默认版本。在过去一年多的时间里,各大组件库、框架也紧跟…...
Springboot项目Aop、拦截器、过滤器横向对比
前言伟人曾经说过,没有调查就没有发言权(好像是伟人说的,不管谁说的,这句话是正确的),有些东西看着简单,张口就来,但很有可能是错的。我个人的经验是,aop、过滤器、拦截器的实现方式很简单&…...
为了之后找工作不被虐,每天刷3道《剑指offer》Day-1
本文已收录于专栏🌻《刷题笔记》文章目录前言💖 1、二维数组中的查找题目描述思路💖 2、替换空格题目描述思路💖 3、从尾到头打印链表题目描述思路一(反转函数)思路二(递归)思路二&a…...
Linux-磁盘管理介绍
Linux-磁盘管理介绍 计算硬盘介绍 硬盘是计算机主要存储媒介之一,由一个或者多个铝制或者玻璃制的碟片组成,碟片外覆盖有铁磁性材料,硬盘内部由磁道、柱面、扇区、磁头等部件组成; cylinder:柱面sector:扇区 磁道与…...
爬虫架构(一):爬虫中的去重处理
目录一、概要二、去重应用场景以及基本原理2.1 爬虫中什么业务需要使用去重2.2 去重实现的基本原理2.3 根据原始数据进行去重判断2.4 根据原始数据的特征值进行去重判断2.5 临时去重容器与持久化去重容器2.6 常用几种特殊的原始数据特征值计算三、基于信息摘要算法的去重3.1 信…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
