[Leetcode][第696题][JAVA][计算二进制子串][分组]

曾经终败给现在 2022-11-26 07:41 79阅读 0赞

#### 【问题描述】\[简单\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 按字符分组 ######

将字符串 ss 按照 00 和 11 的连续段分组，存在counts 数组中，例如 s = 00111011，可以得到这样的counts 数组：**counts=\{2,3,1,2\}**。

这里counts 数组中两个相邻的数一定代表的是两种不同的字符。假设 counts 数组中两个相邻的数字为 u 或者 v，它们对应着 u 个 0 和 v 个 1，或者 u 个 1 和 v 个 0。它们能组成的满足条件的子串数目为 min\{u,v\}，即一对相邻的数字对答案的贡献。

我们只要遍历所有相邻的数对，求它们的贡献总和，即可得到答案。

**时间复杂度：O(N) 空间复杂度：O(N)**

class Solution { 
        public int countBinarySubstrings(String s) { 
            List<Integer> counts = new ArrayList<Integer>();
            int ptr = 0, n = s.length();
            while (ptr < n) { 
                char c = s.charAt(ptr);
                int count = 0;
                while (ptr < n && s.charAt(ptr) == c) { 
                    ++ptr;
                    ++count;
                }
                counts.add(count);
            }
            int ans = 0;
            for (int i = 1; i < counts.size(); ++i) { 
                ans += Math.min(counts.get(i), counts.get(i - 1));
            }
            return ans;
        }
    }

对于某一个位置 i，其实我们只关心 i - 1位置的counts 值是多少，所以可以用一个 last 变量来维护当前位置的前一个位置，这样可以省去一个 counts 数组的空间。

**时间复杂度：O(N) 空间复杂度：O(1)**

class Solution { 
        public int countBinarySubstrings(String s) { 
            int ptr = 0, n = s.length(), last = 0, ans = 0;
            while (ptr < n) { 
                char c = s.charAt(ptr);
                int count = 0;
                while (ptr < n && s.charAt(ptr) == c) { 
                    ++ptr;
                    ++count;
                }
                ans += Math.min(count, last);
                last = count;
            }
            return ans;
        }
    }

###### 2. 遍历 数前面个数大于后面个数的子串 ######

定义两个变量preLen和curLen，分别表示前面连续字符串中字符的个数，现在连续字符串中字符的个数。  
当前字符和上一个字符相等时curLen++,不相等时preLen=curLen,然后curLen设为1。  
如果preLen>=curLen,那么结果+1。  
例如0011,应该输出为2。  
1.curLen=1,preLen=0,ret=0;  
2.curLen=2,preLen=0,ret=0;  
3.curLen=1,preLen=2,ret=1;//001中的01  
4.curLen=2,preLen=2,ret=2;//0011中的0011

class Solution { 
        public int countBinarySubstrings(String s) { 
            int preLen=0,curLen=1,ret=0;
            for(int i=1;i<s.length();i++){ 
                if(s.charAt(i-1)==s.charAt(i)) curLen++;
                else{ 
                    preLen=curLen;
                    curLen=1;
                }
                if(preLen>=curLen) ret++;
            }
            return ret;
        }
    }

#### 【总结】 ####

###### 1. 字符串数数题目 分类数找规律是一种思路 ######

###### 2.这题简单题难在思路 ######

###### 3. ######

转载链接：https://leetcode-cn.com/problems/count-binary-substrings/solution/ji-shu-er-jin-zhi-zi-chuan-by-leetcode-solution/

参考链接：https://leetcode-cn.com/problems/count-binary-substrings/solution/yi-ge-bi-jiao-qiao-miao-de-ban-fa-by-uygn9i8c6n/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20221124/c5119aec3b274b9d8110a68e701e70f5.png