数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用两个手指在 C++ 中输入单词的最小距离
假设我们有一个如下所示的键盘布局：
| A | B | C | D | E | F |
| G | H | I | J | K | L |
| M | N | O | P | Q | R |
| S | T | U | V | W | X |
| Y | Z |
其中每个英文字母大写字母都位于某个坐标处，例如，字母 A 位于 (0,0)，字母 B 位于 (0,1)，字母 P 位于 (2,3)，字母 Z 位于 (4,1)。现在如果我们有一个单词，我们必须找到使用仅两个手指键入此字符串的最小总距离。两个位置 (x1,y1) 和 (x2,y2) 之间的距离为 |x1 - x2| + |y1 - y2|。并且我们可以从键盘上的任何位置开始。
因此，如果输入类似于“HAPPY”，则输出将为 6，因为从 H 开始，因此成本为 0，然后是 A，因此从 H 到 A 的成本为 2，然后是 P，因此成本为 0，然后再次是 P，成本为 0，最后是 Y，因此从 P 到 Y 的成本为 4，因此总成本为 6 + 4 = 10。
为了解决这个问题，我们将遵循以下步骤：
定义一个 map memo
定义一个函数 getHash()，它将接收 a、b、c、d、e，
temp := 0
当 a 不为零时，执行以下操作：
temp := temp * 10 + a mod 10，a := a / 10
当 b 不为零时，执行以下操作：
temp := temp * 10 + b mod 10，b := b / 10
当 c 不为零时，执行以下操作：
temp := temp * 10 + d mod 10，d := d / 10
当 e 不为零时，执行以下操作：
temp := temp * 10 + e mod 10，e := e / 10
返回 temp
定义一个方法 getXY()，它将接收 c
定义一对 ret
a := c - 'A' 的 ASCII 码
ret.second := a mod 6
ret.first := a / 6
返回 ret
定义一个函数 getDist()，它将接收 a、b、c、d，
如果 a 等于 -1 且 b 等于 -1，则：
返回 0
返回 |(b - d) + |a - c||
定义一个函数 solve()，它将接收 x1、y1、x2、y2、word、idx，
如果 idx 等于 word 的大小，则：
返回 0
state := getHash(x1 + 2, y1 + 2, x2 + 2, y2 + 2, idx + 2)
如果 state 在 memo 中，则：
返回 memo[state]
定义一对 temp := getXY(word[idx])
ans := 0
A := getDist(x1, y1, temp.first, temp.second + solve(temp.first, temp.second, x2, y2, word, idx + 1))
B := getDist(x2, y2, temp.first, temp.second + solve(x1, y1, temp.first, temp.second, word, idx + 1))
ans := A 和 B 的最小值
返回 memo[state] = ans
从主方法执行以下操作：
返回 solve(-1, -1, -1, -1, word, 0)
让我们看看以下实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
map<int, int> memo;
int getHash(int a, int b, int c, int d, int e){
int temp = 0;
while (a) {
temp = temp * 10 + a % 10;
a /= 10;
}
while (b) {
temp = temp * 10 + b % 10;
b /= 10;
}
while (c) {
temp = temp * 10 + c % 10;
c /= 10;
}
while (d) {
temp = temp * 10 + d % 10;
d /= 10;
}
while (e) {
temp = temp * 10 + e % 10;
e /= 10;
}
return temp;
}
pair<int, int> getXY(char c){
pair<int, int> ret;
int a = c - 'A';
ret.second = a % 6;
ret.first = a / 6;
return ret;
}
int getDist(int a, int b, int c, int d){
if (a == -1 && b == -1)
return 0;
return abs(b - d) + abs(a - c);
}
int solve(int x1, int y1, int x2, int y2, string word, int idx){
if (idx == word.size())
return 0;
int state = getHash(x1 + 2, y1 + 2, x2 + 2, y2 + 2, idx + 2);
if (memo.find(state) != memo.end())
return memo[state];
pair<int, int> temp = getXY(word[idx]);
int ans = 0;
int A = getDist(x1, y1, temp.first, temp.second) +
solve(temp.first, temp.second, x2, y2, word, idx + 1);
int B = getDist(x2, y2, temp.first, temp.second) + solve(x1,
y1, temp.first, temp.second, word, idx + 1);
ans = min(A, B);
return memo[state] = ans;
}
int minimumDistance(string word){
memo.clear();
return solve(-1, -1, -1, -1, word, 0);
}
};
main(){
Solution ob;;
cout << (ob.minimumDistance("HELLO"));
}输入
"HELLO"
输出
4
197 次浏览
