最长上升子序列模型 | 动态规划
参考《算法竞赛进阶指南》、AcWing题库
895. 最长上升子序列
题目描述
给定一个长度为 NNN 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 NNN。
第二行包含 NNN 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤10001 \le N \le 10001≤N≤1000，
−109≤数列中的数≤109-10^9 \le 数列中的数 \le 10^9−109≤数列中的数≤109
输入样例：
1273 1 2 1 8 5 6
输出样例：
14
算法分析
贪心写法见 1010.拦截导弹
Solution
1234567891011121314151617181920#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 1010;int a[N], f[N];int main() { int n ; cin >&g ...
数字三角形模型 | 动态规划
参考《算法竞赛进阶指南》、AcWing题库
898. 数字三角形
题目描述
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
12345 7 3 8 8 1 0 2 7 4 44 5 2 6 5
输入格式
第一行包含整数 nnn，表示数字三角形的层数。
接下来 nnn 行，每行包含若干整数，其中第 iii 行表示数字三角形第 iii 层包含的整数。
输出格式
输出一个整数，表示最大的路径数字和。
数据范围
1≤n≤5001 \le n \le 5001≤n≤500,
−10000≤三角形中的整数≤10000-10000 \le 三角形中的整数 \le 10000−10000≤三角形中的整数≤10000
输入样例：
123456573 88 1 0 2 7 4 44 5 2 6 5
输出样例：
130
Solution
自上而下
123456789101112131415161718192021222 ...
由数据范围反推算法复杂度以及算法内容
作者： yxc, 2018-09-10 22:27:18 , 阅读 21650
一般 ACM 或者笔试题的时间限制是 1 秒或 2 秒。
在这种情况下，C++ 代码中的操作次数控制在 107∼10810^7 \sim 10^8107∼108 为最佳。
下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：
n≤30n \le 30n≤30, 指数级别, dfs + 剪枝，状态压缩 dp
n≤100n \le 100n≤100 => O(n3)O(n^3)O(n3)，floyd，dp，高斯消元
n≤1000n \le 1000n≤1000 => O(n2)O(n^2)O(n2)，O(n2logn)O(n^2logn)O(n2logn)，dp，二分，朴素版 Dijkstra、朴素版 Prim、Bellman-Ford
n≤10000n \le 10000n≤10000 => O(n∗n)O(n * \sqrt n)O(n∗n)，块状链表、分块、莫队
n≤100000n \le 100000n≤100000 => O(nlogn)O(nlogn)O(n ...
区间问题
区间合并
56. 合并区间
Difficulty: 中等
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start<sub style="display: inline;">i</sub>, end<sub style="display: inline;">i</sub>] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
123输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
123输入：intervals = [[1,4],[4,5]]输出：[[1,5]]解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 10<sup>4</ ...
方向数组的应用
54. 螺旋矩阵
Difficulty: 中等
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
12输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5]
示例 2：
12输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100
Solution
123456789101112131415161718192021class Solution {public: static const int N = 10; bool used[N][N] = {}; int dx[4] = {0, 1, 0, -1&# ...
N皇后
51. N 皇后
Difficulty: 困难
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
123输入：n = 4输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
12输入：n = 1输出：[["Q"]]
提示：
1 <= n <= 9
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
Solution
12345678910111213141516171819202122232425 ...
Hexo博客 | Hexo插入视频
Hexo搭建博客后，如果想在博客中分享视频，避免网站服务器带宽的限制，需要添加其他视频网站的外链播放器，具体该怎么操作呢？
Solution 1: hexo-tag-aplayer
hexo-tag-dplayer 是 DPlayer 播放器的 Hexo 标签插件。
因为版本维护者不再支持新版本的更新，有些 bug 没有解决，所以对于高版本的 Hexo 支持不友好，甚至安装阶段就会报错。所以，我不是很支持继续使用该方法。
ps. 想继续坚持使用该方法的，可以移步阅读 在 Hexo 搭建的博客中插入音乐或者视频。
Solution 2: 视频网站外链
Hexo 支持 iframe 的方式插入视频，所示我们可以把视频上传到哔哩哔哩、优酷、腾讯视频等，然后生成外链再拿来用。
大部分视频网站的外链播放器在视频开头都会加上 30 秒 - 2 分钟的广告，于是选择 B 站，无广告，无广告，无广告！
去 B 站获取视频外链
选择视频下方 “分享” 里的嵌入代码，而不是视频地址。否则进入 Hexo 博客后，网页会自动跳转到 bilibili 的视频页面，而不是自己的博客页面。
在文章中插入视频外 ...
Hexo博客 | 页面插入并展示PDF文档
hexo-pdf插件一键搞定，页面展示PDF
安装hexo-pdf插件
1npm install --save hexo-pdf
使用本地资源
使用本地资源，可以在 markdown 文件路径下创建一个同名文件夹，其内放 pdf 文件
例如：
在需要的文章添加如下语句：
1{% pdf mydocument.pdf %}
使用网络资源
12{% pdf pdf资源链接 %}{% pdf https://github.com/zgzhengSEU/Algorithm-Learning/blob/main/笔记/背包问题九讲V2.pdf %}
由于Github上传文档有容量限制，可以用OneDrive个人版来生成PDF文档直链
OneDrive
GoogleDrive + PoweredBy.Cloud CDN加速
实测效果和OneDrive差不多，不细写了
GoogleDrive + GoIndex + CloudFlare Workers 构建直链网盘
实测效果和OneDrive差不多 ...
《工程矩阵》资源汇总
整理不易，一键三连啊兄弟们！
东南大学工程矩阵视频
东南大学工程矩阵课程讲义
东南大学工程矩阵课堂板书
东南大学工程矩阵习题讲解
东南大学工程矩阵近十年试卷
东南大学工程矩阵模拟题12套
东南大学工程矩阵历年试题解答
亲，给个好评吧~
关于枚举去重
18. 四数之和
Difficulty: 中等
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
12输入：nums = [1,0,-1,0,-2,2], target = 0输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
12输入：nums = [2,2,2,2,2], target = 8输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
Solution
Language: cpp
12345678910 ...
