【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;}
};~希望对你有启发~