提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

算法笔记的学习心得和知识总结（三）|CodeUp and Pat篇（算法笔记第四章 排序算法）

算法笔记排序 总结 and 知识 PAT 第四章
2023-09-14 09:15:35 时间

目录结构

算法笔记CodeUp Pat汇总

文章快速说明索引

学习目标：

因为最近一来要准备一下浙大PAT考试，二来复习一下将近遗忘的算法知识。正好把当年快翻烂掉的《算法笔记》再学一遍，权做C/C++和DSA的复习之用！注：因为进入工作岗位之后，基础知识的使用和遗忘会变得十分常见！面向过程 面向对象逐渐变成了面向百度编程，可是对于参加算法或编程竞赛而言 Baidu恐怕也帮不上忙了！古人云：温故而知新，可以为师矣！

1、CodeUp链接 ，点击前往
2、浙大PAT链接，点击前往
3、Tsinghua Online Judge，点击前往

本文有详细的实例（《算法笔记》书中的全部例题，都是可以直接通过评测系统的），如有疑问或者其他想法的小伙伴请在下面留言 Thanks♪(･ω･)ﾉ！

注：这些例题源码答案主要着重于通过 评测系统 （AC），故而仍有很多优化之处 小伙伴自行斟酌。这些也仅仅是起到一个抛砖引玉，相互借鉴的作用！

其顺序为书中的例题顺序，格式为：习题链接和题目源码

学习内容：（详见目录）

1、算法笔记 胡凡著

学习时间：

2020年12月08日 19:57:06

学习产出：

1、《算法笔记》复习
2、CSDN 技术博客 1篇

注：这一章涉及到基础的算法 而排序算法是个重点，下面是我之前的相关博客（C++版）:

1、DSA之十大排序算法 十大排序算法汇总（C++），点击前往
2、十大排序算法 本人Git仓库链接，点击前往

或者直接选择相应的排序算法：

1、DSA之十大排序算法第一种：Bubble sort，点击前往
2、DSA之十大排序算法第二种：Straight Selection Sort，点击前往
3、DSA之十大排序算法第三种：Straight Insertion Sort，点击前往
4、DSA之十大排序算法第四种：Shell Sort，点击前往
5、DSA之十大排序算法第五种：Merge Sort，点击前往
6、DSA之十大排序算法第六种：Quick Sort，点击前往
7、DSA之十大排序算法第七种：Heap Sort，点击前往
8、DSA之十大排序算法第八种：Counting Sort，点击前往
9、DSA之十大排序算法第九种：Bucket Sort，点击前往
10、DSA之十大排序算法第十种：Radix Sort，点击前往

一、PAT    B1025

PAT B1001题 题目链接，点击前往

题目描述：
在这里插入图片描述
样例输入输出：
在这里插入图片描述
评测结果如下：
在这里插入图片描述
本题提交代码为：

/**══════════════════════════════════╗
*作    者：songbaobao                                                  ║
*职    业：我以我血荐轩辕                                              ║
*CSND地址：https://blog.csdn.net/weixin_43949535                       ║
**GitHub ：https://github.com/TsinghuaLucky912/My_own_C-_study_and_blog║
**GitEE  ：https://gitee.com/lucky912_admin/code-up_-pat               ║
*═══════════════════════════════════╣
*创建时间：                                                           
*功能描述：                                                            
*                                                                      
*                                                                      
*═══════════════════════════════════╣
*结束时间:                                                           
*═══════════════════════════════════╝
//                .-~~~~~~~~~-._       _.-~~~~~~~~~-.
//            __.'              ~.   .~              `.__
//          .'//              西南\./联大               \\`.
//        .'//                     |                     \\`.
//      .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \\`.
//    .'//.-"                 `-.  |  .-'                 "-.\\`.
//  .'//______.============-..   \ | /   ..-============.______\\`.
//.'______________________________\|/______________________________`.
*/
#include <iostream>
#include <vector>
#include <string.h>
#include <unordered_map>
#include <ctype.h>
#include <queue>
#include <list>
#include <map>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Student
{
	char registration_number[14] = { 0 };// 考试证号
	int score;// 分数
	int location_number;// 考场号
	int local_rank;// 本考场内的排名
}student[30001];

bool mycompare(Student &a, Student &b)//比较函数
{
	if (a.score != b.score)return a.score > b.score;//先按分数从高到低 排序
	else return strcmp(a.registration_number, b.registration_number) < 0;//分数相同   按照准考证号从小到大排序
}

int main()
{
	int N, total = 0, location_number = 1;
	scanf("%d", &N);
	while (N--)
	{
		int K, local_rank = 1, localNum;
		scanf("%d", &K);
		localNum = K;
		while(localNum--)
		{
			scanf("%s%d", student[total].registration_number, &student[total].score);
			student[total].location_number = location_number;
			total++;
		}
		sort(student + total - K, student + total, mycompare);
		student[total - K].local_rank = local_rank;
		for (int i = total - K + 1; i < total; ++i)
		{
			if (student[i].score != student[i - 1].score)
			{
				local_rank = i + 1 - (total - K);
				student[i].local_rank = local_rank;
			}
			else
			{
				student[i].local_rank = student[i - 1].local_rank;
			}
		}
		location_number++;
	}
	
	sort(student, student + total, mycompare);
	printf("%d\n", total);

	int finalrank = 1;
	printf("%s %d %d %d\n", student[0].registration_number, finalrank,
		student[0].location_number, student[0].local_rank);
	for (int i = 1; i < total; ++i)
	{
		if (student[i].score != student[i - 1].score)
		{
			finalrank = i + 1;
		}
		printf("%s %d %d %d\n", student[i].registration_number, finalrank,
				student[i].location_number, student[i].local_rank);
	}
	return 0;
}
/**
*备用注释：
*
*
*
*/

二、CodeUp 581

CodeUp 581题 题目链接，点击前往

在这里插入图片描述
本题全部源码如下：

/**══════════════════════════════════╗
*作    者：songbaobao                                                  ║
*职    业：我以我血荐轩辕                                              ║
*CSND地址：https://blog.csdn.net/weixin_43949535                       ║
**GitHub ：https://github.com/TsinghuaLucky912/My_own_C-_study_and_blog║
**GitEE  ：https://gitee.com/lucky912_admin/code-up_-pat               ║
*═══════════════════════════════════╣
*创建时间：                                                           
*功能描述：                                                            
*                                                                      
*                                                                      
*═══════════════════════════════════╣
*结束时间:                                                           
*═══════════════════════════════════╝
//                .-~~~~~~~~~-._       _.-~~~~~~~~~-.
//            __.'              ~.   .~              `.__
//          .'//              西南\./联大               \\`.
//        .'//                     |                     \\`.
//      .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \\`.
//    .'//.-"                 `-.  |  .-'                 "-.\\`.
//  .'//______.============-..   \ | /   ..-============.______\\`.
//.'______________________________\|/______________________________`.
*/
#include <iostream>
#include <vector>
#include <string.h>
#include <unordered_map>
#include <ctype.h>
#include <queue>
#include <list>
#include <map>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;

#if PA1025
struct Student
{
	char registration_number[14] = { 0 };// 考试证号
	int score;// 分数
	int location_number;// 考场号
	int local_rank;// 本考场内的排名
}student[30001];

bool mycompare(Student &a, Student &b)//比较函数
{
	if (a.score != b.score)return a.score > b.score;//先按分数从高到低 排序
	else return strcmp(a.registration_number, b.registration_number) < 0;//分数相同   按照准考证号从小到大排序
}
#endif

#if C
struct Student
{
	int id;
	char name[9];
	int score;

	Student(int id1, char name1[], int score1)
	{
		id = id1;
		strcpy(name, name1);
		score = score1;
	}
};

// 在codeup上面使用 引用会有报错 到时候去掉 & 即可
bool cmp1(Student& a, Student& b)
{
	return a.id < b.id;
}

bool cmp2(Student& a, Student& b)
{
	int result = strcmp(a.name, b.name);
	if (result != 0)
		return result < 0;
	return a.id < b.id;
}

bool cmp3(Student& a, Student& b)
{
	if (a.score != b.score)
		return a.score < b.score;
	return a.id < b.id;
}
#endif 

struct Animal
{
	int weight;
	char color[11];

	Animal(int w, char c[])
	{
		weight = w;
		strcpy(color, c);
	}
};

bool cmpAnimal(Animal a, Animal b)
{
	return a.weight > b.weight;
}

#if I
struct Student
{
	char id[21];
	int m;
	int score;

	Student(char id1[], int m1, int score1)
	{
		strcpy(id, id1);
		m = m1;
		score = score1;
	}
};

bool cmpStudentScore(Student& a, Student& b)
{
	if (a.score != b.score)
		return a.score > b.score;
	return a.id < b.id;
}
#endif

int main()
{
#if PA1025
	int N, total = 0, location_number = 1;
	scanf("%d", &N);
	while (N--)
	{
		int K, local_rank = 1, localNum;
		scanf("%d", &K);
		localNum = K;
		while(localNum--)
		{
			scanf("%s%d", student[total].registration_number, &student[total].score);
			student[total].location_number = location_number;
			total++;
		}
		sort(student + total - K, student + total, mycompare);
		student[total - K].local_rank = local_rank;
		for (int i = total - K + 1; i < total; ++i)
		{
			if (student[i].score != student[i - 1].score)
			{
				local_rank = i + 1 - (total - K);
				student[i].local_rank = local_rank;
			}
			else
			{
				student[i].local_rank = student[i - 1].local_rank;
			}
		}
		location_number++;
	}
	
	sort(student, student + total, mycompare);
	printf("%d\n", total);

	int finalrank = 1;
	printf("%s %d %d %d\n", student[0].registration_number, finalrank,
		student[0].location_number, student[0].local_rank);
	for (int i = 1; i < total; ++i)
	{
		if (student[i].score != student[i - 1].score)
		{
			finalrank = i + 1;
		}
		printf("%s %d %d %d\n", student[i].registration_number, finalrank,
				student[i].location_number, student[i].local_rank);
	}
#endif

#if A
	int N;
	while (~scanf("%d", &N))
	{
		vector<int>myvec;
		int val;
		for (int i = 0; i < N; ++i)
		{
			cin >> val;
			myvec.push_back(val);
		}

		sort(myvec.begin(), myvec.end());
		for (vector<int>::iterator it = myvec.begin(); it != myvec.end(); ++it)
		{
			cout << *it << " ";
		}
		cout << endl;
	}
#endif

#if B
	int N;
	while (~scanf("%d", &N))
	{
		vector<int>myvec;
		int val;
		for (int i = 0; i < N; ++i)
		{
			cin >> val;
			myvec.push_back(val);
		}

		sort(myvec.begin(), myvec.end());

		cout << myvec[N - 1] << endl;
		int i = 0;
		for (vector<int>::iterator it = myvec.begin(); it != myvec.end() && i < N - 1; ++it, ++i)
		{
			cout << *it << " ";
		}
		if (N == 1)
			cout << -1;
		cout << endl;
	}
#endif

#if C
	int N, C, count = 0;
	while (~scanf("%d%d", &N, &C), N != 0)
	{
		vector<Student>myvec;
		int id, score; char name[9] = { 0 };
		for (int i = 0; i < N; ++i)
		{
			cin >> id >> name >> score;
			myvec.push_back(Student(id, name, score));
		}

		if (1 == C)
		{
			sort(myvec.begin(), myvec.end(), cmp1);
		}
		else if (2 == C)
		{
			sort(myvec.begin(), myvec.end(), cmp2);
		}
		else if (3 == C)
		{
			sort(myvec.begin(), myvec.end(), cmp3);
		}

		// cout << "Case " << C << ":" << endl;

		printf("Case %d:\n", ++count);
		for (vector<Student>::iterator it = myvec.begin(); it != myvec.end(); ++it)
		{
			// cout << setfill('0') << setw(6) << it->id << " " << it->name << " " << it->score << endl;
			printf("%06d %s %d\n", it->id, it->name, it->score);
		}
	}
#endif 

#if D
	char str[201] = { 0 };
	while (NULL != gets_s(str))
	{
		vector<char>myvec;
		int len = strlen(str);
		for (int i = 0; i < len; ++i)
		{
			myvec.push_back(str[i]);
		}
		sort(myvec.begin(), myvec.end());

		for (vector<char>::iterator it = myvec.begin(); it != myvec.end(); ++it)
		{
			cout << *it;
		}
		cout << endl;
	}
#endif

#if F
	int N;
	while (~scanf("%d", &N))
	{
		int w; char color[11] = { 0 };
		
		vector<Animal>myvec;

		for (int i = 0; i < N; ++i)
		{
			cin >> w >> color;
			myvec.push_back(Animal(w, color));
		}
		sort(myvec.begin(), myvec.end(), cmpAnimal);

		for (vector<Animal>::iterator it = myvec.begin(); it != myvec.end(); ++it)
		{
			cout << it->color << endl;
		}
	}
#endif

#if G
	int N;
	while (~scanf("%d", &N), N != 0)
	{
		int val, mid;
		if (1 == N)
		{
			cin >> val;
			cout << val << endl;

			continue;
		}

		vector<int>myvec;
		for (int i = 0; i < N; ++i)
		{
			cin >> val;
			myvec.push_back(val);
		}
		sort(myvec.begin(), myvec.end());

		mid = N / 2;

		if (N % 2 == 1)
		{
			cout << myvec[mid] << endl;
		}
		else
		{
			cout << (myvec[mid - 1] + myvec[mid]) / 2 << endl;
		}
	}
#endif

#if H

	int array[10] = { 0 };

	while (cin >> array[0] >> array[1] >> array[2] >> array[3] >> array[4] >> array[5] >>
		array[6] >> array[7] >> array[8] >> array[9])
	{
		vector<int>myvec1;
		vector<int>myvec2;

		for (int i = 0; i < 10; ++i)
		{
			if (array[i] % 2 == 1)
				myvec1.push_back(array[i]);
			else
				myvec2.push_back(array[i]);
		}
		sort(myvec1.begin(), myvec1.end());
		sort(myvec2.begin(), myvec2.end());

		for (vector<int>::reverse_iterator it = myvec1.rbegin(); it != myvec1.rend(); ++it)
		{
			cout << *it << " ";
		}
		for (vector<int>::iterator it = myvec2.begin(); it != myvec2.end(); ++it)
		{
			cout << *it << " ";
		}
		cout << endl;
	}

#endif

#if I
	int N, M, G;

	while (~scanf("%d", &N), N != 0)
	{
		scanf("%d%d", &M, &G);

		vector<int>perScore;
		vector<Student>perStudent;
		int perscore;
		int num = 0;
		for (int i = 0; i < M; ++i)
		{
			cin >> perscore;
			perScore.push_back(perscore);
		}

		for (int i = 0; i < N; ++i)
		{
			char id[21];
			int m;
			int totalScore = 0;

			cin >> id >> m;

			for (int i = 0; i < m; ++i)
			{
				int val;
				cin >> val;
				
				totalScore += perScore[val - 1];
			}

			perStudent.push_back(Student(id, m, totalScore));
		}
		
		sort(perStudent.begin(), perStudent.end(), cmpStudentScore);

		for (vector<Student>::iterator it = perStudent.begin(); it != perStudent.end(); ++it)
		{
			if (it->score >= G)
				num++;
		}
		cout << num << endl;
		for (vector<Student>::iterator it = perStudent.begin(); it != perStudent.end(); ++it)
		{
			if (it->score >= G)
				cout << it->id << " " << it->score << endl;
		}
	}
#endif

#if E
	int m;
	while (~scanf("%d", &m))
	{
		vector<vector<int>>myvec;
		vector<int>result;
	
		int val;
		for (int i = 0; i < m; ++i)
		{
			int sum = 0;
			vector<int>vec;
			for (int j = 0; j < m; ++j)
			{
				cin >> val;
				sum += val;
				vec.push_back(val);
			}
			result.push_back(sum);
			myvec.push_back(vec);
		}

		int sum1 = 0;
		int sum2 = 0;
		for (int i = 0; i < m; ++i)
		{
			int sum3 = 0;
			for (int j = 0; j < m; ++j)
			{
				if (i == j)
				{
					sum1 += myvec[i][j];
				}
				if (m == (i + j + 1))
				{
					sum2 += myvec[i][j];
				}
					
				sum3 += myvec[j][i];
			}
			
			result.push_back(sum3);
		}
		result.push_back(sum1);
		result.push_back(sum2);

		sort(result.begin(), result.end());

		for (vector<int>::reverse_iterator it = result.rbegin(); it != result.rend(); ++it)
		{
			cout << *it << " ";
		}
		cout << endl;

	}
#endif

	return 0;
}
/**
*备用注释：
*
*
*
*/

相关文章