利用辗转相除法解决字符串公因子问题--LeetCode1071《Blind-Stab》

2023-10-18 18:20

本文主要是介绍利用辗转相除法解决字符串公因子问题--LeetCode1071《Blind-Stab》,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

有没有那么一瞬间,看到某个思路想法,突然眼前一亮觉得牛逼的时刻?

今天在力扣做题的时候,做到一个简单但是解法很有意思的题目,题号是1071,题目如下。

   

   

为什么说这道题很妙,就是它用到了辗转相除法去解决字符串找公共子因子。同时利用了递归调用。下面我们来分析一下这道题;

思路:

1、暴力法,一开始我用的就是暴力法,就是简单的找,利用那个更短的字符串,先拆第一个,判断是否是公共因子,不是在第一个和第二个,,,,直到找到为止,很明显,这种方法太low了,而且太傻了。

2、利用辗转相除法。怎么讲?

辗转相除法:

辗转相除法也称欧几里得算法,也就是大数学家欧几里得发明的求最大公因数算法嘛:欧几里得算法(辗转相除法)。

证明这里就算了,不涉及,我们知道怎么用就行了。

1、两个数a,b。这里用25 和 10来说;找这两个数的最大公因数;

2、先用大的去对小的取余(也可以反过来,但是结果可能是负的):25%10= 2....5;

3、然后用上次被取余的数也就是10,去对余数也就是5取余,也就是:10%5=2....0;

4、当余数为0的时候,那么这最后一次被取余的数也就是5就是a和b也就是25和10的最大公因数;

5、关键算法就是:

        {int a = 25;int b = 10;int c = 25;while(c!=0){c = a%b;a = b;b = c;}return a;}

 3、其实如果我们不去简单的遍历暴力破解,那我们就去利用辗转相除法解决这道公因子问题。一个是数,一个是字符串,看起来没什么联系,但是它们一个找的是数的公共因子,一个找的是字符串的公共字符串因子,这其实就有了联系。

解题:

1、因为是字符串,并且找的是公共因子,那我们可以肯定,如果这个公共因子存在,那么这个公共因子肯定是str1和str2都含有的一个字符串,不然怎么叫公共子串呢,并且,这个子串的长度一定小于等于也就是不超过Math.abs(str1.length() - str2.length())即两个字符串的长度差。

2、但现在好像我们求的X更加特殊,就是str1和str2都是X的倍数,也就是n个X的叠加,这就不单单是公共因子问题了。

3、因为上面说的这个条件,那么,若这个X存在,必然是满足  str1 + str2 == str2 +str1.为什么这么讲呢,因为str1和str2都是若干个X组成,假设str1为XXX...  ,str2为XXX... ,那么很明显,相加是会满足上面那个式子的,反过来说,如果不满足这个条件,那它就不存在这个X,自然返回的就是空字符串"";

4、好,那么我们已经解决了不满足的那一半,接下来是满足的那一半,问题就是变成了存在且找出的问题了。我们知道既然str1和str2都是X倍数,那么str1和str2中必然皆存在X,所以是关键就是找到X,既然都存在X,那么我们在str1或str2中截取X就行了,那具体是截取哪一段呢?

5、既然是X的叠加,那么str1和str2从角标0开始肯定是属于X的,只是关键我们不知道结束位子在哪,当然可以用暴力法一个一个增加去找,但是这样没意思,而且太慢了,所以我们想到了利用我们的辗转相除法,因为我们找的是数字,也就是该截取的长度,所以才可以用辗转相除法。公共最大因子,最大公因数。

6、我们将str1和str2的长度作为参数传进一个找最大公因数的方法,直到找到这个最大公因数的长度,返回,不然就一直找。条件就是余数为0.

7、可以利用递归调用,return a==0?b:gcd(b%1,a);用的比较灵活,找到了就返回a这个余数,没有就交换参数变量继续找。

8、返回的长度,直接截取就行。下面看代码。

class Solution {public String gcdOfStrings(String str1, String str2) {if (!(str1 + str2).equals(str2 + str1))return "";return str1.substring(0,gcd(str1.length(),str2.length()));}public int gcd(int a,int b){return a == 0 ? b :gcd(b%a,a);}
}

 所以,就是这么短,就是这么快,就是这么惊艳。

总结:

1、我们解决问题不应该仅仅局限于问题本事,应该跳出问题看共性,看本质,也就是归为一类问题。

2、辗转相除法还是很牛逼的,看来不单单可以利用于找最大公因数,而是可以拓展到一系列相似问题。

3、递归写的也很漂亮啊,多学习。

4、陌生人,一起加油,一起坚持!

 

 

 

 

 

 

 

 

 

这篇关于利用辗转相除法解决字符串公因子问题--LeetCode1071《Blind-Stab》的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/234342

相关文章

Springboot项目启动失败提示找不到dao类的解决

《Springboot项目启动失败提示找不到dao类的解决》SpringBoot启动失败,因ProductServiceImpl未正确注入ProductDao,原因:Dao未注册为Bean,解决:在启... 目录错误描述原因解决方法总结***************************APPLICA编

MySQL常用字符串函数示例和场景介绍

《MySQL常用字符串函数示例和场景介绍》MySQL提供了丰富的字符串函数帮助我们高效地对字符串进行处理、转换和分析,本文我将全面且深入地介绍MySQL常用的字符串函数,并结合具体示例和场景,帮你熟练... 目录一、字符串函数概述1.1 字符串函数的作用1.2 字符串函数分类二、字符串长度与统计函数2.1

解决pandas无法读取csv文件数据的问题

《解决pandas无法读取csv文件数据的问题》本文讲述作者用Pandas读取CSV文件时因参数设置不当导致数据错位,通过调整delimiter和on_bad_lines参数最终解决问题,并强调正确参... 目录一、前言二、问题复现1. 问题2. 通过 on_bad_lines=‘warn’ 跳过异常数据3

解决RocketMQ的幂等性问题

《解决RocketMQ的幂等性问题》重复消费因调用链路长、消息发送超时或消费者故障导致,通过生产者消息查询、Redis缓存及消费者唯一主键可以确保幂等性,避免重复处理,本文主要介绍了解决RocketM... 目录造成重复消费的原因解决方法生产者端消费者端代码实现造成重复消费的原因当系统的调用链路比较长的时

深度解析Nginx日志分析与499状态码问题解决

《深度解析Nginx日志分析与499状态码问题解决》在Web服务器运维和性能优化过程中,Nginx日志是排查问题的重要依据,本文将围绕Nginx日志分析、499状态码的成因、排查方法及解决方案展开讨论... 目录前言1. Nginx日志基础1.1 Nginx日志存放位置1.2 Nginx日志格式2. 499

SpringBoot监控API请求耗时的6中解决解决方案

《SpringBoot监控API请求耗时的6中解决解决方案》本文介绍SpringBoot中记录API请求耗时的6种方案,包括手动埋点、AOP切面、拦截器、Filter、事件监听、Micrometer+... 目录1. 简介2.实战案例2.1 手动记录2.2 自定义AOP记录2.3 拦截器技术2.4 使用Fi

kkFileView启动报错:报错2003端口占用的问题及解决

《kkFileView启动报错:报错2003端口占用的问题及解决》kkFileView启动报错因office组件2003端口未关闭,解决:查杀占用端口的进程,终止Java进程,使用shutdown.s... 目录原因解决总结kkFileViewjavascript启动报错启动office组件失败,请检查of

C# $字符串插值的使用

《C#$字符串插值的使用》本文介绍了C#中的字符串插值功能,详细介绍了使用$符号的实现方式,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录$ 字符使用方式创建内插字符串包含不同的数据类型控制内插表达式的格式控制内插表达式的对齐方式内插表达式中使用转义序列内插表达式中使用

SQL Server安装时候没有中文选项的解决方法

《SQLServer安装时候没有中文选项的解决方法》用户安装SQLServer时界面全英文,无中文选项,通过修改安装设置中的国家或地区为中文中国,重启安装程序后界面恢复中文,解决了问题,对SQLSe... 你是不是在安装SQL Server时候发现安装界面和别人不同,并且无论如何都没有中文选项?这个问题也

SpringBoot 异常处理/自定义格式校验的问题实例详解

《SpringBoot异常处理/自定义格式校验的问题实例详解》文章探讨SpringBoot中自定义注解校验问题,区分参数级与类级约束触发的异常类型,建议通过@RestControllerAdvice... 目录1. 问题简要描述2. 异常触发1) 参数级别约束2) 类级别约束3. 异常处理1) 字段级别约束