leetcode
leetcode 1001 ~ 1050
单行键盘

单行键盘

难度:

标签:

题目描述

代码结果

运行时间: 30 ms, 内存: 16.1 MB


/*
 * 思路:
 * 使用Java Stream的方式来实现相同的逻辑。我们可以先将键盘字符的位置存储在一个Map中,
 * 然后使用Stream和reduce方法来计算总距离。
 */

import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public int calculateTime(String keyboard, String word) {
        // 将键盘字符的位置存储在一个Map中
        Map<Character, Integer> charPosition = IntStream.range(0, keyboard.length())
            .boxed()
            .collect(Collectors.toMap(keyboard::charAt, i -> i));

        // 使用Stream和reduce方法来计算总距离
        return IntStream.range(0, word.length())
            .map(i -> charPosition.get(word.charAt(i)))
            .reduce(new int[]{0, 0}, (acc, pos) -> new int[]{pos, acc[1] + Math.abs(pos - acc[0])}, (a, b) -> b)[1];
    }
}

解释

方法:

首先,创建一个字典来存储键盘上每个字符的索引,以便快速查找任意字符的位置。然后,初始化一个变量来跟踪当前指针的位置(从键盘的第一个字符开始)。遍历给定的单词中的每个字符,使用字典查找该字符在键盘上的位置,计算从当前位置移动到该字符位置的距离(使用绝对值),并将该距离累加到总移动距离中。更新当前位置为该字符的位置。最终,返回累加的总移动距离。

时间复杂度:

O(n + m)

空间复杂度:

O(n)

代码细节讲解

🦆
在这个算法中,为什么选择用字典来存储键盘上每个字符的索引,而不是使用其他数据结构?
字典提供了键到值的映射,这使得查找操作非常高效,复杂度为O(1)。在本算法中,需要频繁地查找每个字符在键盘上的位置,使用字典可以快速访问任何字符的索引,从而使得整体算法更加高效。如果使用数组或列表,虽然能以索引快速访问元素,但在这种场景下,我们需要根据字符来获取其索引,这会导致需要遍历数组来查找字符,效率较低。
🦆
如何处理在给定的单词中出现键盘上不存在的字符?
在实现算法前,应当考虑输入的有效性。对于键盘上不存在的字符,算法可以设计为抛出异常或返回一个错误信息。在代码实现中,可以在查找字典时先检查字符是否存在于字典中,如果不在,可以抛出一个值错误异常(例如,使用`raise ValueError('Character not found on the keyboard')`),确保算法的健壮性。
🦆
算法对于非标准长度的键盘(不是26个字母)的处理方式是否有所不同?
算法本身对键盘的长度没有特定的限制。因为算法是基于提供的`keyboard`字符串来创建索引映射的,只要`keyboard`字符串中的字符与单词中的字符匹配,算法就能正确运行。无论键盘是标准26个字母的键盘还是包含更多或更少字符的键盘,只要保证单词中的字符都能在键盘字符串中找到,算法就不需要做出调整。
🦆
在当前算法中,若键盘的布局发生改变,例如字符顺序不同,是否需要对算法进行调整?
算法的核心部分不需要调整,因为它是根据`keyboard`字符串动态构建字符位置索引的。只要`keyboard`参数正确反映了键盘上字符的当前布局,算法就能正确计算出字符之间的距离。因此,算法已经适配了键盘布局的任何变化,只需要确保传入正确的键盘布局字符串即可。

相关问题