区块链技术博客
www.b2bchain.cn

leetcode514. 自由之路/记忆化dfs

这篇文章主要介绍了leetcode514. 自由之路/记忆化dfs的讲解,通过具体代码实例进行18058 讲解,并且分析了leetcode514. 自由之路/记忆化dfs的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=18058

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

文章目录

    • 题目:514. 自由之路
    • 基本思想:记忆化dfs

题目: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 的下一个字符(下一阶段), 直至完成所有拼写。
示例:

leetcode514. 自由之路/记忆化dfs

输入: 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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

基本思想:记忆化dfs

  • 这道题的思想很直观,考虑每一种情况,找最终结果最小的值,当前情况下有两种选择顺时针旋转和逆时针旋转
  • 如果直接进行dfs不进行任何的优化,结果会超时,这里参考如下链接:点击链接,进行如下两方面的优化:
    • 将ring中的每一个字符保存在map中,每次查找字符的时候不用进行遍历了
    • dfs的过程中保存中间结果,避免出现重复的递归,因为子问题存在重复的现象(这里其实不太好想,可以模拟下递归过程来理解下)
class Solution { public:     int findRotateSteps(string ring, string key) {         /*         利用dfs,每一次转化成key的时候,其实是有两种选择,考虑每一种选择,最后找到最小步数;         在此过程中要保存已经旋转后的字符串         */         map<char, vector<int>> mp;//保存ring中每个字符对应的位置         map<pair<int, int>, int> memo;//保存下key中字符和ring中的对应位置,避免重复搜索         for(int i = 0; i < ring.size(); ++i){             mp[ring[i]].push_back(i);         }                 return dfs(memo, ring, mp, 0, key, 0) + key.size(); //这里加上的按下按钮的次数     }     int dfs(map<pair<int, int>, int> &memo, string ring, map<char, vector<int>>& mp, int ring_pos, string key, int key_pos){         int res = INT_MAX;         if(key_pos == key.size()){             return 0;         }         if(memo.find({key_pos, ring_pos}) != memo.end()){             return memo[{key_pos, ring_pos}];         }         for(auto pos : mp[key[key_pos]]){             // int t1 = (pos - ring_pos + ring.size()) % ring.size();             // int t2 = (ring_pos - pos + ring.size()) % ring.size();             int t1 = abs(pos - ring_pos);             int t2 = ring.size() - t1;             res = min(res, min(t1, t2) + dfs(memo, ring, mp, pos, key, key_pos + 1));         }         memo[{key_pos, ring_pos}] = res;         return res;      } }; 

本文转自互联网,侵权联系删除leetcode514. 自由之路/记忆化dfs

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » leetcode514. 自由之路/记忆化dfs
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们