PAT-Advanced Linear

2020-04-14

Abstract：能在线性时间内解决的一些典型问题

1054 The Dominant Color (20分)

解法一：std::map

显然可以通过排序的map来维护出现的个数来求出众数，但是注意当map中存在众数时要记得break，否则部分测试点会超时

但是显然这不是最优解，很简单就不贴代码了（其实是没写/）

解法二：线性扫描

这是这道题的正解，通过相互抵消的办法线性时间内得到众数

维护一个初始为0的变量，如果存在众数，那么当众数++，非众数–时，最终的和一定为正，反之则不行

#include<iostream>
#include<algorithm>

int r, c, pixel, num = 0, curr;

int main() {
	std::ios::sync_with_stdio(false); std::cin.tie(0);
	std::cin >> r >> c;
	for (int i = 0; i < r * c; i++) {
		std::cin >> pixel;
		if (num == 0) curr = pixel;           // 如果当前和归零，说明一定不是众数
		if (pixel == curr) num++; else num--; // 否则继续观察，最后剩下的一定是众数
	}
	std::cout << curr;
}

1071 Speech Patterns (25分)

解法一：std::unordered_map

思路同上题，用map + 一些简单的字符串处理会比较方便

但是我暂时没想到不用map的做法

#include<iostream>
#include<string>
#include<unordered_map>

std::unordered_map <std::string, int> map;
int num = 0, max = 0;

int main() {
	std::ios::sync_with_stdio(false); std::cin.tie(0);
	std::string s, curr;
	std::getline(std::cin, s);
	for (int i = 0; i < s.length(); i++) {
		char c = s[i];
		if (isalnum(c)) curr.push_back(tolower(c));
		if (!isalnum(c) || i == s.length() - 1) {
			if (!curr.empty()) map[curr]++;
			curr.clear();
		}
	}
	
	for (auto it = map.begin(); it != map.end(); it++) {
		if (it->second > max){
			s = it->first;
			max = it->second;
		}
	}
	std::cout << s << " " << max;
}

Overyam