网站建设趋势2017,网站建设全程揭秘,软件合集软件资料2023,西安企业网站建设哪家专业Problem: 2645. 构造有效字符串的最少插入数 文章目录 思路解题方法复杂度Code 思路 决定开头的差距#xff1b;决定中间的补足决定末尾的差距#xff1b; 解题方法 开头的位置对于a不做处理#xff0c;b则做出加一的处理#xff0c;c则是加二的处理方法#xff1b;中间的… Problem: 2645. 构造有效字符串的最少插入数 文章目录 思路解题方法复杂度Code 思路 决定开头的差距决定中间的补足决定末尾的差距 解题方法 开头的位置对于a不做处理b则做出加一的处理c则是加二的处理方法中间的位置对于当前位置是a如果下一个位置是b不做处理如果是c则是加一a则是加2同理可得b对于a1b2c对于b1c2.综合上面两点将加一和加二的情况进行分类处理 末尾c不处理b1a2 复杂度 时间复杂度 O ( n ) O(n) O(n) 添加空间复杂度 O ( 1 ) O(1) O(1) Code
class Solution {
public:int addMinimum(string word) {int lenword.size();int aMinimum0;aMinimumabs(a-word[0]);aMinimumc-word[len-1];for(int i 1;ilen;i){if(word[i-1]-word[i]-2||word[i-1]-word[i]1){aMinimum1;}if(word[i-1]word[i]){aMinimum2;}}return aMinimum;}
};
