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

【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 <= 1000
  • str1str2 仅由小写字母组成。

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.字符串的最大公因子 题目描述&#xff1a; 对于字符串 s 和 t&#xff0c;只有在 s t t t … t t&#xff08;t 自身连接 1 次或多次&#xff09;时&#xff0c;我们才认定 t 能除尽 s。 给定两个字符串 str1 和 str2 。返回 最长字符串 x&#xff0c;要…...

《C++:计算机视觉图像识别与目标检测算法优化的利器》

在当今科技飞速发展的时代&#xff0c;计算机视觉领域正经历着前所未有的变革与突破。图像识别和目标检测作为其中的核心技术&#xff0c;广泛应用于安防监控、自动驾驶、智能医疗等众多领域&#xff0c;其重要性不言而喻。而 C语言&#xff0c;凭借其卓越的性能、高效的资源控…...

大模型的构建与部署(2)——数据清洗

版权声明 本文原创作者:谷哥的小弟作者博客地址:http://blog.csdn.net/lfdfhl1. 数据清洗的必要性与影响 1.1 数据清洗对模型性能的影响 数据清洗是数据预处理的关键步骤,对于模型训练的性能和准确性有着直接的影响。原始数据中的缺失值、重复值、异常值以及数据格式不一致…...

试题转excel;word转excel;大风车excel

一、问题描述 一名教师朋友&#xff0c;偶尔会需要整理一些高质量的题目到excel中 以往都是手动复制搬运&#xff0c;几百道题几乎需要一个下午的时间 关键这些事&#xff0c;枯燥无聊费眼睛&#xff0c;实在是看起来就很蠢的工作 就想着做一个工具&#xff0c;可以自动处理…...

微信小程序webview和小程序通讯

1.背景介绍 1.1需要在小程序嵌入vr页面&#xff0c;同时在vr页面添加操作按钮与小程序进行通信交互 1.2开发工具&#xff1a;uniapp开发小程序 1.3原型图 功能&#xff1a;.点击体验官带看跳转小程序的体验官带看页面 功能&#xff1a;点击立即咨询唤起小程序弹窗打电话 2.…...

ChatGPT大模型 创作高质量文案的使用教程和案例

引言 随着人工智能技术的飞速发展,大语言模型如 ChatGPT 在创作文案、生成内容方面展现出了强大的能力。无论是个人用户还是企业用户,都可以利用 ChatGPT 提高工作效率、激发创意、甚至解决实际问题。本文将详细介绍 ChatGPT 如何帮助创作各类高质量文案,并通过具体案例展示…...

Vue Web开发(八)

1. VueWeb面包屑和tag的布局 本章节完成VueWeb面包屑和tag的布局&#xff0c;并且与左侧菜单联系&#xff0c;涉及组件间通信。 1.1. 页面创建 &#xff08;1&#xff09;首先我们先完成每个页面的路由&#xff0c;之前已经有home页面和user页面&#xff0c;缺少mail页面和其…...

element-ui实现table表格的嵌套(table表格嵌套)功能实现

最近在做电商类型的官网&#xff0c;希望实现的布局如下&#xff1a;有表头和表身&#xff0c;所以我首先想到的就是table表格组件。 表格组件中常见的就是&#xff1a;标题和内容一一对应&#xff1a; 像效果图中的效果&#xff0c;只用基础的表格布局是不行的&#xff0c;因…...

【考前预习】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&#xff08;Mapped Diagnostic Context&#xff09;是一个用于在多线程环境中追踪和传递日志上下文信息的机制。2.映射诊断环境。3.MDC是一个线程本地的、可维护的、可传递的上下文环境。4.它允许开发…...

Android 好的开源库

1. 权限请求框架 GitHub - getActivity/XXPermissions: Android 权限请求框架&#xff0c;已适配 Android 14 2. 下载框架 GitHub - lingochamp/okdownload: A Reliable, Flexible, Fast and Powerful download engine....

Go 语言结构

Go 语言结构 Go 语言,也称为 Golang,是一种由 Google 开发和支持的静态类型、编译型编程语言。它于 2009 年首次发布,旨在提高多核处理器、网络资源和大型代码库的性能。Go 语言以其简洁的语法、并发支持和强大的标准库而闻名,特别适合构建高性能的网络服务和分布式系统。…...

【漆学军】MT5几个重要类库的使用例子

MT5编程&#xff0c;有两种方式&#xff0c;一种是函数式编程&#xff0c;一种是面向对象编程。 面向对象编程&#xff0c;会让我们编写代码变得非常简单。 面向对象编程&#xff0c;主要是要熟悉4个类库。 #include <Trade\PositionInfo.mqh> #include <Trade\Tra…...

在 Ubuntu 24.04.1 LTS (WSL) 中使用 openssl 生成 keybox.xml

看到“生成 keybox.xml”&#xff0c;大概率都会联想到 PIF 和 Tricky Store。这里就不多解释它们的用途了。最近在网上看到生成非 AOSP keybox 的教程&#xff0c;在这里做一些补充&#xff0c;并将代码打包成一个 Python 脚本。 参考自&#xff1a; Idea 提供者&#xff1a…...

【JavaSE基础】第十六章:IO流

一、理解 1.简单而言&#xff1a;流就是内存与存储设备之间传输数据的通道、管道。 2.流的分类&#xff1a; (1) 按方向 ( 以 JVM 虚拟机为参照物 ) 【重点】 输入流&#xff1a;将< 存储设备 > 中的内容读入到 < 内存 > 中。 输…...

常见漏洞—SSRF_FastCGI

FastCGI协议 简介 Fast CGI源自旧版本的CGI 路由/结构图 # 访问url --> 浏览器生成HTTP请求报文 --> web server解析请求&#xff08;例如nginx&#xff09; web server 是内容的分发者 当访问静态页面时&#xff0c;web server 会直接返回资源&#xff0c;例如index.htm…...

LeetCode 283.移动零(超简单讲解)

283.移动零 题目示例示例1示例2 解题思路快慢指针实现设计 详细代码 题目 给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。 示例 示例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抽风的情况&#xff0c;时通时断&#xff0c;时快时慢&#xff0c;非常考验心情。 以前碰到连不上的时候&#xff0c;我大多就是在gitee和gitcode网站找一下镜像&#xff0c;找到后直接git clone 新地址即可。但是碰到 --recursive的时候就不行了&…...

ctfshow-web 151-170-文件上传

151. 我们首先想到就是上传一句话木马。但是看源代码限制了png。 &#xff08;1&#xff09;改前端代码。 这里是前端限制了上传文件类型&#xff0c;那我们就改一下就好了嘛,改成php。 这里直接修改不行&#xff0c;给大家推荐一篇简短文章&#xff0c;大家就会了&#xff08…...

酒精测试仪

简 介&#xff1a; 本文介绍了一款酒精测试仪的使用方法。测试仪开机后需等待15秒预热&#xff08;数字倒计时&#xff09;&#xff0c;预热结束后对着吹气口吹气3秒即可显示测量结果。实验表明&#xff0c;该仪器灵敏度较高&#xff1a;直接吹气显示11左右&#xff0c;不吹气显…...

避开这些坑!Mapbox图层管理实战:动态加载GeoJSON数据的正确姿势

Mapbox高级图层管理实战&#xff1a;GeoJSON动态加载与性能优化全解析 当处理省级以上GIS数据可视化时&#xff0c;Mapbox的图层管理能力直接决定了应用的流畅度和用户体验。许多开发者在使用GeoJSON数据源时&#xff0c;常遇到内存泄漏、渲染卡顿、交互延迟等问题。本文将深入…...

终极Übersicht小部件调试指南:10个实用工具和高效方法

终极bersicht小部件调试指南&#xff1a;10个实用工具和高效方法 【免费下载链接】uebersicht ˈyːbɐˌzɪt 项目地址: https://gitcode.com/gh_mirrors/ue/uebersicht bersicht是一款强大的macOS桌面小部件工具&#xff0c;让开发者能够在桌面上创建和运行自定义小部…...

知识获取受限?5款开源工具助你合法解锁付费内容

知识获取受限&#xff1f;5款开源工具助你合法解锁付费内容 【免费下载链接】bypass-paywalls-chrome-clean 项目地址: https://gitcode.com/GitHub_Trending/by/bypass-paywalls-chrome-clean 你是否曾在学术研究关键时刻被期刊付费墙阻挡&#xff1f;是否因新闻网站的…...

告别环境配置烦恼:用快马一键生成keil5兼容c51与stm32的完整安装指南

作为一名嵌入式开发者&#xff0c;我深知在Keil5中同时配置C51和STM32开发环境的痛苦。每次换电脑或者重装系统&#xff0c;都要花大半天时间折腾各种安装包、环境变量和驱动问题。最近发现InsCode(快马)平台可以一键生成完整的配置指南&#xff0c;简直拯救了我的开发效率。下…...

【飞控】QGroundControl与Mission Planner:如何根据项目需求选择最佳地面站

1. 两款地面站软件的核心定位差异 第一次接触无人机开发时&#xff0c;我也曾被QGroundControl和Mission Planner搞得晕头转向。这两款软件就像工具箱里的不同工具&#xff0c;关键是要知道什么时候该用哪一把。QGroundControl&#xff08;简称QGC&#xff09;给我的第一印象是…...

HunyuanVideo-Foley高算力适配:RTX4090D显存利用率优化至92%实测

HunyuanVideo-Foley高算力适配&#xff1a;RTX4090D显存利用率优化至92%实测 1. 镜像概述与核心优势 HunyuanVideo-Foley私有部署镜像专为视频与音效生成任务深度优化&#xff0c;基于RTX 4090D 24GB显存硬件平台打造。经过CUDA 12.4与驱动550.90.07的针对性调优&#xff0c;…...

郭老师-最高级的活法:不渡无缘之人

最高级的活法 ——不干涉他人的因果“说教只会引来仇恨&#xff0c; 疼痛才是最好的老师。”&#x1f33f; 真正的慈悲&#xff0c; 不是拉人上岸&#xff0c; 而是—— 允许他沉下去&#xff0c;再自己浮起来。⚖️ 一、四大悲哀&#xff1a;强行渡人&#xff0c;反被拖下水行…...

瑞芯微RK3399固件急救指南:用upgrade_tool搞定系统崩溃后的快速还原

RK3399固件灾难恢复实战&#xff1a;从分区表重建到全系统还原 当一块搭载RK3399的开发板因固件损坏而变砖时&#xff0c;那种面对黑屏的无力感&#xff0c;相信每个嵌入式开发者都深有体会。去年我们产线就遭遇过因批量升级失败导致30台设备集体罢工的紧急状况&#xff0c;正…...

避开这3个坑,你的软考数据库设计题至少多拿10分:从E-R图合并冲突到SQL约束实战

软考数据库设计题避坑指南&#xff1a;从E-R图到SQL约束的实战技巧 每次软考结束&#xff0c;总有一批考生捶胸顿足——"那道数据库设计题明明会做&#xff0c;怎么又丢分了&#xff1f;"作为参加过三次软考阅卷的数据库讲师&#xff0c;我发现90%的失分都集中在几个…...