leetcode696：计数二进制字符串（count-binary-substrings）

[carloscn]

问题描述

给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。

重复出现（不同位置）的子串也要统计它们出现的次数。

示例 1：

输入：s = "00110011" 输出：6 解释：6 个子串满足具有相同数量的连续 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。 注意，一些重复出现的子串（不同位置）要统计它们出现的次数。 另外，"00110011" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。 示例 2：

输入：s = "10101" 输出：4 解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。   提示：

1 <= s.length <= 105 s[i] 为 '0' 或 '1'

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/count-binary-substrings

[carloscn]

问题分析

在评论中非常有技巧的做法，的确是很难想，参考一下训练一下思维就好。但我们本质还是训练的是编程能力，编程能力就是能够随意的把脑海中的想法实现出来，而这个想法可能是有技巧的，也可能是笨拙的。只要能训练达到把思路快速转为程序我觉得就达到了训练的目的。追求技巧和思维只作为一个次级优先级的。

fn count_num(in_str: &str) -> bool
{
    let len:usize = in_str.len();
    let mut count_a:usize = 0;
    let mut count_b:usize = 0;
    let mut reversed:bool = false;
    let in_bytes = in_str.as_bytes();
    let mut byte:u8 = in_bytes[0].clone();

    if len < 2_usize {
        return false;
    }

    for i in in_bytes {

        if (reversed == false) && (byte == *i) {
            count_a += 1;
            byte = (*i).clone();
            continue;
        } else {
            reversed = true;
            byte = (*i).clone();
        }

        if (reversed == true) && (byte == *i) {
            count_b += 1;
            byte = (*i).clone();
            continue;
        } else {
            return false;
        }
    }

    if count_a == count_b {
        return true;
    } else {
        return false;
    }

}

fn count_binary_substr(in_str:&str) -> usize
{
    let mut count:usize = 0;
    let sub_vec:Vec<String> = utils::str::append_all_substr(in_str);
    let mut i:usize = 0;
    let mut result:bool = false;

    while i < sub_vec.len() {
        result = count_num(&sub_vec[i]);
        if result == true {
            count += 1;
            println!("found {}", &sub_vec[i]);
        }
        i += 1;
    }
    return count;
}

static bool count_num(const char *str)
{
    size_t len = strlen(str);
    size_t i = 0;
    size_t count_a = 0;
    size_t count_b = 0;
    bool reversed = false;
    char c = str[0];

    if (len < 2) {
        return false;
    }

    for (i = 0; i < len; i ++) {
        if (reversed == false && c == str[i]) {
            count_a ++;
            c = str[i];
            continue;
        } else {
            reversed = true;
            c = str[i];
        }

        if (reversed == true && c == str[i]) {
            count_b ++;
            c = str[i];
            continue;
        } else {
            return false;
        }
    }

    if (count_a == count_b) {
        return true;
    } else {
        return false;
    }
}

static int32_t count_binary_substr(const char *str, size_t *result)
{
    int32_t ret = 0;
    size_t len = 0;
    bool res = false;
    size_t count = 0;
    size_t i = 0, j = 0;
    char *dup_str = NULL;
    STRLIST_T *list = NULL;

    UTILS_CHECK_PTR(str);
    UTILS_CHECK_PTR(result);
    UTILS_CHECK_LEN(len = strlen(str));

    list = strlist_malloc();
    UTILS_CHECK_PTR(list);

    dup_str = strdup(str);
    UTILS_CHECK_PTR(dup_str);

    len = strlist_append_all_substr(list, dup_str);
    strlist_infolog(list);

    for (i = 2; i < len; i ++) {
        res = count_num(strlist_get_str_at(list, i));
        if (res == true) {
            count ++;
            LOG("found %s\n", strlist_get_str_at(list, i));
        }
    }

    LOG("the reuslt is %zu\n", count);
    *result = count;

finish:
    strlist_free(list);
    return ret;
}
###

[carloscn]

code:

https://github.com/carloscn/structstudy/blob/master/c_programming/str/n38_count_binary_substrings_696.c https://github.com/carloscn/structstudy/blob/master/rust_programming/str/src/n38_count_binary_substrings_696.rs

result: