UVa 10082

題目

http://domen111.github.io/UVa-Easy-Viewer/?10082

人在打字常常打錯，現在給你一項任務，將所有輸入的字元都變成在鍵盤中左邊一位的字元

當然，題目保證不會輸入像是 Q A Z ` 的邊界字元，請放心

想法

直接將鍵盤上的字刷過一遍，沒錯，刷過去

建立一個字串 $tbl$ ，包含鍵盤上的所有字母，並且是由上到下、由左到右的順序

接下來每次我們輸入的時候，只需要到 $tbl$ 找到當前的字母，然後輸出他的前一個就可以了

Code

#include<iostream> 
using namespace std;
string tbl="`1234567890-=QWERTYUIOP[]ASDFGHJKL;'ZXCVBNM,./'";
string s;
int main(){
	while(getline(cin,s)){
		for(int i=0 ; i<s.size() ; i++){
			if(s[i]==' ')
				cout<<" ";
			else{
				for(int j=0 ; j<tbl.size() ; j++){
					if(s[i]==tbl[j]){
						cout<<tbl[j-1];
						break;
					}
				}
			}
		}
		cout<<"\n";
	}
	return 0;
}

時間複雜度分析

假設 $tbl$ 的字串長度為 $N$

每次查詢時間複雜度最差為 $O(N)$

每筆測資時間複雜度為 $O(len(s)N)$