微信网站技术方案,寮步营销型网站建设价格,wordpress修改后台管理地址=,去韩国用什么地图导航构造有效字符串的最少插入数
题目要求 解题思路
考虑abc的个数
假设答案有n个abc组成#xff0c;那么需要插入的字符个数为 3 ∗ n − l e n ( s ) 3*n - len(s) 3∗n−len(s)。
对于相邻的两个字符x和y#xff08;x在y左侧#xff09;#xff1a;
如果 x…构造有效字符串的最少插入数
题目要求 解题思路
考虑abc的个数
假设答案有n个abc组成那么需要插入的字符个数为 3 ∗ n − l e n ( s ) 3*n - len(s) 3∗n−len(s)。
对于相邻的两个字符x和yx在y左侧
如果 x y xy xy那么x和y可以在同一个abc内否则一定不在如果 x ≥ y x\ge y x≥y那么x和y一定不可以在同一个abc内
所以 n n n就是 x ≥ y x\ge y x≥y 的次数加1
代码 class Solution:def addMinimum(self, s: str) - int:ans ord(s[0]) - ord(s[-1]) 2for x, y in pairwise(map(ord, s)):ans (y - x 2) % 3return ans
复杂度分析
时间复杂度 O ( n ) O(n) O(n)其中 n n n为word的长度空间复杂度 O ( 1 ) O(1) O(1)
