(字符串 ) 459. 重复的子字符串——【Leetcode每日一题】

news/2024/2/28 17:18:14

❓459. 重复的子字符串

难度:简单

给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。

示例 2:

输入: s = “aba”
输出: false

示例 3:

输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)

提示

  • 1 < = s . l e n g t h < = 1 0 4 1 <= s.length <= 10^4 1<=s.length<=104
  • s 由小写英文字母组成

💡思路:

法一:暴力

  • 就是一个 for 循环获取 子串的终止位置, 然后判断子串是否能重复构成字符串,又嵌套一个 for循环,所以是 O ( n 2 ) O(n^2) O(n2) 的时间复杂度。

法二: KMP(后续更新)

🍁代码:(Java、C++)

法一:暴力

Java

class Solution {public boolean repeatedSubstringPattern(String s) {int n = s.length();for(int i = 1; i <= n / 2; i++){if(n % i != 0) continue;for(int j = 0; j <= n - 2 * i; j += i){String str1 = s.substring(j, j + i);String str2 = s.substring(j + i, j + 2 * i);if(str1.compareTo(str2) != 0) break;if(j == n - 2 * i) return true;}}return false;}
}

C++

class Solution {
public:bool repeatedSubstringPattern(string s) {int n = s.size();for(int i = 1; i <= n / 2; i++){if(n % i != 0) continue;for(int j = 0; j <= n - 2 * i; j += i){if(s.compare(j, i, s, j + i, i) != 0) break;if(j == n - 2 * i) return true;}}return false;}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2),其中 n 为字符串 s 的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/194106.html

相关文章

狂肝两万字带你用pytorch搞深度学习!!!

深度学习 基础知识和各种网络结构实战 ... 狂肝两万字带你用pytorch搞深度学习&#xff01;&#xff01;&#xff01; 深度学习前言一、基本数据&#xff1a;Tensor1.1 Tensor的创建1.2 torch.FloatTensor1.3 torch.IntTensor1.4 torch.randn1.5 torch.range1.6 torch.zeros/o…

YUV与RGB互转各种公式

原创不易 转载请注明出处和作者 转载地址&#xff1a;https://www.cnblogs.com/luoyinjie/p/7219319.html 关于写这篇文章的原因: 本人也是摸索了很长时间才弄懂其中的原理&#xff0c;里面涉及的知识点太多了&#xff0c; 比如色彩空间&#xff0c; Gamma&#xff0c; 什么的&…

PyTorch 第六章

文章目录 一 Neural Style Transfer1图片风格迁移2.图片表示3.Content Loss4.Style Loss 二 Generative Adversarial Networks1 基本含义2 DCGAN 三 CycleGAN1. Network2.模型架构3.损失函数 四 代码实战1.图片风格迁移 Neural Style Transfer2.Generative Adversarial Network…

C++:多重继承:虚函数表、指针的位置问题

文章目录 建议多重继承虚函数表虚函数表的存放位置&#xff0c;二进制文件 建议 需要看《深入理解C对象模型》 这本书。 多重继承 多重继承就不应该存在&#xff0c;因为严重违反“简单原则”&#xff1b;不易理解&#xff0c;不易维护&#xff0c;不易开发。 就C Primer pl…

语义分割yolov5 v4.0 baseline快速复现 快速跑通 图像分割 图像分类 重新训练,训练结果,测试结果,实验图片-20210227

本机环境说明 操作系统版本 :~$ cat /etc/*release DISTRIB_IDUbuntu DISTRIB_RELEASE18.04 DISTRIB_CODENAMEbionic DISTRIB_DESCRIPTION"Ubuntu 18.04.5 LTS" NAME"Ubuntu" VERSION"18.04.5 LTS (Bionic Beaver)" IDubuntu ID_LIKEdebian PR…

【异步电机系列】电机参数离线辨识(含源码实现)

【一、闲话 很久没有认真更新自己的博客了&#xff01;正好这段时间在学习异步电机控制&#xff0c;所以把过程中的一些东西写下来&#xff0c;当是回顾也是备忘。本来想是把整个过程的问题和收获都记录下来的&#xff08;包括硬件设计、mcu控制、算法等&#xff09;&#xff0…

二进制包20分钟快速安装部署 Kubernetes v1.14.0 集群

文章目录 二进制包20分钟快速安装部署 Kubernetes v1.14.0 集群一 环境二 架构三 安装过程3.1 初始化脚本3.2 安装脚本3.3 安装失败回滚脚本 四 总结 二进制包20分钟快速安装部署 Kubernetes v1.14.0 集群 一 环境 操作系统Docker版本Kubernetes版本Etcd版本Flannel版本CentO…

bluetoothd源码剖析(一)启动流程

蓝牙系列&#xff1a; bluez调试笔记_weixin_41069709的博客-CSDN博客_bluezbluez移植https://blog.csdn.net/weixin_41069709/article/details/125168114?csdn_share_tail%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22125168114%22%2C%22sour…

海思HI35XX之----音频模块使用总结

HI3518C /海思音频编解码 /海思音频数据帧头 /HI35XX音频编解码流程 /HI35XX音频属性配置 7722 https://blog.csdn.net/zqj6893/article/details/25562633 AUDIO 模块包括音频输入、音频输出、音频编码、音频解码四个子模块。音频输入和 输出模块通过对 Hi35xx 芯片 SIO …

PHP全栈学习笔记33

javascript能做什么&#xff1f; 语句与注解&#xff0c;标识符&#xff0c;字面量&#xff0c;变量命名规范 JavaScript中的数据类型&#xff0c;其它类型如何转为数据型&#xff0c;操作符 字符方法&#xff0c;数组方法&#xff0c;函数与对象&#xff0c;函数表达式&#…

色彩空间转换公式

一、 公式&#xff1a;基于BT.601-6 BT601 UV 的坐标图&#xff08;量化后&#xff09;&#xff1a; &#xff08;横坐标为u&#xff0c;纵坐标为v&#xff0c;左下角为原点&#xff09; 通过坐标图我们可以看到UV并不会包含整个坐标系&#xff0c;而是呈一个旋转了一定角度的…

YUV与RGB互转各种公式 (YUV与RGB的转换公式有很多种,请注意区别!!!)

YUV与RGB互转各种公式 (YUV与RGB的转换公式有很多种&#xff0c;请注意区别&#xff01;&#xff01;&#xff01;) 一、 公式&#xff1a;基于BT.601-6 BT601 UV 的坐标图&#xff08;量化后&#xff09;&#xff1a; &#xff08;横坐标为u&#xff0c;纵坐标为v&#xff…

特征工程:基于梯度提升的模型的特征编码效果测试

为梯度提升学习选择默认的特征编码策略需要考虑的两个重要因素是训练时间和与特征表示相关的预测性能。Automunge库是处理表格数据常用的库&#xff0c;它可以填充空值&#xff0c;也可以进行分类的编码和归一化等操作&#xff0c;默认的境况下Automunge对分类特征进行二值化处…

Linux分配home容量给根目录

Linux分配home容量给根目录 1.概述 使用KVM创建的Linux系统&#xff0c;为系统分配了500G空间&#xff0c;创建完成后才发现根目录只有50G&#xff0c;其他的都在home文件夹下&#xff0c;下面将home下的空间分配给根目录。 2.卸载home 2.1.查看磁盘信息 [rootlocalhost j…

Oracle 10g RAC跨实例控制并行

在Oracle 10g RAC中的并行执行由两个参数:instance_groups和parallel_instance_group来控制。并且这两个参数必须同时使用才能生效。 instance_groups可以设置多个参数值&#xff0c;但它是静态参数&#xff0c;parallel_instance_groups可以在系统级别和会话级别运态进行修改…

oracle 11g bootstrap$系列一

背景 oracle从nomount到mount&#xff0c;内部机制到底是怎么样的&#xff0c;要经历哪些过程&#xff0c;了解这些&#xff0c;对于理解ORACLE&#xff0c;会大有帮助&#xff0c;拓宽分析解决问题能力。 结论 1,测试环境为oracle 11.2.0.1 2,bootstrap$为底层表&#xff…

【AI】Stable-Diffusion-WebUI使用指南

注&#xff1a;csdn对图片有审核&#xff0c;审核还很奇葩&#xff0c;线稿都能违规&#xff0c;为保证完整的阅读体验建议移步至个人博客阅读 最近AI绘画实现了真人照片级绘画水准&#xff0c;导致AI绘画大火&#xff0c;公司也让我研究研究&#xff0c;借此机会正好了解一下…

免费主机 虚拟主机 香港虚拟主机

免费主机 虚拟主机 香港虚拟主机http://zhuji.zzhinan.com/

虚拟服务器哪个便宜,虚拟主机哪家便宜?怎样挑选合适的虚拟主机?

虚拟主机的选择直接影响到了我们的建站&#xff0c;如果真的是想要确保后续的使用不出现问题&#xff0c;那么肯定还是要了解一下其实用性、稳定性&#xff0c;以及具体的价格情况。那么虚拟主机哪家便宜&#xff1f;哪个虚拟主机才是我们的首选呢&#xff1f; 一&#xff0c;明…

虚拟主机如何买便宜

决定虚拟主机价格的因素包括网页空间、流量以及数据库&#xff0c;这些配置越高&#xff0c;价格也就越贵。如果想以更便宜的价格买到虚拟主机&#xff0c;那当然要在虚拟主机有优惠的时候入手。 决定虚拟主机价格的因素包括网页空间、流量以及数据库&#xff0c;这些配置越高…
最新文章