欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1221. Split a String in Balanced Strings

程序员文章站 2022-04-08 09:11:14
...

第一次解:2020.1.30

这个题想了五分钟,觉得可能还是需要使用队列。队列的东西有些遗忘,需要复习一下。【看了一分钟觉得其实需要的队列内容不多,汗????,其实直接使用vector就可以处理】

第一次的解决方案(用时30分钟):

速度很慢,需要优化

1221. Split a String in Balanced Strings

class Solution {
public:
    int balancedStringSplit(string s) 
    {
        int res = 0;
        int nums = s.length();
        if(nums == 1)
        {
            return 0;
        }

        std::vector<char> parts;
        int i=0;
        for(;i<nums;)
        {
            if(parts.size()==0)
            {
                if(i>0)
                {
                    res += 1;
                }
                parts.push_back(s[i]);
                ++ i;
            }
            else
            {
                if(parts.back() == s[i])//容器内存放的元素和当前排查的元素一致
                {
                    parts.push_back(s[i]);
                    ++ i;
                }
                else
                {
                    parts.pop_back();
                    ++ i;
                }
            }
        }
        if(i == nums && parts.size()==0)
        {
            res += 1;
        }
        return res;   
    }
};

学习一下别人的解决方案:

我的想法是考虑每一个子串是否是平衡的,但是实际上,一旦一个子串是平衡的,说明他前面的那个也是平衡的。换言之,前面的平衡不会影响到对后面的判断。其他人的解决方案都是从这样的角度来考虑的。我的解决方案太耗时耗力了。是我想太多并且想的不对。因为给定的长字符串就是平衡的,所以一旦部分是平衡的,剩下的一定也是平衡的。所以考虑当前或者说当前和以前就可以了,不用考虑之后。

 

 

 

 

相关标签: 基础算法