STACK

发布时间:2024年01月11日

1. LC 2645 构造有效字符串的最少插入数

这题模拟栈即可,不需要真的用,因为一直访问的都是栈顶元素,所以维护一个栈顶指针即可。

维护下一个需要使用到的元素。例如上一个是a,那么下一个就是b。如果上一个是c,那么下一个是a。取余即可。

如果当前元素位于这个应有的元素后方,那么需要补齐中间的;如果在前方,说明上一轮abc还有缺,需要补上;如果正好就是这个应有元素,那么看下一个字符即可。

时间O(n)空间O(1)

class Solution {
    static int mod = 3;
    public int addMinimum(String word) {
        char[] ch = word.toCharArray();
        int top=0,dis;
        int cnt = 0;
        int index = 0;
        while(index<ch.length){
            char c = ch[index];
            dis = c-'a';
            if(dis==top){
                top = (top+1)%mod;
                index++;
            }else{
                if(dis>top){
                    cnt += dis-top;
                }else{
                    cnt += mod+dis-top;
                }
                top = dis;
            }
        }
        if(top!=0){
            cnt += mod - top;
        }
        return cnt;
    }
}

文章来源:https://blog.csdn.net/lyh20021209/article/details/135523853
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。