蓝桥杯3514字串简写
目录
【蓝桥杯】3514字串简写
暴力
发现只能通过20%测试点。
k = int(input())
s, c1, c2 = input().split()
le = len(s)
s = [0] + [i for i in s] # 1 -- le
cnt = 0
for i in range(1, le - (k-1) +1):
if s[i] == c1:
for j in range(i+(k-1),le+1):
if s[j] == c2:cnt +=1
print(cnt)优化
if s[i] == c1:
for j in range(i+(k-1),le+1):
if s[j] == c2:cnt +=1这一步分其实在求区间
range(i+(k-1),le+1)
内
c2
的个数，由于要遍历所以很费时。想到可以用前缀和提前处理这一部分，节省一层循环。
k = int(input())
s, c1, c2 = input().split()
le = len(s)
s = [0] + [i for i in s] # 1 -- le
pre = [0 for i in range(le+1)]
for i in range(1,le+1):
if s[i] == c2:
pre[i] = pre[i-1] + 1
else:
pre[i] = pre[i-1]
# print(pre)
cnt = 0
for i in range(1, le - (k-1) +1):
if s[i] == c1:
cnt += pre[-1] - pre[i+(k-1)-1]
print(cnt)总结
利用前缀和来替换掉循环。
这题多了一个长度k的限制条件，写起来要处理好下标索引。