【动态规划】【 数学】C++算法：514自由之路

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

数学

力扣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)

动态规划的细节，方便检查

代码

核心代码

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;

}

};