這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)LeetCode中計(jì)數(shù)二進(jìn)制子串的示例分析，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。
魏都網(wǎng)站制作公司哪家好，找成都創(chuàng)新互聯(lián)公司！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、成都響應(yīng)式網(wǎng)站建設(shè)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營(yíng)維護(hù)。成都創(chuàng)新互聯(lián)公司從2013年創(chuàng)立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選成都創(chuàng)新互聯(lián)公司。
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.
方法一：暴力算法，遇到超長(zhǎng)字符串會(huì)超時(shí)，故棄。
方法二：發(fā)現(xiàn)字符串其中規(guī)律
如'00000111'，一個(gè)連續(xù)'0'與連續(xù)'1'的字符串，符合題意要求的子字符串為min('0‘的個(gè)數(shù), '1'的個(gè)數(shù))=min(5,3)=3。
如’000011100111‘字符串，以連續(xù)相同字符分為一個(gè)區(qū)間規(guī)則，得到[0,3]，[4,6]，[7,8]，[9,11]共4個(gè)區(qū)間。
由2. 得到區(qū)間，將其兩兩相鄰配對(duì)，如[0,3]與[4,6]，[4,6]與[7,8]，再由1. 得出規(guī)律求出兩配對(duì)區(qū)間符合題意要求的子字符串個(gè)數(shù)，最后將其累加，便能得到最后結(jié)果。
方法三：方法二改進(jìn)版。
重慶分公司
重慶分公司
import java.util.ArrayList;
import java.util.List;
public class CountBinarySubstrings {
// 方法一：暴力算法，遇到超長(zhǎng)字符串會(huì)超時(shí)
public int countBinarySubstrings(String s) {
int result = 0;
// List 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 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;
}
// 方法三：方法二的改進(jìn)版
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();
}
} 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中計(jì)數(shù)二進(jìn)制子串的示例分析了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
