3234. 计算具有主导1的子串数量

Medium

题目描述

给你一个二进制字符串 s。

返回具有主导1的子串数量。

如果字符串中1的数量大于或等于0的数量的平方，则该字符串具有主导1。

示例 1：

输入：s = “00011”

输出：5

解释：

具有主导1的子串如下表所示。

i	j	s[i..j]	0的数量	1的数量
3	3	1	0	1
4	4	1	0	1
2	3	01	1	1
3	4	11	0	2
2	4	011	1	2

示例 2：

输入：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

约束条件：

1 <= s.length <= 4 * 10^4
s 仅由字符 ‘0’ 和 ‘1’ 组成。

解题思路

本题要求找到所有满足"1的数量 ≥ 0的数量的平方"的子串。

核心观察：

如果一个子串有 z 个0，那么需要至少 z² 个1才能成为主导1的子串
当 z ≥ √n 时，z² 会很大，这样的子串很少存在

算法思路：

我们固定左端点 l，然后考虑所有以 l 为起点的子串。关键观察是：

如果子串中0的数量超过 √n，那么需要的1的数量会非常大，这样的情况很少
我们可以枚举0的数量（最多 √n 个），然后计算需要多少个1

具体步骤：

对于每个起始位置 l，枚举接下来的最多 √n 个0的位置
对于每个0的数量 z，计算需要的最少1的数量：z²
找到满足条件的右端点范围，累加答案

优化：

预处理所有0的位置，便于快速定位
对于每个左端点，只需要考虑有限个0的情况
时间复杂度：O(n√n)

代码实现

class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.length();
        int sqrtN = sqrt(n) + 1;
        vector<int> zeros; // 存储所有0的位置
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                zeros.push_back(i);
            }
        }
        
        int result = 0;
        
        for (int l = 0; l < n; l++) {
            int ones = 0;
            int zeroCount = 0;
            
            // 找到l右边第一个0的位置
            int zeroIdx = lower_bound(zeros.begin(), zeros.end(), l) - zeros.begin();
            
            for (int r = l; r < n; r++) {
                if (s[r] == '1') ones++;
                else zeroCount++;
                
                // 如果0的数量超过sqrtN，后面的子串都不可能满足条件
                if (zeroCount > sqrtN) break;
                
                // 检查当前子串是否满足条件
                if (ones >= zeroCount * zeroCount) {
                    result++;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        n = len(s)
        sqrt_n = int(n ** 0.5) + 1
        zeros = []  # 存储所有0的位置
        
        for i in range(n):
            if s[i] == '0':
                zeros.append(i)
        
        result = 0
        
        for l in range(n):
            ones = 0
            zero_count = 0
            
            for r in range(l, n):
                if s[r] == '1':
                    ones += 1
                else:
                    zero_count += 1
                
                # 如果0的数量超过sqrt_n，后面的子串都不可能满足条件
                if zero_count > sqrt_n:
                    break
                
                # 检查当前子串是否满足条件
                if ones >= zero_count * zero_count:
                    result += 1
        
        return result

public class Solution {
    public int NumberOfSubstrings(string s) {
        int n = s.Length;
        int sqrtN = (int)Math.Sqrt(n) + 1;
        List<int> zeros = new List<int>(); // 存储所有0的位置
        
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') {
                zeros.Add(i);
            }
        }
        
        int result = 0;
        
        for (int l = 0; l < n; l++) {
            int ones = 0;
            int zeroCount = 0;
            
            for (int r = l; r < n; r++) {
                if (s[r] == '1') {
                    ones++;
                } else {
                    zeroCount++;
                }
                
                // 如果0的数量超过sqrtN，后面的子串都不可能满足条件
                if (zeroCount > sqrtN) {
                    break;
                }
                
                // 检查当前子串是否满足条件
                if (ones >= zeroCount * zeroCount) {
                    result++;
                }
            }
        }
        
        return result;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var numberOfSubstrings = function(s) {
    const n = s.length;
    const zeros = [];

    for (let i = 0; i < n; i++) {
        if (s[i] === '0') zeros.push(i);
    }

    let answer = 0;
    let onesRun = 0;
    for (const character of s) {
        if (character === '1') {
            onesRun++;
        } else {
            answer += onesRun * (onesRun + 1) / 2;
            onesRun = 0;
        }
    }
    answer += onesRun * (onesRun + 1) / 2;

    const pairsWithSumLessThan = (leftChoices, rightChoices, threshold) => {
        if (threshold <= 0) return 0;

        const fullRows = Math.min(
            leftChoices,
            Math.max(0, threshold - rightChoices + 1)
        );
        const partialEnd = Math.min(leftChoices, threshold);
        const partialRows = Math.max(0, partialEnd - fullRows);
        const partial = partialRows * threshold
            - (fullRows + partialEnd - 1) * partialRows / 2;
        return fullRows * rightChoices + partial;
    };

    for (let first = 0; first < zeros.length; first++) {
        const previousZero = first === 0 ? -1 : zeros[first - 1];
        const leftChoices = zeros[first] - previousZero;

        for (let last = first; last < zeros.length; last++) {
            const zeroCount = last - first + 1;
            if (zeroCount * zeroCount + zeroCount > n) break;

            const nextZero = last + 1 < zeros.length ? zeros[last + 1] : n;
            const rightChoices = nextZero - zeros[last];
            const coreOnes = zeros[last] - zeros[first] + 1 - zeroCount;
            const requiredExtraOnes = zeroCount * zeroCount - coreOnes;
            const invalid = pairsWithSumLessThan(
                leftChoices,
                rightChoices,
                requiredExtraOnes
            );
            answer += leftChoices * rightChoices - invalid;
        }
    }

    return answer;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n√n)	外层循环O(n)，内层最多扫描√n个0
空间复杂度	O(k)	k为字符串中0的个数，最坏情况O(n)

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目