Question
Example1
Input: "00110011"Output: 6Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".Notice that some of these substrings repeat and are counted the number of times they occur.Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.
Example2
Input: "10101"Output: 4Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.
Solution
题目大意:
给一个只有01组成的字符串,求子串数,子串必须满足
- 0和1出现次数一样
- 保证0连续1连续
思路:
参考下面参考链接的思路:
上一个连续子串长度记为preRunLength,当前连续子串长度记为curRunLength,res记为满足条件的子串数
Java实现:
public int countBinarySubstrings(String s) { int preRunLength = 0, curRunLength = 1, res = 0; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == s.charAt(i - 1)) { // 当前字符与上一字符相同,表示当前连续子串未断 curRunLength++; // 当前连续子串长度加1 } else { // 当前字符与上一字符不同,表示当前连续子串结束 preRunLength = curRunLength; // 当前连续子串长度变为上一个连续子串长度 curRunLength = 1; // 当前连续子串长度为1 } if (preRunLength >= curRunLength) res++; // 当前连续子串长度小于上一个连续子串长度就满足要求 } return res;}