PAT-Advanced String

Abstract：PAT 字符串相关

1061 Dating (20分)

解法一

#include<iostream>

int d, h, m;
std::string s1, s2, s3, s4;

void parse_input() { // 自己写的时候也很蛋疼，如果你觉得有点乱就看看别人的题解吧
	std::cin >> s1 >> s2 >> s3 >> s4;
	for (unsigned int i = 0, idx = 0; i < s1.length() && i < s2.length(); i++) {
		if (s1[i] == s2[i]) { // 前提是两者相同       
			// 先找day
			if (idx == 0 && s1[i] >= 'A' && s1[i] <= 'G')                        
				{ d = s1[i] - 'A' + 1; idx++; continue; }
			// 再找hour, isdigit可以简化判断, 以0-9和A-N计算结果
			if (idx == 1 && ((s1[i] >= 'A' && s1[i] <= 'N') || isdigit(s1[i])))
				{ h = isdigit(s1[i]) ? s1[i] - '0' : s1[i] - 'A' + 10; break; }           		
		}
	}
	for (unsigned int i = 0; i < s3.length() && i < s4.length();i++) {
		if (s3[i] == s4[i] && isalpha(s3[i])) { m = i; break; }   // 直接取得索引就行
	}
}

std::string get_day(int day) {
	switch (day) {
		case 1: return "MON";
		case 2: return "TUE";
		case 3: return "WED";
		case 4: return "THU";
		case 5: return "FRI";
		case 6: return "SAT";
		case 7: return "SUN";
	}
}

int main(){
	parse_input();
	std::string day = get_day(d);
	std::cout << day << " ";
	printf("%02d:%02d", h, m); // 我也想用 pure C++，奈何麻烦 	
}

1024 Palindromic Number (25分)

解法一

10的10次方，显然是要用字符串来模拟大数加减法的

#include<iostream>
#include<string>

int k;
std::string num;

bool isPalindromic(std::string& s) {
	int i = 0, j = s.size() - 1;
	while (i <= j) {
		if (s[i] != s[j])return false;
		i++; j--;
	}
	return true;
}

std::string getReverseSum(std::string a) {
	int carry = 0;
	std::string b = a; std::reverse(b.begin(), b.end());
	for (int i = 0; i < a.size(); i++) {
		a[i] = a[i]+ b[i] - '0' + carry;
		if (a[i] > '9') { a[i] -= 10; carry = 1; }
		else carry = 0;
	}
	if (carry) a += '1';             // 进位加在末尾再reverse就行了
	std::reverse(a.begin(), a.end());
	return a;
}

int main() {
	std::cin >> num >> k;
	for (int i = 0; i < k; i++) {
		if (isPalindromic(num)) {
			std::cout << num << std::endl << i;
			return 0;
		}
		else num = getReverseSum(num);
	}
	std::cout << num << std::endl << k;
}

1031 Hello World for U (20分)

解法一

关键在于知道怎么分割，题目要求U字要尽可能地“方”，而且给出了明确的表达式：

n1 = n3 = max{ n2 | n1 + n2 + n3 + 2 = N }

显然在最后一行之前应该有 N / 3行，也就是 n1 = n3 = 1+(N/3)，因为len / 3 = (len + 2) / 3

最后一行的长度为

#include<iostream>

int main() {
	std::string s;
	std::cin >> s;
	int len = s.length() - 1, i = 0, num = len / 3 + len % 3;
	for (i = 0; i < len / 3; i++) {
		std::cout << s[i];
		for (int k = 0; k < num - 1; k++) std::cout << " ";
		std::cout<< s[len - i] << std::endl;
	}
	std::cout << s.substr(i, num + 1);
}

1038 Recover the Smallest Number (30分)

解法一

字符串排序，逐一对比，如果长度不同，长的那个截断前半部分，递归比较

记得处理前导零，还要注意一种特殊情况，全是0时，此时需要输出0，也即全程前导零

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

int compare(const std::string s1, const std::string s2) {
	int len1 = s1.length(), len2 = s2.length(), len = std::min(len1, len2);
	for (int i = 0; i < len; i++)
		if (s1[i] != s2[i]) return s1[i] < s2[i];
	
	if (len1 > len2)
		return compare(s1.substr(len, len1 - len), s2);
	else if (len1 < len2)
		return compare(s1, s2.substr(len, len2 - len));
	else return 0;
}

int main() {
	int num;
	std::cin >> num;
	std::vector<std::string> list = std::vector<std::string>(num);
	for (int i = 0; i < num; i++) std::cin >> list[i];

	std::sort(list.begin(), list.end(), compare);

	bool leadingZero = true;
	for (const std::string& s : list) {
		for (char c : s) {
			if (leadingZero && c == '0') continue;
			if (leadingZero && c != '0') leadingZero = false;
			std::cout << c;
		}
	}
	if (leadingZero) std::cout << 0; // 特殊处理全0
}

解法二

另一种方法是直接用string自带的比较去做，直接比较 s1+s2 和 s2+s1 可以直接得出结果，但是速度略慢一些，因为字符串拼接需要复制整串到一个新的char数组里，反复拼接的消耗还是比较大的

int compare(const std::string& s1, const std::string& s2){
    return s1 + s2 < s2 + s1;
}