【leetcode详解】T3137(思路详解 代码优化感悟)

 思路详解

        要解决这个问题,我们的大致思路是这样:找到长度为k的字符串 (记为stringA) ,统计重复次数最多的那一个,则最终对应的k周期字符串就是 [stringA * n] 的形式( n =  word.length() / k)

        要实现多对象的计数,map是一个很好的选择

 unordered_map<string, int>mp;//字符串, 出现次数

        根据上面的调整后的最终形式不难发现,stringA 还应满足位置条件,即起始位置必须在k的整数倍上。

        于是咱们的for循环就以k为递增周期

 for(int i=0; i<word.length(); i+=k)

初步的代码实现如下:

class Solution {
public:int minimumOperationsToMakeKPeriodic(string word, int k) {if(word.length() == k)  return 0;unordered_map<string, int>mp;int re = 0, mx = 1;string cur;for(int i=0; i<=word.length()-k; i+=k){cur = word.substr(i, k);if(mp.find(cur) != mp.end()){mp[cur]++;mx = max(mx, mp[cur]);				}else{mp[cur] = 1;}}return word.length()/k - mx;		}
};

代码优化

        由于笔者见识太有限了,上面的代码虽AC,但双复杂度双高

        观摩了其他大佬的写法,同样的思路,不同的语法实现,提交后直接逼近双百了!

下面分享下笔者的感悟:

        笔者自己感觉,自己最开始的代码时间上吃亏在了 cur = word.substr(i, k); 这一调用.substr()函数截取长度为k字符串的操作上。同时,也增加了一个cur的存储空间,加重了空间复杂度的负担。

        更好的程序是运用了string_view类型来构建map,可以在大大减少存储空间的情况下便利某段字符串的访问

//更多关于string 和 string_view的区别的讨论,推荐参考文章:

【C++干货】高效能的 string_view 和扎实稳定的 string-CSDN博客

出色的代码见下,真是简明干练,佩服!

class Solution {
public:int minimumOperationsToMakeKPeriodic(string word, int k) {unordered_map<string_view, int>mp;for(int i=0; i<=word.length()-k; i+=k)mp[{word.c_str()+i, word.c_str()+i+k}]++;//不存在的键对应的值默认是0return word.length()/k - max_element(mp.begin(), mp.end(), [](auto& a, auto& b){return a.second < b.second;})->second;	//lambda表达式,相当于构建了一个cmp函数}
};

//关于lambda表达式的基本用法,推荐参考文章: 

【C++浅析】lambda表达式:基本结构 & 使用示例-CSDN博客

~希望对你有启发!~

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

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

相关文章

iOS 18.1 Beta 2评测:新变化与体验升级

苹果公司近日向开发者推送了iOS 18.1 Beta 2更新&#xff0c;这一版本基于beta1版本进行多个方面优化和改进&#xff0c;为用户带来了更加流畅和个性化的使用体验。作为一位热衷于体验新系统的用户&#xff0c;小编也是第一时间升级了Beta 2版本&#xff0c;并对其进行了全面的…

51 无显式主键时 mysql 增加的 DB_ROW_ID

前言 这里主要是 探讨, 在我们创建了一个 无主键的数据表, 然后 mysql 会为我们增加的这一个 DB_ROW_ID 的相关 新建一个无主键字段的数据表如下 CREATE TABLE implicit_id_table (username varchar(16) DEFAULT NULL,age int(11) DEFAULT NULL ) ENGINEInnoDB DEFAULT CH…

Docker 部署loki日志 用于微服务

因为每次去查看日志都去登录服务器去查询相关日志文件&#xff0c;还有不同的微服务&#xff0c;不同日期的文件夹&#xff0c;超级麻烦&#xff0c;因为之前用过ELK&#xff0c;原本打算用ELK&#xff0c;在做技术调研的时候发现了一个轻量级的日志系统Loki&#xff0c;果断采…

如何一键删除iPhone相册所有照片

拍照已成为我们记录日常生活的常态。但是&#xff0c;大量照片便会积累在设备上&#xff0c;这不仅占用了大量存储空间&#xff0c;而且随着时间的推移&#xff0c;管理这些照片也变得越来越困难。如果你决定清理旧照片&#xff0c;或者出于隐私考虑需要删除所有照片&#xff0…

【数据结构】链式结构实现:二叉树

二叉树 一.快速创建一颗二叉树二.二叉树的遍历1.前序、中序、后序遍历&#xff08;深度优先遍历DFS&#xff09;2.层序遍历&#xff08;广度优先遍历BFS&#xff09; 三.二叉树节点的个数四.二叉树叶子节点的个数五.二叉树的高度六.二叉树第k层节点个数七.二叉树查找值为x的节点…

什么是机器人快换盘?

机器人快换盘&#xff0c;行业内也称作工具快换盘、换枪盘、快换工具盘、快速更换器、快换器、 快换夹具、治具快换等。是末端执行器快速更换装置&#xff08;End-Of-Arm Tooling&#xff0c;简称EOAT&#xff09;&#xff0c;是工业自动化领域中用于机器人手臂上的一种重要设备…

MiniCPM-V: A GPT-4V Level MLLM on Your Phone论文阅读

大模型的趋势&#xff1a;模型性能越来越好&#xff0c;模型参数变小&#xff0c;端边设备计算能力变强。 MiniCPM-V优点 结果好、OCR能力突出、多分辨率、多语言、易于部署 模型结构 图片encoder适用vit。输入整体以及切片。切片使用自适应算法&#xff0c;通过计算分数&am…

人机环境系统智能已经超越了传统的空间智能和物理世界的概念

人机环境系统智能已经超越了传统的空间智能和物理世界的概念&#xff0c;进入了更为复杂的层次。在人机环境系统中&#xff0c;智能不仅涉及对物理世界的感知和理解&#xff0c;还包括对人类语言、情感、意图等的理解和生成。人工智能技术的应用&#xff0c;如自然语言处理、机…

C++静态数组的用法

每日诗词&#xff1a; 疏影横斜水清浅&#xff0c;暗香浮动月黄昏。 ——《山园小梅其一》林逋 目录 数组的基础操作&#xff1a; 数组元素的增加&#xff1a; 演示&#xff1a; 数组元素的删除&#xff1a; 演示&#xff1a; 数组元素的访问和修改&#xff1a; 演示&am…

WLAN射频调优

射频调优的基本原则 信道优化的基本原则 2.4G射频在非高密部署场景中推荐采用1、6、11这种3个不重叠的信道进行规划&#xff0c;同理也可以选用2、7、12或3、8、13的组合方式&#xff1b;在高密部署场景中则推荐采用1、5、9、13共4个信道组合进行规划。5G射频推荐采用36、40、…

HQChart使用教程101-创建内置键盘精灵

HQChart使用教程101-创建内置键盘精灵 键盘精灵步骤1. 创建键盘精灵实例2. 设置事件回调3. 初始化键盘精灵4. 设置码表数据5. 监听"keydown","mousedown" 交流QQ群HQChart代码地址键盘精灵源码 完整实例 键盘精灵 键盘精灵是一种便捷操作软件的功能工具&a…

【人工智能】Python融合机器学习、深度学习和微服务的创新之路

1. &#x1f680; 引言1.1 &#x1f680; 人工智能的现状与发展趋势1.2 &#x1f4dc; 机器学习、深度学习和神经网络的基本概念1.3 &#x1f3c6; 微服务架构在人工智能中的作用 2. &#x1f50d; 机器学习的演变与创新2.1 &#x1f31f; 机器学习的历史回顾2.2 &#x1f9e0;…

UE----IPA 安装 在手机上后 显示 不受信任的开发者

进入设置 ----》 点击 通用 ----》点击 VPN与设备管理 点击信任 然后 再打开开发者模式即可 在隐私与安全性里 下滑 最底部 即可看到开发者模式

JavaScript学习笔记(十二):JS Web API

1、Web API - 简介 Web API 是开发人员的梦想。 它可以扩展浏览器的功能它可以极大简化复杂的功能它可以为复杂的代码提供简单的语法 1.1 什么是 Web API&#xff1f; API 指的是应用程序编程接口&#xff08;Application Programming Interface&#xff09;。 Web API 是 …

机器学习第十四章-概率图模型

目录 14.1 隐马尔可夫模型 14.2马尔科夫随机场 14.3条件随机场 14.4学习与推断 14.4.1变量消去 14.4.2信念传播 14.5近似推断 14.5.1 MCMC采样 14.5.2 变分推断 14.6 话题模型 14.1 隐马尔可夫模型 概率围棋型是一类用图来表达变量相关关系的概率模型.它以图为表示工具…

Python入门级[ 基础语法 函数... ] 笔记 例题较多

本文是刚学习Python的笔记&#xff0c;当时使用的编辑器是交互式编程&#xff0c;所以很多代码可能在你们的编译器上面不能运行&#xff0c;我用快引用引起来了&#xff0c;还需要大家自己动手试一试。 内容涉及的比较简单&#xff0c;主要还是Python的语法部分&#xff1a;三…

短链接系统设计方案

背景 需要设计一个短链接系统&#xff0c;主要功能主要有如下几点&#xff1a; ToB&#xff1a; 输入一个长链接&#xff0c;转换成短链接。这个短链接有时效性&#xff0c;可以设定指定过期时间。这个系统的每天会生成千万级别的短链接。数据具备可分析功能。 ToC&#xf…

借助Vercel 十分钟搭建属于自己的AI应用站点

轻松依托 Vercel,快速构建 Nexior AI 平台 Nexior 是一个令人惊叹的开源项目&#xff0c;托管于 GitHub。通过它&#xff0c;您能够一键便捷地部署专属的 AI 应用站点&#xff0c;包括 AI 问答、Midjourney 绘画、知识库问答、艺术二维码等&#xff0c;完全不需要自己去开发 A…

springBoot+ druid配置多数据源

springBoot druid配置多数据源 1.在yml加&#xff1a; spring:#1.JDBC数据源datasource:druid:first:username: PYpassword: ral2024url: jdbc:mysql://localhost:3306/mysql?serverTimezoneUTC&characterEncodingutf8&useUnicodetrue&useSSLfalsedriver-class-n…

前端进行分页Vue3+Setup写法

当后端不方便提供数据分页查询接口时&#xff0c;就需要前端来自己分割进行分页操作 在有可能的情况下还是建议用分页查询接口&#xff0c;减少网络数据传输 首先el-table绑定数组 分页组件&#xff0c;变量自己定义防止报错 <el-paginationlayout"->, total, siz…