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

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) 思路: 根据题意我们必须根据数字获取对应的字符数组&#xff0c;因此我们先定义1个字符数组表示这个电话表 private String[] letters {"","","abc","…...

路径之谜 蓝桥杯 89

题目描述小明冒充 X 星球的骑士&#xff0c;进入了一个奇怪的城堡。城堡里边什么都没有&#xff0c;只有方形石头铺成的地面。假设城堡地面是 nn 个方格。如下图所示。按习俗&#xff0c;骑士要从西北角走到东南角。可以横向或纵向移动&#xff0c;但不能斜着走&#xff0c;也不…...

Mysql数据库如何调优

MYSQL数据库调优 索引 1、对于常用的查询字段加索引&#xff0c;但如果常用字段只有几个常量值就不需要加索引&#xff0c;或者使用索引会失效的情况&#xff1b; 2、索引失效的情况&#xff1a; ​ 1、索引列使用函数&#xff0c;计算&#xff08;加减乘除等&#xff09; …...

CAN(FD)记录仪在新能源汽车整车控制器(VCU)、电池管理系统(BMS)、电机控制器(MCU)、发动机ECU中的应用,免去出差烦恼

今天介绍CAN(FD)记录仪在新能源汽车整车控制器&#xff08;VCU&#xff09;、电池管理系统&#xff08;BMS&#xff09;、电机控制器&#xff08;MCU&#xff09;、发动机ECU中的应用 第一步&#xff1a;新能源汽车整车控制器&#xff08;VCU&#xff09;先供上电&#xff0c…...

【设计模式】23种设计模式之七大原则

【设计模式】23种设计模式之七大原则什么是设计模式的原则1、单一职责原则基本介绍案例分析注意事项2、接口隔离原则基本介绍案例分析代码实现3、依赖倒转原则基本介绍案例分析依赖传递的三种方式注意事项4、里氏替换原则关于继承性的思考和说明基本介绍案例分析5、开闭原则ocp…...

python - 文件操作

1. 概念 计算机内存通常分为两种类型&#xff1a;主存储器和辅助存储器。 主存储器是计算机中最重要的存储器类型之一。它是计算机中用于存储正在运行的程序和数据的存储器。主存储器通常是易失性的&#xff0c;这意味着当计算机关闭时&#xff0c;其中存储的数据将被删除。主存…...

docker打包golang应用

一、错误的打包方式在本地环境编译&#xff0c;然后将可执行程序放入 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 内容管理&#xff08;淘汰策略/删除策略&#xff09;4、Redis 事务5、Redis 缓存三大问题6、Redis 集群7、Redis 应用redis 内容列举 官网&#xff1a;https://redis.io/ 中文…...

贪心算法(一)

一、概念 贪心算法的核心思想是&#xff0c;在处理一个大问题时&#xff0c;划分为多个局部并在每个局部选择最优解&#xff0c;并且认为在每个局部选择最优解&#xff0c;那么最后全局的问题得到的就是最优解。 贪心算法可以解决一些问题&#xff0c;但是不适用于所有问题&a…...

【栈和队列OJ题】有效的括号用队列实现栈用栈实现队列设计循环队列

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录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…...

动态内存的开辟

&#x1f436;博主主页&#xff1a;ᰔᩚ. 一怀明月ꦿ ❤️‍&#x1f525;专栏系列&#xff1a;线性代数&#xff0c;C初学者入门训练&#xff0c;题解C&#xff0c;C的使用文章&#xff0c;「初学」C &#x1f525;座右铭&#xff1a;“不要等到什么都没有了&#xff0c;才下…...

【蓝桥杯-筑基篇】搜索

&#x1f353;系列专栏:蓝桥杯 &#x1f349;个人主页:个人主页 目录 递归树 1.递归构建二进制串 2.全排列的 DFS 解法 3.全排列的 BFS 解法 4.数的划分法 5.图书推荐 递归树 递归树是一种用于分析递归算法时间复杂度的工具。它可以将递归算法的执行过程可视化&#xf…...

week5-质数-最大公约数-快速幂-组合计数-博弈论

蓝桥 等差数列——欧几里得算法质数质数的判定——试除法分解质因数——试除法筛质数——埃氏筛法筛质数——线性筛法质数问题质数距离约数试除法求约数约数个数约数之和最大公约数-欧几里得算法(辗转相除法)扩展欧几里得算法裴蜀定理应用——线性同余方程消灭老鼠Hankson的趣…...

CloudCompare 二次开发(6)——插件中拖拽添加Qt窗口(区域生长算法为例)

目录 一、概述二、插件制作三、Cmake编译四、插件代码五、结果展示一、概述 手动拖拽的方式搭建Qt对话框界面的制作流程,以PCL中的点云区域生长算法为例进行制作。 二、插件制作 1、将....\plugins\example路径下的ExamplePlugin复制一份并修改名字为CCPointCloudProcess。 …...

2023值得推荐的高颜值Vue3.0 Web PC端UI框架,赶紧收藏学习!

Hello&#xff0c;我是前端胡说&#xff0c;本期给大家带来2023值得推荐的Vue3.0 UI组件库&#xff0c;希望大家喜欢&#xff01; Vue3 正式发布已经有一段时间了&#xff0c;2022年2月也正式变成 Vue 项目的默认版本。在过去一年多的时间里&#xff0c;各大组件库、框架也紧跟…...

Springboot项目Aop、拦截器、过滤器横向对比

前言伟人曾经说过&#xff0c;没有调查就没有发言权(好像是伟人说的&#xff0c;不管谁说的&#xff0c;这句话是正确的)&#xff0c;有些东西看着简单&#xff0c;张口就来&#xff0c;但很有可能是错的。我个人的经验是&#xff0c;aop、过滤器、拦截器的实现方式很简单&…...

为了之后找工作不被虐,每天刷3道《剑指offer》Day-1

本文已收录于专栏&#x1f33b;《刷题笔记》文章目录前言&#x1f496; 1、二维数组中的查找题目描述思路&#x1f496; 2、替换空格题目描述思路&#x1f496; 3、从尾到头打印链表题目描述思路一&#xff08;反转函数&#xff09;思路二&#xff08;递归&#xff09;思路二&a…...

Linux-磁盘管理介绍

Linux-磁盘管理介绍 计算硬盘介绍 硬盘是计算机主要存储媒介之一&#xff0c;由一个或者多个铝制或者玻璃制的碟片组成&#xff0c;碟片外覆盖有铁磁性材料&#xff0c;硬盘内部由磁道、柱面、扇区、磁头等部件组成; cylinder&#xff1a;柱面sector&#xff1a;扇区 磁道与…...

爬虫架构(一):爬虫中的去重处理

目录一、概要二、去重应用场景以及基本原理2.1 爬虫中什么业务需要使用去重2.2 去重实现的基本原理2.3 根据原始数据进行去重判断2.4 根据原始数据的特征值进行去重判断2.5 临时去重容器与持久化去重容器2.6 常用几种特殊的原始数据特征值计算三、基于信息摘要算法的去重3.1 信…...

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

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

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...