「算法笔记」的读书笔记系列

本笔记来源于「算法笔记 胡凡」第四章 入门篇(2) 算法初步

「算法笔记」(一) 算法初步

1 | 排序

这里算法笔记只讲了选择排序和插入排序, 其中选择排序是不稳定的排序, 插入排序是稳定的排序, 下面给出多个常见排序的复杂度和稳定性分析:

引自

选择排序

// 每次选出[i, n]中最小的元素, 不稳定
void selectSort(vector<int>& vec) {
    int n = vec.size();
    for (int i = 0; i < n; ++i) {
        int k = i;
        for (int j = i; j < n; ++j) {
            if (vec[j] < vec[k]) {
                k = j;
            }
        }
        swap(vec[k], vec[i]);
    }
}

直接插入排序

void insertSort(vector<int>& vec) {
    int n = vec.size();
    for (int i = 1; i < n; ++i) {
        int temp = vec[i], j = i;
        // 找到插入的位置
        while (j > 0 && temp < vec[j - 1]) {
            vec[j] = vec[j - 1];
            j--;
        }
        vec[j] = temp;
    }
}

归并, 快排, 堆排

我的算法期末复习博客中包含了相关介绍(基于「算法 第四版」)

2 | 散列 (hash)

散列(hash, 哈希): 将元素通过一个函数转换为整数, 使得该整数可以尽量唯一地代表这个元素

元素key —> 整数H(key)

常用的hash算法:

• 除留余数法H(key) = key % mod

• 直接定址法H(key) = key

• 平方取中法 (少见) (取key^2的若干中间位作为hash值)

常用的解决冲突算法:

当H(key1) == H(key2)时, 产生冲突, 需要解决冲突, 下面是常用方法:

• 线性探查法 (Linear Probing)

当H(key)产生冲突时H(key)++直到没有冲突

• 平方探查法(Quadratic Probing)

H(key) +- k^2其中k从1到n取值

• 链地址法(拉链法)

把所有相同的key, 连接成一条单链表

字符串哈希

将A-Z的26个字母对应到0-25, 从而将字符串用26进制表示, 剩余处理同上

哈希表的大小需要为$26^{len}-1$, len为字符串长度

int hashFunc(char S[], int len) {
    int id = 0;
    for (int i = 0; i < len; ++i) {
        id = id * 26 + (S[i] - 'A');  // 转换为26进制表示
    }
    return id;
}

如果出现小写字母, 则变为52进制

出现数字, 变为62进制

3 | 二分

递归和贪心比较简单, 这里略过

经典的二分查找: 如何在一个严格递增序列A中找出给定的数x

二分查找代码:

// 二分法在有序vec中寻找x, 返回值为x的下标, 如果没找到返回-1
int binarySearch(vector<int>& vec, int x) {
    int left = 0, right = vec.size() - 1;
    int mid;
    while (left <= right) {
        mid = left + ((right - left) >> 1); // 防止溢出
        if (vec[mid] == x) return mid;
        else if (vec[mid] > x) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

upper_bound 和lower_bound

关于lower_bound和upper_bound函数的实现:

lower_bound用于寻找第一个大于等于x的元素

upper_bound用于寻找第一个大于x的元素

lower_bound的实现:

// 第一个大于等于x的元素下标
int lowerBound(vector<int>& vec, int x) {
    int left = 0;
    int right = vec.size();  //加入x比所有元素都大, 应当返回vec.size()
    int mid;
    while (left < right) {
        mid = left + ((right - left) >> 1);
        if (vec[mid] >= x) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

upper_bound的实现:

// 第一个大于x的元素下标
int upperBound(vector<int> &vec, int x) {
    int left = 0, right = vec.size();
    int mid;
    while (left < right) {
        mid = left + ((right - left) >> 1);
        if (vec[mid] > x) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

解决这类问题(寻找有序序列第一个满足某条件元素的位置)题目的写法:

int solve (int left, int right) {
    int mid;
    while (left < right) {
        mid = (left + right) / 2;
        if (条件成立) { // 条件成立, 第一个满足条件的元素位置 <= mid
        	right = mid;
        } else { // 条件不成立, 第一个满足条件的元素位置 > mid
            left = mid + 1;
        }
    }
    return left;
}

快速幂

基本问题:

给定三个整数a, b, m, 求$\mathrm{a}^{\mathrm{b}}\%\mathrm{m}$

直接暴力的写法:

llpow(long long a, long long b, long long m) {
    long long ans = 1;
    for (int i = 0; i < b; ++i) {
        ans = ans * a % m;
    }
    return ans;
}

时间复杂度O(b), 当b很大时(>$10^8$), 暴力的方法行不通

快速幂的方法基于如下两个事实:

1. 如果b是奇数, 那么$\mathrm{a}^{\mathrm{b}}=\mathrm{a}\times \mathrm{a}^{\mathrm{b}-1}$
2. 如果b是偶数, 那么$\mathrm{a}^{\mathrm{b}}=\mathrm{a}^{\frac{\mathrm{b}}{2}}\times \mathrm{a}^{\frac{\mathrm{b}}{2}}$

递归写法

显然b为奇数的情况可以转换为b为偶数的情况, 基于二分的思想则得到快速幂的O(logb)递归写法:

long long binaryPow(long long a, long long b, long long m) {
    if (b == 0) return 1;
    if (b & 1) return a * binaryPow(a, b - 1, m) % m; // b为奇数
    else { // b为偶数
        // 先计算mul = binaryPow而不要使用binaryPow * binaryPow的形式, 否则时间复杂度将变为O(b)
        long long mul = binaryPow(a, b / 2, m);
        return mul * mul % m;
    }
}

迭代写法

比如b = 13可以写为1101, 则$13=2^3+2^2+2^0$, 即$\mathrm{a}^{13}=\mathrm{a}^{2^3}\times \mathrm{a}^{2^2}\times \mathrm{a}^{2^0}$

所以得到迭代写法如下:

1. 初始ans = 1
2. 判断b(二进制)的末尾是否为1, 如果是, ans *= a
3. a*=a(平方)并将b右移一位
4. b > 0则返回步骤2

binaryPow(long long a, long long b, long long m) {
    long long ans = 1;
    while (b > 0) {
        if (b & 1) {
            ans = ans * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}

迭代与递归的效率对比差不多, 但是迭代更好理解(