极客笔记C++ 计算使用给定的单排键盘键入一个单词所需的时间
下面的文章讨论了一种有效的方法来计算使用单排键盘键入一个单词所需的总时间。这是一个有趣的问题，并且以前在技术面试中曾被问到。
问题陈述
考虑一种假设情景，在该情景中，键盘上的所有键都在一排中放置。第一个键的索引为0，最后一个键的索引为25。
对于给定的字符串’s’，计算在指定为’keyboard_layout’的特殊键盘上键入’s’的所有字符所需的时间。
从一个键移动到其相邻键所需的时间为单位时间。遍历可以在两个方向上进行。初始时，我们在索引0处。
示例
输入
keyboard = "mnbvcxzqwertyuioplkjhgfdsa", word = "cat"
输出
39
说明
最初我们处在索引0，即m
要到达“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
解决方案方法
要找到在一个特殊的单行键盘上键入给定单词所花费的总时间，键盘布局由键盘布局给出，我们首先将要键入的单词和键盘布局存储在两个字符串变量中。
我们保持手指的前一个位置和当前位置。键入每个字符所需的时间由|curr_pos – prev_pos|给出，并在每次迭代中添加到总时间中。每次迭代后，我们更新prev_pos为curr_pos。
伪代码
- 开始
-
从用户读取输入字符串键盘和单词
-
设置时间 = 0 和 prev_pos = 0
-
对于单词中的每个字符c，做以下操作：
- 设置 curr_pos = keyboard.find(c)
-
设置时间 = 时间 + 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++ code to find the typing time for the word using a one row keyboard
#include <iostream>
#include <string>
using namespace std;
// To compute the time taken to type the word using a given single row keyboard, the following function is used.
int timeTaken(string keyboard_layout, string word){
// Initialize time and previous position variables
int time = 0, prev_pos = 0;
// Iterate over each character in the word
for (char c : word){
// Find the position of the current character in the keyboard_layout
int curr_pos = keyboard_layout.find(c);
// Calculate the time taken to type the current character and add it to the total time
time += abs(curr_pos - prev_pos);
// Update the previous position to the current position
prev_pos = curr_pos;
}
// Return the typing time for the word
return time;
}
int main(){
string keyboard_layout = "mnbvcxzqwertyuioplkjhgfdsa";
string word = "tutorialspoint";
// function call to calculate time taken to type word
int time = timeTaken(keyboard_layout, word);
// Print the result
cout <<"Typing time for the word using a one row keyboard: " << time << endl;
return 0;
}
输出
Typing time for the word using a one row keyboard: 87
时间和空间复杂度分析
时间复杂度：O(n)
- n = 给定要打字的单词的长度。
-
程序遍历单词字符串中的每个字符，该字符串的长度为n。
-
对于每个字符，它在键盘字符串上执行查找操作，该字符串的长度为26（一个常数）。
-
因此，程序的时间复杂度= O(n * 26) = O(n)。
空间复杂度：O(1)
-
程序使用固定数量的内存来存储键盘和单词字符串，以及一些整数变量。
-
这意味着程序的内存需求不会随着输入大小的增加而增加。
结论
本文讨论了一种使用给定单行键盘计算打字所需时间的高效解决方法。通过示例解释了问题陈述，以便更好地理解。此外，解决方案还包括伪代码、演练、C++程序以及对解决方案的时间和空间复杂度的深入分析，以便更深入地理解。