题目:给定一个字符串 s,计算具有相同数量0和1的非空(连续)子字符串的数量,并且这些子字符串中的所有0和所有1都是组合在一起的。
重复出现的子串要计算它们出现的次数。
示例:
输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0:“0011”,“01”,“1100”,“10”,“0011” 和 “01”。请注意,一些重复出现的子串要计算它们出现的次数。
另外,“00110011”不是有效的子串,因为所有的0(和1)没有组合在一起。
最先想用栈来解决,但发现行不通。然后慢慢发现规律了,我们可以用一个指针对准第一个数字的起点(最先是0),然后用另一个指针对准另一个数字的起点(如示例中第一个1的位置),然后两个指针一起跑,只要它们对应位置的值不相等,那答案就加1。值相等后必然是其中一个数字跑完了,可以根据和前一个位置对比得出是跑在前面的指针跑完了还是跑在后面的,如果是前面的先跑完了就让后面的指针直接跑到下一个起点(即前面的指针本次的起点),接着开始下一轮,直到有一个指针到达末尾。
好吧上面一段其实并不用看,我们只需要将相同的数字看作一组,然后遍历每组的数字个数组成的数组,相邻元素取最小值,加起来就得到结果了。比如示例的数组为[2, 2, 2, 2],相邻取最小再加起来就是6。
其实理论上说两个方法是差不多的,后者像是前者的抽象化。我们刷算法题总是容易下意识的用人类思维思考,然后用计算机去“模拟”,所以经常会遇到将思维转化为代码时不流畅和容易出错。我认为所谓算法思想,就是一种将人类思维抽象成计算机思维的能力。