单行键盘
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
在这个算法中,为什么选择用字典来存储键盘上每个字符的索引,而不是使用其他数据结构?
▷🦆
如何处理在给定的单词中出现键盘上不存在的字符?
▷🦆
算法对于非标准长度的键盘(不是26个字母)的处理方式是否有所不同?
▷🦆
在当前算法中,若键盘的布局发生改变,例如字符顺序不同,是否需要对算法进行调整?
▷