本文主要是介绍蓝桥杯第1037题子串分值和 C++ 字符串 逆向思维 巧解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
思路和解题方法
方案一——遍历+哈希表
仅能过60%样例,大多数同学都用的该方法，就不过多赘述
#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; }
首先，代码声明了一些变量：
i、n和sum是用于迭代、记录字符串长度和计算最终结果的变量，都被初始化为 0。a是一个字符数组，用于存储输入的字符串，数组大小为 1000000。s是一个长度为 26 的整型数组，用于记录每个小写字母最后一次出现的位置。通过
cin输入字符串到数组a中，并使用strlen函数获取字符串a的长度赋值给变量n。使用
for循环遍历字符串a中的每一个字符：
- 在循环内部，根据公式
(i+1-s[a[i]-'a']) * (n-i)更新变量sum的值，其中：
i+1表示当前字符在字符串中的位置（从 1 开始计数）。s[a[i]-'a']表示当前字符最后一次出现的位置（将字母映射为数组索引）。(n-i)表示以当前字符结尾的子串的个数。- 然后，将当前字符的位置信息
i+1更新到数组s中对应字母的位置上，以便后续计算时使用。最后，通过
cout输出最终计算得到的结果sum。代码
#include <iostream> #include <stdlib.h> #include <cstring> using namespace std; int main() {long long int i, n, sum = 0; // 声明变量 i，n，sum，并初始化 sum 为 0char a[1000000]; // 声明一个字符数组 a，用于存储输入的字符串，数组大小为 1000000int 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; // 输出最终计算得到的结果 sumreturn 0; }
复杂度
时间复杂度:
O(n)
时间复杂度：
- 输入字符串的长度为 n，因此遍历字符串的时间复杂度为 O(n)。
- 在循环内部，执行的操作是常数时间的，不随输入规模变化。
- 因此，整个代码的时间复杂度为 O(n)。
空间复杂度
O(1)
空间复杂度：
- 使用了常数大小的辅助变量和数组，不随输入规模变化。
- 因此，代码的空间复杂度为 O(1)。
总结起来，这段代码的时间复杂度为 O(n)，空间复杂度为 O(1)。
觉得有用的话可以点点赞，支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
这篇关于蓝桥杯第1037题子串分值和 C++ 字符串 逆向思维 巧解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
