这是悦乐书的第293次更新，第311篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第161题（顺位题号是696）。给定一个字符串s，计算具有相同数字0和1的非空且连续子串的数量，并且这些子串中的所有0和所有1都是连续的。重复出现的子串也计算在内。例如：
输入：“00110011”
输出：6
说明：有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011”和“01”。其中一些子字符串重复出现了，但是也需要计算它们出现的次数。此外，“00110011”不是有效的子字符串，因为所有0（和1）都没有组合在一起。
输入：“10101”
输出：4
说明：有4个子串：“10”，“01”，“10”，“01”具有相同数量的连续1和0。
注意：
-
字符串长度将介于1到50,000之间。
-
s只包含“0”或“1”字符。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
题目的意思是在给定的字符串中找到连续的0和1组成的子串个数，其中0和1是挨着的，可以有多个连续的0与多个连续的1。比如，0011，其中就有两个子串符合，一是第二位与第三位组成的01，二是其本身，两个0和两个1。再比如00111，同样也只有两个子串符合，一是01，二是0011。所以，我们的判断标准就变成了，在一个由0和1组成的连续子串中，0的个数与1的个数，取其中的较小值，就是可能的子串数。
对此，我们将原字符串中，将每段连续的0或者1的个数统计出来，然后比较相邻的两段的值，取其中较小的进行累加，最后就是该字符串所有可能的子串数。
此解法的时间复杂度是O(n)，空间复杂度是O(n)。
public int countBinarySubstrings(String s) {
int[] arr = new int[s.length()];
arr[0] = 1;
int index = 0;
for (int i=1; i<s.length(); i++) {
if (s.charAt(i) != s.charAt(i-1)) {
arr[++index] = 1;
} else {
arr[index]++;
}
}
int count = 0;
for (int i=1; i <= index; i++) {
count += Math.min(arr[i], arr[i-1]);
}
return count;
}
03 第二种解法
第一种解法中，我们将每段分组的值存到了新数组中，在分段完后，再去计算总数，但是我们也可以不使用新数组，直接在统计分段时，就将值累加起来。我们使用两个临时变量，一个存储当前这段分组的长度，一个存储上一段分组的长度，在循环字符串中的字符时，如果当前字符和前一个字符不相等，说明该分段了，此时需要先比较两个临时变量的值，取较小的累加到count上去，然后将上一段的长度赋值给另外一个变量，当前新段的长度重置为1。在循环结束后，还需要再取两者之间的较小值再累加一次，因为有可能最后一段就是连续的，而不能在循环里进行判断了。
public int countBinarySubstrings(String s) {
int currentLength = 1, prevLength = 0, count = 0;
for (int i=1; i<s.length(); i++) {
if (s.charAt(i) != s.charAt(i-1)) {
count += Math.min(prevLength, currentLength);
prevLength = currentLength;
currentLength = 1;
} else {
currentLength++;
}
}
count += Math.min(prevLength, currentLength);
return count;
}
04 小结
算法专题目前已日更超过四个月，算法题文章161+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论