企业网站建设的建议,网站管理系统安装,云商城是什么,九秀直播间【问题描述】[简单] 【解答思路】
1. 按字符分组
将字符串 ss 按照 00 和 11 的连续段分组#xff0c;存在counts 数组中#xff0c;例如 s 00111011#xff0c;可以得到这样的counts 数组#xff1a;counts{2,3,1,2}。
这里counts 数组中两个相邻的数一定代表的是两种…【问题描述】[简单] 【解答思路】
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) {ListInteger counts new ArrayListInteger();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,不相等时preLencurLen,然后curLen设为1。 如果preLencurLen,那么结果1。 例如0011,应该输出为2。 1.curLen1,preLen0,ret0; 2.curLen2,preLen0,ret0; 3.curLen1,preLen2,ret1;//001中的01 4.curLen2,preLen2,ret2;//0011中的0011
class Solution {public int countBinarySubstrings(String s) {int preLen0,curLen1,ret0;for(int i1;is.length();i){if(s.charAt(i-1)s.charAt(i)) curLen;else{preLencurLen;curLen1;}if(preLencurLen) 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/
