浏览器为什么打不开网站,办个网站需要投资多少,公司做网页推广要多少钱,wordpress wp_head文章目录1. 题目2. 解题1. 题目 二指输入法定制键盘在 XY 平面上的布局如上图所示#xff0c;其中每个大写英文字母都位于某个坐标处#xff0c; 例如字母 A 位于坐标 (0,0)#xff0c;字母 B 位于坐标 (0,1)#xff0c;字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。
…
文章目录1. 题目2. 解题1. 题目 二指输入法定制键盘在 XY 平面上的布局如上图所示其中每个大写英文字母都位于某个坐标处 例如字母 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示例 3
输入word NEW
输出3示例 4
输入word YEAR
输出7提示
2 word.length 300
每个 word[i] 都是一个大写英文字母。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-distance-to-type-a-word-using-two-fingers 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
dp[i][c1][c2] 表示输入完 i 字符后手指1在 c1 字符手指2在 c2 字符0表示还没有输入字符1-26表示A-Z时的最小移动距离
class Solution {
public:int minimumDistance(string s) {vectorvectorint pos(27, vectorint(2));int count 1;for(int i 0; i 5 count 27; i)for(int j 0; j 6 count 27; j){pos[count] {i, j};//字符的坐标}int n s.size(), mindis INT_MAX;int dp[301][27][27];memset(dp, 0x7f, sizeof(dp));dp[0][s[0]-A1][0] 0;//输入第一个字符给手指1for(int i 1; i n; i){ //剩余字符int c s[i]-A1;//当前字符序号 1-26for(int c1 1; c1 26; c1){for(int c2 0; c2 26; c2){if(dp[i-1][c1][c2] 0x7f7f7f7f)continue;//状态不存在// 当前字母c由第1个手指输入dp[i][c][c2] min(dp[i][c][c2], dp[i-1][c1][c2]abs(pos[c][0]-pos[c1][0])abs(pos[c][1]-pos[c1][1]));// 当前字母c由第2个手指输入if(c2 0)//第二个手指还没输入dp[i][c1][c] min(dp[i][c1][c], dp[i-1][c1][c2]);//第一次输入没有成本elsedp[i][c1][c] min(dp[i][c1][c], dp[i-1][c1][c2]abs(pos[c][0]-pos[c2][0])abs(pos[c][1]-pos[c2][1]));}}}for(int c1 1; c1 26; c1)for(int c2 0; c2 26; c2)mindis min(mindis, dp[n-1][c1][c2]);return mindis;}
};32 ms 7.5 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
