做旅游网站的需求分析报告,怎么让搜索引擎收录网站,重庆景点排名前十,手机价格大全文章目录 Tag题目来源解题思路方法一#xff1a;考虑 abc 的个数 写在最后 Tag
【字符串】【2024-01-11】 题目来源
2645. 构造有效字符串的最少插入数 解题思路
方法一#xff1a;考虑 abc 的个数
思路
如果答案由 t 个 “abc” 组成#xff0c;那么需要插入字符个数为… 文章目录 Tag题目来源解题思路方法一考虑 abc 的个数 写在最后 Tag
【字符串】【2024-01-11】 题目来源
2645. 构造有效字符串的最少插入数 解题思路
方法一考虑 abc 的个数
思路
如果答案由 t 个 “abc” 组成那么需要插入字符个数为 3t - n。
如何求 t ?
我们考虑相邻的两个字符如果前一个字符大于或者等于后一个字符对应的 ASCII 码比较则 t t 1初始的 t 1。
算法
class Solution {
public:int addMinimum(string word) {int t 1;int n word.size();for (int i 1; i n; i) {t word[i-1] word[i];}return 3*t - n;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) n n n 为字符串 word 的长度。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
