[数据结构与算法][Leetcode] 1513.仅含 1 的子串数 - Rust 实现

Leetcode 1513. 仅含 1 的子串数

问题描述

给你一个二进制字符串 s（仅由 ‘0’ 和 ‘1’ 组成的字符串）。

返回所有字符都为 1 的子字符串的数目。

由于答案可能很大，请你将它对 10^9 + 7 取模后返回。

解题思路

连续1串的包含子串数具有规律，满足等差数列.

所以题目就变成了找到所有连续1串，记录其长度后计算长度和。

由于结果可能中途上溢，所以用了64位来保存中间结果。

如果64位也不够，因为2^32-1 > 10 ^ 9 + 7，可以考虑在加法前判断是否溢出如果溢出先取模再加。

实现

impl Solution {
    pub fn count(v: i64) -> i64 {
        (v+1)*v/2
    }

    pub fn num_sub(s: String) -> i32 {
        let mut ans: i64 = 0;
        let mut cur_count: i64 = 0;
        let mut is_continus:bool = false;
        for i in s.chars() {
            match i {
                '1' => {
                    if is_continus {
                        cur_count += 1;
                    }else{
                        is_continus = true;
                        cur_count = 1;
                    }
                }
                _ => {
                    if is_continus == true {
                        ans += Solution::count(cur_count);
                    }
                    cur_count = 0;
                    is_continus = false;
                }
            }
        }
        if is_continus == true && cur_count != 0 {
            ans += Solution::count(cur_count);
        }
        (ans % (10_i64.pow(9)+7)) as i32
    }
}