解题思路:
这题如果暴力遍历(O(n*n)),超时是肯定的
由于必须遍历数组,所以只能在O(n)的基础上做一些操作
思路:
遍历‘a’-‘z’,找出s中每一个字母能做的最大贡献,换句话说就是单看一个字母能存在于多少个字符串中 并且能计数
由于忽略重复性,对于单个字母的贡献可以从上一个字母的下标一直到字符串尾
s = input() c = 'a' ans = 0 while ord(c)<=ord('z'): if c in s: li = [-1] for i in range(len(s)): if c==s[i]: li.append(i) li.append(len(s)) for i in range(1, len(li)): ans += (li[i]-li[i-1])*(li[-1]-li[i]) c = chr(ord(c)+1) print(ans)
注意事项:
参考代码:
0.0分
7 人评分
C语言程序设计教程(第三版)课后习题6.5 (C++代码)浏览:458 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:672 |
1013题解浏览:561 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:1921 |
矩形面积交 (C语言代码)浏览:1314 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:1000 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:775 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:1003 |
小O的数字 (C++代码)浏览:763 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:530 |