作者推荐
本文涉及知识点
数学
力扣514 自由之路
电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。
给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。
最初，ring 的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。
旋转 ring 拼出 key 字符 key[i] 的阶段中：
您可以将 ring 顺时针或逆时针旋转 一个位置 ，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。
示例 1：
输入: ring = “godding”, key = “gd”
输出: 4
解释:
对于 key 的第一个字符 ‘g’，已经在正确的位置, 我们只需要1步来拼写这个字符。
对于 key 的第二个字符 ‘d’，我们需要逆时针旋转 ring “godding” 2步使它变成 “ddinggo”。
当然, 我们还需要1步进行拼写。
因此最终的输出是 4。
示例 2:
输入: ring = “godding”, key = “godding”
输出: 13
提示：
1 <= ring.length, key.length <= 100
ring 和 key 只包含小写英文字母
保证 字符串 key 一定可以由字符串 ring 旋转拼出
动态规划
** 时间复杂度 ** : O(nmm) n=key.length m等于一个字符在ring中出现的次数。
三层循环：
一层循环枚举key的字符。
二层循环当前字符的位置。
三层循环前一个字符的位置。
两个表盘位置，逆时针和顺时针最少需要转动的次数。
iMin=min(i1,i2) iMax = max(i1,i2)
min(iMax-iMin,iMin+ring.length-iMax)
动态规划的细节，方便检查
| 动态规划的状态表示 | pre中的元素{prePos,preSetp} 按完上一个字符后，金属盘所在的位置和需要步数。 |
| 动态规划的转移方程 | 枚举当前字符位置和前一字符位置，计算最小值 |
| 动态规划的初始状态 | {0，0} |
| 动态规划的填表顺序 | key从前到后处理,确保动态规划的无后效性 |
| 动态规划的返回值 | max(preStep) |
代码
核心代码
class Solution { public: int findRotateSteps(string ring, string key) { vector<vector<int>> vCharIndexs(26); for (int i = 0; i < ring.length(); i++) { vCharIndexs[ring[i] - 'a'].emplace_back(i); } vector<pair<int, int>> pre; pre.emplace_back(0, 0); for (const auto& ch : key) { vector<pair<int, int>> dp; const auto& cur = vCharIndexs[ch - 'a']; for (const auto& curPos : cur) { int curStep = INT_MAX; for (const auto [prePos, step] : pre) { const int iMin = min(prePos, curPos), iMax = max(prePos, curPos); curStep = min(curStep, step + 1 + min(iMax - iMin, iMin + (int)ring.length() - iMax)); } dp.emplace_back(curPos, curStep); } pre.swap(dp); } int iRet = INT_MAX; for (const auto [prePos, step] : pre) { iRet = min(iRet, step); } return iRet; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { string ring, key; { Solution sln; ring = "godding", key = "gd"; auto res = sln.findRotateSteps(ring, key); Assert(4, res); } { Solution sln; ring = "godding", key = "godding"; auto res = sln.findRotateSteps(ring, key); Assert(13, res); } }
2023年1月版
class Solution {
public:
int findRotateSteps(string ring, string key) {
std::unordered_map<char, vector> mCharPos;
for (int i = 0; i < ring.length(); i++)
{
mCharPos[ring[i]].push_back(i);
}
std::unordered_map<int,int> vPrePosOpeNum;//当前位置及最少操作次数
vPrePosOpeNum[0] = 0;
for (const char& ch : key)
{
std::unordered_map<int, int> vPosOpeNum;
for (const auto& pos : mCharPos[ch])
{
for (const auto& prePos : vPrePosOpeNum)
{
//大的减小的
int iMove = abs(prePos.first - pos);
iMove = min(iMove,min(prePos.first, pos) + (int)ring.length() - max(prePos.first, pos));
const int iOpeNum = iMove + prePos.second + 1;
if (vPosOpeNum.count(pos))
{
vPosOpeNum[pos] = min(vPosOpeNum[pos], iOpeNum);
}
else
{
vPosOpeNum[pos] = iOpeNum;
}
}
}
vPrePosOpeNum.swap(vPosOpeNum);
}
int iMin = INT_MAX;
for (const auto& prePos : vPrePosOpeNum)
{
iMin = min(iMin, prePos.second);
}
return (INT_MAX == iMin) ? -1 : iMin;
}
};
