problem
题意:具有相同个数的1和0的连续子串的数目;
solution1:还不是特别理解。。。
遍历元数组,如果是第一个数字,那么对应的ones或zeros自增1。然后进行分情况讨论,如果当前数字是1,然后判断如果前面的数字也是1,则ones自增1,否则ones重置为1。如果此时zeros大于ones,res自增1。反之同理,如果当前数字是0,然后判断如果前面的数字也是0,则zeros自增1,否则zeros重置为1。如果此时ones大于zeros,res自增1。
class Solution { public: int countBinarySubstrings(string s) { int zeros = 0, ones = 0, res = 0; for(int i=0; i<s.size(); ++i) { if(i==0) s[i]=='0' ? zeros++ : ones++; else if (s[i]=='1') { ones = (s[i-1]=='1') ? ones+1 : 1; if(zeros>=ones) res++; } else if(s[i]=='0') { zeros = (s[i-1]=='0') ? zeros+1 : 1; if(ones>=zeros) res++; } } return res; } };
solution2:
class Solution { public: int countBinarySubstrings(string s) { int pre = 0, cur = 1, res = 0; for(int i=1; i<s.size(); ++i) { if(s[i]==s[i-1]) cur++; else { pre = cur; cur = 1; } if(pre>=cur) res++; } return res; } };
参考
1. Leetcode_easy_696. Count Binary Substrings;
2. Grandyang;
完