本文介绍: 仅能过60%样例,大多数同学都用的该方法,就不过多赘述insumas通过cin输入字符串到数组a中,并使用strlen函数获取字符串a的长度赋值给变量n。使用for循环遍历字符串asumi+1(n-i)i+1s最后,通过cout输出最终计算得到的结果sum。
题目
思路和解题方法
方案一——遍历+哈希表
#include <iostream> #include <unordered_map> using namespace std; int main() { string s; cin >> s; int n = s.size(); int res = n; for (int i = 0; i < n; ++i) { unordered_map<char, int> m; ++m[s[i]]; for (int j = i + 1; j < n; ++j) { ++m[s[j]]; res += m.size(); } } cout << res; return 0; }
代码
#include <iostream> #include <stdlib.h> #include <cstring> using namespace std; int main() { long long int i, n, sum = 0; // 声明变量 i,n,sum,并初始化 sum 为 0 char a[1000000]; // 声明一个字符数组 a,用于存储输入的字符串,数组大小为 1000000 int s[26] = {0}; // 声明一个长度为 26 的整型数组 s,用于记录每个小写字母最后一次出现的位置 cin>>a; // 输入字符串到数组 a 中 n = strlen(a); // 获取字符串 a 的长度 for(i = 0; i < n; i++) // 遍历字符串 a { sum += (i+1-s[a[i]-'a']) * (n-i); // 根据公式更新 sum 的值 s[a[i] - 'a'] = i+1; // 更新数组 s 中对应字母的位置信息 } cout<<sum<<endl; // 输出最终计算得到的结果 sum return 0; }
复杂度
时间复杂度:
O(n)
空间复杂度
O(1)
空间复杂度:
如果愿意的话关注一下。会对你有更多的帮助。
原文地址:https://blog.csdn.net/jgk666666/article/details/134733446
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_31624.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。