C语言 | Leetcode C语言题解之第466题统计重复个数

题目:

题解:

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <limits.h>#define MMAX(a, b)        ((a) > (b)? (a) : (b))
#define MMIN(a, b)        ((a) < (b)? (a) : (b))//【算法思路】字符串。典型的双字符串循环节问题。
// s1:      |abaacdbac | abaacdbac | abaacdbac | abaacdbac | abaacdbac | abaacdbac
// s2:      |a    d  c    b   d|a         d  c    b   d|a     b  c b          d|
// s2_idx:  |0         |3          |1          |3
// s2_cnt:  |0         |0          |1          |1
//--------------------------------------------------------------------------------
// s1_cnt   |0         |1          |2          |3          |4          |5
int getMaxRepetitions(char * s1, int n1, char * s2, int n2){if(n1 == 0) {return 0;}int slen1 = strlen(s1);int slen2 = strlen(s2);//极限情况,最多重复slen2 +1可以遇到重复int *s2_idxs = (int *)calloc(slen2 + 1, sizeof(int));int *s2_cnts = (int *)calloc(slen2 + 1, sizeof(int));int s2_idx = 0;int s2_cnt = 0;//查找循环节for(int i = 0; i < n1; i++) {//完成在s1内的一轮查找for(int j = 0; j < slen1; j++) {if(s1[j] == s2[s2_idx]) {s2_cnt = s2_idx == slen2 - 1? s2_cnt + 1 : s2_cnt;s2_idx = s2_idx == slen2 - 1? 0 : s2_idx + 1;}}//进行一次记录s2_idxs[i] = s2_idx;s2_cnts[i] = s2_cnt;//在0~i-1的范围内,查找循环节for(int j = 0; j < i; j++) {if(s2_idxs[j] == s2_idxs[i]) {//在循环节之前循环的次数//int pre_cnt = s2_cnts[j];//循环节中的s2的个数乘以循环次数int core_cnt = (s2_cnts[i] - s2_cnts[j]) * ((n1 - 1 - j) / (i - j));//将剩余的s1的循环个数加到前面,计算除循环节外的个数int pre_and_post_cnt = s2_cnts[j + ((n1 - 1 - j) % (i - j))];return (core_cnt + pre_and_post_cnt) / n2;}}}return s2_cnts[n1 - 1] / n2;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/442635.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

打卡第六天 P10287 [GESP样题 七级] 最长不下降子序列

今天是我打卡第六天&#xff0c;做个普及/提高−题吧(#^.^#) 原题链接&#xff1a;[GESP样题 七级] 最长不下降子序列 - 洛谷 题目描述 输入格式 输出格式 输出一行一个整数表示答案。 输入输出样例 输入 #1 5 4 2 10 6 3 1 5 2 2 3 3 1 1 4 输出 #1 3 输入 #2 6 11 …

微服务——分布式事务

目录 分布式事务 1.1分布式事务的特性 1.2分布式事务应用背景 ​编辑 1.3.认识Seata 1.4部署TC服务 1.4.1.准备数据库表 1.4.2.准备配置文件 1.4.3.Docker部署 1.5.微服务集成Seata 1.5.1.引入依赖 1.5.2.改造配置 1.5.3.添加数据库表 ​编辑1.6.XA模式 1.6.1.两…

JavaScript函数基础(通俗易懂篇)

10.函数 10.1 函数的基础知识 为什么会有函数&#xff1f; 在写代码的时候&#xff0c;有一些常用的代码需要书写很多次&#xff0c;如果直接复制粘贴的话&#xff0c;会造成大量的代码冗余&#xff1b; 函数可以封装一段重复的javascript代码&#xff0c;它只需要声明一次&a…

精品WordPress主题/响应式个人博客主题Kratos

Kratos 是一款专注于用户阅读体验的响应式 WordPress 主题&#xff0c;整体布局简洁大方&#xff0c;针对资源加载进行了优化。 Kratos主题基于Bootstrap和Font Awesome的WordPress一个干净&#xff0c;简单且响应迅速的博客主题&#xff0c;Vtrois创建和维护&#xff0c; 主…

LeetCode 刷题基础 -- 模板原型Ⅰ

模板原型 - 基础篇 学习网站一、进制转换二、二分查找① 查找指定元素② 查找第一个大于等于 x 值的序列下标③ 查找第一个大于 x 值的序列下标④ 单峰序列 三、双指针① 两数之和② 序列合并③ 集合求交④ 集合求并 四、其他高效技巧与算法① 区间和② 01 对③ 左小数 五、数学…

BLE MESH学习1-基于沁恒CH582学习

BLE MESH学习1-基于沁恒CH582学习 一、BLE mesh说明 mesh组网可以实现相比点对点模式更远的距离、更灵活的网络形式、更可靠的连接和更多的设备加入。BLE mesh在IoT中的传感器和控制具有重要意义。我的目的也是IoT领域&#xff0c;实现自己的传感器读取、开关控制等类似米家智…

知识改变命运 数据结构【java对象的比较】

0&#xff1a;前言 在基本数据类型中&#xff0c;我们可以直接使用号比较是否相等&#xff0c;还记的学堆哪里时候&#xff0c;插入一个数据&#xff0c;就会与其他数据进行比较&#xff0c;当时我们传入的是Integer类型&#xff0c;在Integer类里面已经实现了compare。 如果…

西门子S7-1200博途软件项目的下载

S7-1200的CPU本体上集成了PROFINET通信口&#xff0c;通过这个通信口可以实现CPU与编程设备的通信。 此外&#xff0c;S7-1200 可以通过连接CM1243-5扩展模块&#xff0c;然后电脑通过PC ADAPTER USB A2电缆、或者电脑上的CP卡&#xff08;例如CP5612&#xff09;通过PROFIBUS…

手写mybatis之SQL执行器的定义和实现

前言 所有系统的设计和实现&#xff0c;核心都在于如何解耦&#xff0c;如果解耦不清晰最后直接导致的就是再继续迭代功能时&#xff0c;会让整个系统的实现越来越臃肿&#xff0c;稳定性越来越差。而关于解耦的实践在各类框架的源码中都有非常不错的设计实现&#xff0c;所以阅…

陪伴系统,会成为女性向游戏的下一个争夺点吗?

乙游提供给女性玩家的只有恋爱感吗&#xff1f; 一般来说&#xff0c;对于乙女游戏的概括常常以为玩家提供“恋爱陪伴感”为主&#xff0c;恋爱很好理解&#xff0c;通过与多位男主角的剧情互动来模拟在真实恋爱中的情感交互&#xff0c;当下乙游都将重点放在了营造恋爱感上。…

55页可编辑PPT | 制造企业数字化转型顶层规划案例

基于集团的战略和运营特点&#xff0c;数字化转型应如何考虑&#xff1f; 在集团的战略和运营特点基础上进行数字化转型&#xff0c;需要实现业务多元化&#xff0c;整合资源和流程&#xff0c;推动国际化拓展&#xff0c;实施差异化战略&#xff0c;并通过数据驱动决策&#…

Vue工程化结构环境安装及搭建教程 : 之nvm

vue需要的环境&#xff1a; node.js : Node.js和Vue.js通常会一起使用。Node.js作为后端服务器&#xff0c;处理服务器端的逻辑和数据访问&#xff0c;而Vue.js则负责前端用户界面的构建和交互。通过Ajax通信&#xff0c;Vue.js应用程序向Node.js服务器发送请求&#xff0c;并…

【Ubuntu】git

文章目录 1.配置SSH key2. 基础知识操作命令1分支branch 如果对git命令使用不熟悉&#xff0c;推荐一个非常棒的git在线练习工具 Learn Git Branching。 https://m.runoob.com/git/git-basic-operations.html 1.配置SSH key ssh-keygen -t rsa -C "YOUR EMAIL"完成…

PDF无法导出中文

font/SIMSUN.TTC with Identity-H is not recognized. 查看BaseFont源码发现".ttc," 改为"SIMSUN.TTC,a"提示数字转换异常 改为"SIMSUN.TTC,11"提示数字索引必须介于0和1之间 改为0或1结果正常 BaseFont baseFont BaseFont.createFont("/U…

迎接国庆旅游热潮,火山引擎数据飞轮助力景区数智化升级

随着人们生活水平的提高和旅游消费观念的转变&#xff0c;国庆假期成为人们出行旅游的黄金时段。同程旅行发布的报告显示&#xff0c;北京、杭州、重庆、上海、南京、成都等城市仍是 “十一” 假期国内热门的目的地&#xff0c;而一些新兴的宝藏旅游目的地如新疆阿勒泰、云南迪…

四.python核心语法

目录 1.序列 1.1. 索引 1.2. 切片 1.3. 总结 2.加法和乘法 2.1. 加法 2.2. 乘法 3.常用函数 3.1.sum()函数 3.2.max()函数和min()函数 3.3.len()函数 4. list 列表 [ ] 基本操作 4.1. 列表的定义 4.2. 列表的创建&#xff08;list()函数&#xff09; 4.3. 列表的…

RabbitMQ概述

什么是MQ MQ (message queue)消息队列 MQ从字⾯意思上看,本质是个队列,FIFO先⼊先出&#xff0c;只不过队列中存放的内容是消息(message).消息可以⾮常简单,⽐如只包含⽂本字符串,JSON等,也可以很复杂,⽐如内嵌对象 RabbitMQ是MQ的一种实现,是Rabbit 企业下的⼀个消息队列产…

Python 如何使用 scikit-learn 进行模型训练

如何使用 scikit-learn 进行模型训练 一、简介 在现代的数据科学和机器学习领域&#xff0c;Python 已经成为最流行的编程语言之一。而其中最流行的机器学习库之一就是 scikit-learn。scikit-learn 提供了许多方便的工具和函数来实现常见的机器学习任务&#xff0c;包括数据预…

数据分析:宏基因组群落TOPOSCORE拓扑结构打分

文章目录 介绍数据TOPOSCORE算法SCORE计算TOPOSCORE实操tp_helper.R导入数据生存分析Fisher精确检验聚类分析SIG定义Toposcoring 分数计算Akkermansia muciniphila的考虑TOPOSCORE的验证总结系统信息介绍 研究背景:肠道微生物群对癌症患者对免疫检查点抑制剂(ICIs)的临床反…

笔记整理—linux进程部分(9)互斥锁

互斥锁也叫互斥量&#xff0c;可以看作一种特殊的信号量。信号量可以>0&#xff0c;大家可以排队使用信号量&#xff0c;互斥锁只有0、1&#xff0c;主要实现关键段保护&#xff0c;只能在某一时间给某一任务去调用这段资源&#xff0c;这段内容用之前上锁&#xff0c;用完时…