1221. Split a String in Balanced Strings
程序员文章站
2022-04-08 09:11:14
...
第一次解:2020.1.30
这个题想了五分钟,觉得可能还是需要使用队列。队列的东西有些遗忘,需要复习一下。【看了一分钟觉得其实需要的队列内容不多,汗????,其实直接使用vector就可以处理】
第一次的解决方案(用时30分钟):
速度很慢,需要优化
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;
}
};
学习一下别人的解决方案:
我的想法是考虑每一个子串是否是平衡的,但是实际上,一旦一个子串是平衡的,说明他前面的那个也是平衡的。换言之,前面的平衡不会影响到对后面的判断。其他人的解决方案都是从这样的角度来考虑的。我的解决方案太耗时耗力了。是我想太多并且想的不对。因为给定的长字符串就是平衡的,所以一旦部分是平衡的,剩下的一定也是平衡的。所以考虑当前或者说当前和以前就可以了,不用考虑之后。