做网站客户要求多很烦,济南 网站设计公司,wordpress登录微信插件下载失败,如何将qq音乐链接到wordpress本文涉及知识点
动态规划汇总 字符串 状态机动态规划
LeetCode1320. 二指输入的的最小距离
二指输入法定制键盘在 X-Y 平面上的布局如上图所示#xff0c;其中每个大写英文字母都位于某个坐标处。
例如字母 A 位于坐标 (0,0)#xff0c;字母 B 位于坐标 (0,1)#xff0…本文涉及知识点
动态规划汇总 字符串 状态机动态规划
LeetCode1320. 二指输入的的最小距离
二指输入法定制键盘在 X-Y 平面上的布局如上图所示其中每个大写英文字母都位于某个坐标处。
例如字母 A 位于坐标 (0,0)字母 B 位于坐标 (0,1)字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。 给你一个待输入字符串 word请你计算并返回在仅使用两根手指的情况下键入该字符串需要的最小移动总距离。 坐标 (x1,y1) 和 (x2,y2) 之间的 距离 是 |x1 - x2| |y1 - y2|。 注意两根手指的起始位置是零代价的不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。 示例 1 输入word “CAKE” 输出3 解释 使用两根手指输入 “CAKE” 的最佳方案之一是 手指 1 在字母 ‘C’ 上 - 移动距离 0 手指 1 在字母 ‘A’ 上 - 移动距离 从字母 ‘C’ 到字母 ‘A’ 的距离 2 手指 2 在字母 ‘K’ 上 - 移动距离 0 手指 2 在字母 ‘E’ 上 - 移动距离 从字母 ‘K’ 到字母 ‘E’ 的距离 1 总距离 3 示例 2 输入word “HAPPY” 输出6 解释 使用两根手指输入 “HAPPY” 的最佳方案之一是 手指 1 在字母 ‘H’ 上 - 移动距离 0 手指 1 在字母 ‘A’ 上 - 移动距离 从字母 ‘H’ 到字母 ‘A’ 的距离 2 手指 2 在字母 ‘P’ 上 - 移动距离 0 手指 2 在字母 ‘P’ 上 - 移动距离 从字母 ‘P’ 到字母 ‘P’ 的距离 0 手指 1 在字母 ‘Y’ 上 - 移动距离 从字母 ‘A’ 到字母 ‘Y’ 的距离 4 总距离 6 提示 2 word.length 300 每个 word[i] 都是一个大写英文字母。
动态规划
vPosr和vPosc记录各字母所在行列。
动态规划规格的状态表示
dp[i][j][k] 表示处理了i个字母两只手指分别在字母i和j的最少移动次数。 pre[j][k] dp[i][j][k] dp[j][k] dp[i1][j][k] 空间复杂度O(n ∑ ∑ \sum\sum ∑∑)其中n word.lenght ∑ \sum ∑ 是字符集的大小为26。
动态规划的转移方程
任何前置状态都有只有两个转化方式。移动手指1移动手指2。 单个状态的时间复杂度O(1) 总时间复杂度O(n ∑ ∑ \sum\sum ∑∑)
动态规划的初始状态
全部为0
动态规划的填表顺序
i 0 : to n-1
动态规划的返回值
min(pre)
代码
核心代码
templateclass ELE, class ELE2
void MinSelf(ELE* seft, const ELE2 other)
{*seft min(*seft, (ELE)other);
}class Solution {
public:int minimumDistance(string word) {int rs[26], cs[26];for (int i 0; i 26; i) {rs[i] i / 6;cs[i] i % 6;}vectorvectorint pre(26, vectorint(26));for (int i 0; i word.length(); i) {const int cur word[i] - A;vectorvectorint dp(26, vectorint(26, m_iNotMay));for (int j1 0; j1 26; j1) {for (int j2 0; j2 26; j2) {const int need1 abs(rs[j1] - rs[cur]) abs(cs[j1] - cs[cur]);MinSelf(dp[cur][j2], pre[j1][j2] need1);const int need2 abs(rs[j2] - rs[cur]) abs(cs[j2] - cs[cur]);MinSelf(dp[j1][cur], pre[j1][j2] need2);}}pre.swap(dp);}int iRet m_iNotMay;for (const auto v : pre) {iRet min(iRet, *std::min_element(v.begin(),v.end()));}return iRet;}const int m_iNotMay 1000000;
};单元测试 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 word;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){word AB;auto res Solution().minimumDistance(word);AssertEx(0, res);}TEST_METHOD(TestMethod01){word ABC;auto res Solution().minimumDistance(word);AssertEx(1, res);}TEST_METHOD(TestMethod02){word ABCD;auto res Solution().minimumDistance(word);AssertEx(2, res);}TEST_METHOD(TestMethod03){word ABM;auto res Solution().minimumDistance(word);AssertEx(1, res);}TEST_METHOD(TestMethod04){word ABCM;auto res Solution().minimumDistance(word);AssertEx(2, res);}TEST_METHOD(TestMethod11){word CAK;auto res Solution().minimumDistance(word);AssertEx(2, res);}TEST_METHOD(TestMethod1){ word CAKE;auto res Solution().minimumDistance(word); AssertEx(3, res);}TEST_METHOD(TestMethod20){word HAPP;auto res Solution().minimumDistance(word);AssertEx(2, res);}TEST_METHOD(TestMethod2){word HAPPY;auto res Solution().minimumDistance(word);AssertEx(6, res);}};
}扩展阅读
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话《喜缺全书算法册》以原理、正确性证明、总结为主。按类别查阅鄙人的算法文章请点击《算法与数据汇总》。有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
