資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
