LeetCode中計數二進制子串的示例分析

這期內容當中小編將會給大家帶來有關LeetCode中計數二進制子串的示例分析，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

Description

https://leetcode.com/problems/count-binary-substrings/

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.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"
Output: 6
Explanation: 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.

Example 2:

Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Note:

• s.length will be between 1 and 50,000.

• s will only consist of "0" or "1" characters.

Analysis

方法一：暴力算法，遇到超長字符串會超時，故棄。

方法二：發現字符串其中規律

1. 如'00000111'，一個連續'0'與連續'1'的字符串，符合題意要求的子字符串為min('0‘的個數, '1'的個數)=min(5,3)=3。

2. 如’000011100111‘字符串，以連續相同字符分為一個區間規則，得到[0,3]，[4,6]，[7,8]，[9,11]共4個區間。

3. 由2. 得到區間，將其兩兩相鄰配對，如[0,3]與[4,6]，[4,6]與[7,8]，再由1. 得出規律求出兩配對區間符合題意要求的子字符串個數，最后將其累加，便能得到最后結果。

方法三：方法二改進版。

Submission

import java.util.ArrayList;
import java.util.List;

public class CountBinarySubstrings {

	// 方法一：暴力算法，遇到超長字符串會超時
	public int countBinarySubstrings(String s) {
		int result = 0;
		// List<String> resultList = new ArrayList<>();
		for (int i = 0; i < s.length(); i++) {
			int state = 1;
			char tempChar = s.charAt(i);
			int firstCharCount = 1, secondCharCount = 0, rightPartCount = 0;
			for (int j = i + 1; j < s.length(); j++) {
				if (state == 1) {

					if (tempChar == s.charAt(j)) {
						firstCharCount++;
					} else {
						state = 2;
						tempChar = s.charAt(j);
					}
				}

				if (state == 2) {
					if (tempChar == s.charAt(j)) {
						secondCharCount++;
					}
					rightPartCount++;

					if (rightPartCount == firstCharCount) {
						if (secondCharCount == firstCharCount) {
							result++;
							// resultList.add(repeat(tempChar=='1'?'0':'1', firstCharCount) +
							// repeat(tempChar, secondCharCount));
						}
						break;
					}
				}
			}
		}

		return result;
	}

	// 方法二：
	public int countBinarySubstrings2(String s) {
		List<int[]> list = new ArrayList<>();
		int result = 0, tempIndex = 0;
		for (int i = tempIndex + 1; i <= s.length(); i++) {
			if (i == s.length() || s.charAt(i) != s.charAt(tempIndex)) {
				list.add(new int[] { tempIndex, i - 1 });
				tempIndex = i;
			}
		}

		for (int i = 0; i < list.size(); i++) {
			int[] leftPart = list.get(i);
			if (i + 1 == list.size()) {
				break;
			}
			int[] rightPart = list.get(i + 1);

			int leftSize = leftPart[1] - leftPart[0] + 1;
			int rightSize = rightPart[1] - rightPart[0] + 1;

			result += Math.min(leftSize, rightSize);
		}
		return result;
	}

	// 方法三：方法二的改進版
	public int countBinarySubstrings3(String s) {
		int result = 0, lastIndex = 0, lastSize = 0;
		for (int i = lastIndex + 1; i <= s.length(); i++) {

			if (i == s.length() || s.charAt(i) != s.charAt(lastIndex)) {

				if (lastSize == 0) {
					lastSize = i - lastIndex;
				} else {
					int currentSize = i - lastIndex;
					result += Math.min(lastSize, currentSize);
					lastSize = currentSize;
				}
				lastIndex = i;
			}

		}

		return result;
	}

	private String repeat(char c, int times) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < times; i++) {
			sb.append(c);
		}
		return sb.toString();
	}

}

Test

import static org.junit.Assert.*;
import org.junit.Test;

public class CountBinarySubstringsTest {

	@Test
	public void test() {
		CountBinarySubstrings obj = new CountBinarySubstrings();

		assertEquals(6, obj.countBinarySubstrings("00110011"));
		assertEquals(4, obj.countBinarySubstrings("10101"));
	}
	
	@Test
	public void test2() {
		CountBinarySubstrings obj = new CountBinarySubstrings();
		
		assertEquals(6, obj.countBinarySubstrings2("00110011"));
		assertEquals(4, obj.countBinarySubstrings2("10101"));
	}
	
	@Test
	public void test3() {
		CountBinarySubstrings obj = new CountBinarySubstrings();
		
		assertEquals(0, obj.countBinarySubstrings3("00"));
		assertEquals(1, obj.countBinarySubstrings3("001"));
		assertEquals(6, obj.countBinarySubstrings3("00110011"));
		assertEquals(4, obj.countBinarySubstrings3("10101"));
		assertEquals(3, obj.countBinarySubstrings3("00110"));
	}
}

上述就是小編為大家分享的LeetCode中計數二進制子串的示例分析了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。