题目以及简单翻译

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.
给出一个字符串 s,计算由 ‘0’ 和 ‘1’ 组成的,连续且不为空的字符串,并且所有的 ‘0’ 和 ‘1’都是连续的。

Substrings that occur multiple times are counted the number of times they occur.
计算子串对称状况发生次数。
例子 1:

分析: 六个 ‘0’ 和 ‘1’ 分别连续出现相同次数的子串:”0011″, “01”, “1100”, “10”, “0011”, 和 “01”.

注意,重复的子串也记作发生次数。

同时,”00110011″ ‘0’ 和 ‘1’ 出现次数相同,但是其中由 ‘0’ 和 ‘1’并未连续出现。

例子 2:

分析: 四个符合条件的子串: “10”, “01”, “10”, “01”

注意:

  • s.length 在 1 和 50,000 之间
  • s 只包含 “0” 或者 “1” 字符。

解题思路

占内存且不讨好的方法

字符串 s 存储的东西其实并不重要,我们只要知道每一个字符串片段中中 0 和 1 出现了几次,比如“0011”,我们可以理解为“22”,合法子串一共六个,”0011″, “01”.

聪明的方法

两个值分别存储0和1的数量,0(或者1)存满(一个0(或者1)区间存储完毕)之后,开始存储1(或者0)同时结果增加,直到1也存满,此时轮换继续。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部