696. 计数二进制子串

696. 计数二进制子串

第一次解：
暴力方法
遍历每个数据，找到其后第一个不同的数，然后看是能与其有匹配数量，有的话总数加一。

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
    let len = s.length;
    let p = 0;
    let q;
    let res = 0;
    while(p < len) {
        q= p+1;
        while(q < len) {
            if(s[q] !== s[p]) {
                break;
            } 
            q++;
        }
        if(q < len && s[q] !== s[p]) {
            let repeatNum = q-p-1;
            let flag = true;
            while(repeatNum > 0) {
                if( (q < len-1) && (s[q+1] === s[q])) {
                    repeatNum--;
                    q++;
                } else {
                    flag = false;
                    break;
                }
            }
            if(repeatNum===0 && flag) {
                res++;
            }
        }
        p++;
    }
    return res;
};

结果：
超出时间限制

第二次解：
找到不同数的数量保存进数组，每次取Math.min(pre,cur)，累加后即得最后总数。

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
    let len = s.length;
    let arr = [1];
    let res = 0;
    for(let i = 1; i < len; i++) {
        if(s[i] === s[i-1]) {
            arr[arr.length-1]++;
        } else {
            arr.push(1);
        }
    }
    let arrLen = arr.length;
    for(let j = 1; j<arrLen; j++) {
        res += Math.min(arr[j], arr[j-1]);
    }
    return res;
};

结果通过。

第三次 使用更少的空间
不保留数组，仅保留前一个和当前数数量的值。

/**
 * @param {string} s
 * @return {number}
 */
var countBinarySubstrings = function(s) {
    let len = s.length;
    let res = 0;
    let pre = 0;
    let cur = 1;
    for(let i = 1; i < len; i++) {
        if(s[i] === s[i-1]) {
            cur++;
        } else {
            res += Math.min(pre, cur);
            pre = cur;
            cur = 1;
        }
    }
    return res+ Math.min(pre, cur);
};