【LeetCode每日一题】Leetcode 1071.字符串的最大公因子
Leetcode 1071.字符串的最大公因子
题目描述:
对于字符串 s 和 t,只有在 s = t + t + t + … + t + t(t 自身连接 1 次或多次)时,我们才认定 t 能除尽 s。
给定两个字符串 str1 和 str2 。返回 最长字符串 x,要求满足 x 能除尽 str1 且 x 能除尽 str2
示例 1:
输入: str1 = "ABCABC", str2 = "ABC"
输出: "ABC"
示例 2:
输入: str1 = "ABABAB", str2 = "ABAB"
输出: "AB"
示例 3:
输入: str1 = "LEET", str2 = "CODE"
输出: ""
提示:
1 <= str1.length, str2.length <= 1000str1和str2仅由小写字母组成。
Java 实现代码
class Solution {public String gcdOfStrings(String str1, String str2) {if (!str1.concat(str2).equals(str2.concat(str1))) {return "";}return str1.substring(0, gcd(str1.length(), str2.length()));}public int gcd(int a, int b) {int remainder = a % b;while (remainder != 0) {a = b;b = remainder;remainder = a % b;}return b;}
}
解题思路:
- 核心思想是:对于两个数 a 和 b,它们的最大公约数等于 b 和 a % b 的最大公约数。
- 如果 a % b 不等于 0,那么递归计算 gcd(b, a % b)。
- 直到余数为 0,最后返回 b,即最大公约数。
复杂度分析:
- 时间复杂度:O(n) ,字符串拼接比较是否相等需要 O(n) 的时间复杂度,求两个字符串长度的最大公约数需要 O(logn) 的时间复杂度,所以总时间复杂度为 O(n+logn)=O(n) 。
- 空间复杂度:O(n) ,程序运行时建立了中间变量用来存储 str1 与 str2 的相加结果
相关文章:
【LeetCode每日一题】Leetcode 1071.字符串的最大公因子
Leetcode 1071.字符串的最大公因子 题目描述: 对于字符串 s 和 t,只有在 s t t t … t t(t 自身连接 1 次或多次)时,我们才认定 t 能除尽 s。 给定两个字符串 str1 和 str2 。返回 最长字符串 x,要…...
《C++:计算机视觉图像识别与目标检测算法优化的利器》
在当今科技飞速发展的时代,计算机视觉领域正经历着前所未有的变革与突破。图像识别和目标检测作为其中的核心技术,广泛应用于安防监控、自动驾驶、智能医疗等众多领域,其重要性不言而喻。而 C语言,凭借其卓越的性能、高效的资源控…...
大模型的构建与部署(2)——数据清洗
版权声明 本文原创作者:谷哥的小弟作者博客地址:http://blog.csdn.net/lfdfhl1. 数据清洗的必要性与影响 1.1 数据清洗对模型性能的影响 数据清洗是数据预处理的关键步骤,对于模型训练的性能和准确性有着直接的影响。原始数据中的缺失值、重复值、异常值以及数据格式不一致…...
试题转excel;word转excel;大风车excel
一、问题描述 一名教师朋友,偶尔会需要整理一些高质量的题目到excel中 以往都是手动复制搬运,几百道题几乎需要一个下午的时间 关键这些事,枯燥无聊费眼睛,实在是看起来就很蠢的工作 就想着做一个工具,可以自动处理…...
微信小程序webview和小程序通讯
1.背景介绍 1.1需要在小程序嵌入vr页面,同时在vr页面添加操作按钮与小程序进行通信交互 1.2开发工具:uniapp开发小程序 1.3原型图 功能:.点击体验官带看跳转小程序的体验官带看页面 功能:点击立即咨询唤起小程序弹窗打电话 2.…...
ChatGPT大模型 创作高质量文案的使用教程和案例
引言 随着人工智能技术的飞速发展,大语言模型如 ChatGPT 在创作文案、生成内容方面展现出了强大的能力。无论是个人用户还是企业用户,都可以利用 ChatGPT 提高工作效率、激发创意、甚至解决实际问题。本文将详细介绍 ChatGPT 如何帮助创作各类高质量文案,并通过具体案例展示…...
Vue Web开发(八)
1. VueWeb面包屑和tag的布局 本章节完成VueWeb面包屑和tag的布局,并且与左侧菜单联系,涉及组件间通信。 1.1. 页面创建 (1)首先我们先完成每个页面的路由,之前已经有home页面和user页面,缺少mail页面和其…...
element-ui实现table表格的嵌套(table表格嵌套)功能实现
最近在做电商类型的官网,希望实现的布局如下:有表头和表身,所以我首先想到的就是table表格组件。 表格组件中常见的就是:标题和内容一一对应: 像效果图中的效果,只用基础的表格布局是不行的,因…...
【考前预习】4.计算机网络—网络层
往期推荐 【考前预习】3.计算机网络—数据链路层-CSDN博客 【考前预习】2.计算机网络—物理层-CSDN博客 【考前预习】1.计算机网络概述-CSDN博客 目录 1.网络层概述 2.网络层提供的两种服务 3.分类编址的IPV4 4.无分类编址的IPV4—CIDR 5.IPV4地址应用规划 5.1使用定长子…...
【java】MDC
目录 1. 说明2. 作用3. 使用4. 与TraceID的关系5. 注意事项 1. 说明 1.MDC(Mapped Diagnostic Context)是一个用于在多线程环境中追踪和传递日志上下文信息的机制。2.映射诊断环境。3.MDC是一个线程本地的、可维护的、可传递的上下文环境。4.它允许开发…...
Android 好的开源库
1. 权限请求框架 GitHub - getActivity/XXPermissions: Android 权限请求框架,已适配 Android 14 2. 下载框架 GitHub - lingochamp/okdownload: A Reliable, Flexible, Fast and Powerful download engine....
Go 语言结构
Go 语言结构 Go 语言,也称为 Golang,是一种由 Google 开发和支持的静态类型、编译型编程语言。它于 2009 年首次发布,旨在提高多核处理器、网络资源和大型代码库的性能。Go 语言以其简洁的语法、并发支持和强大的标准库而闻名,特别适合构建高性能的网络服务和分布式系统。…...
【漆学军】MT5几个重要类库的使用例子
MT5编程,有两种方式,一种是函数式编程,一种是面向对象编程。 面向对象编程,会让我们编写代码变得非常简单。 面向对象编程,主要是要熟悉4个类库。 #include <Trade\PositionInfo.mqh> #include <Trade\Tra…...
在 Ubuntu 24.04.1 LTS (WSL) 中使用 openssl 生成 keybox.xml
看到“生成 keybox.xml”,大概率都会联想到 PIF 和 Tricky Store。这里就不多解释它们的用途了。最近在网上看到生成非 AOSP keybox 的教程,在这里做一些补充,并将代码打包成一个 Python 脚本。 参考自: Idea 提供者:…...
【JavaSE基础】第十六章:IO流
一、理解 1.简单而言:流就是内存与存储设备之间传输数据的通道、管道。 2.流的分类: (1) 按方向 ( 以 JVM 虚拟机为参照物 ) 【重点】 输入流:将< 存储设备 > 中的内容读入到 < 内存 > 中。 输…...
常见漏洞—SSRF_FastCGI
FastCGI协议 简介 Fast CGI源自旧版本的CGI 路由/结构图 # 访问url --> 浏览器生成HTTP请求报文 --> web server解析请求(例如nginx) web server 是内容的分发者 当访问静态页面时,web server 会直接返回资源,例如index.htm…...
LeetCode 283.移动零(超简单讲解)
283.移动零 题目示例示例1示例2 解题思路快慢指针实现设计 详细代码 题目 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 请注意 ,必须在不复制数组的情况下原地对数组进行操作。 示例 示例1 …...
GIS原理及应用、地理坐标系与投影坐标系
文章目录 一、GIS定义1.1 地理信息系统1.2 建模1.3 相关教程1.4 GIS前沿方向 二、GIS数据格式2.1 矢量2.2 栅格2.3 矢量与栅格的区别 三、GIS数据组织3.1 抽象3.2 分层3.3 栅格与切片 四、坐标系4.1 坐标系简介4.2 大地坐标系GCS4.3 投影坐标系PCS4.4 投影变换 五、空间数据库与…...
用github镜像加速, --recursive还是去github站怎么处理?
小伙伴们大多碰到过github抽风的情况,时通时断,时快时慢,非常考验心情。 以前碰到连不上的时候,我大多就是在gitee和gitcode网站找一下镜像,找到后直接git clone 新地址即可。但是碰到 --recursive的时候就不行了&…...
ctfshow-web 151-170-文件上传
151. 我们首先想到就是上传一句话木马。但是看源代码限制了png。 (1)改前端代码。 这里是前端限制了上传文件类型,那我们就改一下就好了嘛,改成php。 这里直接修改不行,给大家推荐一篇简短文章,大家就会了(…...
Mermaid Live Editor终极指南:10个团队协作和项目管理的实用技巧
Mermaid Live Editor终极指南:10个团队协作和项目管理的实用技巧 【免费下载链接】mermaid-live-editor Edit, preview and share mermaid charts/diagrams. New implementation of the live editor. 项目地址: https://gitcode.com/GitHub_Trending/me/mermaid-l…...
[LangChain智能体本质论-01]两种视角看待Agent和ReAct循环
作为LangChain智能体的Agent采用一种被称为ReAct循环的执行流程(如下图所示),这是一种结合了“推理”(Reasoning)与“行动”(Acting)的交互模式,旨在让Agent能像人类一样通过逻辑思考…...
tomcat和国产web中间件区别和联系
国产中间件 宝蓝德 https://www.bessystem.com/product/e717be5b091e4e14a7339aa4be49ca80/info?p101东方通 https://www.tongtech.com/sy.html非国产tomcat tomcat的项目发布方式 将项目复制到tomcat/webapps中启动Tomcat服务器,双击 startup.bat访问项目 IDEA 中…...
Flutter项目打包未签名ipa的保姆级教程(含Xcode配置与常见错误解决)
Flutter项目打包未签名ipa的保姆级教程(含Xcode配置与常见错误解决) 当你完成了一个Flutter应用的开发,准备将其交付给第三方进行签名或部署到CI/CD流水线时,生成一个未签名的ipa文件是必经之路。对于刚接触iOS打包的Flutter开发者…...
从CNN到Mamba:为什么这个轻量级双分支结构在医学图像分类中表现更好?
从CNN到Mamba:轻量级双分支结构如何重塑医学图像分类范式 医学影像分析正面临前所未有的挑战——随着CT、MRI、超声等成像技术的普及,每天产生的医学图像数据呈指数级增长。传统CNN架构在应对高分辨率医学图像时,往往陷入局部特征提取的局限&…...
天问Block环境下ASRPRO语音芯片实战:语音交互、GPIO控制与PWM调光开发指南
1. 天问Block与ASRPRO芯片开发入门 第一次接触天问Block和ASRPRO语音芯片时,我被它们的组合惊艳到了。这个开发环境就像乐高积木一样,通过拖拽代码块就能完成复杂的功能开发,特别适合像我这样的硬件爱好者。ASRPRO作为一款专为语音交互设计的…...
使用Alpine配置WSL ssh门户
1. 哑铃图是什么? 哑铃图(Dumbbell Plot),有时也称为DNA图或杠铃图,是一种用于比较两个相关数据点的可视化图表。 它源于人们对更有效数据比较方式的持续探索。 在传统的时间序列比较中,我们通常使用两条折…...
springboot+vue基于web的高校学生宿舍报修系统
目录同行可拿货,招校园代理 ,本人源头供货商高校学生宿舍报修系统功能分析(SpringBootVue)系统角色划分核心功能模块学生端功能维修端功能管理端功能系统管理功能技术实现要点扩展功能建议数据安全考虑项目技术支持源码获取详细视频演示 :文章…...
TEA算法逆向实战:从特征识别到脚本魔改的CTF通关指南
1. TEA算法特征快速识别指南 第一次在CTF比赛中遇到TEA算法时,我盯着反编译代码看了半小时都没反应过来。直到后来总结出几个关键特征,现在遇到这类题目基本能在30秒内锁定目标。最明显的标志就是那个魔性的delta常量0x9E3779B9(或者它的补码…...
Stable Yogi Leather-Dress-Collection效果展示:2.5D视角下皮衣动态褶皱与身体贴合度真实感
Stable Yogi Leather-Dress-Collection效果展示:2.5D视角下皮衣动态褶皱与身体贴合度真实感 想象一下,你是一位动漫角色设计师,需要为角色设计一套充满质感的皮衣。传统的流程需要你手绘线稿、上色、刻画光影和褶皱,整个过程耗时…...
