leetcode514. 自由之路/记忆化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 的下一个字符(下一阶段), 直至完成所有拼写。
示例:

在这里插入图片描述

输入: 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;

    }
};
版权声明:本文为qq_31672701原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_31672701/article/details/109623639

智能推荐

一致性hash算法

散列(hash)在我看来就是一个数组,而与数组不同的点在于数组是按顺序写入的,而hash是按照一定的hash算法确定元素在数组中的位置的。hash最难的问题在于会有冲突出现,如果两个object根据相应的hash算法得出的值一样便产生了hash冲突。在所有解决hash冲突的方法中,我最欣赏的是链式解决法,即将hash到同一位置的元素用链表连接。当然还有其它几种处理hash冲突的算法,比如建立公共溢...

OpenCV-Python learning-1.安装,图片读取显示

1. OpenCV与OpenGL区别 https://www.zhihu.com/question/20212016 一个是让机器识别东西的,OpenCV是给电脑做眼睛的。 一个是让机器计算出更好画面的,OpenGL用在游戏渲染方面很多。 OpenCV(Open Source Computer Vision Library)是一个基于(开源)发行的跨平台计算机视觉库,OpenGL(全写Open G...

Mycat+Mysql分布式架构改造和性能压力测试

架构实现 Mycat作为数据库高可用中间件具备很多的功能,如负载均衡,分库分表,读写分离,故障迁移等。结合项目的实际情况,分库分表功能对于关联查询有很高的要求,需要从业务角度考虑分库分表后的关联查询SQL的分析,业务代码动作较大,所以在此方案中我们不考虑分库分表。主要应用Mycat的负载均衡及故障迁移的功能即可。 整个架构改造包括两个部分,第一是单例Mysql改为多个Mysql,同时负载均衡,并且...

人脸识别之疲劳检测(二)阈值法、KNN分类和K-means聚类

Table of Contents 1、均值法 2、中值法 3、KNN 4、K-means 结合上一节在获得人眼特征点后需要对睁眼闭眼状态做出判断,方法的选择需要经验结合公平的评价方法,使用大量测试集得到不同方法下的精确度并做出比较: 1、均值法 50帧睁眼数据取均值,得到不同阈值下精确度。 2、中值法 50帧睁眼数据取中值,得到不同阈值下精确度。 3、KNN KNN是一种ML常用分类算法,通过测...

CodeForce Tic-Tac-Toe

Two bears are playing tic-tac-toe via mail. It's boring for them to play usual tic-tac-toe game, so they are a playing modified version of this game. Here are its rules. The game is played on the foll...

猜你喜欢

Python雾里看花-抽象类ABC (abstract base class)

首先认识模块 abc,python中没有提供抽象类与抽象方法,然而提供了内置模块abc来模拟实现抽象类,例如提供泛映射类型的抽象类 abc.MutableMapping 继承abc.MutableMapping构造一个泛映射类型(类似python中的dict) 当然继承abc.Mapping 也可以,毕竟MutableMapping是其子类 dict是python中典型的映射类型数据结构,其接口的...

python 文件操作

2, with open (‘xx.txt’,‘w’,encoding=‘utf-8’) as f: f.write(‘文件内容或对象’)...

【Python基础】使用统计函数绘制简单图形

机器学习算法与自然语言处理出品 @公众号原创专栏作者 冯夏冲 学校 | 哈工大SCIR实验室在读博士生 2.1 函数bar 用于绘制柱状图 2.2 函数barh 用于绘制条形图 2.3 函数hist 用于绘制直方图 直方图与柱状图的区别 函数pie 用于绘制饼图 2.5 函数polor 用于绘制极线图 极线图是在极坐标系上绘出的一种图。在极坐标系中,要确定一个点,需要指明这个点距原点的角...

css:顶部按钮固定,上面内容滑动

这种需求我们平时见到很多的,实现方法也多的参差不齐,下面我说一种简单的。如图: 可以看到只有红线部分滚动,底下按钮是固定的。 代码...

环形公路堵车概率模型(含详细解析)

文章目录 基础理论 代码实现 图形分析 基础理论 路面上有n辆车,以不同的速度向前行驶, 模拟堵车问题。 有以下假设: 假设某辆车的当前速度是v。 若前方可见范围内没车,则它在下一秒的车速提高到v+1,直到达到规定的最高限速。 若前方有车,前车的距离为d,且d < v,则它下 一秒的车速降低到d-1 。 每辆车会以概率p随机减速v-1。、 代码实现 图形分析 图形中颜色越重的地方,说明很多车...