【leetcode 详解】生成特殊数字的最少操作【中等】(C++思路精析)

 题目见下:

测试数据: 

解题思路笔记:

        最初拿到这道题是很蒙的,联想不到什么数据结构的模型(肯定是笔者积累太少了),甚至惯性地想怎么实现“删除数字”的操作:在原字符串中抽出一个字符然后将剩余数字按原顺序拼接?

         看着看着下面的测试数据,我突然意识到,能整除25的数确实很特殊,即若长度足够,则必然以【00,50, 25, 75】来结尾,这样一来,未知长度的字符串问题,就转化为了:专注于找可以放在结尾的两字符的问题。

        进一步观察题目要求可以发现,既然咱们要的就是 “最小删除个数” 这么个结果,中间过程怎么实现都行,也就是不必按题目表述的 “删除一个字符,检查是否可整除25” 介么生硬地来。这大概也是像笔者一样的编程初学者容易陷入的误区,实现过程的思路总是跟着题目叙述跑,但优质的(时空复杂度较低)的解法往往需要明确问题核心,创意性地从新的角度切入。

//更多创意性解法,这里推荐文章

PTA 7-4 列车调度(C/ C++ 一个数组就好啦!)-CSDN博客

最后,附上AC代码:

class Solution {
private:void Myfunc(string num, int cur0, char c1, char c2, int &re){int len = num.length();int help1=len, help2=len;while(1){if(help1 >= cur0 ) help1 = num.rfind(c1, help1-1);if(help2 >= cur0 ) help2 = num.rfind(c2, help2-1);if(help1 < cur0 && help2 < cur0) break;//说明:调试过程中发现,num.npos其实就等于 -1,可以进行整数比较}if(help1 == num.npos && help2 == num.npos){if(cur0 != num.npos && c1 == '0') re = len - 1;//只有当末尾数字为0时才进行这部操作} else{if(help1 != num.npos) re = min(re, len-2-help1);if(help2 != num.npos) re = min(re, len-2-help2);} }public:int minimumOperations(string num) {if(!num.compare("0")) return 0;//特殊情况处理int re = num.length();int cur0 = num.rfind('0'), cur5 = num.rfind('5');if(cur0 != num.npos){Myfunc(num, cur0, '0', '5', re);}if(cur5 != num.npos){Myfunc(num, cur5, '2', '7', re);}return re;}
};

~希望对你有启发~

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

面试 SQL整理 常见的SQL面试题:大厂经典60题(一)

目录 SQL基础知识整理: 数据库基础知识 为什么要使用数据库 数据保存在内存 数据保存在文件 数据保存在数据库 什么是SQL&#xff1f; 什么是MySQL? 数据库三大范式是什么 mysql有关权限的表都有哪几个 MySQL的binlog有有几种录入格式&#xff1f;分别有什么区别&…

ElasticSearch(五)— 文本分析与分词

一、文本分析 文本分析( analysis )是在文档被发送并加入倒排索引之前&#xff0c;Elasticsearch 在其主体上进行的操作。在文档被加入索引之前&#xff0c;Elasticsearch 让每个被分析字段经过一系列的处理步骤。 字符过滤–使用字符过滤器转变字符。文本切分为分词—将文本…

JAVA同城圈子达人交友系统源码支持微信小程序+公众号+H5+APP

&#x1f308; 同城圈子达人交友系统&#xff0c;遇见志同道合的TA&#xff01; &#x1f389; 开篇&#xff1a;告别孤单&#xff0c;同城圈子等你来探索&#xff01; 在这个快节奏的城市生活中&#xff0c;你是否常常感到孤独&#xff0c;渴望找到一群志同道合的朋友&#…

2024年铜川宜君半程马拉松,暴晒+爬坡152安全完赛

1、赛事背景 2024年7月21日&#xff0c;我参加了2024年铜川宜君半程马拉松赛&#xff0c;7月举办的赛事很少&#xff0c;全国都算温度比较高的&#xff0c;虽然宜君是一个山城&#xff0c;还是会担心气温会高。 临开赛1、2周&#xff0c;陕西区域降水比较多&#xff0c;赛前一…

如何实现ECharts图表根据屏幕大小自适应?

​&#x1f308;个人主页&#xff1a;前端青山 &#x1f525;系列专栏&#xff1a;Vue篇 &#x1f516;人终将被年少不可得之物困其一生 依旧青山,本期给大家带来Vue篇专栏内容:Vue-ECharts自适应 目录 前言 1920*1080分辨率示图 8184*2432分辨率示图 以vue3ts开发为例 (…

C++第十弹 ---- vector的介绍及使用

目录 前言vector的介绍及使用1. vector的使用1.1 vector的定义1.2 iterator的使用1.3 vector空间增长问题1.4 vector增删查改 2. vector迭代器失效问题(重点) 总结 前言 本文介绍了C中的vector数据结构及其使用方法。 更多好文, 持续关注 ~ 酷酷学!!! 正文开始 vector的介绍…

面试场景题系列--(2)短 URL 生成器设计:百亿短 URL 怎样做到无冲突?--xunznux

文章目录 面试场景题&#xff1a;短 URL 生成器设计&#xff1a;百亿短 URL 怎样做到无冲突&#xff1f;1. 需求分析2. 短链接生成算法2.1 自增法2.2 散列函数法2.3 预生成法 3. 部署模型3.1 其他部署方案 4. 设计4.1 重定向响应码4.2 短 URL 预生成文件及预加载4.3 用户自定义…

代码静态检查简介

在软件开发领域&#xff0c;确保代码质量是项目成功的关键要素之一。代码静态检查作为一种重要的质量保证手段&#xff0c;通过在不运行代码的情况下&#xff0c;对代码进行自动化的分析和审查&#xff0c;帮助开发团队及时发现并修复潜在的缺陷、安全漏洞以及不符合编码规范的…

Jenkins详细使用教程

目录 1. 什么是Jenkins&#xff1f; 2. 为什么使用Jenkins&#xff1f; 3. 安装Jenkins 3.1 下载相关文件 3.2 解压Linux版本的JDK 3.3 配置JDK环境 3.4 运行jenkins.war 3.5 安装完成 4. 访问Jenkins 5. 修改密码 6. 集成JDK 7. Jenkins集成Git 7.1 使用Jenkins拉取…

7月26日贪心练习-摆动序列专题

前言 大家好&#xff0c;今天学习用贪心思想解决摆动序列问题&#xff0c;共三题&#xff0c;分享自己的思路&#xff0c;请大家多多支持 算法思想 大家可以先看看这道我们后面会讲的题看看怎么个事&#xff0c;. - 力扣&#xff08;LeetCode&#xff09; 由此题题解说明算…

若依ruoyi+AI项目二次开发

//------------------------- //定义口味名称和口味列表静态数据 const dishFlavorListSelectref([ {name:"辣度",value:["不辣","微辣","中辣","重辣"]}, {name:"忌口",value:["不要葱","不要…

JVM之对象的创建过程

目录 对象的创建&#xff1a; 对象内存分配的两种方式&#xff1a; 指针碰撞&#xff1a; 空闲列表&#xff1a; 对象的内存布局&#xff08;基本结构&#xff09;&#xff1a; 对象的访问定位&#xff1a; 主流的访问方式主要有使用句柄和直接指针两种。 对象的创建&…

基于微信小程序+SpringBoot+Vue的流浪动物救助(带1w+文档)

基于微信小程序SpringBootVue的流浪动物救助(带1w文档) 基于微信小程序SpringBootVue的流浪动物救助(带1w文档) 本系统实现的目标是使爱心人士都可以加入到流浪动物的救助工作中来。考虑到救助流浪动物的爱心人士文化水平不齐&#xff0c;所以本系统在设计时采用操作简单、界面…

FPGA实现LCD1602控制

目录 注意&#xff01; 本工程采用野火征途PRO开发板&#xff0c;外接LCD1602部件进行测试。 有偿提供代码&#xff01;&#xff01;&#xff01;可以定制功能&#xff01;&#xff01;&#xff01; 联系方式见底部 一、基础知识 1.1 引脚信息 1.2 指令 1.2.1 清屏 1.…

ubuntu实践

目录 扩容 本机上ping不通新建立的虚拟机 ssh连接 装sshd ssh客户端版本较低&#xff0c;会报key exchange算法不匹配问题 ubuntun上装docker 将centos7下的安装包改造成适配 ubuntu的包 参考文章 扩容 Hyper-V 管理器安装的ubutun扩容磁盘空间说明_hype-v磁盘扩容-…

人工智能算法工程师(中级)课程20-模型注意力机制之注意力机制的原理、计算方式与代码详解

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下人工智能算法工程师(中级)课程20-模型注意力机制之注意力机制的原理、计算方式与代码详解。本文深入探讨了注意力机制在深度学习中的应用与原理&#xff0c;尤其聚焦于序列到序列模型的上下文中。通过直观的解释和详…

48 mysql 全局变量修改了时区, 客户端拿到的依然是旧时区

前言 这是一个 我们最近碰到的问题 在我们的一个 服务平台 查询到的时间字段 比 当前时区的当前时间多 8 小时 然后 这个问题 也是挺神奇的, navicate 上面查询到的 时间是在正常的时间 然后 查询环境变量 tz_zone 是 “08:00”, 也没有问题, 但是 客户端这边 拿到的是 当…

【HTML+CSS】HTML超链接:构建网页导航的基石

目录 什么是HTML超链接&#xff1f; 基本语法 示例 链接到另一个网页 链接到同一页面内的不同部分 常用属性 在Web开发的广阔世界中&#xff0c;HTML&#xff08;HyperText Markup Language&#xff09;作为网页内容的标准标记语言&#xff0c;扮演着至关重要的角色。而在…

nodejs安装及环境配置轨道交通运维检测系统App-OA人事办公排班故障维修

✌网站介绍&#xff1a;✌10年项目辅导经验、专注于计算机技术领域学生项目实战辅导。 ✌服务范围&#xff1a;Java(SpringBoo/SSM)、Python、PHP、Nodejs、爬虫、数据可视化、小程序、安卓app、大数据等设计与开发。 ✌服务内容&#xff1a;免费功能设计、免费提供开题答辩P…

【SpringCloud】企业认证、分布式事务,分布式锁方案落地-2

目录 高并发缓存三问 - 穿透 缓存穿透 概念 现象举例 解决方案 缓存穿透 - 预热架构 缓存穿透 - 布隆过滤器 布隆过滤器 布隆过滤器基本思想​编辑 了解 高并发缓存三问 - 击穿 缓存击穿 高并发缓存三问 - 雪崩 缓存雪崩 解决方案 总结 为什么要使用数据字典&…