学习算法

算法学习笔记

,

刷题笔记

Sample Level

  • 排序

    • B1015/A1062:

      这是一道分类排序题，可以将成绩分成5个类别，最后一个类别不用输出。

      思路一：将类别作为结构体的一个成员，将所有学生进行排序（快速排序算法），平均复杂度为：$O(NlogN)$。
      思路二：分类存储每一类成绩，再分别对其排序。

      超时问题：

      最开始以为是因为排序算法的复杂度过高导致的超时，后经查阅其他人的博客发现，超时的原因是cin的速度比较慢，这里应该使用scanf函数来控制输入，如果使用cin函数，应该使用以下函数ios::sync_with_stdio(false)以取消cin和cout的同步机制（但是这种方法还是比scanf慢，因此此题建议使用scanf

      总结：

      1. 基本排序算法的实现-快速排序

        快速排序每次选择一个哨兵i作为标准，将整个序列分成两个部分：大于i的元素和小于i的元素。通过递归每次将两个部分再次进行排序，最终完成对序列整体的排序。

        代码实现：

         // 函数中的compare函数自己实现
 void quick_sort(Student students[], int start, int ends){
     if(start < ends){
         int low = start, high = ends;
         Student tmp = students[low];
         while(low < high){//把数组分成两个部分：应该排在tmp前面的和后面的
             while(low < high && compare(tmp, students[high]) == true){
                 //如果tudents[high]排在tmo的后面
                 high--;
             }
             students[low] = students[high];
             while(low < high && compare(tmp, students[low]) == false){
                 low++;
             }
             students[high] = students[low];
         }
         students[low] = tmp;
         quick_sort(students, start, low-1);
         quick_sort(students, low+1, ends);
     }
 }

      2. 使用库函数：sort()函数的使用方法

        下面简单介绍sort()函数的使用方法：

        sort()函数包含在algorithm库中

        Sorting:
        | method name | function |
        | :—————-:|:—————:|
        | sort |Sort elements in range (function template ) |
        | stable_sort | Sort elements preserving order of equivalents (function template ) |
        | partial_sort | Partially sort elements in range (function template )|
        |partial_sort_copy|Copy and partially sort range (function template )|
        |is_sorted | Check whether range is sorted (function template )|
        | is_sorted_until| Find first unsorted element in range (function template )|
        | nth_element|Sort element in range (function template )|

        sort的功能是对一个区间内的元素进行排序，默认非降序排序，可以通过自己实现compare函数控制排序。（不稳定排序，如果需要使用稳定排序，可以使用stable_sort函数进行排序）

        sort(first, last, comp)对$[first, last)$范围内的元素进行排序（左开右闭）

        comp参数是一个函数指针，这个函数应该返回一个bool值，sort函数根据bool值进行排序。

        e.g.,

        bool comp(Elem a, Elem b)返回true, 则表示排序过程中，a应该排在b的前面。

        实例1，vector排序：

         bool compare(Stu &s1, Stu &s2){
     int flag = false;
     if(s1.sum != s2.sum) return s1.sum > s2.sum;
     else if(s1.de != s2.de) return s1.de > s2.de;
     else return s1.id < s2.id;

     return flag;
 }

 //省略其他代码， stus是一个vector数组

 for(int i = 0; i < 4; i++){
     sort(stus[i].begin(), stus[i].end(), compare);
 }

        实例2，数组排序：

         //students是长度为m的数组
 sort(students, students + m, compare);

      3. algorithm库中可以使用的其他排序算法（见上表）

      4. 涉及到排序问题的关键在于怎样实现compare函数，通常根据题目的条件来实现相应的compare函数

    • 子问题：排名(Rank)

      排名问题的要点在于：如果存在相同分数的记录，排名应该保持相同，直到下一个分数出现才累计排名。

      e.g., 1，2，2，4，5，5，5，8

      • A1012

        • 简单的模拟题，最开始被我弄得很复杂，最终参考题解的代码如下：
        #include
#include
#include
#include
#include
using namespace std;
const int maxn=2010;
struct student{
    int id;
    int grade[4];
};
char course[4]={'A','C','M','E'};
student stu[maxn];
int RANK[10000000][4]={0};
int now;//当前第几门课
bool cmp(student a,student b){
    return a.grade[now]>b.grade[now];
}
int main(){
    int N,M;
    scanf("%d%d",&N,&M);
    for(int i=0;i

      • A1025

      题目是合并几块无序数据，并且按照分数进行总的排序。最终输出总排名和局部排名。

  • 简单Hash问题

    • 常用思路:
      • ASCII码散列，处理字符串相减等问题
      • 检查某些项是否出现
      • 两数相加问题
    • 简单问题中，可以通过使用散列的方法，降低时间复杂度。重点是在这个过程中，应该要考虑好散列表的大小，确保数据完全散列到表内。
分享到