算法进阶

text::C++

text:: 数据结构与算法

一、排序

可视化排序

1 冒泡排序

冒泡排序：对一个数组多次重复遍历。它要比较相邻的两项，并且交换顺序排错的项。每对数组进行一次遍历，就会有一个最大项排在了正确的位置。

改进：加一个 flag = False，如果一趟循环未发生任何排序则保持 False 表示已经排好了序。

时间： $O (n^{2})$

c++

void BubbleSort(vector<int>& arr)
{
    int len = arr.size();
    for (int i = 0; i < len - 1; i++)
    {
        bool flag = false;

        for (int j = i; j < len - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                flag = true;
            }
        }

        if (flag == false)
            break;
    }
}

python

def bubble_sort(lst):
    l = len(lst)
    for _ in range(l):
        flag = False
        for j in range(l - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
                flag = True
        # print(lst)

        if not flag:
            break
    return lst


lst = [8, 7, 3, 6, 5, 2, 4, 1, 7, 6]
print(bubble_sort(lst))

2 选择排序

同理冒泡，但是一开始不做交换，只记录位置，到单次循环的最后一次才进行交换。就是每次选一个最大或最小的值放到最前面。

时间： $O (n^{2})$

c++

void SelectSort(vector<int>& arr)
{
    int len = arr.size();
    for (int i = 0; i < len; i++)
    {
        int idx = i;

        for (int j = i; j < len; j++)
        {
            if (arr[idx] > arr[j])
            {
                idx = j;
            }
        }

        int temp = arr[i];
        arr[i] = arr[idx];
        arr[idx] = temp;
    }
}

python

def select_sort(lst):
    l = len(lst)
    for i in range(l):
        idx = i
        for j in range(i, l):
            if lst[j] < lst[idx]:
                idx = j
        # print(lst)
        lst[i], lst[idx] = lst[idx], lst[i]

    return lst


lst = [8, 7, 3, 6, 5, 2, 4, 1, 7, 6]
print(select_sort(lst))

3 插入排序

维持一个已经排好序的子列表，位置一直在列表前部，然后逐步扩大到这个子列表直到全表，例如抓牌。

时间： $O (n^{2})$

c++

void InsertSort(vector<int>& arr)
{
    int len = arr.size();
    for (int i = 1; i < len; i++)
    {
        for (int j = i; j > 0; j--)
        {
            if (arr[j] < arr[j - 1])
            {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
            else
                break;
        }
    }
}

python

def insert_sort(lst):
    l = len(lst)
    for i in range(1, l):
        for j in range(i, 0, -1):
            if lst[j] < lst[j - 1]:
                lst[j], lst[j - 1] = lst[j - 1], lst[j]
            else:
                break
        print(lst)
    return lst


lst = [8, 7, 3, 6, 5, 2, 4, 1, 7, 6]
print(insert_sort(lst))

4 希尔排序

因为列表越有序，插入排序比对次数越少，所以希尔排序就是分块的插入排序。希尔排序需要选定一个增量序列，间隔一般为 n / 2，例：选 1,3,5 项或 1,4,7 项。（不稳定）

然后第一趟 5 - 排序：每次以 5 为间隔做插入排序。

然后第二趟 3 - 排序：每次以 3 为间隔做插入排序。

然后第三趟 1 - 排序：每次以 1 为间隔做插入排序。

所有序列中最坏的情况： $O (n^{2})$

Hibbard 增量序列：

取法为 2^k - 1：{1, 3, 7, 15, 31, 63, 127, … }

时间： $O (n^{\frac{3}{2}})$

模拟平均结果【无人能证明】： $O (n^{\frac{5}{4}})$

Sedgewick 增量序列：

时间： $O (n^{\frac{4}{3}})$

模拟平均结果【猜测结果】： $O (n^{\frac{7}{6}})$

c++

void ShellSort(vector<int>& arr)
{
    int len = arr.size();
    for (int inc = len / 2; inc > 0; inc /= 2)
    {
        // 插入排序
        for (int i = inc; i < len; i++)
        {
            int key = arr[i];
            int j;
            for (j = i; j >= inc && key < arr[j - inc]; j -= inc)
                arr[j] = arr[j - inc];
            arr[j] = key;
        }
        // 每一趟的结果
        //for (int i = 0; i < arr.size(); i++)
        //	cout << arr[i] << " ";
        //cout << endl;
    }
}

python

def shell_sort(lst):
    l = len(lst)
    steps = []
    n = 1

    nxt = 2 ** n - 1
    while nxt < l:
        steps.append(nxt)
        n += 1
        nxt = 2 ** n - 1
    steps.reverse()

    for step in steps:
        for i in range(step, l):
            key = lst[i]
            j = i
            while j >= step and key < lst[j - step]:
                lst[j] = lst[j - step]
                j -= step
            lst[j] = key
        # print(lst)
        step //= 2

    return lst


lst = [8, 7, 3, 6, 5, 2, 4, 1, 7, 6]
print(shell_sort(lst))

5 归并排序

递归算法，将数据表持续分裂成两半，对两半分别进行归并排序。（稳定）

时间分裂： $O (l o g n)$ ，归并： $O (n)$ ，总： $O (n l o g n)$ ，会牺牲空间

c++

void Merge(vector<int>& nums, int left, int mid, int right) {
    int left_size = mid - left + 1;
    int right_size = right - mid;

    vector<int> left_nums(left_size);
    vector<int> right_nums(right_size);

    for (int i = 0; i < left_size; i++) {
        left_nums[i] = nums[left + i];
    }

    for (int j = 0; j < right_size; j++) {
        right_nums[j] = nums[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;
    while (i < left_size && j < right_size) {
        if (left_nums[i] <= right_nums[j]) {
            nums[k] = left_nums[i];
            i++;
        }
        else {
            nums[k] = right_nums[j];
            j++;
        }
        k++;
    }

    while (i < left_size) {
        nums[k] = left_nums[i];
        i++;
        k++;
    }

    while (j < right_size) {
        nums[k] = right_nums[j];
        j++;
        k++;
    }
}

void MergeSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        MergeSort(nums, left, mid);
        MergeSort(nums, mid + 1, right);

        Merge(nums, left, mid, right);
    }
}

python

# 创建新列表
def merge(lst1, lst2, lst):
    lp = 0
    rp = 0
    while lp + rp < len(lst):
        print(lp)
        if rp == len(lst2) or (lp < len(lst1) and lst1[lp] < lst2[rp]):
            lst[lp + rp] = lst1[lp]
            lp += 1
        else:
            lst[lp + rp] = lst2[rp]
            rp += 1

def merge_sort(lst):
    lens = len(lst)
    if lens < 2:
        return

    mid = lens // 2

    lst1 = lst[:mid]
    lst2 = lst[mid:]

    merge_sort(lst1)
    merge_sort(lst2)
    merge(lst1, lst2, lst)
    return lst


lst = [8, 7, 3, 6, 5, 2, 4, 1, 7, 6]
print(merge_sort(lst))

6 快速排序

递归算法，依据一个” 中值” 数据项把数据表分为两半：小于中值的一半和大于中值的一半，然后再分别进行快速排序。（不稳定）

时间总能分裂： $O (l o g n)$ ，移动： $O (n)$ ，总： $O (n l o g n)$

若中值偏离中部，时间： $O (n^{2})$ ，因为递归会导致其不如冒泡。

c++

void QuickSort(vector<int>& arr, int left, int right)
{
    if (left >= right)
    {
        return;
    }

    int key = arr[left];
    int lp = left;
    int rp = right;
    while (lp < rp)
    {
        while (lp < rp && arr[rp] >= key)
        {
            rp--;
        }
        while (lp < rp && arr[lp] <= key)
        {
            lp++;
        }
        if (lp < rp)
        {
            swap(arr[lp], arr[rp]);
        }
    }
    swap(arr[lp], arr[left]);
    QuickSort(arr, left, lp - 1);
    QuickSort(arr, rp + 1, right);
}

python

# 三数取中法
def find_mid_value_index(lst, left, right):
    mid = (left + right) // 2

    left_value = lst[left]
    mid_value = lst[mid]
    right_value = lst[right]

    if left_value <= mid_value <= right_value:
        return mid
    elif left_value <= right_value <= mid_value:
        return right
    elif mid_value <= left_value <= right_value:
        return left
    elif mid_value <= right_value <= left_value:
        return right
    elif right_value <= left_value <= mid_value:
        return left
    elif right_value <= mid_value <= left_value:
        return mid


def fast_sort(lst, left, right):
    if left >= right:
        return

    idx = find_mid_value_index(lst, left, right)
    lst[idx], lst[left] = lst[left], lst[idx]

    key = lst[left]
    lp = left
    rp = right
    while lp < rp:
        # 必须先移动rp，否则若不采用三数取中法会出错，测试案例[4,6,6]
        while lp < rp and lst[rp] >= key:
            rp -= 1
        while lp < rp and lst[lp] <= key:
            lp += 1
        if lp < rp:
            lst[lp], lst[rp] = lst[rp], lst[lp]
    lst[left], lst[lp] = lst[lp], lst[left]
    fast_sort(lst, left, lp - 1)
    fast_sort(lst, rp + 1, right)
    return lst

lst = [8, 7, 3, 6, 5, 2, 4, 1, 7, 6]
print(fast_sort(lst, 0, len(lst) - 1))

*7 堆排序

二叉堆的排序。

时间： $O (n l o g n)$

*8 桶排序

先遍历一遍数据，找到最小和最大值，然后将其等分成多个桶，然后再遍历一遍，将数据放入对应的桶中，之后对桶做单独排序。（稳定）

桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

时间： $O (n^{2})$

空间： $O (n * k)$

*9 基数排序

c++

...

10 计数排序

找出待排序数组中的最大值 maxVal 和最小值 minVal。

创建一个长度为 maxVal - minVal + 1 的计数数组 countArray，用于统计每个元素的出现次数。

遍历待排序数组，统计每个元素出现的次数并存储到 countArray 中。

计算每个元素在排序后的数组中的起始位置（前缀和），修改 countArray 使其表示元素应该放置的位置。

将 countArray 的对应的值依次赋回给原数组。

时间： $O (n + k)$

空间： $O (n + k)$

c++

void CountSort(vector<int>& arr)
{
    int len = arr.size();
    int maxVal = arr[0];
    int minVal = arr[0];
    for (int i = 1; i < arr.size(); i++)
    {
        if (arr[i] > maxVal)
        {
            maxVal = arr[i];
        }
        if (arr[i] < minVal)
        {
            minVal = arr[i];
        }
    }

    vector<int> countArray(maxVal - minVal + 1, 0);
    for (int i = 0; i < arr.size(); i++)
    {
        countArray[arr[i] - minVal]++;
    }

    int p = 0;

    for (int i = 0; i < countArray.size(); i++)
    {
        for (int j = 0; j < countArray[i]; j++)
        {
            arr[p++] = i + minVal;
        }
    }
}

二、递归与分治

1 递归

1.1 Fibonacci 数列

斐波那契数列_百度百科 (baidu.com)

对于斐波那契数列，可以按题意直接递归，也可以将递归结果存起来，进行递推。

c++

#include<iostream>
using namespace std;

// 递归算法
int fibonacci_back(int n) {
	if (n <= 1) return 1;
	return fibonacci_back(n - 1) + fibonacci_back(n - 2);

}
// 递推算法
int fibonacci_front(int n) {
	int f[2] = { 1, 1 };
	if (n < 2) return f[n];
	for (int i = 2; i <= n; i++)
	{
		int temp = f[0] + f[1];
		f[0] = f[1];
		f[1] = temp;
	}
	return f[1];
}

void main() {
	int n = 15;
	for (int i = 0; i <= n; i++)
	{
		cout << "递归" << i << "：" << fibonacci_back(i) << endl;
		cout << "递推" << i << "：" << fibonacci_front(i) << endl;
	}
}

1.2 集合全排列问题

对集合的元素进行排列。

c++

// 产生元素k到m的全排列，作为前k到1个元素的后缀
void Perm(int list[], int k, int m, int& res)
{
	// 构成一次全排列输出结果
	if (k == m)
	{
		for (int i = 0; i <= m; i++)
			cout << list[i] << " ";
		cout << endl;
		res++;
	}
	else
	{
		// 在数组list中，产生元素k到m的全排列
		for (int j = k; j <= m; j++)
		{
			swap(list[k], list[j]);
			Perm(list, k + 1, m, res);
			swap(list[k], list[j]);
		}
	}
}

void main() {
	int list[len];
	int res = 0;
	for (int i = 0; i < len; i++)
	{
		list[i] = i + 1;
	}
	Perm(list, 0, 3, res);
    // 输出排列的个数
	cout << res << endl;
}

1.3 整数划分问题

把一个正整数划分成任意个整数相加。记正整数 n，m 是它的划分，所以可以有如下情况：

f(1, m) = 1, m >= 1：无论 m 为几，n 只能分成 1

f(n, 1) = 1, n >= 1：无论 n 为几，只有一种划分，就是 n 个 1

f(n, m) = f(n, n), m >= n：m 比 n 大时，n 也分不出 m，所以可以化简成 m = n

f(n, n) = 1 + f(n, n - 1)：当二者相等时，可以向下划分，例如 6=5+1，5=1+4 等

f(n, m) = f(n, m - 1) + f(n - m, m )，n > m > 1：由此划分成两数之和后继续划分。例如：f(6,4) = f(6,3) + f(2, 4)，意思是 6=4+2，然后 4 和 2 可以递归向下分。

c++

int split(int n, int m)
{
	if (n == 1 || m == 1) return 1;
	else if (n < m) return split(n, n);
	else if (n == m) return split(n, n - 1) + 1;
	else return split(n, m - 1) + split(n - m, m);
}

2 分治

2.1 分治基础

分治步骤：

分解：将问题分解成若干个与原问题形式相同的相互独立的子问题。

解决：直接解决容易解决的小问题，否则递归地解决各个子问题。

合并：将各个子问题的解合并为原问题的解。

适用场景：

问题可以被分解，且各个子问题是独立的。

问题缩小到一定程度可以被容易解决

子问题的解可以合并为该问题的解。

c++

// 设计伪代码
Divide_and_Conquer(P)
{
    if( |P| <= n0 ) return adhoc(P);
    // divide P into smaller substances P1,P2, ... ,Pk;
    for(int i = 0;i <= k;k++)
        yi = Divide_and_Conquer(Pi); // 递归解决Pi问题
    return merge(y1,y2, ... , yk); // 合并子问题
}

2.2 二分查找

c++

// n是数组长度
template<class Type>
int BinarySearch(Type arr[], const Type& res, int len)
{
	int lp = 0;
	int rp = len - 1;
	while (lp <= rp)
	{
		int mid = (lp + rp) / 2;
		if (res == arr[mid]) return mid;
		else if (res > arr[mid]) lp = mid + 1;
		else rp = mid - 1;
	}
	return -1;
}

*2.3 循环赛日程表

设有 n 个选手进行循环比赛，其中 n = pow(2,k)，要求每名选手要与其他 n-1 名选手都赛一次，每名选手每天比赛一次，循环赛共进行 n-1 天，要求每天没有选手轮空。

输入：k

输出：表格形式的比赛安排表

c++

class Solution {
private:
	int len = 100;
public:
	vector<vector<int>> arr;

	Solution() {
		arr.resize(len, vector<int>(len));
		for (int i = 0; i < len; i++) {
			arr[i].resize(len);
		}
	}

	void Copy(int tox, int toy, int fromx, int fromy, int r) {
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < r; j++) {
				arr[tox + i][toy + j] = arr[fromx + i][fromy + j];
			}
		}
	}

	void Table(int k) {
		int i, r;
		int n = 1 << k;

		for (int i = 0; i < n; i++)
			arr[0][i] = i + 1;

		for (r = 1; r < n; r <<= 1)
			for (int i = 0; i < n; i += 2 * r) {
				Copy(r, r + i, 0, i, r);
				Copy(r, i, 0, r + i, r);
			}
	}

	void Print(int k) {
		for (int i = 0; i < k; i++) {
			for (int j = 0; j < k; j++) {
				cout << arr[i][j] << " ";
			}
			cout << endl;
		}
	}
};

*2.4 棋盘覆盖问题

算法分析与设计：棋盘覆盖问题（分治法）_算法设计与分析棋盘覆盖问题_SongXJ— 的博客 - CSDN 博客

*2.5 选择问题

在数组中找到第 k 小的元素。

思路：快速排序。

c++

class Solution {
private:
	vector<int> arr;
public:
	Solution(vector<int> arr) {
		this->arr = arr;
	}

	int select(int left, int right, int k) {
		// 找到了第k小的元素
		if (left >= right) return arr[left];
		int lp = left;
		int rp = right + 1;
		// 把最左边的元素作为分界数据
		int p = arr[lp];
		// 把左侧>=p的元素和右侧<=p的元素交换
		while (true) {
			// 左侧>=p的元素
			do {
				lp++;
			} while (arr[lp] < p);
			// 右侧<=p的元素
			do {
				rp--;
			} while (arr[rp] > p);
			if (lp >= rp) break; // 没有发现交换对象
			swap(arr[lp], arr[rp]);
		}
		// 快速排序算法描述中的nleft = rp - left
		if (rp - left + 1 == k) return p;
		arr[left] = arr[rp]; // 把p与arr[rp]交换
		arr[rp] = p; // 结点rp处划分左右子集
		if (rp - left + 1 < k) return select(rp + 1, right, k - (rp - left + 1)); // 在右子集中查找
		else return select(left, rp - 1, k); // 在左子集中查找
	}
};

*2.6 输油管道问题

【算法】输油管道问题_算法实现最优的输油计划 - CSDN 博客

2.7 半数集问题

给定一个自然数 n 给定一个自然数 n，由 n 开始可以依次产生半数集 set (n) 中的数如下：

n ∈ set(n)；

在 n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；

按此规则进行处理，直到不能再添加自然数为止。

例如，set (6) = {6,16,26,126,36,136}。半数集 set (6) 中有 6 个元素。

注意半数集是多重集。

对于给定的自然数 n，计算半数集 set (n) 中的元素个数。

c++

class Solution {
private:
	vector<int> temp;
public:
	Solution() : temp(1000, 0) {}
	// 普通分治
	int comp(int n)
	{
		int res = 1;
		if (n > 1)
			for (int i = 1; i <= n / 2; i++)
				res += comp(i);
		return res;
	}

	// 记忆化，添加数组保存结果，防止重复搜索
	int MemoryComp(int n)
	{
		int res = 1;
		if (temp[n] > 0) return n;
		if (n > 1)
			for (int i = 1; i <= n / 2; i++)
				res += comp(i);
		temp[n] = res;
		return res;
	}
};

2.8 整数因子分解

大于 1 的正整数 n 可以分解成：n=x1 * x2 * ... * xm

例如 12 可以分成：12=12、12=6 x 2、12=3 x 4、12=3 x 2 x 2 共 4 种。

c++

class Solution {
public:
	void slove(int n, int& res)
	{
		if (n == 1) res++;
		else for (int i = 2; i <= n; i++)
			if (n % i == 0) slove(n / i, res);
	}
};

*2.9 取余运算

输入三个正整数 a，p，k，求 a^p % k

分治法 —— 取余运算 (快速幂)-CSDN 博客

== 上次学到这 ==

三、动态规划

1 动态规划基础

常用于求解具有某种最优性质的问题。

步骤：

找出最优解的性质，并刻画其结构特征

递归地定义最优解（写出动态规划方程）

以自底向上的方式计算出最优值

根据计算最优值时得到的信息，构造一个最优解

特征：

最优子结构：当问题的最优解包含其子问题的最优解时，称该问题具有最优子结构性质。

重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。

2 矩阵连乘积问题

动态规划之矩阵连乘问题详细解读（思路解读 + 填表 + 代码）_矩阵连乘问题的动态规划算法 - CSDN 博客

c++

// 普通动态规划算法
#include<iostream>
using namespace std;

const int N = 100;
int A[N];//矩阵规模
int m[N][N];//最优解
int s[N][N];
void MatrixChain(int n)
{
	int r, i, j, k;
	for (i = 0; i <= n; i++)//初始化对角线
	{
		m[i][i] = 0;
	}
	for (r = 2; r <= n; r++)//r个矩阵连乘
	{
		for (i = 1; i <= n - r + 1; i++)//r个矩阵的r-1个空隙中依次测试最优点
		{
			j = i + r - 1;
			m[i][j] = m[i][i] + m[i + 1][j] + A[i - 1] * A[i] * A[j];
			s[i][j] = i;
			for (k = i + 1; k < j; k++)//变换分隔位置，逐一测试
			{
				int t = m[i][k] + m[k + 1][j] + A[i - 1] * A[k] * A[j];
				if (t < m[i][j])//如果变换后的位置更优，则替换原来的分隔方法。
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}

// 输出括号
void print(int i, int j)
{
	if (i == j)
	{
		cout << "A[" << i << "]";
		return;
	}
	cout << "(";
	print(i, s[i][j]);
	print(s[i][j] + 1, j);//递归1到s[1][j]
	cout << ")";
}

int main()
{
	int n;//n个矩阵
	cin >> n;
	int i, j;
	for (i = 0; i <= n; i++)
	{
		cin >> A[i];
	}
	MatrixChain(n);
	cout << "最佳添加括号的方式为：";
	print(1, n);
	cout << "\n最小计算量的值为：" << m[1][n] << endl;
	return 0;
}

c++

** // 递归算法
int Recurve(int i, int j)
{
	if (i == j) return 0;
	int u = Recurve(i, i) + Recurve(i + 1, j) + p[i - 1] * p[i] * p[j];
	s[i][j] = i;
	for (int k = i + 1; k < j; k++)
	{
		int t = Recurve(i, k) + Recurve(k + 1, j) + p[i - 1] * p[i] * p[j];
	}
	m[i][j] = u;
	return u;
}

c++

** // 备忘录方式
int LookupChain(int i, int j)
{
	if (m[i][j] > 0) return m[i][j];
	if (i == j) return 0;
	int u = LookupChain(i, i) + LookupChain(i + 1, j) + p[i - 1] * p[i] * p[j];
	s[i][j] = i;
	for (int k = i + 1; k < j; k++)
	{
		int t = LookupChain(i, i) + LookupChain(i + 1, j) + p[i - 1] * p[i] * p[j];
		if (t < u)
		{
			u = t;
			s[i][j] = k;
		}
	}
	m[i][j] = u;
	return u;
}

3 最长公共子序列

最长公共子序列 (LCS) 详解 + 例题模板（全）-CSDN 博客

4 最大字段和

最大子段和问题（3 种方法）-CSDN 博客

5 0-1 背包问题

【0-1 背包问题】详细解析 + 图解 + 详细代码_01 背包问题 - CSDN 博客

【动态规划】01 背包问题（通俗易懂，超基础讲解）_背包问题动态规划表 - CSDN 博客

6 最长单调递增子序列

最长单调递增子序列 —— 动态规划算法 - CSDN 博客

7 数字三角形问题

数字三角形问题（动态规划）_已知数字三角形如下所示。请利用动态规划技术寻找一条从顶部数字出发，到达最底层 - CSDN 博客

8 补充题目

ZOJ1027-Human Gene Functions

ZOJ1074-To the Max

ZOJ1093-Monkey and Banana

ZOJ1107-FatMouse and Cheese

ZOJ1108-FatMouse’s Speed

ZOJ1147-Formatting Text

ZOJ1149-Dividing

ZOJ1163-The Staircases

ZOJ1183-Scheduling Lectures

ZOJ1196-Fast Food

ZOJ1206-Win the Bonus

ZOJ1227-Free Candies

ZOJ1234-Chopsticks

2376. 统计特殊整数 - 力扣（LeetCode）

四、贪心算法

1 贪心算法基础

每次选择问题的最优解，最后得到整个问题的最优解。

求解过程：

候选集合 A：为了构造问题的解决方案，有一个候选集合 A 作为问题的可能解，即问题的最终解均取自于候选集合 A

解集合 S：随着贪心选择的进行，解集合 S 不断扩展，直到构成满足问题的完整解。

解决函数 solution：检查解集合 S 是否构成问题的完整解。

选择函数 select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。

可行函数 feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。

c++

Greedy(A)
{
    S = {};  // 初始解集合为空集 
    while(not solution(S))  // 集合S没有构成一个问题的解
    {
        x = select(A);  // 在候选集合A中做贪心选择
        if feasible(S, x)  // 判断集合S中加入x后的解是否可行
        {
            S = S + {x};
            A = A - {x};
        }
    }
}

2 活动安排问题

算法笔记（0002） - 【贪心算法】活动安排问题_【贪心】最优活动安排 - CSDN 博客

3 背包问题

背包问题贪心算法求解_贪心算法解决背包问题 - CSDN 博客

4 最优装载问题

贪心算法 — 最优装载问题_装载问题贪心算法 - CSDN 博客

5 单源最短路径

【算法】单源最短路径 ——dijkstra 算法_单源最短路径算法 - CSDN 博客

6 最小生成树

最小生成树详解 (模板 + 例题)-CSDN 博客

7 删数问题

算法：（贪心算法）— 删数问题_深入浅出学算法 052 - 删数问题 - CSDN 博客

8 多处最优服务次序问题

算法设计与分析 —— 多处最优服务次序问题多出最优服务次序问题客院载论的博客 - CSDN 博客

9 补充

ZOJ1012-Mainframe

ZOJ1025-Wooden Sticks

ZOJ1029-Moving Tables

ZOJ1076-Gene Assembly

ZOJ1161-Gone Fishing

ZOJ1171-Sorting the Photos

ZOJ2109-FatMouse’ Trade

五、回溯算法

1 回溯算法基础

有许多问题，当需要找到它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。

回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种以深度优先的方式系统地搜索问题的解的方法称为回溯法。

空间树相关概念：

活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点

扩展结点：当前正在生成其儿子结点的活结点叫扩展结点（正扩展的结点）

死结点：不再进一步扩展或者其儿子结点已全部生成的结点就是死结点

*（似乎能回溯的都能动态规划）

回溯和递归的区别（简述）_递归和回溯的区别 - CSDN 博客

【算法思想：回溯法】回溯算法入门级详解_回溯法算法_Allen Chou 的博客 - CSDN 博客

2 装载问题

算法设计 - 回溯法 —— 装载问题_用回溯法编写一个递归程序解决如下装载问题：有 n 个集装箱要装上 2 艘载重分别为 - CSDN 博客

3 0-1 背包问题

回溯法 ——0-1 背包问题回溯法求解 0-1 背包问题 - 小透明 - 的博客 - CSDN 博客

4 图的 m 着色问题

图的 m 着色问题回溯法求解_图的 m 着色问题是子集树还是排列树 - CSDN 博客

5 n 皇后问题

回溯算法之 N 皇后问题_n 皇后问题回溯法_nepu_bin 的博客 - CSDN 博客

6 旅行商问题

旅行商问题回溯法求解 - CSDN 博客

7 流水作业调度问题

回溯法之流水作业调度问题_回溯法作业调度问题输入什么信息 - CSDN 博客

8 子集和问题

回溯法 —— 求解子集和问题_回溯法求解子集和问题 - CSDN 博客

9 补充

ZOJ1145-Dreisam Equations

ZOJ1157-A Plug for UNIX

ZOJ1166-Anagram Checker

ZOJ1213-Lumber Cutting

六、分支限界算法

1 分支限界基础

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

分支限界算法总结_分支限界法实验总结 - CSDN 博客

2 单源最短路径问题

分支限界法之单源最短路径_分支限界法单源最短路径 - CSDN 博客

3 装载问题

装载问题 - 分支限界法 (队列式分支限界法，优先队列式分支限界法)_使用先队列式分支限界法求解最优装载问题:n=3,c1=c2=50,w={10,40,40}, 请：实现 - CSDN 博客

4 0-1 背包问题

0-1 背包问题 - 分支限界法 (优先队列分支限界法)_分支界限法的 0-1 背包问题 - CSDN 博客

5 旅行商问题

分支限界法求解旅行商问题 (TSP) 旅行商问题分支限界法飘飘飄飘的博客 - CSDN 博客

6 ZOJ1136-Multiple

ZOJ 1136 Multiple（分支界限算法）_zoj1136-multiple-CSDN 博客

7 回溯算法与分支界限算法的比较

方法	回溯法	分支限界法
解空间树的搜索方式	深度优先搜索	广度优先搜索
存储结点的数据结构	搜索过程中动态产生问题的解空间	队列、优先队列
结点存储特性	只保存从根节点到当前扩展结点的路径	每个结点只有一次成为活结点的机会
应用范围	能够找出满足约束条件的所有解	找出满足约束条件的一个解或特定意义下的最优解

七、图的搜索算法

1 图的深度优先搜索

图的遍历（深度优先搜索）_深度优先遍历 - CSDN 博客

2 图的深度优先搜索例题

ZOJ1002-Fire Net

ZOJ1008-Gnome Tetravex

ZOJ1047-Image Perimeters

ZOJ1084-Channel Allocation

ZOJ1142-Maze

ZOJ1190-Optimal Programs

ZOJ1191-The Die Is Case

ZOJ1204-Additive Equations

ZOJ1245-Triangles

ZOJ2100-Seeding

3 图的广度优先搜索

图的广度优先搜索详解 - CSDN 博客

4 图的广度优先搜索例题

ZOJ1079-Robotic Jigsaw

ZOJ1085-Alien Security

ZOJ1103-Hike on a Graph

ZOJ1148-The Game

ZOJ1217-Eight

ZOJ1091-Knight Moves

5 A*

Introduction to the A* Algorithm (redblobgames.com)

八、图论

1 网络流问题

1.1 网络流基础

【网络流优化 (一)】网络流问题综述 - 知乎 (zhihu.com)

流与割的概念：网络流 - 割的概念以及定理_割网络流 - CSDN 博客

剩余网络和增广路：网络流 - 最大流（残量网络、增广路经、Edmonds-Karp 算法、Dinic 算法、最小割边集）-CSDN 博客

1.2 Ford-Fulkerson 算法

最大流问题 ——Ford Fulkerson 算法_fordfulkerson 算法求最大流 - CSDN 博客

1.3 Edmonds-Karp 算法

最大流算法：Edmond-Karp 算法 ——Ford-Fulkerson 算法 ——Dinic 算法 - CSDN 博客

ZOJ1734-Power Network——Edmonds-Karp 算法

1.4 ISAP 算法

最大流算法 - ISAP - permui - 博客园 (cnblogs.com)

ZOJ1734-Power Network——ISAP 算法

1.5 Dinic 算法

8 分钟看懂最大流算法 Dinic - 步步拆解 - 知乎 (zhihu.com)

Dinic 算法详解及实现 - 0giant - 博客园 (cnblogs.com)

ZOJ1734-Power Network——Dinic 算法

1.6 最小费用流 ——SPFA 算法

最短路径问题 —-SPFA 算法详解_1342:【例 4-1】最短路径问题 spfa-CSDN 博客

ZOJ2404-Going Home——SPFA 算法

2 二分图匹配问题

2.1 匹配问题

经典算法问题 —— 稳定匹配（Stable Matching） - 知乎 (zhihu.com)

2.2 二分图最大匹配 —— 匈牙利算法

算法学习笔记 (5)：匈牙利算法 - 知乎 (zhihu.com)

ZOJ1137-Girls and Boys

ZOJ1140-Courses—— 匈牙利算法

PJU1274-The Perfect Stall—— 匈牙利算法

2.3 Hopcroft-Karp 算法

二分图最大匹配之 Hopcroft-Karp 算法详解 - CSDN 博客

ZOJ1140-Courses——Hopcroft-Karp 算法

PJU1247-The Perfect Stall——Hopcroft-Karp 算法

2.4 二分图最佳匹配 ——Kuhn Munkres 算法

KM 算法详解 - CSDN 博客

二分图匹配 —-Munkres 算法 - 知乎 (zhihu.com)

ZOJ2404-Going Home——Kuhn Munkres 算法

九、数论

1 扩展欧几里得算法

扩展欧几里得算法详解 - CSDN 博客

2 欧拉函数

欧拉函数 φ(n) 的计算及欧拉定理 - 知乎 (zhihu.com)

3 中国剩余定理

中国剩余定理 (超详细讲解)-CSDN 博客

4 一元线性同余方程组

【数论】同余（四）：一元线性同余方程组（两两相消、中国剩余定理）-CSDN 博客

5 HDU1572-X 问题

HDU-1573-X 问题（中国剩余定理 + LCM）_lcm 中国剩余定理 - CSDN 博客

6 补充

PJU2115-C Looooops

ZOJ1906-Relatives

PJU2480-Longge’s Problem

PJU3696-The Luckiest Number

ZOJ1160-Biorhythms

PJU2891-Strange Way to Express Integers

十、组合数学

1 母函数

生成函数 (母函数)—— 目前最全的讲解 - CSDN 博客

普通型母函数：普通型母函数和指数型母函数 - CSDN 博客

指数型母函数：【组合数学】指数型母函数应用 (多重集排列问题 | 不同球放在不同盒子里 | 奇 / 偶数序列的指数生成函数推导)_组合数学指数型母函数例题 - CSDN 博客

Stirling 数：【组合数学】Stirling 数 - 知乎 (zhihu.com)

Catalan 数：浅谈 Catalan 数（一） - 知乎 (zhihu.com)

2 母函数例题

HDU2082 - 找单词

HDU1521 - 排列组合

HDU2065-“红色病毒” 问题

HDU3625-Examining the Rooms

POJ2084-Game of Connections

3 容斥原理和鸽巢原理

容斥原理：容斥原理详解 - CSDN 博客

错排问题：【组合数学】错排问题 (递推公式 | 通项公式 | 推导过程) ★_错排问题递推公式 - CSDN 博客

鸽巢原理：鸽巢原理详解（口水化解释）-CSDN 博客

4 容斥原理和鸽巢原理例题

HDU2048 - 神、上帝以及老天爷

PJU2356-Find a Multiple

ZOJ2836-Number Puzzle

十一、其他

1 快速幂

50. Pow (x, n) - 力扣（LeetCode）

利用二分思想，首先判断 n 的正负，正的直接递归，负的先取正，然后最后结果用 1 除以即可。然后进行递归，当 n 为 0 表示走到尽头，返回 1。否则利用二分思想，可以将数一直开方。由递推可知，当一个 n 是偶数时，可以直接相乘，如果 n 是奇数，就在此基础上再乘一个 x。比如 x ** 4 变成 x ** 9，此时 n 是 9，向下二分得到是 (x ** 4 ) * (x ** 4 ) * x，因此奇数要多乘一个 x。

python

# 递归法
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def pow(n):
            if n == 0: return 1
            y = pow(n // 2) 
            return y * y if (n & 1) == 0 else y * y * x
    
        return pow(n) if n >= 0 else 1 / pow(-n)