Java教程

算法训练:pat甲级训练(三道基础题)

本文主要是介绍算法训练:pat甲级训练(三道基础题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
第一题:1005 Spell It Right (20分)

在这里插入图片描述

我的AC代码:算法使用的是映射,难度:简单题

#include <iostream>
#include <string>
#include <stack>
using namespace std;

const int maxn = 105;
int main() {
	char* Val = new char[maxn] {'\0'};
	string Map[10] = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
	int res = 0;
	cin >> Val;
	for (int i = 0; '\0' != Val[i]; ++i)
		res += (Val[i] - '0');
	stack<string> ans;
	if (!res)
		cout << Map[0];
	else {
		while (res) {
			ans.push(Map[res % 10]);
			res /= 10;
		}
		while (1 < (int)ans.size()) {
			cout << ans.top() << ' ';
			ans.pop();
		}
		cout << ans.top();
	}
	return 0;
}
第二题:1006 Sign In and Sign Out (25分)

在这里插入图片描述

我的AC代码:主要练习STL&引用传参&排序,难度:简单题

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

struct Student {
	string id;
	int sHour, sMinu, sSeco;
	int tHour, tMinu, tSeco;
	Student(string id_, int Hour_, int Minu_, int Seco_, int _Hour, int _Minu, int _Seco) :id(id_), sHour(Hour_), sMinu(Minu_), sSeco(Seco_), tHour(_Hour), tMinu(_Minu), tSeco(_Seco) {  }
};
vector<Student> VecStu;
bool cmp1(Student s1, Student s2) {
	if (s1.sHour != s2.sHour)
		return s1.sHour < s2.sHour;
	else if (s1.sMinu != s2.sMinu)
		return s1.sMinu < s2.sMinu;
	else
		return s1.sSeco < s2.sSeco;
}
bool cmp2(Student s1, Student s2) {
	if (s1.tHour != s2.tHour)
		return s1.tHour > s2.tHour;
	else if (s1.tMinu != s2.tMinu)
		return s1.tMinu > s2.tMinu;
	else
		return s1.tSeco > s2.tSeco;
}
int parseInt(string str) {
	int num = 0;
	for (int i = 0; '\0' != str[i]; ++i)
		num = num * 10 + (str[i] - '0');
	return num;
}
void getTime(int& H, int& M, int& S, string str) {
	H = parseInt(str.substr(0, 2));
	M = parseInt(str.substr(3, 2));
	S = parseInt(str.substr(6));
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		string id, sTime, tTime;
		cin >> id >> sTime >> tTime;
		int sHour, sMinu, sSeco;
		getTime(sHour, sMinu, sSeco, sTime);
		int tHour, tMinu, tSeco;
		getTime(tHour, tMinu, tSeco, tTime);
		VecStu.push_back(Student(id, sHour, sMinu, sSeco, tHour, tMinu, tSeco));
	}
	Student TempFirst = VecStu[0], TempLast = VecStu[0];
	for (int i = 1; i < n; ++i) {
		if (cmp1(VecStu[i], TempFirst)) 
			TempFirst = VecStu[i];
		if (cmp2(VecStu[i], TempLast))
			TempLast = VecStu[i];
	}
	cout << TempFirst.id << ' ' << TempLast.id;
	return 0;
}
第三题:1007 Maximum Subsequence Sum (25分)

在这里插入图片描述

我的AC代码:维护最优子序列,变量模拟下标移动,难度中等题

#include <iostream>
using namespace std;

const int maxn = 10005;
int n, a[maxn], s, t, j, ans = -1, cnt;
int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		cnt += a[i];
		if (cnt < 0) {
			cnt = 0;
			j = i + 1;
		}
		else if (cnt > ans) {
			ans = cnt;
			s = j;
			t = i;
		}
	}
	if (ans >= 0)
		cout << ans << ' ' << a[s] << ' ' << a[t];
	else
		cout << 0 << ' ' << a[0] << ' ' << a[n - 1];
	return 0;
}
这篇关于算法训练:pat甲级训练(三道基础题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!