2025-03-14：统计 1 显著的字符串的数量。用go语言，给定一个二进制字符串 s，请你计算其中被称为“1 显著”的子字符

福大大架构师每日一题

发布于 2025-03-14 17:02:26

5000

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-03-14：统计 1 显著的字符串的数量。用go语言，给定一个二进制字符串 s，请你计算其中被称为“1 显著”的子字符串的数量。

一个子字符串被视为“1 显著”，当它包含的 1 的数量大于或等于 0 的数量的平方。

1 <= s.length <= 40000。

s 仅包含字符 '0' 和 '1'。

输入：s = "101101"。

输出：16。

解释：

1 不显著的子字符串如下表所示。

总共有 21 个子字符串，其中 5 个是 1 不显著字符串，因此有 16 个 1 显著子字符串。

i	j	s[i..j]	0 的数量	1 的数量
1	1	0	1	0
4	4	0	1	0
1	4	0110	2	2
0	4	10110	2	3
1	5	01101	2	3

答案2025-03-13：

题目来自leetcode3234。

大体步骤如下：

1.初始化变量tot1和切片a，切片a中包含了-1作为哨兵，用于记录'0'字符的位置。

2.遍历输入二进制字符串s，对于每个字符：

• 如果当前字符为'0'，将其位置添加到切片a中。
• 如果当前字符为'1'，则计算"1 显著"的子字符串数量(ans)。
• 针对切片a中的不同组合计算额外的"1 显著"子字符串数量，并将计算结果累加到ans中。

3.返回ans作为结果。

总体时间复杂度:

• 代码中的主要循环是遍历输入字符串s，时间复杂度为O(n)，其中n是输入字符串的长度。

总体空间复杂度:

• 额外空间主要用于存储切片a，其最大长度为输入字符串s的长度n，因此额外空间复杂度为O(n)。

在整个过程中，代码根据字符'0'和'1'的分布来计算"1 显著"的子字符串的数量，具体的实现方式是通过维护一个辅助数组a来记录'0'字符的位置，然后根据条件计算"1 显著"的子字符串数量。

Go完整代码如下：

package main

import (
    "fmt"
)

func numberOfSubstrings(s string) (ans int) {
    tot1 := 0
    a := []int{-1} // 哨兵
    for right, b := range s {
        if b == '0' {
            a = append(a, right)
        } else {
            ans += right - a[len(a)-1]
            tot1++
        }
        for k := len(a) - 1; k > 0 && (len(a)-k)*(len(a)-k) <= tot1; k-- {
            cnt0 := len(a) - k
            cnt1 := right - a[k] + 1 - cnt0
            ans += max(a[k]-a[k-1]-max(cnt0*cnt0-cnt1, 0), 0)
        }
    }
    return
}

func main() {
    s := "101101"
    result := numberOfSubstrings(s)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

defnumber_of_substrings(s: str) -> int:
    ans = 0
    tot1 = 0
    a = [-1]  # 哨兵
    for right, b inenumerate(s):
        if b == '0':
            a.append(right)
        else:
            ans += right - a[-1]
            tot1 += 1

        for k inrange(len(a) - 1, 0, -1):
            if (len(a) - k) * (len(a) - k) > tot1:
                break
            cnt0 = len(a) - k
            cnt1 = right - a[k] + 1 - cnt0
            ans += max(a[k] - a[k - 1] - max(cnt0 * cnt0 - cnt1, 0), 0)

    return ans

if __name__ == "__main__":
    s = "101101"
    result = number_of_substrings(s)
    print(result)