算法基础
目录
- 目录
- 0. 简介
- 1. 第一周 枚举
- 2. 第二周 递归(一)
- 3. 第三周 递归(二)
- 4. 第四周 二分算法
- 5. 第五周 分治
- 6. 第六周 动态规划(一)
- 7. 第七周 动态规划(二)
- 8. 第八周 深度优先搜索(一)
- 9. 第九周 深度优先搜索(二)
- 10. 第十周 广度优先搜索
- 11. 第十一周 贪心算法
0. 简介
- 课程来源于北大郭炜老师的MOOC，在中国大学MOOC平台上有网课，课程名为程序设计与算法(二)算法基础，第九次开课，课程有附带的习题，该博客记录了我的随堂笔记，课件在MOOC网站有
- 2022/11/19: openjudge上测验题目都做完了，平台上还有一个考试没有做，可以等到2023/1/14那天把考试题目做一下
- 课件的代码和测试的代码都在c++learning文件夹里有留存
1. 第一周 枚举
1.1. 完美立方
- 枚举: 基于逐个尝试答案的一种问题求解策略
- 例如: 求小于N的最小素数
- 完美立方:
- 解题思路:
1.2. 生理周期
- 题干:
- 解题思路:
1.3. 称硬币
- 题干:
- 解题思路
1.4. 熄灯问题
- 题干:
- 解题思路:
局部的思想，化繁为简
- 可以用0-31的十进制数来表示第一列的数据，因为其二进制数刚好对应开关的状态
2. 第二周 递归(一)
2.1. 求阶乘
- 递归的基本概念: 一个函数调用其自身就是递归
- 递归和普通函数调用一样是通过栈实现
- 递归的作用
- 替代多重循环
- 解决本来就是递归形式定义的问题
- 将问题分解为规模更小的问题进行求解: 比如n！变成n * (n-1)
2.2. 汉诺塔问题
- 任务描述:
- 解决思路: 把盘子从A移动到C的过程分解为三个小问题，分别是移动n-1个盘子从A到B，然后移动1个盘子从A到C，最后移动n-1个盘子从B到C，这就是一个递归问题
- 递归的核心思想是将大问题分解为规模更小的问题，同时还要保证是从n变成n-1
- 代码实现:
2.3. n皇后问题
- 问题描述:
用递归代替多重循环，皇后的攻击范围是横竖斜
- 解决思路: 同样是从第1行开始逐个往后摆放，但是这里的n是未知数，所以循环的层数不确定，这个时候就可以用递归代替循环，构造一个函数，表示从第k行开始摆放棋子，然后在循环内部判断每一列的位置是否能摆放，就是一个穷举问题了
- 代码实现:
这个代码设计很巧妙的地方是，它会遍历所有的情况，只要是满足条件的就会输出，所以会返回所有可能的结果
2.4. 逆波兰表达式求值
- 问题描述:
- 输入输出例子:
- 解决思路: 一个数也可以看成一个逆波兰表达式，那么就可以直接用递归求解，实现过程中需要边输入边递归
- 代码实现:
3. 第三周 递归(二)
3.1. 表达式求值
- 问题描述:
- 解决思路: 先看看表达式递归的定义
即然把表达式的递归过程弄清楚了，那么只需要定义表达式、项、因子的函数即可
- 代码实现:
3.2. 上台阶问题
- 问题描述:
- 输入输出样例:
- 解决思路: 将n级台阶的走法看成n-1级台阶的走法+n-2级台阶的走法，分别代表在第一步走一阶还是两阶，这里需要设置边界条件来防止无限递归
- 代码实现:
3.3. 放苹果问题
- 问题描述:
- 解决思路: 又是计算方法的总数，那么和上台阶问题一样，用表达式来表示递归，分类讨论。假设i个苹果，k个盘子，如果k>i，那么等价于把i个苹果放到i个盘子里，因为一定有k-i个盘子空着；如果k<=i，那么又将问题分为有没有空盘子，如果有空盘子，那么至少有一个空盘子，表示为把i个苹果放到k-1个盘子里，如果没有空盘子，那么等价于把i-k个苹果放到k个盘子里
- 代码实现:
3.4. 算24问题
- 问题描述:
- 输入输出样例:
- 判断两个浮点数是否相等，用两个浮点数的差是否小于某个值
- 解决思路: 不论给了多少个数计算24，都需要首先计算出两个数的计算结果，这个计算过程可以是加减乘除任意，然后得到的结果再和剩下的n-1个数算24，这样就可以变成一个递归问题，边界条件是只剩一个数的时候是否是24
- 代码实现:
4. 第四周 二分算法
4.1. 程序或算法的时间复杂度
- 时间复杂度的定义:
重点是明白程序中固定的操作是什么
- 复杂度有平均复杂度和最坏复杂度两种，两者可能一致，也可能不一致，一般来说只要平均复杂度不太高，算法的效率就还可以
- 常见的时间复杂度:
4.2. 二分查找的原理和实现
- 首先可以看这么一个问题:
- 二分查找的实现: 时间复杂度是O(log(n))
- 查找比待查找数小的最大坐标的函数实现:
- 二分查找的问题前提是序列必须是递增或者递减的，即有序的
- 为了防止数据溢出，写中点的时候要这么写: int mid = L + (R - L) / 2
- 整型在转型的时候是向下取整
4.3. 二分法求方程的根
- 二分法求方程的根需要方程满足一定的条件，不是所有的方程都可以用二分法求根
- 问题描述及求解思路:
- 代码实现:
- 如果一个序列不是有序的，可以用排序算法对序列先进行排序然后二分查找
5. 第五周 分治
5.1. 归并排序
- 分治的基本概念:
- 分治的典型应用: 归并排序
- 归并排序的思路就是先分治，然后归并，代码实现如下：
- 归并排序的时间复杂度:
5.2. 快速排序
- 快速排序的思想:
- 代码实现:
- 快速排序的时间复杂度是O(nlog(n))，这是在运气不坏的情况下得出的结果(平均复杂度)，运气最坏的情况下时间复杂度为O($n^2$)(最坏复杂度)
5.3. 例题: 输出前m大的数
- 问题描述:
- 解决思路:
用分治的思想解决问题，先把前m个元素移到数组的最右边，然后在对这m个元素进行快排
- 具体解决方法:
- 时间复杂度计算:
5.4. 例题: 求排序的逆序数
- 问题描述:
- 解决思路:
分治一般都使用了递归
6. 第六周 动态规划(一)
6.1. 数字三角形
- 问题描述:
- 输入格式:
- 解题思路: 看成递归问题
- 递归程序代码实现:
- 虽然说在代码逻辑这一方面，递归算法没有问题，但是这个算法的时间复杂度太高，程序很容易超时:
- 之前的递归算法中存在过多的重复计算，如果能把每一步的计算结果保存起来，那么即可避免重复计算，算法的时间复杂度为O($n^2$)
- 记忆递归型动规程序:
用一个二维数组存储每一个结点的max值，那么读取到这个结点时，就可以直接获得数值，避免了重复计算
- 也可以用递推的思想解决问题，先把最后一行的结果计算出来，然后从下到上逐步计算，用一个双重循环解决
- 代码实现:
- 还可以对空间进行优化，因为下一层的数值在计算上一层的数值后就没有用了，那么完全不需要用一个二维数组存储maxsum，完全可以用一个一维数组存放。再进一步来说，连maxSum数组都可以不要，直接用D的第n行替代maxSum
- 空间优化后的代码实现:
6.2. 动态规划解题的一般思路
- 递归到动规的一般转化方法:
- 动规解题的一般思路:
- 第一步: 将原问题分解为子问题
- 第二步: 确定状态
- 第三步: 确定一些初始状态的值
- 第四步: 确定状态转移方程
- 能用动规解决的问题的特点:
6.3. 最长上升子序列
- 问题描述:
- 输入输出格式:
- 解题思路:
- 找子问题:
- 确定状态:
- 找出状态转移方程:
- 代码实现:
- 动规的常用两种形式:
6.4. 最长公共子序列
- 问题描述:
- 输入输出样例:
- 解题思路:
重要的还是找到一个合适的子问题与状态
- 状态转移方程
- 证明一下这个递推公式是正确的:
- 代码实现:
6.5. 最佳加法表达式
- 问题描述:
- 解题思路:
7. 第七周 动态规划(二)
7.1. Help Jimmy
- 问题描述:
- 输入输出样例:
- 解题思路:
板子的顺序其实没有关系，重要的关注点是当前板子的左侧或右侧正下方的板子是哪个板子，然后计算出从每个板子的左侧或者右侧下降需要的最短时间，也就是说这里的状态指的是不同的板子
- 伪代码实现:
将下落点看成宽度为0的板子是一种很好的思路
- 时间复杂度:
7.2. 滑雪
- 问题描述:
- 输入输出样例:
- 解题思路:
这个题目递推的顺序很奇怪，如果按照二维数组的排序顺序来递推会出现问题，这里比较好的解决思路是把点按照高度排序，因为如果高度低的点值没求出来的话，高度高的点的值一定求不出来。然后这里排完序后有两种解决思路，一种是按顺序把每个点的值根据周围四个低的点求出，另一种思路是按照顺序每次更新周围四个点的值
7.3. 神奇的口袋
- 问题描述:
- 输入输出样例:
- 当然可以用枚举的方法暴力求解
- 也可以用递推的方法求解:
设计一个递推的函数，代表前k个物品凑w体积的方法个数，那么在新出现这个物品时有两个选择，即选或不选
- 动规解法:
用二维数组来表示状态
7.4. 0-1背包问题
- 问题描述:
- 解题思路: 和上一小节的思路类似，状态同样用二维数组表示，然后找出状态转移方程求解即可
可以用滚动数组的思想来优化空间，递推的过程是从右往左替换滚动数组的过程
7.5. 分蛋糕
- 问题描述:
- 输入输出样例:
- 解题思路:
由于这里存在高宽，所以状态需要用三维数组表示
- 递推公式:
8. 第八周 深度优先搜索(一)
8.1. 在图上寻找路径和遍历
- 问题描述:
- 利用这种策略，可能出现的情况:
- 深度优先搜索(Depth-First-Search)的定义:
- 刚才那个问题的伪代码实现:
- 如果要记录路径，代码实现:
8.2. 图的表示方法: 邻接矩阵和邻接表
- 邻接矩阵表示图:
- 邻接表表示图:
8.3. 城堡问题:
- 问题描述:
- 输入输出样例:
- 解题思路: 这种比较抽象的问题可以通过建模转换成相对简单的题目，把城堡的方块看成节点，然后如果两个方块连接，则连接这两个节点
求房间个数等价于求极大连通子图个数
- 代码实现:
8.4. 踩方格
- 问题描述:
- 解决思路: 用递归的思路解决问题，第一步的选择有三种，那么走n步的方案数等于这三种走法的方案和
- 代码实现:
9. 第九周 深度优先搜索(二)
9.1. 寻路问题
- 问题描述:
- 解题思路: 从城市1开始深度优先遍历整个图，找到能到达城市N的最优路线(在不超过开销情况下的最短路径)
但是这种方法会超时，所以我们需要对算法进行改进(剪枝)，最容易想到的方法是最优性剪枝，但是发现这种剪枝方法还是超时了
这种剪枝方法能保存中间计算结果，效果比之前的最优性剪枝要好
- 代码实现:
9.2. 生日蛋糕
- 下棋也是一个深度搜索的过程
- 问题描述:
蛋糕的高和半径是递减的
- 解题思路:
- 代码实现:
- 剪枝(剪枝在深度优先搜索中很重要)
10. 第十周 广度优先搜索
10.1. 抓住那头牛
- 问题描述:
- 解决思路:
第一种想法是用深度优先搜索解决问题，让农夫尝试所有的走法，不能走重，不能往下走了就回溯
第二种想法是用广度优先搜索的思路解决问题，对所有的节点进行分层，广搜的优点是确保可以找到最优解，但是因为拓展出来的节点比较多，且多数节点都需要保存，因此需要的存储空间较大，用队列保存节点
- 广搜算法:
光看文字可能有些晦涩难懂，下面有open表和close表变化的实例
- 代码实现
在了解广度优先搜索的概念后，代码实现的难点在于队列queue的使用，queue的实例化可以用queue<T>来实现，q.front()是取当前元素，q.push()是在队列尾部添加元素，q.pop()是删除头部元素
10.2. 迷宫问题
- 问题描述:
- 解决思路: 广搜
这里队列不能用STL的queue实现(因为要给出最短路径)，要自己写，可以用一维数组实现
其实就是记录了每个节点的父节点，在达到重点的时候可以一路返回过去得到路径
10.3. 鸣人和佐助
鸣人和佐助问题是迷宫问题的一个变种
- 问题描述:
- 解决思路:
由于每个位置的查克拉不同也会导致状态的不同，所以状态用三个参数表示，然后根据条件拓展节点
- 问题变种:
10.4. 八数码问题
- 问题描述:
- 解决思路:
用广度优先搜索来解决问题，优先拓展浅层节点，在逐渐深入
- 广度优先搜索的代码框架:
- 这个题目的关键点在于判重，状态数目大，如何存储才能较快判断一个状态是否重复
- 一些可能的编码方案:
- 继续优化问题的方法: 判定八数码问题是否有解
移动0的位置，不改变排列的奇偶性
- 代码实现(单向广搜，用set判重)
- 其余优化问题的方法: 双向广搜、针对本题的预处理、A*算法
- 广搜和深搜的比较:
11. 第十一周 贪心算法
11.1. 圣诞老人的礼物
- 问题描述:
- 样例输入输出:
第一行表示箱子总数和可携带的最大重量，其余行都表示箱子的信息，第一列是价值，第二列是重量
- 解决思路:
因为要携带尽可能价值高的糖果，所以可以把所有箱子的价值重量比算出来，然后排列，按顺序装糖果。这种方法就是贪心算法的思路
- 代码实现:
这里实现candy的结构体时，结构体里面重载了运算符<，operator是转换运算符，这样就可以直接调用sort对candies进行排序
- 证明这种方法是正确的:
- 贪心算法:
每一步行动总是按照某种指标选取最优的操作来进行
11.2. 电影节
- 问题描述:
- 样例输入输出:
- 解决思路:
- 证明贪心算法的正确性:
11.3. 分配畜栏
- 问题描述:
- 解决思路:
按照奶牛的开始挤奶时间来分配奶牛的畜栏，可以用队列存储最早结束的畜栏的时间
- 代码实现:
priority是优先队列，在优先队列中，优先级高的元素先出队列，并非按照先进先出的顺序
11.4. 放置雷达
- 问题描述:
- 解决思路
- 首先把题目问题转换一下:
- 接下来我们通过观察得到一个重要的结论，那就是如果一个雷达可以覆盖多个雷达，那么这个雷达可以在所覆盖雷达的最右边的起点
- 贪心算法实现步骤:
11.5. 钓鱼
- 问题描述:
- 解决思路:
Comments