Medium

题目描述

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

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

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

示例 1：

输入：s = “00011”

输出：5

解释：

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

ijs[i..j]0的数量1的数量
33101
44101
230111
341102
2401112

示例 2：

输入：s = “101101”

输出：16

解释：

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

由于总共有21个子串，其中5个没有主导1，因此有16个子串具有主导1。

ijs[i..j]0的数量1的数量
11010
44010
14011022
041011023
150110123

约束条件：

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

解题思路

解题思路

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

核心观察：

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

算法思路：

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

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

具体步骤：

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

优化：

  • 预处理所有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 sqrtN = Math.floor(Math.sqrt(n)) + 1;
    const zeros = []; // 存储所有0的位置
    
    for (let i = 0; i < n; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

相关题目