哪些网站教你做系统,网页翻译功能,网站建设思路,佛山网站建设哪个好本文涉及知识点
贡献法
LeetCode2262. 字符串的总引力
字符串的 引力 定义为#xff1a;字符串中 不同 字符的数量。 例如#xff0c;“abbca” 的引力为 3 #xff0c;因为其中有 3 个不同字符 ‘a’、‘b’ 和 ‘c’ 。 给你一个字符串 s #xff0c;返回 其所有子字符…本文涉及知识点
贡献法
LeetCode2262. 字符串的总引力
字符串的 引力 定义为字符串中 不同 字符的数量。 例如“abbca” 的引力为 3 因为其中有 3 个不同字符 ‘a’、‘b’ 和 ‘c’ 。 给你一个字符串 s 返回 其所有子字符串的总引力 。 子字符串 定义为字符串中的一个连续字符序列。
示例 1 输入s “abbca” 输出28 解释“abbca” 的子字符串有
长度为 1 的子字符串“a”、“b”、“b”、“c”、“a” 的引力分别为 1、1、1、1、1总和为 5 。长度为 2 的子字符串“ab”、“bb”、“bc”、“ca” 的引力分别为 2、1、2、2 总和为 7 。长度为 3 的子字符串“abb”、“bbc”、“bca” 的引力分别为 2、2、3 总和为 7 。长度为 4 的子字符串“abbc”、“bbca” 的引力分别为 3、3 总和为 6 。长度为 5 的子字符串“abbca” 的引力为 3 总和为 3 。 引力总和为 5 7 7 6 3 28 。 示例 2 输入s “code” 输出20 解释“code” 的子字符串有长度为 1 的子字符串“c”、“o”、“d”、“e” 的引力分别为 1、1、1、1 总和为 4 。长度为 2 的子字符串“co”、“od”、“de” 的引力分别为 2、2、2 总和为 6 。长度为 3 的子字符串“cod”、“ode” 的引力分别为 3、3 总和为 6 。长度为 4 的子字符串“code” 的引力为 4 总和为 4 。 引力总和为 4 6 6 4 20 。 提示 1 s.length 105 s 由小写英文字母组成
贡献法
n s.length 累计s[i]的对各子串贡献的引力。 s[left…r] 如果有相等的字符则引力算到第一个字符上下标最小字符。 令和s[i]相等的前一个下标为i1则s[i]对符合以下条件的子数组贡献1 [left,r] ,left ∈ \in ∈(i1,i] r ∈ \in ∈[i,n) 累计 (i-i1)*(n-i) 为了不处理边界情况v[0] -1。
代码
核心代码
class Solution {
public:long long appealSum(string s) {vectorvectorint indexs(26, vectorint(1, -1));const int N s.length();for (int i 0; i N; i) {indexs[s[i] - a].emplace_back(i);}long long llRet 0;for (const auto v : indexs) {for (int i 1; i v.size(); i) {llRet (long long)(v[i] - v[i - 1]) * (N - v[i]);}}return llRet;}
};单元测试
templateclass T1, class T2
void AssertEx(const T1 t1, const T2 t2)
{Assert::AreEqual(t1, t2);
}templateclass T
void AssertEx(const vectorT v1, const vectorT v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i 0; i v1.size(); i){Assert::AreEqual(v1[i], v2[i]);}
}templateclass T
void AssertV2(vectorvectorT vv1, vectorvectorT vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i 0; i vv1.size(); i){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{ string s;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){s c;auto res Solution().appealSum(s);AssertEx(1LL, res);}TEST_METHOD(TestMethod03){s cc;auto res Solution().appealSum(s);AssertEx(3LL, res);}TEST_METHOD(TestMethod01){s abbca;auto res Solution().appealSum(s);AssertEx(28LL, res);}TEST_METHOD(TestMethod02){s code;auto res Solution().appealSum(s);AssertEx(20LL, res);}};
} 扩展阅读
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话《喜缺全书算法册》以原理、正确性证明、总结为主。按类别查阅鄙人的算法文章请点击《算法与数据汇总》。有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
