自学网站建设作业,宣传片制作软件app,成都网站建设公司电话,番禺网站制作多少钱文章目录1. 题目2. 解题1. 题目
电子游戏“辐射4”中#xff0c;任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘#xff0c;并使用表盘拼写特定关键词才能开门。
给定一个字符串 ring#xff0c;表示刻在外环上的编码#xff1b;给定另一个字符串 ke…
文章目录1. 题目2. 解题1. 题目
电子游戏“辐射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 的下一个字符下一阶段, 直至完成所有拼写。
示例
输入: ring godding, key gd
输出: 4
解释:对于 key 的第一个字符 g已经在正确的位置, 我们只需要1步来拼写这个字符。 对于 key 的第二个字符 d我们需要逆时针旋转 ring godding 2步使它变成 ddinggo。当然, 我们还需要1步进行拼写。因此最终的输出是 4。提示
ring 和 key 的字符串长度取值范围均为 1 至 100
两个字符串中都只有小写字符并且均可能存在重复字符
字符串 key 一定可以由字符串 ring 旋转拼出。来源力扣LeetCode 链接https://leetcode-cn.com/problems/freedom-trail 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
直接暴力dfs搜索超时
class Solution { // 超时int steps INT_MAX;int n;vectorvectorint pos;
public:int findRotateSteps(string ring, string key) {n ring.size();pos.resize(26);for(int i 0; i ring.size(); i)pos[ring[i]-a].push_back(i); //记录相同字符的所有位置dfs(key, 0, 0, 0);return steps;}void dfs(string key, int start, int i, int step){if(step steps)return;if(i key.size()){if(step steps)steps step;return;}for(int j 0; j pos[key[i]-a].size(); j){int delta min(abs(start-pos[key[i]-a][j]), n-abs(start-pos[key[i]-a][j]));dfs(key, pos[key[i]-a][j], i1, stepdelta1);}}
};class Solution { //记忆化递归int n;vectorvectorint pos;vectorvectorint memo;
public:int findRotateSteps(string ring, string key) {n ring.size();pos.resize(26);memo vectorvectorint (101, vectorint(101, INT_MAX));for(int i 0; i ring.size(); i)pos[ring[i]-a].push_back(i);return dfs(key, 0, 0, 0);}int dfs(string key, int start, int i, int step){if(memo[start][i] ! INT_MAX)return memo[start][i];if(i key.size()){return 0;}for(int j 0; j pos[key[i]-a].size(); j){int delta min(abs(start-pos[key[i]-a][j]), n-abs(start-pos[key[i]-a][j]));int s dfs(key, pos[key[i]-a][j], i1, 0);memo[start][i] min(memo[start][i], sdelta1);}return memo[start][i];//从start位置开始找第 i 个字符时的最小步数}
};48 ms 25.4 MB
class Solution { //DP
public:int findRotateSteps(string ring, string key) {int n ring.size();vectorvectorint pos(26);vectorvectorint dp(101, vectorint(101, INT_MAX));for(int i 0; i ring.size(); i)pos[ring[i]-a].push_back(i);for(int i 0; i key.size(); i){for(int j 0; j pos[key[i]-a].size(); j){if(i 0){int delta min(pos[key[i]-a][j], n-pos[key[i]-a][j]);dp[i][j] min(dp[i][j], delta1);}else{for(int k 0; k pos[key[i-1]-a].size(); k){ //上一个字符的状态int delta min(abs(pos[key[i-1]-a][k]-pos[key[i]-a][j]), n-abs(pos[key[i-1]-a][k]-pos[key[i]-a][j]));dp[i][j] min(dp[i][j], dp[i-1][k]delta1);}}}}int len key.size();return *min_element(dp[len-1].begin(), dp[len-1].end());}
};40 ms 25.3 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
