[leetcode 3234][Go]统计1显著的字符串的数量

题目链接

leetcode 3234 统计1显著的字符串的数量

解题思路

设i为右边界，并记录每个0的坐标，pos0[0]为-1，pos0[n]为第n个0的坐标，每当i右移时进行以下操作:

记录0下标，记录1的数量

若s[i]为0，记录i并追加到pos0，设oneSum当前[0,i]内1的数量 

1
2
3
4
5
if s[i] == '1' {
    oneSum++
} else {
    pos0 = append(pos0, i)
}

计算以i结尾符合要求的子串数量

获取最近的0的坐标p，此时(p，i]内没有0，任意子串都符合要求，计算(p,i]内以i结尾的子串数量ret+=p-i 

1
2
3
//zeroSum表示[0,i]内0的数量
zeroSum := len(pos0)
ret += i - pos0[zeroSum-1]
从后往前遍历i之前的所有0下标j，计算[pos0[j],i]内0的数量cnt0=zeroSum-j，计算(pos0[j-1],i]内1的数量cnt1=i-pos[j-1]-cnt0，若k为pos0[j-1]+1，不断右移k，此时每右移一次就会减少一个1，只要[k,i]之前1的数量大于0的数量的平方且k在j的左边，那么子串[k,i]符合条件 
1
2
3
4
5
6
7
8
9
10
11
//若[j,i]之间0的数量的平方已经大于[0,i]内1的数量便可结束遍历
for j := zeroSum - 1; j > 0 && (zeroSum-j)*(zeroSum-j) <= oneSum; j-- {
    cnt0 := zeroSum - j
    cnt1 := i - pos0[j-1] - cnt0
    //k最多只能右移到j，所以cnt1-cnt0*cnt0+1应比pos0[j]-pos[j-1]小		for j := zeroSum - 1; j > 0 && (zeroSum-j)*(zeroSum-j) <= oneSum; j-- {
			cnt0 := zeroSum - j
			cnt1 := i - pos0[j-1] - cnt0
			ret += max(0, min(pos0[j]-pos0[j-1], cnt1-cnt0*cnt0+1))
		}
    ret += max(0, min(pos0[j]-pos0[j-1], cnt1-cnt0*cnt0+1))
}

时间复杂度

外层循环为，内层循环最多为，所以内层循环时间复杂度为

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func numberOfSubstrings(s string) int {
	var n = len(s)
	var pos0 = []int{-1}
	var ret = 0
	oneSum := 0
	for i := range n {
		if s[i] == '1' {
			oneSum++
		} else {
			pos0 = append(pos0, i)
		}
		zeroSum := len(pos0)
		ret += i - pos0[zeroSum-1]
		for j := zeroSum - 1; j > 0 && (zeroSum-j)*(zeroSum-j) <= oneSum; j-- {
			cnt0 := zeroSum - j
			cnt1 := i - pos0[j-1] - cnt0
			ret += max(0, min(pos0[j]-pos0[j-1], cnt1-cnt0*cnt0+1))
		}
	}
	return ret
}