企业网站 留言板,技术支持 合肥网站建设,百度seo优化软件,美的网站建设本文涉及知识点
动态规划汇总
LeetCode 2306. 公司命名
给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下#xff1a; 从 ideas 中选择 2 个 不同 名字#xff0c;称为 ideaA 和 ideaB 。 交换 ideaA 和 ideaB 的首字母。 如果得到的两个新…本文涉及知识点
动态规划汇总
LeetCode 2306. 公司命名
给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下 从 ideas 中选择 2 个 不同 名字称为 ideaA 和 ideaB 。 交换 ideaA 和 ideaB 的首字母。 如果得到的两个新名字 都 不在 ideas 中那么 ideaA ideaB串联 ideaA 和 ideaB 中间用一个空格分隔是一个有效的公司名字。 否则不是一个有效的名字。 返回 不同 且有效的公司名字的数目。 示例 1 输入ideas [“coffee”,“donuts”,“time”,“toffee”] 输出6 解释下面列出一些有效的选择方案
(“coffee”, “donuts”)对应的公司名字是 “doffee conuts” 。(“donuts”, “coffee”)对应的公司名字是 “conuts doffee” 。(“donuts”, “time”)对应的公司名字是 “tonuts dime” 。(“donuts”, “toffee”)对应的公司名字是 “tonuts doffee” 。(“time”, “donuts”)对应的公司名字是 “dime tonuts” 。(“toffee”, “donuts”)对应的公司名字是 “doffee tonuts” 。 因此总共有 6 个不同的公司名字。
下面列出一些无效的选择方案
(“coffee”, “time”)在原数组中存在交换后形成的名字 “toffee” 。(“time”, “toffee”)在原数组中存在交换后形成的两个名字。(“coffee”, “toffee”)在原数组中存在交换后形成的两个名字。 示例 2
输入ideas [“lack”,“back”] 输出0 解释不存在有效的选择方案。因此返回 0 。
提示 2 ideas.length 5 * 104 1 ideas[i].length 10 ideas[i] 由小写英文字母组成 ideas 中的所有字符串 互不相同
动态规划的状态表示
n ideas.length m ideas[i].length dp[j][k] 表示处理完ideas[0…i-1]符合以下条件的ideas数量 首字母可以换成‘a’j首字符为’a’k。 空间复杂度O( ∑ ∑ \sum\sum ∑∑) ∑ \sum ∑是字符集的大小此处为26。
动态规划的转移方程
tmp ideas[i]; for( j 0 ; j 26;j) { tmp[0] ‘a’j; 如果tmp不存在 dp[j][ideas[i][0]-‘a’]; } 单个状态的转移方程时间复杂度O(m ∑ \sum ∑) 总时间复杂度O(n × ( m ∑ ) \times (m\sum) ×(m∑))
动态规划的初值
全为0。
动态规划的填表顺序
i从0到大
动态规划的返回值
tmp ideas[i]; for( j 0 ; j 26;j) { tmp[0] ‘a’j; 如果tmp不存在 ret dp[ideas[i][0]-‘a’][j] } 最终返回值ret*2 只枚举了下标小的在前面其实下标小的可以在后面。 ** 注意** 返回值的循环和转移方程的循环不能合并且先处理返回值。
代码
核心代码
class Solution{
public:long long distinctNames(vectorstringideas) {int dp[26][26] { 0 };unordered_setstring sHas(ideas.begin(), ideas.end());long long ret 0;for (const auto s : ideas) {const int inx s[0] - a;auto tmp s;for (int j 0; j 26; j) {tmp[0] a j;if (!sHas.count(tmp)) {ret dp[inx][j];}}for (int j 0; j 26; j) {tmp[0] a j;if (!sHas.count(tmp)) {dp[j][inx];}}}return ret*2;}
};单元测试
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
{ vectorstring ideas;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){ideas { coffee, donuts, time, toffee };auto res Solution().distinctNames(ideas);AssertEx(6LL, res);}TEST_METHOD(TestMethod01){ideas { lack,back };auto res Solution().distinctNames(ideas);AssertEx(0LL, res);}};
}
返回值优化
累加dp[i][j]和dp[j][i]相乘
class Solution{
public:long long distinctNames(vectorstringideas) {int dp[26][26] { 0 };unordered_setstring sHas(ideas.begin(), ideas.end()); for (const auto s : ideas) {const int inx s[0] - a;auto tmp s;for (int j 0; j 26; j) {tmp[0] a j;if (!sHas.count(tmp)) {dp[j][inx];}}}long long ret 0;for (int i 0; i 26; i) {for (int j 0; j 26; j) {ret (long long)dp[i][j] * dp[j][i];}}return ret;}
};扩展阅读
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话《喜缺全书算法册》以原理、正确性证明、总结为主。按类别查阅鄙人的算法文章请点击《算法与数据汇总》。有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
