计算使用给定的单行键盘输入一个单词所需的时间
以下文章讨论了一种使用单行键盘计算输入一个单词所需总时间的有效方法。这是一个有趣的问题，以前在技术面试中被问过。
问题陈述
考虑一个假设场景，其中键盘上的所有键都放在一行中。第一个键的索引为 0，最后一个键的索引为 25。
对于给定的字符串"s"，计算在布局指定为"keyboard_layout"的特殊键盘上输入"s"的所有字符所需的时间。
从一个键移动到其相邻键所需的时间需要单位时间。可以双向遍历。最初我们在索引 0。
示例
输入
keyboard = "mnbvcxzqwertyuioplkjhgfdsa", word = "cat"
输出
39
解释
最初我们位于索引 0，即 m
要到达"c"，所用时间 = 4，因为 m>n>b>v>c
要到达"a"，所用时间 = 21，因为 c>x>z>q>w>e>r>t>y>u>i>o>p>k>j>h>g>f>d>s>a
要到达"t"，所用时间 = 14，因为 a>s>d>f>g>h>j>k>l>p>o>i>u>y>t
总时间 = 4 + 21 + 14 = 39
输入
keyboard "rfvcdewsxzaqtgbnhyujmkiolp", word = "hat"
输出
24
解释
到达'h'，所用时间 = 16
到达'a'，所用时间 = 6
到达't'，所用时间 = 2
遵循与上述相同的逻辑。
总时间 = 16 + 6 + 2 = 24
输入
keyboard = "plmkoijnbhuygvcftrdxzsewaq", word = "bat"
输出
32
解释
到达'b'，所用时间 = 8
到达'a'，所用时间 = 16
要达到"t"，所用时间 = 8
遵循与上述相同的逻辑。
总时间 = 8 + 16 + 8 = 24
解决方法
要找到在特殊单行键盘上输入给定单词的总时间，其布局为 keyboard_layout，我们首先将要输入的单词和 keyboard_layout 存储在 2 个字符串变量中。
我们保持手指的先前位置和当前位置。输入每个字符所需的时间由 |curr_pos - prev_pos| 给出，并在每次迭代中添加到总时间中。每次迭代后，我们将 prev_pos 更新为 curr_pos。
伪代码
开始
从用户处读取输入字符串 keyboard 和 word
设置 time = 0 和 prev_pos = 0
对 word 中的每个字符 c 执行以下操作:
设置 curr_pos = keyboard.find(c)
设置 time = time + abs(curr_pos - prev_pos)
设置 prev_pos = curr_pos
将时间输出为总单词输入时间。
结束
试运行
keyboard = "qazwsxedcrfvtgbyhnujmikolp"
word = "well"
1. time = 0, prev_pos = 0
2. For each character in word:
- For 'w':
- curr_pos = 0
- time += abs(3 - 0) = 3
- prev_pos = 3
- For 'e':
- curr_pos = 3
- time += abs(6 - 3) = 3
- prev_pos = 6
- For 'l':
- curr_pos = 24
- time += abs(24 - 6) = 18
- prev_pos = 24
- For 'l':
- curr_pos = 24
- time += abs(24 - 24) = 0
- prev_pos = 24
3. Return time = 3 + 3 + 18 + 0 = 24
示例:C++ 程序
该程序将一个字符串 keyboard_layout 作为输入，该字符串表示特殊键盘的布局，所有键都在一行中，以及一个表示要输入的单词的字符串。该程序计算输入单词所需的时间，其中将手指从一个键移动到另一个键所需的时间是它们索引之间的绝对差。该程序通过调用函数 timeTaken() 返回输入单词所需的总时间。
示例
// 使用单行键盘查找单词输入时间的 C++ 代码
#include <iostream>
#include <string>
using namespace std;
// 要计算使用给定单行键盘输入单词所需的时间，请使用以下函数。
int timeTaken(string keyboard_layout, string word){
// 初始化时间和先前位置变量
int time = 0, prev_pos = 0;
// 遍历单词中的每个字符
for (char c : word){
// 查找当前字符在 keyboard_layout 中的位置
int curr_pos = keyboard_layout.find(c);
// 计算输入当前字符所用的时间并将其添加到总时间中
time += abs(curr_pos - prev_pos);
// 将先前位置更新为当前位置
prev_pos = curr_pos;
}
// 返回单词的输入时间
return time;
}
int main(){
string keyboard_layout = "mnbvcxzqwertyuioplkjhgfdsa";
string word = "tutorialspoint";
// 函数调用以计算输入单词所用的时间
int time = timeTaken(keyboard_layout, word);
// 打印结果
cout <<"使用单行键盘输入单词的时间:" << time << endl;
return 0;
}
输出
使用单行键盘输入单词的时间:87
时间和空间复杂度分析
时间复杂度:O(n)
n = 要输入的给定单词的长度。
程序遍历单词字符串中的每个字符，该字符串的长度为 n。
对于每个字符，它在键盘字符串上执行查找操作，该字符串的长度为 26(一个常数)。
因此，程序的时间复杂度 = O(n * 26) = O(n)。
空间复杂度:O(1)
该程序使用固定数量的内存来存储键盘和字符串，以及一些整数变量。
这意味着程序的内存需求不会随着输入大小的增加而增加。
结论
本文讨论了一种有效的解决方法，用于计算使用给定的单行键盘输入单词所需的时间。通过示例解释问题陈述，以便更好地理解。此外，解决方法包括伪代码、试运行、C++ 程序以及对解决方案的时间和空间复杂度的深入分析，以便深入了解。
