算法笔记

C++版本

评测结果

答案正确 Accepted AC
编译错误 Compile Error CE
答案错误 Wrong Answer WA
运行超时 Time Limit Exceeded TLE
运行错误 Runtime Error RE
内存超限 Memory Limit Exceeded MLE
格式错误 Presentation Error PE
输出超限 Output Limit Exceeded OLE

答案正确(Accepted, AC)

恭喜你!所提交的代码通过了数据!这个评测结果应该是大家最喜欢见到的,也非常好理解。如果是单点测试,那么每通过一组数据,就会返回一个Accepted;如果是多点测试,那么只有当通过了所有数据时,才会返回Accepted。

编译错误(Compile Error, CE)

很显然,如果代码没有办法通过编译,那么就会返回Compile Error。这时要先注意是不是选错了语言,然后再看本地的编译器能不能编译通过刚刚提交的代码,修改之后再次提交即可。

答案错误(Wrong Answer, WA)

“答案错误”是比较令人懊恼的结果,因为这说明代码有漏洞或者算法根本就是错误的,只是恰好能过样例而已。不过有时可能是因为输出了一些调试信息导致的,那就删掉多余的输出内容再输出。当然,大部分情况下都需要认真检查代码的逻辑有没有问题。

运行超时(Time Limit Exceeded, TLE)

由于每道题都会规定程序运行时间的上限,因此当超过这个限制时就会返回TLE。一般来说,这一结果可能是由算法的时间复杂度过大而导致的,当然也可能是某组数据使得代码中某处地方死循环了。因此,要仔细思考最坏时间复杂度是多少,或者检查代码中是否可能出现特殊数据死循环的情况。

运行错误(Runtime Error, RE)

这一结果的可能性非常多,常见的有段错误(直接的原因是非法访问了内存,例如数组越界、指针乱指)、浮点错误(例如除数为0、模数为0)、递归爆栈(一般由递归时层数过深导致的)等。一般来说,需要先检查数组大小是否比题目的数据范围大,然后再去检查可不可能有特殊数据可以使除数或模数为0,有递归的情况则检查是否在大数据时递归层数太深。

内存超限(Memory Limit Exceeded, MLE)

每道题目都会有规定程序使用的空间上限,因此如果程序中使用太多的空间,则会返回MLE,例如数组太大一般最容易导致这个结果。

格式错误(Presentation Error, PE)

这应该是最接近Accepted的错误了,基本是由多输出了空格或者换行导致的,稍作修改即可。

输出超限(Output Limit Exceeded, OLE)

如果程序输出了过量的内容(一般是指过量非常多),那么就会返回OLE。一般是由输出了大量的调试信息或者特殊数据导致的死循环输出导致的。


排序

十大经典排序算法

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ In-place 稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ In-place 不稳定
插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ In-place 稳定
希尔排序 $O\left( n\log \left( n \right) \right)$ $O\left( n\log ^2\left( n \right) \right)$ $O\left( n\log ^2\left( n \right) \right)$ $O(1)$ In-place 不稳定
归并排序 $O\left( n\log \left( n \right) \right)$ $O\left( n\log \left( n \right) \right)$ $O\left( n\log \left( n \right) \right)$ $O(n)$ Out-place 稳定
快速排序 $O\left( n\log \left( n \right) \right)$ $O\left( n\log \left( n \right) \right)$ $O(n^2)$ $O\left( \log \left( n \right) \right)$ In-place 不稳定
堆排序 $O\left( n\log \left( n \right) \right)$ $O\left( n\log \left( n \right) \right)$ $O\left( n\log \left( n \right) \right)$ $O(1)$ In-place 不稳定
计数排序 $O(n+k)$ $O(n+k)$ $O(n+k)$ $O(k)$ Out-place 稳定
桶排序 $O(n+k)$ $O(n+k)$ $O(n^2)$ $O(n+k)$ Out-place 稳定
基数排序 $O\left( n\times k \right)$ $O\left( n\times k \right)$ $O\left( n\times k \right)$ $O(n+k)$ Out-place 稳定

Github

冒泡排序

  1. 最快的时候就是序列已经为正序(要排序还有何用)
  2. 最慢的时候就是序列反序(可以写for循环倒序输出数据)
  3. flag判断是一种优化写法
int array[10] = {10,1,3,5,2,6,3,5,7,3};
for(int i = 0; i < 9; i++){ //进行n - 1轮
    int flag = 1; 
    for(int j = 0; j < 9 - i; j++)  //每轮比较n - i - 1次
        if(array[j] > array[j + 1]){
            swap(array[j], array[j + 1]);
            flag = 0;
        }
    if(flag) break; //当flag不等于0的时候即已经完成排序
}

简单选择排序

什么数据进入都是$O(n^2)$的复杂度,数据规模越小越好,不占用额外的内存空间

int array[10] = {10,1,3,5,2,6,3,5,7,3};
for(int i = 0; i < 9; i++){ //进行n - 1轮
    int min = i;
    for(int j = i + 1; j < 10; j++)  
        if(array[j] < array[min])
            min = j;
    if(min != i) //可以不写这句话,并不会消耗很多时间
        swap(array[i], array[min]);
}

插入排序

平均算法复杂度$O(n^2)$

//直接插入
int array[10] = {10,1,3,5,2,6,3,5,7,3}, j, temp;
for(int i = 1; i < 10; i++){
    for( j = i - 1, temp = array[i]; j >=0 && temp < array[j]; j--)
        array[j + 1] = array[j];
    array[j + 1] = temp;
}
//折半插入

2————路归并排序(采用分治法)

与选择排序一样不受输入数据的影响,但是比需要用更大的内存空间去换取$O\left( n\log \left( n \right) \right)$的时间复杂度。

//递归版
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
void merge(int array[], int left_1, int right_1, int left_2, int right_2){
    int i = left_1, j = left_2, temp[maxn], index = 0; //left_2 = right_1 + 1
    while(i <= right_1 && j <= right_2)
        array[i] <= array[j] ? temp[index++] = array[i++] : temp[index++] = array[j++];
    while(i <= right_1) temp[index++] = array[i++];
    while(j <= right_2) temp[index++] = array[j++];
    for(i = 0; i < index; i++)
        array[left_1 + i] = temp[i];
}
void merge_sort(int array[], int left, int right){
    if(left < right){
        int mid = (left + right) / 2;
        merge_sort(array, left, mid);
        merge_sort(array, mid + 1, right);
        merge(array, left, mid, mid + 1, right);
    }
}
int main(){
    int array[10] = {10, 9, 8, 7 , 5, 5, 4 ,3, 2, 1};
    merge_sort(array, 0,  9);
    for(int i = 0; i < 10; i++)
        cout << array[i] << " ";
    return 0;
}
//迭代版
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
void merge(int array[], int left_1, int right_1, int left_2, int right_2){
    int i = left_1, j = left_2, temp[maxn], index = 0; //left_2 = right_1 + 1
    while(i <= right_1 && j <= right_2){
        if(array[i] <= array[j]){
            temp[index++] = array[i++];
        }else{
            temp[index++] = array[j++];
        }
    }
    while(i <= right_1) temp[index++] = array[i++];
    while(j <= right_2) temp[index++] = array[j++];
    for(i = 0; i < index; i++){
        array[left_1 + i] = temp[i];
    }
}
void merge_sort(int array[], int n){
    for(int step = 2; step / 2 <= n; step *= 2){
        for(int i = 0; i < n; i += step){
            int mid = i + step / 2 - 1;
            if(mid + 1 < n){
                merge(array, i , mid, mid + 1, min(i + step - 1, n - 1));
            }
        }
    }
}
int main(){
    int array[] = { 9, 7, 7 , 10, 1, 10, 2, 3};
    int n = sizeof(array) / sizeof(array[0]);
    cout << n << endl;
    merge_sort(array, n);
    for(int i = 0; i < n; i++)
        cout << array[i] << " ";
    return 0;
}
//如果题目只要求给出没一趟结束时的序列,那么完全可以用sort函数代替merge函数(时间允许)可以先考虑用sort函数,然后超时的话自己写归并排序。
void merge_sort(int array[], int n){
    for(int step = 2; step / 2 <= n; step *= 2){
        for(int i = 0; i < n; i += step){
            sort(array + i, array + min(i + step, n));
        }
    }
}

快速排序

稳定&不稳定

相对位置发生变换,例如A5,B8,C5,D2,E9稳定排序后变成D2,A5,C5,B8,E9,不稳定排序后变为D2,C5,A5,B8,E9即A5跑到C5后面,相对位置发生变化。

稳定

#include <bits/stdc++.h>
using namespace std;
struct student{
    string name;
    int score;
}stu[5], stu_1;
int main(){
    for(int i = 0; i < 5; i++)
        cin >> stu[i].name >> stu[i].score;
    for(int i = 0; i < 4; i++){
        int flag = 0;
        for(int j = 0; j < 4 - i; j++){
            if(stu[j].score > stu[j + 1].score){
                flag = 1;
                stu_1 = stu[j];
                stu[j] = stu[j + 1];
                stu[j + 1] = stu_1;
            }
        }
        if(!flag) break;+
    }
    for(int i = 0; i < 5; i++)
        cout << stu[i].name << stu[i].score << endl;
    return 0;
}

不稳定

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s[5], temp;
    for(int i = 0; i < 5; i++)
        cin >> s[i];
    for(int i = 0; i < 4; i++){
        int min = i;
        for(int j = i + 1; j < 5; j++)  
            if(s[j][1] < s[min][1])
                min = j;
        if(min != i){
            temp = s[min];
            s[min] = s[i];
            s[i] = temp;
        }
    }
    for(int i = 0; i < 5; i++)
        cout << s[i] << endl;
    return 0;
}

贪心

简单贪心

是一种求解最优化问题的方法局部最优,要使得全局最优就要每一步都是最优的

B1020
B1023

区间贪心


two pointers

利用序列的递增(递减)性,来将复杂度降至$O(n)$。

例如在给定序列{1,2,3,4,5,6}中找到满足任意两数相加的和为8,eg:2+6=8与3+5=8,不包括6+2=8和3+5=8.

常规解法二重循环枚举,但是这样的复杂度为$O(n^2)$,对n在$10^5$的规模时是不可承受的。

对于递增序列

  1. 当a[j]+a[i] > M, 显然有a[i]+a[j+1] > M,即无需再对a[j]之后的数据进行枚举。
  2. 对于a[i],如果找到一个a[j],使得a[i] + a[j] > M恰好成立,那么a[i + 1] + a[j] > M成立,因此a[i]之后的元素也不用再去枚举。
int array[] = {1,2,3,4,5,6};
int n = sizeof(array) / sizeof(array[0]);
for(int i = 0; i < n; i++)
    for(int j = i + 1; j < n; j++)
        if(array[i] + array[j] == 8)
            cout << array[i] << " + " << array[j]  << " = 8" << endl;

对于递增序列

  1. 如果满足a[i] + a[j] == M,说明找到了其中一组方案,由于序列递增,不等式a[i + 1] + a[j] > M与a[i] + a[j - 1] < M均成立,但是a[i + 1]与a[j - 1]与M的大小关系未知因此剩下的只可能在区间[i+1,j-1]中产生。
  2. 如果满足a[i] + a[j] > M,由于序列递增,不等式a[i + 1] + a[j] > M成立,因此剩下的只可能在区间[i,j-1]中产生。
  3. 如果满足a[i] + a[j] < M,由于序列递增,不等式a[i] + a[j - 1] < M成立,因此剩下的只可能在区间[i + 1, j]产生。

two pointers思想复杂度为$O(n)$

int array[] = {1,2,3,4,5,6};
int n = sizeof(array) / sizeof(array[0]);
for(int i = 0, j = n - 1; i < j; )
    if(array[i] + array[j] == 8){
        cout << array[i] << " + " << array[j]  << " = 8" << endl;
        i++;
        j--;
    }
    else if(array[i] + array[j] < 8) i++;
    else j--;

序列合并问题

两个有序数列合并成一个有序数列

void merge(int array_1[], int array_2[], int array_3[], int n, int m){
int i = 0, j = 0, k = 0;
while(i < n && j < m){
if(array_1[i] <= array_2[j]){
array_3[k++] = array_1[i++];
}else{
array_3[k++] = array_2[j++];
}
}
while(i < n) array_3[k++] = array_1[i++];
while(j < m) array_3[k++] = array_2[j++];
}

广义two pointers是利用本身的序列的特性,使用两个下标i、j对序列进行扫描,可以是同向扫描,也可以是反向扫描。

文章作者: Mr.Zhang
文章标题: 算法笔记
文章链接: https://www.codewing.cn/index.php/46/algorithm-notes/
版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 许可协议。转载请注明来自Ying's Blog!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇