LeetCode 1320:使用两个手指键入单词的最小距离
我正在为LeetCode的1320发布我的Python代码。如果您有时间和想复习，请这样做。
问题
- 您有一个键盘布局，如上面所示，在XY平面中，每个英文大写字母位于某个坐标，例如，字母A位于坐标(0,0)，字母B位于坐标(0,1)，字母P位于坐标(2,3)，字母Z位于坐标(4,1)。
- 给定字符串单词，仅使用两个手指返回键入此类字符串的最小总距离。坐标(x1,y1)和(x2,y2)之间的距离是|x1−x2|+|y1−y2|。
- 请注意，您的两个手指的初始位置被认为是免费的，所以不要计算到您的总距离，您的两个手指也不必从第一个字母或前两个字母开始。
例1:输入: word =“蛋糕”输出:3解释:使用两个手指，键入“蛋糕”的最佳方法是：
- 字母“C”-> cost =0的图1
- 字母'A‘-> cost =从字母'C’到字母'A‘=2的距离
- 字母'K‘-> cost =0的图2
- 字母'E‘-> cost =从字母'K’到字母'E‘=1的距离
总距离=3个约束：
- 每个
word[i]都是一个英文大写字母。
接受Python
import string
import functools
class Solution:
def minimumDistance(self, word: str) -> int:
WIDTH = 6
A_DECIMAL = 65
def get_coordinates(left: int, right: int) -> int:
if not left or not right:
return 0
x_left, y_left = indices[left]
x_right, y_right = indices[right]
return abs(x_left - x_right) + abs(y_left - y_right)
@functools.lru_cache(None)
def get_dp(index, word_a: str = None, word_b: str = None) -> None:
if index == len(chars):
return 0
dist_a = get_coordinates(word_a, chars[index]) + get_dp(index + 1, chars[index], word_b)
dist_b = get_coordinates(word_b, chars[index]) + get_dp(index + 1, word_a, chars[index])
return min(dist_a, dist_b)
chars = ''.join(a for a, b in zip(word, word[1:] + ' ') if a != b)
indices = {char: divmod((ord(char) - A_DECIMAL), WIDTH) for char in string.ascii_uppercase}
return get_dp(0)参考
在LeetCode上，通常有一个名为Solution的类，它有一个或多个public函数，我们不允许重命名这些函数。
回答 1
Code Review用户
发布于 2020-06-23 16:12:16
几点意见
A_DECIMAL及其使用
A_DECIMAL = 65
# [...]
indices = {char: divmod((ord(char) - A_DECIMAL), WIDTH) for char in string.ascii_uppercase}没有什么不对
ord('A')您可以在不定义全局(它不在所需的解决方案上下文中)的情况下使用内联。您甚至可以通过枚举来消除ord的数学。
indices = {char: divmod(idx, WIDTH) for idx, char in enumerate(string.ascii_uppercase)}名称
def get_coordinates(left: int, right: int) -> int:
if not left or not right:
return 0
x_left, y_left = indices[left]
x_right, y_right = indices[right]
return abs(x_left - x_right) + abs(y_left - y_right)不返回坐标，它返回一个距离。另外，left和right误导了我，我想到了两个手指的位置。此外，您还声称参数是ints。实际上你传递的是人物。太草率了。
dist_a = get_coordinates(word_a, chars[index]) + get_dp(index + 1, chars[index], word_b)都快被弄糊涂了。get_coordinates传递一个距离，word_a不是一个单词，而是一个手指指向的字符，get_dp传递的内容不能从名称中猜测，也不存在文档字符串。
算法
您使用深度优先搜索(DFS)，而查找最短路径通常是宽度优先(BFS)更好的方法。使用DFS，你必须搜索整棵树。通过引入一个lru缓存，您发现了一个很好的方法来快捷一些分支。然而，你还是不能尽早找到最短的路径，但你必须检查整棵树。
当手指可以交换时，你处理它们就好像它们不能被交换一样。所以你找到了两条最佳路径，一条从左手手指开始，一条从右边开始。相同的顺序，只有手指被交换。此外，缓存与交换的手指不匹配。
缓存
如前所述，您的缓存与交换的手指不匹配。通过对手指的分类，你可以匹配它们。在函数中的函数上执行lru缓存。由于内部函数只存在，而外部正在运行，您的缓存也只运行一个单词。无法从缓存中处理具有相同单词的另一个调用。如果在类级别上提取函数，并将签名更改为保存剩余的单词，而不是索引，则可以重用缓存的“结束游戏”。
一个从lru缓存中获益的函数是get_coordinates (read get_distance)。
敌对测试用例
您应该实现具有优先级队列的BFS。然后对"FY"*150这样的测试做一些日志记录和计时。当最小距离为0时，DFS将在2700附近计算分支。BFS将注册节点的最大距离为9，但永远不会跟随它们。
其他
线
chars = ''.join(a for a, b in zip(word, word[1:] + ' ') if a != b)应该得到一个解释性的评论或者一个好的函数名。
https://codereview.stackexchange.com/questions/244346
复制
腾讯云开发者
