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

2024-08-20 21:20

本文主要是介绍【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博客

~希望对你有启发!~

这篇关于【leetcode详解】T3137(思路详解 代码优化感悟)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

详解如何通过Python批量转换图片为PDF

《详解如何通过Python批量转换图片为PDF》:本文主要介绍如何基于Python+Tkinter开发的图片批量转PDF工具,可以支持批量添加图片,拖拽等操作,感兴趣的小伙伴可以参考一下... 目录1. 概述2. 功能亮点2.1 主要功能2.2 界面设计3. 使用指南3.1 运行环境3.2 使用步骤4. 核

一文详解JavaScript中的fetch方法

《一文详解JavaScript中的fetch方法》fetch函数是一个用于在JavaScript中执行HTTP请求的现代API,它提供了一种更简洁、更强大的方式来处理网络请求,:本文主要介绍Jav... 目录前言什么是 fetch 方法基本语法简单的 GET 请求示例代码解释发送 POST 请求示例代码解释

详解nginx 中location和 proxy_pass的匹配规则

《详解nginx中location和proxy_pass的匹配规则》location是Nginx中用来匹配客户端请求URI的指令,决定如何处理特定路径的请求,它定义了请求的路由规则,后续的配置(如... 目录location 的作用语法示例:location /www.chinasem.cntestproxy

CSS will-change 属性示例详解

《CSSwill-change属性示例详解》will-change是一个CSS属性,用于告诉浏览器某个元素在未来可能会发生哪些变化,本文给大家介绍CSSwill-change属性详解,感... will-change 是一个 css 属性,用于告诉浏览器某个元素在未来可能会发生哪些变化。这可以帮助浏览器优化

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

详解C++中类的大小决定因数

《详解C++中类的大小决定因数》类的大小受多个因素影响,主要包括成员变量、对齐方式、继承关系、虚函数表等,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录1. 非静态数据成员示例:2. 数据对齐(Padding)示例:3. 虚函数(vtable 指针)示例:4. 继承普通继承虚继承5.

前端高级CSS用法示例详解

《前端高级CSS用法示例详解》在前端开发中,CSS(层叠样式表)不仅是用来控制网页的外观和布局,更是实现复杂交互和动态效果的关键技术之一,随着前端技术的不断发展,CSS的用法也日益丰富和高级,本文将深... 前端高级css用法在前端开发中,CSS(层叠样式表)不仅是用来控制网页的外观和布局,更是实现复杂交

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

详解C#如何提取PDF文档中的图片

《详解C#如何提取PDF文档中的图片》提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使用,下面我们就来看看如何使用C#通过代码从PDF文档中提取图片吧... 当 PDF 文件中包含有价值的图片,如艺术画作、设计素材、报告图表等,提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使

Android中Dialog的使用详解

《Android中Dialog的使用详解》Dialog(对话框)是Android中常用的UI组件,用于临时显示重要信息或获取用户输入,本文给大家介绍Android中Dialog的使用,感兴趣的朋友一起... 目录android中Dialog的使用详解1. 基本Dialog类型1.1 AlertDialog(