Zeratul有一个长度为nn的字符串,字符串只包含0和1两种字符。 现在他想知道,这个字符串中有多少非空子串满足“0和1两种字符的个数相等”。
时间: 2023-05-29 21:05:26 浏览: 57
假设字符串为s,长度为n。我们可以用一个变量cnt来记录当前为止0出现的次数减去1出现的次数的值。如果s的前i个字符的cnt值等于s的前j个字符的cnt值,那么s的第j+1到第i个字符组成的子串就符合条件。
具体地,我们可以使用一个哈希表来记录每个cnt值第一次出现的位置。对于当前处理到的位置i,我们在哈希表中查找cnt值为当前值减去0出现次数与1出现次数差值的位置,如果存在这样的位置j,那么s[j+1:i]就是一个合法的子串。我们统计所有符合条件的子串个数即可。
时间复杂度:O(n)。
代码如下:
相关问题
Zeratul有一个长度为n的字符串,字符串只包含0和1两种字符。 现在他想知道,这个字符串中有多少非空子串满足“0和1两种字符的个数相等”。代码
### 回答1:
思路:
对于一个子串,若其中0和1两种字符的个数相等,则其可以表示为“01”,“10”,“0101”,“1010”等形式,即0和1的交替出现。因此,我们可以遍历字符串,记录当前0和1的个数差,若当前差值为0,则说明找到了一个符合要求的子串。
具体地,我们可以维护一个计数器diff,表示当前0的个数减去1的个数,然后遍历字符串,对于每个字符,若是0,则将diff加1,若是1,则将diff减1。若此时diff为0,则说明找到了一个符合要求的子串。
代码:
### 回答2:
这是一个求解非空子串个数的问题。我们可以采用双层循环来解决。
首先,我们需要遍历字符串的每一个字符,作为子串的起始位置。然后,我们再从起始位置开始遍历到字符串结尾的位置,作为子串的结束位置。
在每一次遍历中,我们需要统计子串中0和1两种字符的个数。为了简化问题,我们可以使用两个变量来计数,一个变量count0用于统计0的个数,另一个变量count1用于统计1的个数。
在遍历的过程中,如果我们发现0和1两个字符的个数相等,就说明满足题目要求,我们可以将结果加1。
下面是示例代码实现:
```python
def countSubstring(s):
res = 0
n = len(s)
for i in range(n):
count0 = count1 = 0
for j in range(i, n):
if s[j] == '0':
count0 += 1
else:
count1 += 1
if count0 == count1:
res += 1
return res
s = input("请输入一个只包含0和1的字符串:")
print("非空子串满足“0和1两种字符的个数相等”的个数为:", countSubstring(s))
```
请注意,这种方法的时间复杂度为O(n^2),其中n为字符串的长度。如果字符串长度较大,可能会导致运行时间较长。
### 回答3:
算法思路如下:
1. 初始化计数器count=0。
2. 遍历字符串的每个位置i。
3. 再次从位置i开始遍历字符串的每个位置j。
4. 对于位置i到j之间的子串,统计其中0和1的个数。
5. 如果0和1的个数相等,count加1。
6. 返回count作为结果。
代码如下:
```python
def countEqualSubstring(s):
count = 0
for i in range(len(s)): # 遍历每个位置i
zeros = 0
ones = 0
for j in range(i, len(s)): # 从位置i开始遍历每个位置j
if s[j] == '0':
zeros += 1
else:
ones += 1
if zeros == ones: # 0和1的个数相等
count += 1
return count
# 测试样例
s = "00110011"
result = countEqualSubstring(s)
print(result) # 输出结果为6
```
以上代码中,通过双重循环遍历所有的子串,并在内层循环中统计0和1的个数,如果个数相等,则计数器count加1。最后返回计数器count作为结果。例如对于字符串"00110011",有6个满足条件的子串:"0011"、"01"、"1100"、"10"、"001100"和"1100"。
对称性和连通性看上去是没什么关系的问题,但是Zeratul为了强行出一道暴力题,想出了这样一个问题: 一个 n × n n×n的01矩阵,有多少种情况使得它满足: 这个01矩阵具有中心对称性,即旋转180度后不变。 这个矩阵不存在0,或者所有的0都在同一个四连块里。
这是一个有趣的问题!为了解决这个问题,我们可以考虑使用组合数学的方法。首先,我们来看中心对称性的情况。
对于一个 n × n 的矩阵来说,如果它具有中心对称性,那么对于每一个位置 (i, j),都需要找到一个位置 (n-i+1, n-j+1),使得它们的值相等。由于这个矩阵只包含 0 和 1,我们可以分两种情况讨论:
1. 如果 (i, j) 和 (n-i+1, n-j+1) 的值都为 0,那么这两个位置可以是任意位置,所以有 2^(n^2/4) 种可能性。
2. 如果 (i, j) 和 (n-i+1, n-j+1) 的值都为 1,那么这两个位置也可以是任意位置,所以有 2^(n^2/4) 种可能性。
因此,对于中心对称性的情况,总共有 2^(n^2/4) × 2^(n^2/4) = 2^(n^2/2) 种可能性。
接下来,我们来看不存在 0 或所有的 0 在同一个四连块里的情况。
如果不存在 0,那么所有的位置都必须是 1,所以只有一种可能性。
如果所有的 0 都在同一个四连块里,那么这个四连块可以是任意大小的矩形,从 1 × 1 到 (n-1) × (n-1)。对于一个 k × k 的矩形来说,有 (n-k+1)^2 种可能性。所以,对于所有可能的 k,总共有 ∑[(n-k+1)^2] 种可能性。
综上所述,满足条件的矩阵总共有 2^(n^2/2) + 1 + ∑[(n-k+1)^2] 种可能性。