PAT-BASIC1029——舊鍵盤/PAT-ADVANCED1084——Broken Keyboard

我的PAT-BASIC代碼倉：https://github.com/617076674/PAT-BASIC

我的PAT-ADVANCED代碼倉：https://github.com/617076674/PAT-ADVANCED

原題連結：

PAT-BASIC1029：https://pintia.cn/problem-sets/994805260223102976/problems/994805292322111488

PAT-ADVANCED1084：https://pintia.cn/problem-sets/994805342720868352/problems/994805382902300672

題目描述：

PAT-BASIC1029：

PAT-ADVANCED1084：

知識點：雙指針

思路：用雙指針分别周遊兩個字元串，比較字元是否相同

index1和index2雙指針都從0位置開始周遊。

（1）如果index1和index2均超出了字元串的長度範圍，則break跳出循環。

（2）如果index1未超出字元串input1的長度範圍，index2超出了字元串input2的長度範圍，那麼input1字元串中index1及之後的字元對應鍵盤上的鍵均是破損的。

（3）如果index1對應的字元與index2對應的字元相等，說明該字元對應的鍵未破損，index1和index2均周遊下一個字元。

（3）如果index1對應的字元與index2對應的字元不相等，說明index1對應的字元所對應的鍵破損，僅令index1周遊下一個字元，index2保持原位置不變。

注意點：

（1）小寫字元要轉化成大寫字元

（2）将新字元加入破損的vector之前，需要用vector<char>::iterator類型的疊代器it來判斷新字元是否在破損的vector中。可以用語句it = find(broken.begin(), broken.end(), c)。如果在broken中未找到字元c，則it == broken.end()。否則，說明在broken中找到了字元c。

時間複雜度是O(n)，其中n輸入的第一個字元串的長度。空間複雜度是O(m)，其中m為破損的鍵數。

C++代碼：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	string input1;
	string input2;

	cin >> input1 >> input2;

	vector<char> broken;
	int index1 = 0;
	int index2 = 0;
	while (true) {
		if (index1 >= input1.length() && index2 >= input2.length()) {
			break;
		} else if (index1 < input1.length() && index2 >= input2.length()) {
			for (int i = index1; i < input1.length(); i++) {
				char c = input1[i];
				if (c >= 'a' && c <= 'z') {
					c = c - 'a' + 'A';
				}
				vector<char>::iterator it;
				it = find(broken.begin(), broken.end(), c);
				if (it == broken.end()) {
					broken.push_back(c);
				}
			}
			break;
		}else if (input1[index1] == input2[index2]) {
			index1++;
			index2++;
		} else if (input1[index1] != input2[index2]) {
			char c = input1[index1];
			if (c >= 'a' && c <= 'z') {
				c = c - 'a' + 'A';
			}
			vector<char>::iterator it;
			it = find(broken.begin(), broken.end(), c);
			if (it == broken.end()) {
				broken.push_back(c);
			}
			index1++;
		}
	}

	for (int i = 0; i < broken.size(); i++) {
		cout << broken[i];
	}
}
           

C++解題報告：