資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用給定單行鍵盤計算輸入單詞所需時間
以下文章討論了一種高效的方法來計算使用單行鍵盤輸入單詞的總時間。這是一個有趣的問題，之前在技術面試中被問到過。
問題陳述
考慮一種假設的情況，其中鍵盤上的所有按鍵都排成一行。第一個鍵的索引為 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 上輸入給定單詞所需的時間，我們首先將要輸入的單詞和鍵盤佈局儲存在兩個字串變數中。
我們保持手指的先前位置和當前位置。輸入每個字元所需的時間由 |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
輸出 time 作為總的單詞輸入時間。
結束
幹執行
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 = 要輸入的給定單詞的長度。
程式遍歷 word 字串中的每個字元，其長度為 n。
對於每個字元，它對 keyboard 字串執行查詢操作，其長度為 26（常數）。
因此，程式的時間複雜度 = O(n * 26) = O(n)。
空間複雜度：O(1)
程式使用固定數量的記憶體來儲存 keyboard 和 word 字串，以及一些整型變數。
這意味著程式的記憶體需求不會隨著輸入大小的增加而增加。
結論
本文討論了一種高效的解決方案方法，用於計算使用給定的單行鍵盤輸入單詞所需的時間。透過示例解釋了問題陳述，以便更好地理解。此外，解決方案方法包括虛擬碼、幹執行、C++程式以及對解決方案時間和空間複雜度的深入分析，以便深入理解。
127 次檢視
